A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma

By Terence Tao. 2006

63 citations recorded by the source corpus.

We introduce a correspondence principle (analogous to the Furstenberg Correspondence Principle) that allows one to extract an infinite random graph or hypergraph from a sequence of increasingly large deterministic graphs or hypergraphs. As an application we present a new (infinitary) proof of the hypergraph removal lemma of Nagle-Schacht-Rödl-Skokan and Gowers, which does not require the hypergraph regularity lemma and requires significantly less computation. This in turn gives new proofs of several corollaries of the hypergraph removal lemma, such as Szemerédi’s Theorem on arithmetic progressions.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/fe07868716ad1418dae2c3e6ad123dd2dae6c9be

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “Alternative perspectives and refinements were given in [8, 94, 187, 188].”
A new proof of the density Hales-Jewett theorem (2009, background): “In the last few years that has changed, and a programme has developed to find new and finitary proofs of the results that were previously known only by infinitary ergodic methods; see, e.g., [RS04, NRS06, RS06, RS07b, RS07a, Gow06, Gow07, Tao06, Tao07].”
Norm convergence of multiple ergodic averages for commuting transformations (2007, background): “More precisely, if Y is a finite set, let 2Y = {E : E ⊂ Y } be the discrete σ-algebra on Y , and let µY be the uniform probability measure on Y .”