A correspondence principle between (hyper)graph theory and probability theory

Terence Tao (UCLA)

www.math.ucla.edu/∼tao/preprints

The Furstenberg correspondence principle

• In 1977, Furstenberg observed an extremely useful correspondence principle between combinatorial questions involving such patterns as arithmetic progressions, and recurrence theorems in ergodic theory. This principle, which can be viewed as a way of connecting finitary and infinitary mathematics, gave a new route to attacking combinatorial problems.

• Advantages: epsilons and deltas disappear. Can utilise infinitary tools that do not have obvious finitary counterparts (Zorn’s lemma, compactness, σ-algebras, Lie groups). Conceptually clearer.

• Disadvantages: Very hard to extract quantitative bounds. Proofs become non-elementary. Not obviously connected to the original finitary problem.

• The most famous instance of this correspondence principle connects Szemerédi’s theorem on arithmetic progressions with the Furstenberg multiple recurrence theorem.

• Szemerédi’s theorem (finitary) If k ≥ 1 and A ⊂ Z/NZ has density |A|/N ≥ δ > 0, then

E_{r∈Z/NZ}|A ∩ T^{r}A ∩ … ∩ T^{(k−1)r}A|/N > c(k, δ)

for some c(k, δ) > 0 that is independent of N, where T : x ↦ x + 1 is the shift map. [Implies that sets of integers of positive density have arbitrarily long arithmetic progressions; recently extended to sets of primes of positive relative density.]

• Furstenberg’s multiple recurrence theorem (infinitary) If k ≥ 1, (Ω, B, P) is a probability space, B ⊂ Ω has positive probability, and T : Ω → Ω is a probability-preserving map, then

lim inf_{N→∞} E_{−N≤r≤N}P(B ∩ T^{r}B ∩ … ∩ T^{(k−1)r}B) > 0.

• Deduction of Furstenberg’s theorem from Szemerédi’s is easy. Converse deduction is the more nontrivial content of the correspondence principle.

How does the correspondence principle work?

(a) Assume the finitary theorem fails;

(b) Assemble a sequence of increasingly large (but finite) counterexamples to the theorem;

(c) Use a “random sampling” method to lift the counterexample to some infinitary universal space;

(d) Extract a weak (infinitary) limit of the counterexample in that universal space;

(e) Deduce that the infinitary theorem fails.

In the case of Szemerédi’s theorem...

(ab) If Szemerédi’s theorem fails, then there is a k ≥ 1, a sequence of increasingly large cyclic groups Z/N_{m}Z, and sets A_{m} ⊂ Z/N_{m}Z with density at least δ such that

lim_{m→∞} E_{n,r∈Z/N_{m}Z}|A_{m}∩T^{r}A_{m}∩…∩T^{(k−1)r}A_{m}|/N_{m} = 0.

Note: the A_{m} all live in different domains.

(c) For each m, select a, λ ∈ Z/N_{m}Z randomly, and form the random set B_{m} ⊂ Z by

B_{m} := {i ∈ Z : a + iλ ∈ A_{m}}.

Note that P(n ∈ B_{m}) ≥ δ for any n, m; also one can arrange that

lim_{m→∞} P(n, n + r, …, n + (k − 1)r ∈ B_{m}) = 0

for any n ∈ Z, r ∈ Z\{0}. Note: the B_{m} all live in the same domain.

(d) One can think of the random set B_{m} as a probability measure on 2Z, the power set of Z. The space of such measures is weakly compact. Thus there exists another random set B such that a subsequence of B_{m} converges to B in the weak probabilistic sense (i.e. the k-point correlation functions converge).

(e) This implies that P(n ∈ B) ≥ δ, but that

P(n, n + r, …, n + (k − 1)r ∈ B) = 0

for any n ∈ Z, r ∈ Z\{0}. This contradicts the Furstenberg recurrence theorem (with Ω = 2Z with the usual shift T B := B + 1).

• Gowers posed the question of whether an analogous correspondence principle holds for graphs. For instance, consider

• Ruzsa-Szemerédi triangle removal lemma (finitary) If a graph G = (V, E) has fewer than ε|V |^{3} triangles, then these triangles can be deleted by removing no more than o_{ε→0}(|V |^{2}) edges.

• Until recently, the only known proof of this lemma required the Szemerédi regularity lemma (followed by a counting lemma). This result implies the k = 3 case of Szemerédi’s theorem (Roth’s theorem).

• Just as the Furstenberg correspondence principle resulted in studying random sets on Z, a graph correspondence principle exists and will involve random graphs on Z.

• The resulting infinitary triangle removal lemma can be proven directly using an infinitary regularity lemma and infinitary counting lemma.

• Definition: A random graph H = (Z, E) on the integers is permutation-invariant if any permutation of the vertices Z leaves the probability distribution of the random graph H unchanged. The edge density of a random permutation-invariant graph is defined as the probability that (1, 2) (say) is an edge of G.

• Example: the random graph G(∞, p) on Z has edge density p; any given triangle occurs with probability p^{3}. Example: a random complete bipartite graph on Z has edge density 1/2; any given triangle surely does not occur.

• Infinitary triangle removal lemma If a permutationinvariant random graph H almost surely does not contain the triangle between 1, 2, 3, then for any ε > 0 there exists a permutation-invariant random subgraph H′ of H which is surely triangle-free, and such that the edge density of H\H′ is at most ε. Furthermore: the recipe for defining an edge of H′ depends on only finitely many edges of H, and the recipe itself forces the triangle-free nature of H′.

How the graph correspondence principle works...

(ab) Assume finitary triangle removal lemma fails. Then there exists increasingly large graphs G_{m} = (V_{m}, E_{m}) with asymptotically vanishing number of triangles that can’t be easily made triangle-free.

(c) For each graph G_{m} on V_{m}, create a random graph H_{m} on Z by sampling infinitely many vertices in V_{m} and measuring the connectivity. (Collisions can occur but can be easily treated.)

(d) Take a weak limit of a subsequence of H_{m} to obtain a new random graph H.

(e) Apply infinitary triangle removal lemma to create triangle-free graph H′. Apply same recipe to H_{m} to obtain triangle-free graph H′_{m}. Use this to contradict hypothesis.

• Note: These weak limits also appear in work of Lovász and Szegedy - focus there is on graph homomorphism densities rather than the interpretation of the limit as a random infinite graph.

Triangle removal via oblivious property testing

• Suppose G = (V, E) is a slightly corrupted version of a randomly chosen complete bipartite graph on a finite vertex set V. This graph will have a small number of triangles. How to efficiently clean it up and restore a complete bipartite (hence triangle-free) graph? Can do so using only a small number of queries to the graph.

• Step 1: Select a small number of vertices v_{1}, …, v_{n} from V at random. Query the connectivity of G between these vertices.

• Step 2: By brute force search, find a bipartite graph K_{A,B} on v_{1}, …, v_{n} that matches G as closely as possible.

• Step 3: For every other vertex v in V, query the connectivity between v and A, and between v and B; use majority vote to divide these vertices into two classes, say A′ and B′.

• Step 4: The complete bipartite graph K_{A′,B′} will then be the cleaned up version of G.

• The triangle removal offered by the infinitary removal lemma is of a similar spirit to this.

The infinitary regularity lemma

• For finite graphs G = (V, E), one can make the graphs mostly ε-regular after partitioning (or “conditioning”) the vertices into classes.

• Probabilistic interpretation: if x_{1}, x_{2}, x_{3} are drawn at random from G, then the events (x_{1}, x_{2}) ∈ E and (x_{1}, x_{3}) ∈ E may have large correlation. But after conditioning on which cell of the partitions x_{1}, x_{2}, x_{3} belong to, these events have much smaller correlation. Similarly for more complex events (the “counting lemma”).

• The infinite version is similar. If H = (Z, E) is a permutation-invariant random graph, then the events (1, 2) ∈ E and (1, 3) ∈ E are correlated (because the degree of 1 can fluctuate). But if we condition on the connectivity of 1 with the negative integers, then these two events become completely independent (ε becomes 0!). Intuition: law of large numbers allows one to extract degree information of 1 from infinitely many connections. Similarly for more complex events; easily proven using permutation invariance.

• Extends painlessly to hypergraphs. (Finitary analogue of this is not painless.) Ultimately gives the hypergraph removal lemma of Nagle-Rödl-Schacht-Skokan and Gowers, which in turn implies Szemerédi’s theorem.

Work in progress...

• The method seems to extend to families of graphs or hypergraphs, leading to a statement of the following form:

• Induced hypergraph family removal lemma If a hypergraph H contains very few (induced) copies of very many of the hypergraphs G_{1}, G_{2}, G_{3}, … in a given family, then it is possible to edit H slightly to destroy all copies of all of the hypergraphs G_{n}.

• The graph version of this was proven by Alon and Shapira. Should imply that all monotone or hereditary hypergraph properties are testable. Implies also the hypergraph removal lemma.

• Also looks like the method shows that edit distance is preserved by random sampling (conjectured by Shapira as a “master theorem”, implies all other results mentioned here):

• Stability of edit distance If a proportion α of edges of a hypergraph H need to be deleted in order to eradicate all copies of hypergraphs G_{1}, G_{2}, G_{3}, … in a given family, then after passing to a random subgraph of H of size n, one should still need to delete a proportion α + o_{n→∞}(1) of edges to delete all copies of G_{1}, G_{2}, . . ..