Source-linked AI summary
A new proof of the graph removal lemma
Jacob Fox
TL;DR
The graph removal lemma had only a regularity-lemma proof for its combinatorial applications, leading to weak bounds. This paper gives a new proof avoiding regularity, obtaining a tower bound of height 5h^4 log ε^-1 and extending the approach to variants. The authors discuss related improved bounds and open problems.
Problem
The regularity-lemma proof of the graph removal lemma leads to weak bounds, motivating a proof with better quantitative estimates that avoids regularity.
Method
The paper proves the graph removal lemma using a new argument based on mean entropy density rather than Szemerédi’s regularity lemma.
Results
If δ^-1 is a tower of twos of height 5h^4 log ε^-1, graphs with at most δn^h copies of H can be made H-free by removing εn^2 edges.
Takeaways & Limitations
The approach gives improved bounds for the graph removal lemma and similar bounds for directed and multicolored analogues.
Takeaways & Limitations
The paper does not make any serious claims beyond discussing variants and open problems in its concluding remarks.
Abstract
from arXiv · showhide
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édi'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.
1 Introduction
The graph removal lemma has broad applications, but its regularity-lemma proof yields weak quantitative bounds. The paper introduces a regularity-free proof with a substantially better bound.
- 1 Introduction: The only known proof used Szemerédi’s regularity lemma, whose tower-type bounds make resulting estimates weak.The regularity lemma’s partition bound can be a tower of twos of height O(ε^-5), while Gowers proved an inherently large lower bound.
- 1 Introduction: The paper’s main result is a new proof of the graph removal lemma that avoids the regularity lemma and gives a better bound.This addresses a repeatedly posed problem concerning improved quantitative estimates for combinatorial applications.
- 1 Introduction: The graph removal lemma says that graphs with few copies of a fixed H can be made H-free by deleting few edges.For each graph H on h vertices and ε > 0, at most δn^h copies imply that deleting at most εn^2 edges suffices, for suitable δ.
- 1 Introduction: The lemma supports applications in graph theory, additive combinatorics, discrete geometry, theoretical computer science, and property testing.It yields a constant-time one-sided-error tester for H-freeness, with running time depending on the removal-lemma bound.
- 1 Introduction: If δ^-1 is a tower of twos of height 5h^4 log ε^-1, then at most δn^h copies of H imply that εn^2 edge deletions suffice.The regularity proof instead gives a tower height polynomial in ε^-1.
- 1 Introduction: The proof replaces regularity’s mean-square-density refinement with mean entropy density, increasing it by Ω(d) while parts grow by one exponential per iteration.The process stops after O(log ε^-1) iterations, producing the improved tower bound.
2 Key Lemma
The section develops auxiliary hypergraph regularity lemmas and proves the key lemma: few labeled copies of H force a shattered pair corresponding to an edge of H.
- 2 Key Lemma: An (α, c, t)-shattering partitions two vertex sets into at most t parts each, with at least a c-fraction of pairs lying in cells of density below α.The shattering parameters are monotone: increasing α or t, or decreasing c, preserves a shattering.
- 2.1 Regular tuples in hypergraphs: Lemma 3 finds an (α, β)-superregular subtuple of size at least α3α−k log β−1n inside any sufficiently dense k-tuple.The proof repeatedly applies Lemma 2, each time retaining an α-fraction of each part while increasing density.
- 2.1 Regular tuples in hypergraphs: Lemma 4 partitions a superregular k-tuple into aligned (α, β)-superregular pieces, leaving an exceptional part smaller than cN.Each retained piece has size at least α3α−k log β−1cN.
- 2.2 Shattering sets with few copies of H: Lemma 5 states that at most dhnh labeled copies of H across equal-sized parts imply an edge (i, j) whose pair admits an (α, c, t)-shattering.Here dh = 2−(2/α)h2, while c depends only on h and t is bounded as a function of α and h.
- 2.2 Shattering sets with few copies of H: The proof proceeds by induction on h, using a hypergraph encoding copies of H−h and superregular partitions to show that otherwise many copies of H would exist.Vertices in Vh with sufficiently many neighbors across every relevant superregular piece generate many copies, contradicting the few-copy assumption.
- 2.2 Shattering sets with few copies of H: The resulting partitions of Vi and Vh form an (α, h−2, 2d−1h)-shattering for some neighbor i of h.This is the contradiction-producing conclusion of the second inductive case.
3 A defect inequality for convex functions
This section strengthens Jensen’s inequality for the convex function x log x when a specified fraction of the weight lies on values far below the weighted average.
- 3 A defect inequality for convex functions: Jensen’s inequality becomes strictly stronger when the values are substantially unequal, especially when some weighted mass lies far below the average.The section formalizes this improvement as a defect inequality.
- 3 A defect inequality for convex functions: For f(x) = x log x, the defect inequality assumes that a proportion c of the weight is on values at most βa, where a is the weighted average.The function is defined at zero by f(0) = 0, with β < 1.
- 3 A defect inequality for convex functions: The inequality reduces to the ordinary Jensen bound when either the average a or the low-weight proportion c is zero.The proof therefore treats the nontrivial case a, c > 0 separately.
- 3 A defect inequality for convex functions: The proof aggregates the low-valued and remaining terms, applies Jensen’s inequality to each group, and compares their group averages with a.The normalized low-group average is at most β, enabling the quantitative defect term.
4 Proof of Theorem 1
The proof replaces regularity-lemma machinery with entropy-based partition refinements. Each refinement increases mean entropy density substantially while controlling the number and sizes of parts, leading to a contradiction.
- Entropy framework: Mean entropy density is convex under partitioning, nondecreasing under refinement, and bounded below by d log d.The function f(x)=x log x is used to define the entropy quantity.
- Entropy framework: A shattering of dense vertex pairs yields a refinement whose mean entropy density increases by Ω(d).The refinement exploits partitions of shattered pairs and the convexity properties of f.
- Partition control: A size-balancing refinement puts all but at most υn vertices into parts of one common size, using at most (2υ^-1 + 1)k parts.The remaining vertices lie in smaller parts.
- Iterative refinement: Deleting at most ε0n^2/2 edges preserves at least ε0n^2/2 edge-disjoint copies of H in the structured subgraph.The surviving copies use distinct equal-sized parts and dense pairs that are shattered.
5 Concluding remarks
The concluding remarks extend the improved approach to homomorphism, directed, and colored removal lemmas, and connect it to arithmetic variants. They also identify unresolved gaps and directions for regularity-free proofs.
- Homomorphism removal: The improved graph-removal bound also yields an improved bound for the homomorphism removal lemma.The argument uses finitely many homomorphic images and blow-ups to convert many copies of an image into copies of H.
- Directed and colored variants: The same proof strategy gives a similar improved bound for the directed graph removal lemma.The directed argument begins with a partition aligning the vertices of many edge-disjoint copies of H and then refines it iteratively.
- Directed and colored variants: A similarly improved bound holds for the colored graph removal lemma, with the proof identical to the directed case.The colored version concerns removing edges to eliminate copies having a prescribed edge coloring.
- Arithmetic variants: The approach also supplies a new bound for removal of directed cycles, which feeds into removal results for group equations.Earlier arithmetic removal results relied on directed-cycle removal, while related proofs extend beyond abelian groups.
- Open problems: For nonbipartite H, the upper and lower bounds on δ(ε,H) remain far apart, leaving the gap open.The paper also asks for new proofs of related removal results without versions of the regularity lemma.