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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1645815 (Why is no real title available?)
- scientific article; zbMATH DE number 3473781 (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 878896 (Why is no real title available?)
- scientific article; zbMATH DE number 3407723 (Why is no real title available?)
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A combinatorial proof of the removal lemma for groups
- A new proof of Szemerédi's theorem
- A proof of Green's conjecture regarding the removal properties of sets of linear equations
- A removal lemma for systems of linear equations over finite fields
- A variant of the hypergraph removal lemma
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Maximal antiramsey graphs and the strong chromatic number
- Note on integral distances
- 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
- On sets of integers containing k elements in arithmetic progression
- Problems and results in combinatorial analysis and graph theory
- Property testing and its connection to learning and approximation
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Regularity Lemma for k-uniform hypergraphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Structure and randomness. Pages from year one of a mathematical blog
- Supersaturated graphs and hypergraphs
- Testing subgraphs in directed graphs
- Testing subgraphs in large graphs
- The Maturation of the Probabilistic Method
- 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
Cited in
(86)- Many \(T\) copies in \(H\)-free graphs
- The regularity method for graphs with few 4‐cycles
- The spectral radius of graphs with no odd wheels
- H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
- On 3‐graphs with no four vertices spanning exactly two edges
- More Turán-type theorems for triangles in convex point sets
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Efficient testing without efficient regularity
- Regular decomposition of the edge set of a graph with applications
- Some exact results of the generalized Turán numbers for paths
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- The spectral radius of graphs with no intersecting odd cycles
- Graph removal lemmas
- Independent sets in hypergraphs
- Generalizations of the removal lemma
- Estimating parameters associated with monotone properties
- Average Gromov hyperbolicity and the Parisi ansatz
- Maximal antichains of minimum size
- Extremal problems for pairs of triangles
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- Efficient removal without efficient regularity
- The induced removal lemma in sparse graphs
- The maximum spectral radius of graphs without friendship subgraphs
- On directed versions of the Hajnal-Szemerédi theorem
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- Density theorems and extremal hypergraph problems
- Minimum degree and the graph removal lemma
- The removal lemma for tournaments
- A tight bound for hypergraph regularity
- New short proofs to some stability theorems
- New results on linear size distance preservers
- Short proofs of some extremal results. II.
- On the structure of pointsets with many collinear triples
- Removal lemmas and approximate homomorphisms
- Roth-type theorems in finite groups
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Schur's colouring theorem for noncommuting pairs
- On the communication complexity of high-dimensional permutations
- Graphs without a Rainbow Path of Length 3
- A sparse regular approximation lemma
- Multigraphs (only) satisfy a weak triangle removal lemma
- Induced Ramsey number for a star versus a fixed graph
- Polynomial removal lemma for ordered matchings
- Inflatable graph properties and natural property tests
- 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
- On an almost all version of the Balog-Szemerédi-Gowers theorem
- A removal lemma for linear configurations in subsets of the circle
- Chang's lemma via Pinsker's inequality
- Hypergraph removal lemmas via robust sharp threshold theorems
- A tight bound for Green's arithmetic triangle removal lemma in vector spaces
- Extremal results in sparse pseudorandom graphs
- Prominent examples of flip processes
- Additive structure in convex translates
- A unique characterization of spectral extrema for friendship graphs
- Efficient removal lemmas for matrices
- Polynomial removal lemmas for ordered graphs
- On the KŁR conjecture in random graphs
- Kneser graphs are like Swiss cheese
- An analytic approach to sparse hypergraphs: hypergraph removal
- Estimating the distance to a hereditary graph property
- A novel proof of Roth's removal rule
- Efficient removal lemmas for matrices
- On regularity lemma and barriers in streaming and dynamic matching
- On the maximum number of integer colourings with forbidden monochromatic sums
- Upper bound theorem for odd-dimensional flag triangulations of manifolds
- Lower bounds for testing triangle-freeness in Boolean functions
- Easily testable graph properties
- Directed graphs without rainbow stars
- Generalizations of Fourier analysis, and how to apply them
- Bounds for graph regularity and removal lemmas
- A generalized Turán problem and its applications
- The critical window for the classical Ramsey-Turán problem
- General deletion lemmas via the Harris inequality
- 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
- Triangles in graphs without bipartite suspensions
- A polynomial bound for the arithmetic k-cycle removal lemma in vector spaces
- A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
- New applications of the polynomial method: the cap set conjecture and beyond
- The length of an s-increasing sequence of r-tuples
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Growth rate of the number of empty triangles in the plane
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)
