In a previous post, we discussed the Szemerédi regularity lemma, and how a given graph could be regularised by partitioning the vertex set into random neighbourhoods. More precisely, we gave a proof of

Lemma 1 (Regularity lemma via random neighbourhoods) Let {\varepsilon > 0}. Then there exists integers {M_1,\ldots,M_m} with the following property: whenever {G = (V,E)} be a graph on finitely many vertices, if one selects one of the integers {M_r} at random from {M_1,\ldots,M_m}, then selects {M_r} vertices {v_1,\ldots,v_{M_r} \in V} uniformly from {V} at random, then the {2^{M_r}} vertex cells {V^{M_r}_1,\ldots,V^{M_r}_{2^{M_r}}} (some of which can be empty) generated by the vertex neighbourhoods {A_t := \{ v \in V: (v,v_t) \in E \}} for {1 \leq t \leq M_r}, will obey the regularity property

\displaystyle \sum_{(V_i,V_j) \hbox{ not } \varepsilon-\hbox{regular}} |V_i| |V_j| \leq \varepsilon |V|^2 \ \ \ \ \ (1)

with probability at least {1-O(\varepsilon)}, where the sum is over all pairs {1 \leq i \leq j \leq k} for which {G} is not {\varepsilon}-regular between {V_i} and {V_j}. [Recall that a pair {(V_i,V_j)} is {\varepsilon}-regular for {G} if one has

\displaystyle |d( A, B ) - d( V_i, V_j )| \leq \varepsilon

for any {A \subset V_i} and {B \subset V_j} with {|A| \geq \varepsilon |V_i|, |B| \geq \varepsilon |V_j|}, where {d(A,B) := |E \cap (A \times B)|/|A| |B|} is the density of edges between {A} and {B}.]

The proof was a combinatorial one, based on the standard energy increment argument.

In this post I would like to discuss an alternate approach to the regularity lemma, which is an infinitary approach passing through a graph-theoretic version of the Furstenberg correspondence principle (mentioned briefly in this earlier post of mine). While this approach superficially looks quite different from the combinatorial approach, it in fact uses many of the same ingredients, most notably a reliance on random neighbourhoods to regularise the graph. This approach was introduced by myself back in 2006, and used by Austin and by Austin and myself to establish some property testing results for hypergraphs; more recently, a closely related infinitary hypergraph removal lemma developed in the 2006 paper was also used by Austin to give new proofs of the multidimensional Szemeredi theorem and of the density Hales-Jewett theorem (the latter being a spinoff of the polymath1 project).

For various technical reasons we will not be able to use the correspondence principle to recover Lemma 1 in its full strength; instead, we will establish the following slightly weaker variant.

Lemma 2 (Regularity lemma via random neighbourhoods, weak version) Let {\varepsilon > 0}. Then there exist an integer {M_*} with the following property: whenever {G = (V,E)} be a graph on finitely many vertices, there exists {1 \leq M \leq M_*} such that if one selects {M} vertices {v_1,\ldots,v_{M} \in V} uniformly from {V} at random, then the {2^{M}} vertex cells {V^{M}_1,\ldots,V^{M}_{2^{M}}} generated by the vertex neighbourhoods {A_t := \{ v \in V: (v,v_t) \in E \}} for {1 \leq t \leq M}, will obey the regularity property (1) with probability at least {1-\varepsilon}.

Roughly speaking, Lemma 1 asserts that one can regularise a large graph {G} with high probability by using {M_r} random neighbourhoods, where {M_r} is chosen at random from one of a number of choices {M_1,\ldots,M_m}; in contrast, the weaker Lemma 2 asserts that one can regularise a large graph {G} with high probability by using some integer {M} from {1,\ldots,M_*}, but the exact choice of {M} depends on {G}, and it is not guaranteed that a randomly chosen {M} will be likely to work. While Lemma 2 is strictly weaker than Lemma 1, it still implies the (weighted) Szemerédi regularity lemma (Lemma 2 from the previous post).

— 1. The graph correspondence principle —

The first key tool in this argument is the graph correspondence principle, which takes a sequence of (increasingly large) graphs and uses random sampling to extract an infinitary limit object, which will turn out to be an infinite but random (and, crucially, exchangeable) graph. This concept of a graph limit is related to (though slightly different from) the “graphons” used as graph limits in the work of Lovasz and Szegedy, or the ultraproducts used in the work of Elek and Szegedy. It also seems to be related to the concept of an elementary limit that I discussed in this post, though this connection is still rather tentative.

The correspondence works as follows. We start with a finite, deterministic graph {G = (V,E)}. We can then form an infinite, random graph {\hat G = ({\mathbb Z}, \hat E)} from this graph by the following recipe:

  • The vertex set of {\hat G} will be the integers {{\mathbb Z} = \{ -2,-1,0,1,2,\ldots\}}.
  • For every integer {n}, we randomly select a vertex {v_n} in {V}, uniformly and independently at random. (Note that there will be many collisions, i.e. integers {n,m} for which {v_n=v_m}, but these collisions will become asymptotically negligible in the limit {|V| \rightarrow \infty}.)
  • We then define the edge set {\hat E} of {\hat G} by declaring {(n,m)} to be an edge on {\hat E} if and only if {(v_n,v_m)} is an edge in {E} (which in particular requires {v_n \neq v_m}).

More succinctly, {\hat G} is the pullback of {G} under a random map from {{\mathbb Z}} to {V}.

The random graph {\hat G} captures all the “local” information of {G}, while obscuring all the “global” information. For instance, the edge density of {G} is essentially just the probability that a given edge, say {(1,2)}, lies in {\hat G}. (There is a small error term due to the presence of collisions, but this goes away in the limit {|V| \rightarrow \infty}.) Similarly, the triangle density of {G} is essentially the probability that a given triangle, say {\{(1,2), (2,3), (3,1)\}}, lies in {\hat G}. On the other hand, it is difficult to read off global properties of {G}, such as being connected or {4}-colourable, just from {\hat G}.

At first glance, it may seem a poor bargain to trade in a finite deterministic graph {G} for an infinite random graph {\hat G}, which is a more complicated and less elementary object. However, there are three major advantages of working with {\hat G} rather than {G}:

  • Exchangeability. The probability distribution of {\hat G} has a powerful symmetry or exchangeability property: if one takes the random graph {\hat G} and interchanges any two vertices in {{\mathbb Z}}, e.g. {3} and {5}, one obtains a new graph which is not equal to {\hat G}, but nevertheless has the same probability distribution as {\hat G}, basically because the {v_n} were selected in an iid manner. More generally, given any permutation {\sigma: {\mathbb Z} \rightarrow {\mathbb Z}}, the pullback {\sigma^*(\hat G)} of {\hat G} by {\sigma} has the same probability distribution as {\hat G}; thus we have a measure-preserving action of the symmetric group {S_\infty}, which places us in the general framework of ergodic theory.
  • Limits. The space of probability measures on the space {2^{\binom{{\mathbb Z}}{2}}} of infinite graphs is sequentially compact; given any sequence {\hat G_n = ({\mathbb Z}, \hat E_n)} of infinite random graphs, one can find a subsequence {\hat G_{n_j}} which converges in the vague topology to another infinite random graph. What this means is that given any event {E} on infinite graphs that involve only finitely many of the edges, the probability that {\hat G_{n_j}} obeys {E} converges to the probability that {\hat G} obeys {E}. (Thus, for instance, the probability that {\hat G_{n_j}} contains the triangle {\{(1,2), (2,3), (3,1)\}} will converge to the probability that {\hat G} contains the same triangle.) Note that properties that involve infinitely many edges (e.g. connectedness) need not be preserved under vague limits.
  • Factors. The underlying probability space for the random variable {\hat G} is the space {2^{\binom{{\mathbb Z}}{2}}} of infinite graphs, and it is natural to give this space the Borel {\sigma}-algebra {{\mathcal B}_{\mathbb Z}}, which is the {\sigma}-algebra generated by the cylinder events “{(i,j) \in \hat G}” for {i,j \in {\mathbb Z}}. But this {\sigma}-algebra also has a number of useful sub-{\sigma}-algebras or factors, representing various partial information on the graph {\hat G}. In particular, given any subset {I} of {{\mathbb Z}}, one can create the factor {{\mathcal B}_I}, defined as the {\sigma}-algebra generated by the events “{(i,j) \in \hat G}” for {i,j \in I}. Thus for instance, the event that {\hat G} contains the triangle is measurable in {{\mathcal B}_{\{1,2,3\}}}, but not in {{\mathcal B}_{\{1,2\}}}. One can also look at compound factors such as {{\mathcal B}_I \wedge {\mathcal B}_J}, the factor generated by the union of {{\mathcal B}_I} and {{\mathcal B}_J}. For instance, the event that {\hat G} contains the edges {(1,2), (1,3)} is measurable in {{\mathcal B}_{\{1,2\}} \vee {\mathcal B}_{\{1,3\}}}, but the event that {\hat G} contains the triangle {\{(1,2), (2,3), (3,1)\}} is not.

The connection between the infinite random graph {\hat G} and partitioning through random neighbourhoods comes when contemplating the relative difference between a factor such as {{\mathcal B}_{\{-n,\ldots,-1\}}} and {{\mathcal B}_{\{-n,\ldots,-1\} \cup \{1\}}} (say). The latter factor is generated by the former factor, together with the events “{(1,-i) \in \hat E}” for {i=1,\ldots,n}. But observe if {\hat G = ({\mathbb Z}, \hat E)} is generated from a finite deterministic graph {G = (V,E)}, then {(1,-i)} lies in {\hat E} if and only if {v_1} lies in the vertex neighbourhood of {v_{-i}}. Thus, if one uses the vertex neighbourhoods of {v_{-1},\ldots,v_{-n}} to subdivide the original vertex set {V} into {2^n} cells of varying sizes, the factor {{\mathcal B}_{\{-n,\ldots,-1\} \cup \{1\}}} is generated from {{\mathcal B}_{\{-n,\ldots,-1\}}}, together with the random variable that computes which of these {2^n} cells the random vertex {v_1} falls into. We will see this connection in more detail later in this post, when we use the correspondence principle to prove Lemma 2.

Combining the exchangeability and limit properties (and noting that the vague limit of exchangeable random graphs is still exchangeable), we obtain

Lemma 3 (Graph correspondence principle) Let {G_n = (V_n,E_n)} be a sequence of finite deterministic graphs, and let {\hat G_n = ({\mathbb Z}, \hat E_n)} be their infinite random counterparts. Then there exists a subsequence {n_j} such that {\hat G_{n_j}} converges in the vague topology to an exchangeable infinite random graph {\hat G = ({\mathbb Z}, \hat E)}.

We can illustrate this principle with three main examples, two from opposing extremes of the “dichotomy between structure and randomness”, and one intermediate one.

Example 1 (Random example) Let {G_n = (V_n,E_n)} be a sequence of {\varepsilon_n}-regular graphs of edge density {p_n}, where {|V_n| \rightarrow \infty}, {\varepsilon_n \rightarrow 0}, and {p_n \rightarrow p} as {n \rightarrow \infty}. Then any graph limit {\hat G = ({\mathbb Z},\hat G)} of this sequence will be an Erdös-Rényi graph {\hat G = G(\infty,p)}, where each edge {(i,j)} lies in {\hat G} with an independent probability of {p}.

Example 2 (Structured example) Let {G_n = (V_n,E_n)} be a sequence of complete bipartite graphs, where the two cells of the bipartite graph have vertex density {q_n} and {1-q_n} respectively, with {|V_n| \rightarrow \infty} and {q_n \rightarrow q}. Then any graph limit {\hat G = ({\mathbb Z},\hat E)} of this sequence will be a random complete bipartite graph, constructed as follows: first, randomly colour each vertex {n} of {{\mathbb Z}} red with probability {q} and blue with probability {1-q}, independently for each vertex. Then define {\hat G} to be the complete bipartite graph between the red vertices and the blue vertices.

Example 3 (Random+structured example) Let {G_n = (V_n,E_n)} be a sequence of incomplete bipartite graphs, where the two cells of the bipartite graph have vertex density {p_n} and {1-p_n} respectively, and the graph {G_n} is {\varepsilon_n}-regular between these two cells with edge density {p_n}, with {|V_n| \rightarrow \infty}, {\varepsilon_n \rightarrow 0}, {p_n \rightarrow p}, and {q_n \rightarrow q}. Then any graph limit {\hat G = ({\mathbb Z},\hat E)} of this sequence will be a random bipartite graph, constructed as follows: first, randomly colour each vertex {n} of {{\mathbb Z}} red with probability {q} and blue with probability {1-q}, independently for each vertex. Then define {\hat G} to be the bipartite graph between the red vertices and the blue vertices, with each edge between red and blue having an independent probability of {p} of lying in {\hat E}.

One can use the graph correspondence principle to prove statements about finite deterministic graphs, by the usual compactness and contradiction approach: argue by contradiction, create a sequence of finite deterministic graph counterexamples, use the correspondence principle to pass to an infinite random exchangeable limit, and obtain the desired contradiction in the infinitary setting. (See this earlier blog post of mine for further discussion.) This will be how we shall approach the proof of Lemma 2.

— 2. The infinitary regularity lemma —

To prove the finitary regularity lemma via the correspondence principle, one must first develop an infinitary counterpart. We will present this infinitary regularity lemma (first introduced in this paper) shortly, but let us motivate it by a discussion based on the three model examples of infinite exchangeable graphs {\hat G = ({\mathbb Z}, \hat E)} from the previous section.

First, consider the “random” graph {\hat G} from Example 1. Here, we observe that the events “{(i,j) \in \hat E}” are jointly independent of each other, thus for instance

\displaystyle {\Bbb P}( (1,2), (2,3), (3,1) \in \hat E ) = \prod_{(i,j) = (1,2), (2,3), (3,1)} {\Bbb P}( (i,j) \in \hat E ).

More generally, we see that the factors {{\mathcal B}_{\{i,j\}}} for all distinct {i,j \in {\mathbb Z}} are independent, which means that

\displaystyle {\Bbb P}( E_1 \wedge \ldots \wedge E_n ) = {\Bbb P}(E_1) \ldots {\Bbb P}(E_n)

whenever {E_1 \in {\mathcal B}_{\{i_1,j_1\}}, \ldots, E_n \in {\mathcal B}_{\{i_n,j_n\}}} and the {\{i_1,j_1\},\ldots,\{i_n,j_n\}} are distinct.

Next, we consider the “structured” graph {\hat G} from Example 2, where we take {0 < p < 1} to avoid degeneracies. In contrast to the preceding example, the events “{(i,j) \in \hat E}” are now highly dependent; for instance, if {(1,2) \in \hat E} and {(1,3) \in \hat E}, then this forces {(2,3)} to lie outside of {\hat E}, despite the fact that the events “{(i,j) \in \hat E}” each occur with a non-zero probability of {p (1-p)}. In particular, the factors {{\mathcal B}_{\{1,2\}}, {\mathcal B}_{\{1,3\}}, {\mathcal B}_{\{2,3\}}} are not jointly independent.

However, one can recover a conditional independence by introducing some new factors. Specifically, let {{\mathcal B}_i} be the factor generated by the event that the vertex {i} is coloured red. Then we see that the factors {{\mathcal B}_{\{1,2\}}, {\mathcal B}_{\{1,3\}}, {\mathcal B}_{\{2,3\}}} now become conditionally jointly independent, relative to the base factor {{\mathcal B}_1 \vee {\mathcal B}_2 \vee {\mathcal B}_3}, which means that we have conditional independence identities such as

\displaystyle {\Bbb P}( (1,2), (2,3), (3,1) \in \hat{E} | {\mathcal B}_1 \vee {\mathcal B}_2 \vee {\mathcal B}_3 ) = \prod_{(i,j) = (1,2), (2,3), (3,1)} {\Bbb P}( (i,j) \in \hat{E} | {\mathcal B}_1 \vee {\mathcal B}_2 \vee {\mathcal B}_3 ).

Indeed, once one fixes (conditions) the information in {{\mathcal B}_1 \vee {\mathcal B}_2 \vee {\mathcal B}_3} (i.e. once one knows what colour the vertices {1,2,3} are), the events “{(i,j) \in \hat E}” for {(i,j)=(1,2), (2,3), (3,1)} either occur with probability {1} (if {i, j} have distinct colours) or probability {0} (if {i,j} have the same colour), and so the conditional independence is trivially true.

A similar phenomenon holds for the “random+structured” graph {\hat G} from Example 3, with {0 < p,q < 1}. Again, the factors {{\mathcal B}_{\{i,j\}}} are not jointly independent in an absolute sense, but once one introduces the factors {{\mathcal B}_i} based on the colour of the vertex {i}, we see once again that the {{\mathcal B}_{\{i,j\}}} become conditionally jointly independent relative to the {{\mathcal B}_i}.

These examples suggest, more generally, that we should be able to regularise the graph {\hat G} (or more precisely, the system of edge factors {{\mathcal B}_{\{i,j\}}}) by introducing some single-vertex factors {{\mathcal B}_i}, with respect to which the edge factors become conditionally independent; this is the infinitary analogue of a finite graph becoming {\varepsilon}-regular relative to a suitably chosen partition of the vertex set into cells.

Now, in Examples 2, 3 we were able to obtain this regularisation because the vertices of the graph were conveniently coloured for us (red or blue). But for general infinite exchangeable graphs {\hat G}, such a vertex colouring is not provided to us, so how is one to generate the vertex factors {{\mathcal B}_i}?

The key trick – which is the infinitary analogue of using random neighbourhoods to regularise a finitary graph – is to sequester half of the infinite vertices in {{\mathbb Z}} – e.g. the negative vertices {-1, -2, \ldots} – away as “reference” or “training” vertices, and then and colorise the remaining vertices {i} of the graph based on how that vertex interacts with the reference vertices. More formally, we define {{\mathcal B}_i} for {i=0,1,2,\ldots} by the formula

\displaystyle {\mathcal B}_i := {\mathcal B}_{\{ -1,-2,\ldots\} \cup \{i\}}.

We then have

Lemma 4 (Infinitary regularity lemma) Let {\hat G = ({\mathbb Z},\hat E)} be a infinite exchangeable random graph. Then the {{\mathcal B}_{\{i,j\}} \vee {\mathcal B}_i \vee {\mathcal B}_j} for natural numbers {i,j} are conditinally jointly independent relative to the {{\mathcal B}_i}. More precisely, if {I} is a set of natural numbers, {E} is a subset of {\binom{I}{2}}, and {E_e} is a {{\mathcal B}_e \wedge \bigwedge_{i \in e} {\mathcal B}_i}-measurable event for all {e \in E}, then

\displaystyle \mathop{\mathbb P}( \bigwedge_{e \in E} E_{e} | \bigwedge_{i \in I} {\mathcal B}_i ) = \prod_{e \in E} \mathop{\mathbb P}( E_e | \bigwedge_{i \in I} {\mathcal B}_i ).

Proof: By induction on {E}, it suffices to show that for any {e_0 \in E}, the event {E_{e_0}} and the event {\bigwedge_{e \in E \backslash \{e_0\}} E_e} are independent relative to {\bigwedge_{i \in I} {\mathcal B}_i}.

By relabeling we may take {I = \{1,\ldots,n\}} and {e_0=\{1,2\}} for some {n \geq 2}. We use the exchangeability of {\hat G} (and Hilbert’s hotel) to observe that the random variables

\displaystyle {\Bbb E}( 1_{E_{e_0}} | {\mathcal B}_{\{-1,-2,\ldots\} \cup \{1\}} \vee {\mathcal B}_{\{-1,-2,\ldots\} \cup \{2\}} )

and

\displaystyle {\Bbb E}( 1_{E_{e_0}} | {\mathcal B}_{\{-1,-2,\ldots\} \cup \{1\} \cup \{3,\ldots,n\}} \vee {\mathcal B}_{\{-1,-2,\ldots\} \cup \{2\} \cup \{3,\ldots,n\}} )

have the same distribution; in particular, they have the same {L^2} norm. By Pythagoras’ theorem, they must therefore be equal almost surely; furthermore, for any intermediate {\sigma}-algebra {{\mathcal B}} between {{\mathcal B}_{\{-1,-2,\ldots\} \cup \{1\}} \vee {\mathcal B}_{\{-1,-2,\ldots\} \cup \{2\}}} and {{\mathcal B}_{\{-1,-2,\ldots\} \cup \{1\} \cup \{3,\ldots,n\}} \vee {\mathcal B}_{\{-1,-2,\ldots\} \cup \{2\} \cup \{3,\ldots,n\}}}, {{\Bbb E}( 1_{E_{e_0}} | {\mathcal B} )} is also equal almost surely to the above two expressions. (The astute reader will observe that we have just run the “energy increment argument”; in the infinitary world, it is somewhat slicker than in the finitary world, due to the convenience of the Hilbert’s hotel trick, and the fact that the existence of orthogonal projections (and in particular, conditional expectation) is itself encoding an energy increment argument.)

As a special case of the above observation, we see that

\displaystyle {\Bbb E}( 1_{E_{e_0}} | \bigwedge_{i \in I} {\mathcal B}_i ) = {\Bbb E}( 1_{E_{e_0}} | \bigwedge_{i \in I} {\mathcal B}_i \wedge \bigwedge_{e \in E \backslash \{e_0\}} {\mathcal B}_e ).

In particular, this implies that {E_0} is conditionally independent of every event measurable in {\bigwedge_{i \in I} {\mathcal B}_i \wedge \bigwedge_{e \in E \backslash \{e_0\}} {\mathcal B}_e}, relative to {\bigwedge_{i \in I} {\mathcal B}_i}, and the claim follows. \Box

We remark that the same argument also allows one to easily regularise infinite exchangeable hypergraphs; see my paper for details. In fact one can go further and obtain a structural theorem for these hypergraphs generalising de Finetti’s theorem, and also closely related to the graphons of Lovasz and Szegedy; see this paper of Austin for details.

— 3. Proof of finitary regularity lemma —

Having proven the infinitary regularity lemma, we now use the correspondence principle and the compactness and contradiction argument to recover the finitary regularity lemma, Lemma 2.

Suppose this lemma failed. Carefully negating all the quantifiers, this means that there exists {\varepsilon > 0}, a sequence {M_n} going to infinity, and a sequence of finite deterministic graphs {G_n = (V_n,E_n)} such that for every {1 \leq M \leq M_n}, if one selects vertices {v_1,\ldots,v_M \in V_n} uniformly from {V_n}, then the {2^{M}} vertex cells {V^{M}_1,\ldots,V^{M}_{2^{M}}} generated by the vertex neighbourhoods {A_t := \{ v \in V: (v,v_t) \in E \}} for {1 \leq t \leq M}, will obey the regularity property (1) with probability less than {1-\varepsilon}.

We convert each of the finite deterministic graphs {G_n = (V_n,E_n)} to an infinite random exchangeable graph {\hat G_n = ({\mathbb Z}, \hat E_n)}; invoking the ocrrespondence principle and passing to a subsequence if necessary, we can assume that this graph converges in the vague topology to an exchangeable limit {\hat G = ({\mathbb Z}, \hat E)}. Applying the infinitary regularity lemma to this graph, we see that the edge factors {{\mathcal B}_{\{i,j\}} \wedge {\mathcal B}_i \wedge {\mathcal B}_j} for natural numbers {i,j} are conditionally jointly independent relative to the vertex factors {{\mathcal B}_i}.

Now for any distinct natural numbers {i,j}, let {f(i,j)} be the indicator of the event “{(i,j)} lies in {\hat E}“, thus {f=1} when {(i,j)} lies in {\hat E} and {f(i,j)=0} otherwise. Clearly {f(i,j)} is {{\mathcal B}_{\{i,j\}}}-measurable. We can write

\displaystyle f(i,j) = f_{U^\perp}(i,j) + f_U(i,j)

where

\displaystyle f_{U^\perp}(i,j) := {\Bbb E}( f(i,j) | {\mathcal B}_i \wedge {\mathcal B}_j )

and

\displaystyle f_U(i,j) := f(i,j) - f_{U^\perp}(i,j).

The exchangeability of {\hat G} ensures that {f, f_U, f_{U^\perp}} are exchangeable with respect to permutations of the natural numbers, in particular {f_U(i,j)=f_U(j,i)} and {f_{U^\perp}(i,j)=f_{U^\perp}(j,i)}.

By the infinitary regularity lemma, the {f_U(i,j)} are jointly independent relative to the {{\mathcal B}_i}, and also have mean zero relative to these factors, so in particular they are infinitely pseudorandom in the sense that

\displaystyle {\Bbb E} f_U(1,2) f_U(3,2) f_U(1,4) f_U(3,4) = 0.

Meanwhile, the random variable {f_{U^\perp}(1,2)} is measurable with respect to the factor {{\mathcal B}_1 \vee {\mathcal B}_2}, which is the limit of the factors {{\mathcal B}_{\{-1,-2,\ldots,-M\} \cup \{1\}} \vee {\mathcal B}_{\{-1,-2,\ldots,-M\} \cup \{2\}}} as {M} increases. Thus, given any {\tilde \varepsilon > 0} (to be chosen later), one can find an approximation {\tilde f_{U^\perp}(1,2)} to {f_{U^\perp}(1,2)}, bounded between {0} and {1}, which is {{\mathcal B}_{\{-1,-2,\ldots,-M\} \cup \{1\}} \vee {\mathcal B}_{\{-1,-2,\ldots,-M\} \cup \{2\}}}-measurable for some {M}, and such that

\displaystyle {\Bbb E} |\tilde f_{U^\perp}(1,2) - f_{U^\perp}(1,2)| \leq \tilde \varepsilon.

We can also impose the symmetry condition {\tilde f_{U^\perp}(1,2) =\tilde f_{U^\perp}(2,1)}. Now let {\tilde \varepsilon' > 0} be an extremely small number (depending on {\tilde \varepsilon,n}) to be chosen later. Then one can find an approximation {\tilde f_U(1,2)} to {f_U(1,2)}, bounded between {-1} and {1}, which is {{\mathcal B}_{\{-1,-2,\ldots,-M'\} \cup \{1\}} \vee {\mathcal B}_{\{-1,-2,\ldots,-M'\} \cup \{2\}}}-measurable for some {M'}, and such that

\displaystyle {\Bbb E} |\tilde f_{U}(1,2) - f_{U}(1,2)| \leq \tilde \varepsilon'.

Again we can impose the symmetry condition {\tilde f_{U}(1,2) = \tilde f_{U}(2,1)}. We can then extend {\tilde f_U} by exchangeability, so that

\displaystyle {\Bbb E} |\tilde f_{U}(i,j) - f_{U}(i,j)| \leq \tilde \varepsilon'.

for all distinct natural numbers {i,j}. By the triangle inequality we then have

\displaystyle {\Bbb E} \tilde f_U(1,2) \tilde f_U(3,2) \tilde f_U(1,4) \tilde f_U(3,4) = O(\tilde \varepsilon') \ \ \ \ \ (2)

and by a separate application of the triangle inequality

\displaystyle {\Bbb E} |f(i,j) - \tilde f_{U^\perp}(i,j) - \tilde f_U(i,j)| = O(\tilde \varepsilon). \ \ \ \ \ (3)

The bounds (2), (3) apply to the limiting infinite random graph {\hat G = ({\mathbb Z},\hat E)}. On the other hand, all the random variables appearing in (2), (3) involve at most finitely many of the edges of the graph. Thus, by vague convergence, the bounds (2), (3) also apply to the graph {\hat G_n = ({\mathbb Z}, \hat E_n)} for sufficiently large {n}.

Now we unwind the definitions to move back to the finite graphs {G_n = (V_n,E_n)}. Observe that, when applied to the graph {\hat G_n}, one has

\displaystyle \tilde f_{U^\perp}(1,2) = F_{U^\perp,n}( v_1, v_2 )

where {F_{U,n}: V_n \times V_n \rightarrow [0,1]} is a symmetric function which is constant on the pairs of cells {V^{M}_1,\ldots,V^{M}_{2^{M}}} generated the vertex neighbourhoods of {v_{-1},\ldots,v_{-M}}. Similarly,

\displaystyle \tilde f_{U}(1,2) = F_{U,n}( v_1, v_2 )

for some symmetric function {F_{U,n}: V_n \times V_n \rightarrow [-1,1]}. The estimate (2) can then be converted to a uniformity estimate on {F_{U,n}}

\displaystyle {\Bbb E} F_{U,n}(v_1,v_2) F_{U,n}(v_3,v_2) F_{U,n}(v_1,v_4) F_{U,n}(v_3,v_4) = O(\tilde \varepsilon')

while the estimate (3) can be similarly converted to

\displaystyle {\Bbb E} |1_{E_n}(v_1,v_2) - F_{U^\perp,n}(v_1,v_2) - F_{U,n}(v_1,v_2)| = O(\tilde \varepsilon).

If one then repeats the arguments in the preceding blog post, we conclude (if {\tilde \varepsilon} is sufficiently small depending on {\varepsilon}, and {\tilde \varepsilon'} is sufficiently small depending on {\varepsilon}, {\tilde eps}, {M}) that for {1-\varepsilon} of the choices for {v_{-1},\ldots,v_{-M}}, the partition {V^{M}_1,\ldots,V^{M}_{2^{M}}} induced by the corresponding vertex neighbourhoods will obey (1). But this contradicts the construction of the {G_n}, and the claim follows.

About these ads