Local-vs-global combinatorics
From MaRDI portal
Summary: Many of the most outstanding open problems in combinatorics relate the local and global properties of large discrete structures. The research aimed at solving these questions led to some of the most important developments in this area, as well as in related areas such as theoretical computer science, additive number theory, and harmonic analysis. In this paper we discuss some of these advances and mention several open problems. For the entire collection see [Zbl 07816360].
Recommendations
Cites work
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- A combinatorial proof of the removal lemma for groups
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- A generalized Turán problem and its applications
- A new bound for the Brown-Erdős-Sós problem
- A new proof of Szemerédi's theorem
- A new proof of the graph removal lemma
- A Note on a Question of Erdős and Graham
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- A proof of Green's conjecture regarding the removal properties of sets of linear equations
- A Ramsey variant of the Brown-Erdős-Sós conjecture
- A removal lemma for systems of linear equations over finite fields
- A separation theorem in property testing
- A short proof of Gowers' lower bound for the regularity lemma
- A sparse regular approximation lemma
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A tight bound for Green's arithmetic triangle removal lemma in vector spaces
- A tight bound for hypergraph regularity
- A tight lower bound for Szemerédi's regularity lemma
- A unified framework for testing linear-invariant properties
- A variant of the hypergraph removal lemma
- A Wowzer-type lower bound for the strong regularity lemma
- Additive approximation for edge-deletion problems
- Algebraic property testing: the role of invariance
- An ergodic Szemerédi theorem for commuting transformations
- An extension of the Ruzsa-Szemerédi theorem
- Bounds for graph regularity and removal lemmas
- Constructing dense grid-free linear 3-graphs
- Easily testable graph properties
- Efficient removal without efficient regularity
- Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
- Efficient testing of large graphs
- Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
- Extremal problems on set systems
- Generalizations of the removal lemma
- Graph limits and parameter testing
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 3477291 (Why is no real title available?)
- scientific article; zbMATH DE number 3609704 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 3407723 (Why is no real title available?)
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Introduction to Property Testing
- Large networks and graph limits
- Local Graph Partitions for Approximation and Testing
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Many \(T\) copies in \(H\)-free graphs
- On an extremal hypergraph problem of Brown, Erdős and Sós
- On Certain Sets of Integers (II)
- On graphs with small subgraphs of large chromatic number
- On sets of integers containing k elements in arithmetic progression
- On sets of integers containing no four elements in arithmetic progression
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On the existence of triangulated spheres in 3-graphs, and related problems
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Pentagons vs. triangles
- Probabilistic checking of proofs
- Proof of the Brown-Erdős-Sós conjecture in groups
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Quasi-random graphs
- Quick approximation to matrices and applications
- Regular Partitions of Hypergraphs: Counting Lemmas
- Regular Partitions of Hypergraphs: Regularity Lemmas
- Regularity Lemma for k-uniform hypergraphs
- Regularity lemmas for graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Self-testing/correcting with applications to numerical problems
- Small cores in 3-uniform hypergraphs
- Solving a linear equation in a set of integers I
- Sparse hypergraphs with applications to coding theory
- Szemerédi's lemma for the analyst
- Testability and repair of hereditary hypergraph properties
- Testing graphs in vertex-distribution-free models
- Testing linear inequalities of subgraph statistics
- Testing subgraphs in large graphs
- Testing versus Estimation of Graph Properties
- The Algorithmic Aspects of the Regularity Lemma
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The counting lemma for regular k‐uniform hypergraphs
- The dichotomy between structure and randomness, arithmetic progressions, and the primes
- The induced removal lemma in sparse graphs
- The length of an s-increasing sequence of r-tuples
- The maximum number of triangles in \(C_{2k+1}\)-free graphs
- The primes contain arbitrarily long arithmetic progressions
- The removal lemma for tournaments
- Two-sided error proximity oblivious testing
- Uniform hypergraphs containing no grids
This page was built for publication: Local-vs-global combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198642)
