Local-vs-global combinatorics

DOI10.4171/icm2022/36OpenAlexW4389774850MaRDI QIDQ6198642

Asaf Shapira

Publication date: 20 March 2024

Published in: International Congress of Mathematicians (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/icm2022/36

zbMATH Keywords

regularity lemmahypergraphsproperty testingremoval lemmaquasi randomness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Extremal combinatorics (05D99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small cores in 3-uniform hypergraphs
• Uniform hypergraphs containing no grids
• An extension of the Ruzsa-Szemerédi theorem
• A new proof of the graph removal lemma
• A short proof of Gowers' lower bound for the regularity lemma
• A variant of the hypergraph removal lemma
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Szemerédi's lemma for the analyst
• Pentagons vs. triangles
• A separation theorem in property testing
• Generalizations of the removal lemma
• A combinatorial proof of the removal lemma for groups
• On graphs with small subgraphs of large chromatic number
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Quick approximation to matrices and applications
• An ergodic Szemerédi theorem for commuting transformations
• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• Self-testing/correcting with applications to numerical problems
• Lower bounds of tower type for Szemerédi's uniformity lemma
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• A tight lower bound for Szemerédi's regularity lemma
• A removal lemma for systems of linear equations over finite fields
• Bounds for graph regularity and removal lemmas
• A new bound for the Brown-Erdős-Sós problem
• Testing graphs against an unknown distribution
• Efficient removal without efficient regularity
• A tight bound for hypergraph regularity
• The primes contain arbitrarily long arithmetic progressions
• Additive approximation for edge-deletion problems
• The removal lemma for tournaments
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On the existence of triangulated spheres in 3-graphs, and related problems
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Two-sided error proximity oblivious testing
• The Maximum Number of Triangles in C_2k+1-Free Graphs
• Graph limits and parameter testing
• A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing
• Testability and repair of hereditary hypergraph properties
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A proof of Green's conjecture regarding the removal properties of sets of linear equations
• Probabilistic checking of proofs
• On sets of integers containing k elements in arithmetic progression
• Solving a linear equation in a set of integers I
• The Algorithmic Aspects of the Regularity Lemma
• Extremal problems on set systems
• A sparse regular approximation lemma
• Testing subgraphs in large graphs
• Regularity Lemma for k-uniform hypergraphs
• A Note on a Question of Erdős and Graham
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Wowzer-type lower bound for the strong regularity lemma
• Proof of the Brown–Erdős–Sós conjecture in groups
• Removal lemmas with polynomial bounds
• A unified framework for testing linear‐invariant properties
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• A Generalized Turán Problem and its Applications
• A Ramsey variant of the Brown–Erdős–Sós conjecture
• Sparse Hypergraphs with Applications to Coding Theory
• Constructing dense grid-free linear $3$-graphs
• Local Graph Partitions for Approximation and Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing graphs in vertex-distribution-free models
• The Induced Removal Lemma in Sparse Graphs
• Easily Testable Graph Properties
• Introduction to Property Testing
• Testing versus Estimation of Graph Properties
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regular Partitions of Hypergraphs: Counting Lemmas
• The counting lemma for regular k‐uniform hypergraphs
• On sets of integers containing no four elements in arithmetic progression
• On Certain Sets of Integers (II)
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• The length of an s-increasing sequence of r-tuples
• Quasi-random graphs
• Efficient testing of large graphs
• A new proof of Szemerédi's theorem
• Many \(T\) copies in \(H\)-free graphs
• Testing linear inequalities of subgraph statistics

This page was built for publication: Local-vs-global combinatorics