A new proof of the graph removal lemma
From MaRDI portal
Publication:640795
DOI10.4007/ANNALS.2011.174.1.17zbMATH Open1231.05133arXiv1006.1300OpenAlexW2164542539WikidataQ105584489 ScholiaQ105584489MaRDI QIDQ640795FDOQ640795
Publication date: 20 October 2011
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemer'edi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.
Full work available at URL: https://arxiv.org/abs/1006.1300
Recommendations
[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Szemer%EF%BF%BD%EF%BF%BDdi%27s+regularity+lemma&go=Go Szemer��di's regularity lemma]removal lemmagraph property testing
Cites Work
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Regularity Lemma for k-uniform hypergraphs
- Title not available (Why is that?)
- The counting lemma for regular k‐uniform hypergraphs
- Testing subgraphs in directed graphs
- Property testing and its connection to learning and approximation
- A new proof of Szemerédi's theorem
- On sets of integers containing k elements in arithmetic progression
- Robust Characterizations of Polynomials with Applications to Program Testing
- Title not available (Why is that?)
- ON A GENERALIZATION OF SZEMERÉDI'S THEOREM
- On Certain Sets of Integers
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- Problems and results in combinatorial analysis and graph theory
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- A variant of the hypergraph removal lemma
- A removal lemma for systems of linear equations over finite fields
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A proof of Green's conjecture regarding the removal properties of sets of linear equations
- Title not available (Why is that?)
- Supersaturated graphs and hypergraphs
- A combinatorial proof of the removal lemma for groups
- Testing subgraphs in large graphs
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Structure and randomness. Pages from year one of a mathematical blog
- Title not available (Why is that?)
- Maximal antiramsey graphs and the strong chromatic number
- Note on integral distances
- The Maturation of the Probabilistic Method
Cited In (83)
- The spectral radius of graphs with no odd wheels
- On 3‐graphs with no four vertices spanning exactly two edges
- \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
- On Directed Versions of the Hajnal–Szemerédi Theorem
- More Turán-type theorems for triangles in convex point sets
- Some exact results of the generalized Turán numbers for paths
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Title not available (Why is that?)
- The spectral radius of graphs with no intersecting odd cycles
- Sunflowers and testing triangle-freeness of functions
- Independent sets in hypergraphs
- Generalizations of the removal lemma
- Efficient Removal Lemmas for Matrices
- On an almost all version of the Balog-Szemeredi-Gowers theorem
- Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems
- Average Gromov hyperbolicity and the Parisi ansatz
- Maximal antichains of minimum size
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Extremal problems for pairs of triangles
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- The maximum spectral radius of graphs without friendship subgraphs
- Minimum degree and the graph removal lemma
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- Density theorems and extremal hypergraph problems
- The removal lemma for tournaments
- New applications of the polynomial method: The cap set conjecture and beyond
- A tight bound for hypergraph regularity
- New short proofs to some stability theorems
- Easily Testable Graph Properties
- Removal lemmas and approximate homomorphisms
- Short proofs of some extremal results. II.
- Roth-type theorems in finite groups
- A sparse regular approximation lemma
- Induced Ramsey number for a star versus a fixed graph
- Multigraphs (only) satisfy a weak triangle removal lemma
- A removal lemma for linear configurations in subsets of the circle
- Chang's lemma via Pinsker's inequality
- Extremal results in sparse pseudorandom graphs
- A tight bound for Green's arithmetic triangle removal lemma in vector spaces
- A unique characterization of spectral extrema for friendship graphs
- Kneser graphs are like Swiss cheese
- An analytic approach to sparse hypergraphs: hypergraph removal
- On the KŁR conjecture in random graphs
- Estimating the distance to a hereditary graph property
- On the maximum number of integer colourings with forbidden monochromatic sums
- Efficient removal lemmas for matrices
- Upper bound theorem for odd-dimensional flag triangulations of manifolds
- Lower bounds for testing triangle-freeness in Boolean functions
- Generalizations of Fourier analysis, and how to apply them
- Bounds for graph regularity and removal lemmas
- Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
- On a problem of Erdős and Rothschild on edges in triangles
- The critical window for the classical Ramsey-Turán problem
- Inflatable Graph Properties and Natural Property Tests
- Triangles in graphs without bipartite suspensions
- A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces
- The length of an s-increasing sequence of r-tuples
- A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
- Many \(T\) copies in \(H\)-free graphs
- The Induced Removal Lemma in Sparse Graphs
- Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
- Regular decomposition of the edge set of a graph with applications
- SCHUR’S COLOURING THEOREM FOR NONCOMMUTING PAIRS
- New Results on Linear Size Distance Preservers
- Estimating parameters associated with monotone properties
- On the structure of pointsets with many collinear triples
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Graphs without a Rainbow Path of Length 3
- Polynomial removal lemma for ordered matchings
- The minimum degree removal lemma thresholds
- KKL's influence on me
- Local-vs-global combinatorics
- Small subsets with large sumset: beyond the Cauchy-Davenport bound
- Prominent examples of flip processes
- Additive structure in convex translates
- Efficient Testing without Efficient Regularity
- Polynomial removal lemmas for ordered graphs
- On regularity lemma and barriers in streaming and dynamic matching
- A novel proof of Roth's removal rule
- Directed graphs without rainbow stars
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Growth rate of the number of empty triangles in the plane
- The regularity method for graphs with few 4‐cycles
This page was built for publication: A new proof of the graph removal lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640795)
