Limits of local-global convergent graph sequences

Introduction

The theory of graph convergence is a recently emerging field. It creates a link between combinatorics and analysis similarly as Fürstenberg’s correspondence principle connects finite integer sequences with measure preserving systems. Interestingly (or rather unfortunately) there is no unified theory of graph convergence. Instead there are various convergence notions that work well in different situations. For example the theory of dense graph limits works well if the number of edges is quadratic in the number of vertices but it trivializes for sparser graphs. On the other hand the Benjamini–Schramm limit is only defined for graphs which have a linear number of edges in terms of the vertices. In the regime between linear and quadratic the situation is more complicated.

In this paper we focus on the very sparse case were graphs have degrees bounded by some fixed number $d$ (which we consider as fixed throughout). According to Benjamini and Schramm, a graph sequence $(G_{n})_{n=1}^{\infty}$ is convergent if the distribution of the isomorphism types of neighborhoods of radius $r$ (when a vertex is chosen uniformly at random in $G_{n}$) converges for every fixed $r$. This notion of convergence is called local convergence, weak convergence or Benjamini–Schramm convergence.

The following example illustrates why a different, stronger notion of convergence is needed in some cases. For odd $n$, let $G_{n}$ be a $d$-regular expander graph on $n$ nodes. For even $n$, let $G_{n}$ be the disjoint union of two $d$-regular expander graphs on $n/2$ nodes. Assume that the girth of $G_{n}$ tends to infinity. Then the sequence $G_{n}$ is locally convergent, but clearly even and odd members of the sequence are quite different, and it would be desirable to refine our notion of convergence to distinguish them.

Benjamini and Schramm described a limit object for locally convergent sequences in the form of an involution-invariant distribution on rooted countable graphs with bounded degree. One can also describe this limit object as a graphing (Aldous and Lyons , Elek ), which is a bounded degree graph on a Borel probability space such that the edge set is Borel measurable and it satisfies a certain measure preservation property. (We will give a precise definition below.) Neighborhood statistics in graphings can be defined by using the probability space structure on the vertex set. Every involution-invariant distribution can be represented by a graphing. We note that graphings are common generalizations of bounded degree graphs and measure preserving systems and so they are also interesting from an ergodic theoretic point of view.

However, the graphing representing the limit object of a locally convergent graph sequence is not unique: different graphings can describe the same involution-invariant distribution. In other words, a graphing contains more information than just the limiting neighborhood distribution. This suggests that graphings can be used to represent limit objects for more refined convergence notions. Indeed, in the present paper we show that the limit of a local-global convergent sequence can also be represented by a graphing in the sense that the graphs in the sequence converge to the graphing in the colored neighborhood metric. This means that for every local-global convergent sequence we produce a graphing which contains both local and global information about the graphs.

We highlight the importance of a special family of graphings called Bernoulli graphings. We show that with given local statistics, the Bernoulli graphings contain the least global information. This means that the global properties of a Bernoulli graphing can be modeled with an arbitrary precision on any other graphing with the same local statistics. For a graph $G$, being close to a Bernoulli graphing in the local-global sense means that the local statistics of any coloring on $G$ can be modeled by a randomized process called local algorithm or factor of i.i.d. process.

Roughly speaking, a hyperfinite graph sequence is a bounded degree sequence whose members can be cut into small connected components removing a small set of vertices (or equivalently edges). We prove that a locally convergent hyperfinite sequence is locally-globally convergent, and its limit is a Bernoulli graphing. (This was proved independently by Elek ). It is an interesting question how to construct a non-hyperfinite sequence converging to a Bernoulli graphing.

Local-Global convergence of bounded degree graphs

A rooted graph is a pair $(G,o)$ where $o$ is a vertex of a graph $G$. The radius of a rooted graph is the distance of the farthest vertex in $G$ to $o$. We denote by $U^{r}$ the set of all rooted graphs with radius at most $r$ (and all degrees bounded by $d$). For an integer $r\geq 0$, and a vertex $v$ in a graph $G$, let $N_{G,r}(v)$ denote the subgraph of $G$ rooted at $v$ and induced by the vertices that are at a distance at most $r$ from $v$. Two rooted graphs $(G,o)$ and $(G^{\prime},o^{\prime})$ are said to be isomorphic if there is an isomorphism from $G$ to $G^{\prime}$ that maps $o$ to $o^{\prime}$.

Given a finite graph $G$ and a radius $r\geq 0$, we can choose a node $v\in V(G)$ uniformly and randomly, and consider the distribution of $N_{G,r}(v)$. Let $P_{G,r}$ denote this probability measure on $U^{r}$. We say that a sequence $(G_{n})$ of finite graphs is locally convergent (or Benjamini–Schramm convergent) if $P_{G_{n},r}$ converges to a limit distribution as $n\to\infty$, for every fixed $r\geq 0$.

where $A$ runs through the Borel measurable sets.

To define our refinement of local convergence, we consider vertex colorings. For a finite graph $G$, let $K(k,G)$ denote the set of all vertex colorings with $k$ colors. Fix integers $k$ and $r$, and let $U^{r,k}$ be the set of all triples $(H,o,c)$ where $(H,o)$ is a rooted graph of radius at most $r$ and $c$ is an arbitrary $k$-coloring of $V(H)$. Consider a finite graph $G$ together with a $c\in K(k,G)$. Pick a random vertex $v$ from $G$. Then the restriction of the $k$-coloring to $N_{G,r}(v)$ is an element in $U^{r,k}$, and thus for the graph $G$, every $c\in K(k,G)$ introduces a probability distribution on $U^{r,k}$ which we denote by $P_{G,r}[c]$. Sometimes we refer to the probability distributions $P_{G,r}[c]$ (for $r\geq 0$) as local statistics of the coloring $c$. Let

In other words, if $i$ and $j$ are large enough, then for every $k$-coloring $c_{i}$ of $V(G_{i})$ there is a $k$-coloring $c_{j}$ of $V(G_{j})$ so that the distributions of colored $r$-neighborhoods of $(G_{i},c_{i})$ and $(G_{j},c_{j})$ are almost the same.

Since compact subsets of a compact metric space form a compact space with respect to the Hausdorff metric, it follows that every infinite sequence of finite graphs contains a locally-globally convergent subsequence.

Fixing $k=1$ in Definition 2.1, we recover a metric definition of Benjamini–Schramm convergence. It is easy to construct examples of graph sequences which are convergent in Benjamini–Schramm sense, but not locally-globally. However we do not know whether $k=2$ would give a convergence notion equivalent to local-global convergence.

It is natural to ask if we obtain a different convergence notion if we replace vertex colorings by edge colorings or other locally defined extra structures. It turns out that all local structures can be encoded by vertex colorings, and thus they do not lead to different convergence notions. As an example, we show how to encode edge colorings by vertex colorings.

Let $G$ be a graph with all degrees at most $d$ and let $c:~E(G)\rightarrow[k]$ be an edge coloring of $G$. It is easy to see that there exists an edge coloring $c_{1}:~E(G)\rightarrow[30d^{3}k]$ such that $c_{1}(e)\equiv c(e)$ modulo $k$ for every $e\in E(G)$, and if $c_{1}(e_{1})=c_{1}(e_{2})$ holds, then the edges $e_{1}$ and $e_{2}$ are of distance at least $3$ in the edge graph of $G$. It is clear that $c_{1}$ encodes the coloring $c$ in the sense that local statistics of $c_{1}$ modulo $k$ give the local statistics of $c$. Let $S$ denote the set of subsets of $[30d^{3}k]$ of size at most $d$. We define the vertex coloring $c_{2}:~V(G)\rightarrow S$ by setting $c_{2}(v)$ to be the set of $c_{1}$-colors of the edges incident to $v$. Now it is easy to see that $c_{2}$ encodes the coloring $c_{1}$ in the following way. If $e=(v,w)$ is an edge in $G$, then $\{c_{1}(e)\}$ is the intersection of the sets $c_{2}(v)$ and $c_{2}(w)$.

Involution-invariant measures and graphings

Benjamini and Schramm associated a limit object with every locally convergent graph sequence as follows. Let $\mathfrak{G}$ denote the set of (isomorphism classes of) rooted, connected (possibly infinite) graphs with all degrees at most $d$. For a rooted graph $(B,o)$ with radius $r$, we denote by $\mathfrak{G}(B,o)$ the set of all rooted graphs $(G,o)$ such that $N_{G,r}(o)\cong(B,o)$. For a rooted graph $(G,o)$, we define a neighborhood basis at $(G,o)$ as $\mathfrak{G}(N_{G,r}(o))$. These neighborhoods define a topology on $\mathfrak{G}$. It is easy to see that this is a compact separable space.

The Benjamini–Schramm limit of the locally convergent graph sequence $(G_{n})_{n=1}^{\infty}$ is a probability measure $\nu$ on the Borel sets of $\mathfrak{G}$, such that

for every $r\geq 1$ and every rooted graph $(B,o)$ of radius $r$.

Let $G$ be a finite graph, and let the probability measure $\nu$ on the Borel sets of $\mathfrak{G}$ be defined as $\nu(\mathfrak{G}(B,o))=P_{G,r}(B,o)$ for every $r\geq 1$ and every rooted graph $(B,o)$ of radius $r$. It is easy to see that $\nu$ is involution-invariant. It follows that every measure on $\mathfrak{G}$ that is the limit of finite graphs is involution-invariant. Aldous and Lyons conjectured that all involution-invariant measures arise as graph limits. The Aldous-Lyons conjecture is considered to be one of the most important open problems in this area.

In the dense setting, the set of the symmetric measurable maps $w:^{2}\rightarrow$ were used to generalize the concept of graphs and describe graph limits . For local-global convergence (Definition 2.1), graphings serve this purpose.

Let $X$ be a Polish topological space and let $\nu$ be a probability measure on the Borel sets in $X$. A graphing is a graph $\mathcal{G}$ on $V(\mathcal{G})=X$ with Borel measurable edge set $E(\mathcal{G})\subset X\times X$ in which all degrees are at most $d$ and

for all measurable sets $A,B\subseteq X$, where $e(x,S)$ is the number of edges from $x\in X$ to $S\subseteq X$.

Note that every finite graph $G$ is a graphing where $X=V(G)$ and $\nu_{\mathcal{G}}$ is the uniform distribution on $V(G)$.

If (1) holds, then $\eta^{*}(A\times B)=\int_{A}e(x,B)d\nu(x)$ defines a measure on the Borel sets of $X\times X$. This measure is concentrated on $E(\mathcal{G})$, symmetric in the two coordinates, and its marginal $\nu^{*}$ satisfies $(d\nu^{*}/d\nu)(x)=\deg(x)$. Normalizing by $d_{0}=\int_{X}\deg(x)\,dx$, we get a probability distribution $\eta$ on the set of edges. We can generate a random edge from $\eta$ by selecting a random point $v$ from $\nu^{*}$ and selecting uniformly a random edge incident with $v$. Conversely, if $\mathcal{G}$ is a Borel graph and we have a measure $\eta^{*}$ on $X\times X$ that is concentrated on $E(\mathcal{G})$, so that $\eta^{*}(A\times B)=\int_{A}e(x,B)d\nu(x)$, then (1) follows by Fubini’s theorem, and so $\mathcal{G}$ is a graphing.

Let $\mathcal{G}$ be a graphing (of degree at most $d$) on the probability space $(X,\nu)$. Then it induces a measure $\mu_{\mathcal{G}}$ on $\mathfrak{G}$: pick a random element $x\in X$ and take its connected component $\mathcal{G}_{x}$ rooted at $x$. It is easy to see that $\mu_{\mathcal{G}}$ is an involution-invariant measure. (In fact, (1) just expresses this property.)

Now we are ready to state our main theorem.

Let $(G_{i})_{i=1}^{\infty}$ be a local-global convergent sequence of finite graphs with all degrees at most $d$. Then there exists a graphing $\mathcal{G}$ such that $Q_{G_{n},r,k}\to Q_{\mathcal{G},r,k}$ $(n\to\infty)$ in Hausdorff distance for every $r$ and $k$.

To what degree is the limit object determined? This question leads to different notions of “isomorphism” between graphings.

Let $(\mathcal{G}_{1},X_{1},\nu_{1})$ and $(\mathcal{G}_{2},X_{2},\nu_{2})$ be graphings.

Local equivalence of two graphings means that they induce the same involution-invariant measure on $\mathfrak{G}$. Local-global equivalence implies local equivalence by setting $k=1$.

Assume that $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are two graphings of maximal degree at most $d$. We say that $\mathcal{G}_{1}\prec\mathcal{G}_{2}$ if $\overline{Q}_{\mathcal{G}_{1},r,k}\subseteq\overline{Q}_{\mathcal{G}_{2},r,k}$ for every $r,k\geq 1$. In particular, $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are locally-globally equivalent if and only if both $\mathcal{G}_{1}\prec\mathcal{G}_{2}$ and $\mathcal{G}_{2}\prec\mathcal{G}_{1}$ hold.

In the setting of group actions, this partial order means the same as “weak containment” of the corresponding group actions, and local-global equivalence corresponds to “weak equivalence” (Kechris ).

Recall that a measurable map $\phi:(X,\mu)\to(Y,\nu)$ is called measure-preserving if $\mu(\phi^{-1}(A))=\nu(A)$ for every measurable set $A\subseteq Y$. An easy way to prove a relation $\mathcal{G}_{1}\prec\mathcal{G}_{2}$ between two graphings is the following. We call a measure preserving map $\phi:~V(\mathcal{G}_{1})\to V(\mathcal{G}_{2})$ a local isomorphism if restricted to any connected component of $\mathcal{G}_{1}$, we get an isomorphism with a connected component of $\mathcal{G}_{2}$. Clearly local isomorphisms can be combined. However, a local isomorphism may not be invertible! It is easy to see that the existence of a local isomorphism $\mathcal{G}_{1}\to\mathcal{G}_{2}$ implies that $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are locally equivalent, and $\mathcal{G}_{2}\prec\mathcal{G}_{1}$.

Let $G$ be a finite connected graph, and $G\cup G$ denote the disjoint union of $G$ with itself. The function $\phi:~V(G\cup G)\to V(G)$ that maps both copies of $G$ in $G\cup G$ isomorphically to $G$ is a (non-invertible) local isomorphism. Consequently $G\cup G$ and $G$ are locally equivalent, and $G\prec G\cup G$. However, $G$ and $G\cup G$ are not locally-globally equivalent.

We shall study the local-global equivalence and the local-global partial order in Sections 7 and 8. In particular, we will show that among all graphings in a local equivalence class, there is always a smallest one and a largest one in this partial order.

Local limits of decorated graphs

In this section we extend the formalism behind the Benjamini–Schramm limits for the case when vertices are decorated by elements from a compact space. Let $C$ be a second countable compact Hausdorff space. Let $\mathfrak{G}(C)$ denote the space of (isomorphism classes of) rooted, connected (countable) graphs with all degrees at most $d$ such that the vertices are decorated by elements from $C$. So the points of $\mathfrak{G}(C)$ are triples $(G,o,c)$, where $G$ is a connected countable graph, $o\in V(G)$, and $c:~V(G)\to C$. If $C$ is the trivial (one point) compact space, then $\mathfrak{G}(C)$ can be identified with the space $\mathfrak{G}$ defined earlier. Two important special cases for us will be when $C=$ (assigning $$-weights to vertices), and$C=[k]$(coloring vertices by$k$colors). With a slight abuse of notation, these will be denoted by$\mathfrak{G}$and$\mathfrak{G}[k]$.

We put a compact topology on $\mathfrak{G}(C)$ by specifying a basis of it. Let $r$ be an arbitrary natural number and $(H,o)$ be a finite rooted graph of radius $r$. Assume furthermore that every vertex $v$ of $(H,o)$ is decorated by an open set $U_{v}$ in $C$. Let $S$ be the collection of all $(G,o,c)\in\mathfrak{G}(C)$ where the neighborhood $N_{G,r}(o)$ is isomorphic to $(H,o)$, and furthermore there is an isomorphism $\alpha:~N_{G,r}(o)\rightarrow(H,o)$ such that $c(v)\in U_{\alpha(v)}$ for every $v\in N_{G,r}(o)$. It is easy to see that $\mathfrak{G}(C)$ with this topology is a compact, second countable, Hausdorff space. As a consequence, probability measures on $\mathfrak{G}(C)$ form a compact space in the weak topology.

Let $G$ be a finite graph with all degrees at most $d$ in which the vertices are $C$-labeled. We can construct a probability measure $\mu_{G}$ on $\mathfrak{G}(C)$ by putting a root $o$ on a randomly chosen vertex $v\in V(G)$ and keeping only the connected component of the root. A sequence $(G_{n})_{n=1}^{\infty}$ of $C$-labeled graphs is called locally convergent if the corresponding measures $\{\mu_{G_{n}}\}_{n=1}^{\infty}$ converge in the weak topology to some measure $\mu$. The measure $\mu$ is the limit object of the sequence.

We define involution-invariance completely analogously to the undecorated case, simply replacing $\mathfrak{G}$ by $\mathfrak{G}(C)$ everywhere. Involution-invariant measures on $\mathfrak{G}(C)$ form a closed set in the weak topology. It follows that if $\mu$ is a measure on $\mathfrak{G}(C)$ that is the limit of finite $C$-decorated graphs, then it is involution-invariant.

A $C$-decorated graphing is a graphing $\mathcal{G}$ together with a Borel function $c:~V(\mathcal{G})\rightarrow C$. Similarly as in the undecorated case, every $C$-decorated graphing defines an involution-invariant distribution. The measure $\mu_{\mathcal{G},c}$ on $\mathfrak{G}(C)$ is created by picking a random element $x\in V(\mathcal{G})$, and taking its connected component $\mathcal{G}_{x}$ rooted at $x$ together with the vertex labels given by the restriction of $c$ to $V(\mathcal{G}_{x})$. It is easy to see that $\mu_{\mathcal{G},c}$ is an involution-invariant measure.

We can define a Borel graph on $\mathfrak{G}(C)$. The edge set $\mathcal{E}(C)$ of this graph consists of pairs $((G,o_{1},c),(G,o_{2},c))\in\mathfrak{G}(C)\times\mathfrak{G}(C)$ such that $(o_{1},o_{2})$ is an edge in $G$. Note that loop edges can arise in this graph. For example if there is an automorphism of $(G,c)$ which takes $o_{1}$ to its neighbor $o_{2}$, then $(G,o_{1},c)$ is identified with $(G,o_{2},c)$ in $\mathfrak{G}(C)$. In general it is not true that every involution-invariant measure $\nu$ on $\mathfrak{G}(C)$ turns this graph into a graphing. This is due to the problem with automorphisms which also lead to loops. However it is not hard to show that if for an involution-invariant measure $\nu$, with probability one, a $\nu$-random connected component has no automorphisms, then we get a graphing $(\mathfrak{G}(C),\nu,\mathcal{E}(C))$. One important role of appropriate decorations is to break symmetries, and make this graph a graphing.

A regularization lemma

The following lemma is the main ingredient in proving Theorem 3.2. It serves as a “regularity lemma” in our framework for bounded degree graphs.

For positive integers $r,k$ and real number $\varepsilon>0$, there exists an integer $t_{r,k,\varepsilon}$ such that the following holds. For every graph $G$ with all degrees at most $d$, there exists a $t_{r,k,\varepsilon}$-vertex coloring $q$ of $G$ which satisfies the following conditions.

If $q(v)=q(w)$, then either $v=w$ or the distance of $v$ and $w$ in $G$ is at least $r+1$;

For every $g\in K(k,G)$, there exists $\alpha:[t_{r,k,\varepsilon}]\rightarrow[k]$ such that

Now we further refine $f$ to satisfy the first condition. Let $f^{\prime}$ be a proper coloring of the graph $G$ with $(d+1)^{r}$ colors in which every two vertices in distance at most $r$ receive different colors. The common refinement $q$ of $f$ and $f^{\prime}$ satisfies both conditions.

Proof of the main theorem

By choosing a subsequence from $(G_{i})_{i=1}^{\infty}$ we can assume that the sequence $\{\mu_{i}\}_{i=1}^{\infty}$ weakly converges to a probability distribution $\mu$ on $X$. Our goal is to show that the Borel graph $(X,E)$ with the measure $\mu$ is a graphing which represents the local-global limit of $(G_{i})_{i=1}^{\infty}$.

Let us first observe that for a $\mu$-random element $(G,o,c)$ in $(X,\mu)$, with probability one, the vertex labels $\{c(v):v\in V(G)\}$ are all different. This follows from the fact that the colorings $q^{i}_{r,k,n}$ separate points in $G_{i}$ that are closer than $r+1$, and that this property is preserved in the limit. This means that if $v,w\in V(G)$ are of distance $r$, then with probability one their colors projected to the coordinate $(r,k,n)$ (where $k,n$ are arbitrary) are different.

The measurable graph $(X,E,\mu)$ is a graphing.

Let us introduce the measures $\{\eta_{i}^{*}\}_{i=1}^{\infty}$, similarly as in Section 3, by

where $A,B\subseteq X$ are measurable, and $e(x,B)$ is the number of edges $(x,y)\in E$ with $y\in B$. We define $\eta^{*}$ analogously as $\eta^{*}(A\times B)=\int_{A}e(x,B)d\mu(x)$.

Assume that $A,B\subset X$ are open-closed sets. The weak convergence of $\{\mu_{i}\}_{i=1}^{\infty}$ implies that $\lim_{i\to\infty}\eta_{i}^{*}(A\times B)=\eta^{*}(A\times B)$ and $\lim_{i\to\infty}\eta_{i}^{*}(B\times A)=\eta^{*}(B\times A)$. Note that $\eta^{*}_{i}(A\times B)=\eta^{*}_{i}(B\times A)$, since both are equal (up to normalization by $|V(G_{i})|$) to the number of edges between the sets $\{v|(G_{i},v,q_{i})\in A\}$ and $\{v|(G_{i},v,q_{i})\in B\}$. Here we used the fact that the vertex labels $q_{i}(\cdot)$ are all different and thus automorphisms of $G_{i}$ cannot cause any problems. We obtain that $\eta^{*}(B\times A)=\eta^{*}(A\times B)$, and since such product sets generate the whole $\sigma$-algebra on $X\times X$, the proof is complete.

Pick a $\mu$-random point $x=(G,o,c)\in X$. Let the rooted graph $\mathcal{G}_{x}$ be the connected component of $x$ in the graphing $\mathcal{G}$ rooted at $x$. There is a natural vertex coloring on $\mathcal{G}_{x}$ which is the restriction of the function $q$ to the vertices of $\mathcal{G}_{x}$. So $\mathcal{G}_{x}$ can be regarded as an element in $X$. We claim that with probability one $x=(G,o,c)$ is isomorphic (in a root and label preserving way) to $(\mathcal{G}_{x},q|_{\mathcal{G}_{x}})$. Indeed with probability one all the vertex labels of $G$ are different, and in this case the map given by $v\mapsto(G,v,c)$ defines a decoration-preserving isomorphism between $(G,o,c)$ and $\mathcal{G}_{x}$. (The fact that the vertex labels in $G$ are all different guarantees that the map is one to one.)

We conclude that the probability distribution $P_{\mathcal{G},r}[q_{r,k,n}]$ is the same as the distribution of $(N_{G,r}(o),c_{r,k,n})$ where $(G,o,c)$ is a $\mu$-random element in $X$, and $c_{r,k,n}$ is the projection of $c$ to the coordinate $(r,k,n)$. The lemma now follows from the weak convergence of $\{\mu_{i}\}_{i=1}^{\infty}$ to $\mu$.

Let $n\geq 2/\varepsilon$. By Lemma 6.2 there is an index $i_{0}$ such that

for every index $i\geq i_{0}$. Let $i\geq i_{0}$ be arbitrary, and let $c\in K(k,G_{i})$ be a $k$-coloring of $G_{i}$. Then by Lemma 5.1 there is a map $\alpha:~[t_{r,k,\varepsilon/2}]\rightarrow[k]$ such that

The definition of the total variation distance and (2) imply that

Hence $c^{\prime}=\alpha\circ q_{r,k,n}$ satisfies the required condition.

Let $c:X\rightarrow[k]$ be a Borel coloring. Then for every $\delta>0$, there is a continuous coloring $c_{\delta}:~X\rightarrow[k]$ such that $|\mu(c^{-1}(a)\triangle c_{\delta}^{-1}(a))|\leq\delta$ for all $1\leq a\leq k$. Taking $\delta$ to be sufficiently small, we have

Let the graphing $\mathcal{G}_{i}$ be the same as the graphing $\mathcal{G}$ with the only difference that the measure $\mu$ is replaced by $\mu_{i}$. Since $\{\mu_{i}\}_{i=1}^{\infty}$ converges weakly to $\mu$ and $c_{\delta}$ is continuous, there is an index $i_{0}$ such that if $i\geq i_{0}$, then

The coloring $c_{\delta}$ induces a coloring $f^{i}_{\delta}$ on $G_{i}$ which assigns to every vertex $v\in V(G_{i})$ the $c_{\delta}$ color of the rooted graph $(G_{i},v,q_{i})\in X$. Then we have $P_{G_{i},r}[f^{i}_{\delta}]\equiv P_{\mathcal{G}_{i},r}[c_{\delta}]$. Together with (3) and (4), this completes the proof.

Bernoulli graphings and Bernoulli graph sequences

Probably the most fundamental graphing construction is the Bernoulli graphing corresponding to an involution-invariant measure. These graphings are closely related to factor of i.i.d. processes and local algorithms. In this chapter we explain their role in local-global convergence.

Let $\mu$ be an involution-invariant measure on $\mathfrak{G}$. Let $\nu$ be the probability measure on $\mathfrak{G}$ produced by putting independent random weights from $$on the nodes of a$\mu$-random graph. (Note that different choices of the weights can lead to the same point of$\mathfrak{G}$, if they can be transformed into each other by an automorphism of the$\mu$-random rooted graph.) The triple$(\mathfrak{G},\nu,\mathcal{E})$as defined in Remark 4.1 will be called the Bernoulli graphing corresponding to$\mu$, and denoted by$\mathcal{B}_{\mu}$.

It is not hard to see that $\mathcal{B}_{\mu}$ is a graphing and it represents the involution-invariant distribution $\mu$ (Elek ).

Perhaps it would be more natural to decorate the nodes of the $\mu$-random graph by independent bits, or more generally, by colors from $[k]$ for some fixed $k\geq 2$. This would yield an involution-invariant distribution on $\mathfrak{G}[k]$, but the graph $(\mathfrak{G}[k],\mathcal{E}[k])$ together with this distribution would not necessarily form a graphing.

We define the Bernoulli graphing $\mathcal{B}_{\mathcal{G}}$ corresponding to an arbitrary graphing $\mathcal{G}$ as the Bernoulli graphing defined by the involution-invariant distribution induced by $\mathcal{G}$ on $\mathfrak{G}$. Clearly $\mathcal{G}$ and $\mathcal{B}_{\mathcal{G}}$ are locally equivalent.

A simple example for a Bernoulli graphing is provided by the involution-invariant measure which is concentrated on a single $d$-regular rooted tree. Let $T$ denote the rooted $d$-regular tree, and let $(X,\nu)$ be the probability space in which we put independent random weights from $$on the vertices of$T$. Two points of$X$are connected in$\mathcal{G}$if they can be obtained from each other by moving the root to a neighboring vertex. It seems to be an interesting problem to decide whether the sets$Q_{\mathcal{G},r,k}$ are all closed (see also Question 9.1).

The following is a related construction. For every graphing $\mathcal{G}$ on the probability space $(X,\nu)$, we define its Bernoulli lift $\mathcal{G}^{+}$ as follows. The underlying set $X^{+}$ of $\mathcal{G}^{+}$ will be pairs $(x,\xi)$, where $x\in X$ and $\xi:~V(\mathcal{G}_{x})\to$ assigns weights from $$to the vertices of the connected component$\mathcal{G}_{x}$rooted at$x$. We connect$(x,\xi)$to$(y,\upsilon)$if$y$is a neighbor of$x$and$\xi=\upsilon$. (Note that if$y$is a neighbor of$x$, then$\mathcal{G}_{x}=\mathcal{G}_{y}$.) The measure on$X^{+}$is defined as follows. To generate a random element of$X^{+}$, one picks a$\nu$-random point$x\in X$, and then assigns independent random weights$\xi(u)$to the nodes$u$of$\mathcal{G}_{x}$.

We define two maps $\phi:~V(\mathcal{G}^{+})\to V(\mathcal{G})$ and $\psi:~V(\mathcal{G}^{+})\to V(\mathcal{B}_{\mathcal{G}})$ by $\phi(x,\xi)=x$ and $\psi(x,\xi)=\bigl(\mathcal{G}_{x},\xi\bigr)$. It is easy to check that the maps $\phi$ and $\psi$ are local isomorphisms. This implies that graphing $\mathcal{G}$ is locally equivalent to its Bernoulli lift $\mathcal{G}^{+}$ as well as its Bernoulli graphing $\mathcal{B}_{\mathcal{G}}$.

Our main goal in this section is to describe the relationship between $\mathcal{G}$, $\mathcal{B}_{\mathcal{G}}$ and $\mathcal{G}^{+}$ from the point of view of local-global equivalence.

A graphing is called atom-free if its underlying probability space contains no mass points.

Note that no finite graph corresponds to an atom-free graphing. Using the graphing property (1), it is easy to see that if a graphing contains an atom, then this belongs to a finite component. If $\mathcal{G}$ is the local limit of a sequence of connected graphs $(G_{n})_{n=1}^{\infty}$ with $V(G_{n})|\to\infty$, then all its components are infinite, and hence it is atom-free. On the other hand, if the union of finite components of a graphing has positive weight, then merging isomorphic finite components we get atoms. Furthermore, if $\mathcal{G}$ is the local-global limit of graphs $(G_{n})_{n=1}^{\infty}$ (not necessarily connected) with $|V(G_{n})|\to\infty$, then $\mathcal{G}$ is atom-free. This follows from the observation that a graphing is atom-free if and only if its points have a Borel $k$-coloring with equal color classes for every $k$.

The following is our main result in this section.

Every atom-free graphing is local-global equivalent to its Bernoulli lift.

The map $\psi:~V(\mathcal{G}^{+})\to V(\mathcal{B}_{\mathcal{G}})$ defined above is a local isomorphism from $\mathcal{G}^{+}$ to $\mathcal{B}_{\mathcal{G}}$. Thus we have the relation $\mathcal{B}_{\mathcal{G}}\prec\mathcal{G}^{+}$, which implies by Theorem 7.6:

For every atom-free graphing $\mathcal{G}$, we have $\mathcal{B}_{\mathcal{G}}\prec\mathcal{G}$.

In other words, Bernoulli graphings are minimal elements in the set of atom-free graphings in their local equivalence class. A group theoretical analogue of this fact was obtained by Abért and Weiss in .

In an algorithmic setting, a Borel coloring of $\mathcal{G}^{+}$ can be considered as a coloring that depends not only on the graph, but also on a random real number at each point. To be able to imitate this in $\mathcal{G}$, we have to construct “random-like” colorings on $\mathcal{G}$. For technical reasons, we have to deal with graphings that already have a Borel coloring.

Let $\mathcal{G}$ be a graphing on the space $(X,\nu)$, and let $h:~X\to[l]$ be a Borel coloring. Let $\mu_{r,h,k}$ be the probability distribution on $U^{r,kl}$ obtained from $\nu$ by considering the $r$-neighborhood of a random element $x\in X$ and decorating its vertices by random independent elements from $[k]$ (in addition to the given $l$-coloring $h$). We say that a measurable coloring $c:~X\rightarrow[k]$ is $(r,\varepsilon)$-quasirandom if $d_{\rm var}(P_{\mathcal{G},r}[c\times h],\mu_{r,h,k})\leq\varepsilon$ where $c\times h$ denotes the $kl$-coloring with pairs of colors $(c(x),h(x))$.

It is easy to see that $\pi=(\pi_{1},\pi_{2},\dots)$ separates the points of $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$ with probability $1$ on $X^{n}$. Let $Y_{j}$ denote the set of points $(x_{1},x_{2},\dots,x_{n})$ in $X^{n}$ for which $\pi_{j}$ separates the points in $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$. Then $Y_{j}$ is an increasing chain of measurable sets such that $\nu(\cup_{i=1}^{\infty}Y_{i})=1$. This shows that for some index $j$, we have $\nu(Y_{j})>1-\varepsilon_{1}$ and completes the proof of Claim 1.

Let $x=(x_{1},\dots,x_{n})\in X^{n}$ and let $g$ be a $k$-coloring $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$. Let us say that $x$ is representative if the distribution of the $l$-colored neighborhood $N_{\mathcal{G},h,r}(x_{t})$ for a random $t\in[n]$ is $\varepsilon/6$-close to the distribution $\mu_{r,h}:=P_{\mathcal{G},r}[h]$. Let us say that $(x,g)$ is representative if the distribution of the $kl$-colored neighborhood $(N_{\mathcal{G},h,r}(x_{t}),g)$ is $\varepsilon/3$-close to the distribution $\mu_{r,h,k}$.

Let $x=(x_{1},\dots,x_{n})\in X^{n}$ be chosen randomly and independently from the distribution $\nu$. We note that with probability $1$, the neighborhoods $N_{\mathcal{G},r}(x_{i})$ are disjoint. If $n$ is large enough, then (just by the Law of Large Numbers)

Hence if $g$ is a uniform random $k$-coloring of $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$, and $n$ is large enough, then (by the Law of Large Numbers again), we have

Next, using Claim 1, we fix $j$ so that (for a random $x$) $\pi_{j}$ separates all the points in $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$ with probability at least $1-\varepsilon/3$. Whenever this happens, the restriction of $g_{j}\circ\pi_{j}$ to $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$ is a uniform random $k$-coloring. In other words, we can generate a uniform random $k$-coloring of $\cup_{i=1}^{n}N_{\mathcal{G},r}(x_{i})$ by restricting $g_{j}\circ\pi_{j}$ to it if $\pi_{j}$ separates it, and randomly $k$-coloring it otherwise. Thus

It follows that there is at least one $k$-coloring $g_{j}$ for which

Let us fix such a $g_{j}$. Then $c=g_{j}\circ\pi_{j}$ is an $(r,\varepsilon)$-quasirandom $k$-coloring of $X$. In fact, we can generate a random point of $x$ by first generating $n$ independent random points $x_{1},\dots,x_{n}$ and choosing one of them, $x_{t}$, uniformly at random. Then with probability at least $1-2\varepsilon/3$, $(x,g_{j}\circ\pi_{j})$ is representative, and whenever this happens, the distribution of the $kl$-colored neighborhood $(N_{\mathcal{G},h,r}(x_{t}),g_{j}\circ\pi_{j})$ is $\varepsilon/3$-close to the distribution $\mu_{r,h,k}$. It follows that the total variation distance of $(N_{\mathcal{G},h,r}(x_{t}),g_{j}\circ\pi_{j})$ from $\mu_{r,h,k}$, when $x_{t}$ is also randomly chosen, is at most $\varepsilon$.

For every $r\geq 1$ and $\varepsilon>0$, and every measurable $k$-coloring $c$ of $\mathcal{G}^{+}$, there are positive integers $s,m$ and $l$, a measurable $l$-coloring $h$ of $\mathcal{G}$, and a map $f:~U^{s,m}\times[l]\to[k]$ such that the $k$-coloring $c^{\prime}(x)=f\bigl(\xi_{s,m}(x),h(\phi(x))\big)$ of $\mathcal{G}^{+}$ satisfies

Let $(X^{+},\nu^{+})$ be the underlying space of $\mathcal{G}^{+}$. Let $\mathcal{K}$ denote the set of all subsets of $X^{+}$ of the form $\xi_{m,s}^{-1}(y)\cap\phi^{-1}(B)$, where $y\in U^{s,m}$, and $B$ is a Borel set of $X$. These sets generate the Borel sets of $X^{+}$, hence by the Monotone Class Theorem, the closure under pointwise convergence of the vector space generated by their indicator functions contains every bounded Borel function on $X^{+}$.

In particular, there are pairs of integers $(m_{i},s_{i})$, colored balls $y_{i}\in U^{s_{i},m_{i}}$, Borel sets $B_{i}\subseteq X$ and real coefficients $a_{i}$ $(i=1,\dots,N)$ such that

For a random point $x\in X^{+}$, the probability that the colorings $c$ and $c^{\prime}$ differ on any node in its $r$-neighborhood is less than $\varepsilon$. This implies the lemma.

Now we are able to prove the main theorem in this section.

Proof of Theorem 7.6. Our goal is to approximate every element in $Q_{\mathcal{G}^{+},r,k}$ by an element in $Q_{\mathcal{G},r,k}$ with arbitrary precision $\varepsilon>0$. In other words, we want to construct, for every measurable $k$-coloring $c$ of $\mathcal{G}^{+}$, a measurable $k$-coloring $c_{0}$ of $\mathcal{G}$ that defines a similar distribution of colored neighborhoods.

By Lemma 7.10 we may assume that $c$ is of the form $f\bigl(\xi_{s,m}(x),h(\phi(x))\big)$ where $h$ is an $l$-coloring of $\mathcal{G}$ and $f:~U^{s,m}\to[k]$. Let $q$ be an $(s,\varepsilon)$-quasirandom $m$-coloring of $(\mathcal{G},h)$ guaranteed by Lemma 7.9, and let $\mathcal{G}^{\prime}=(\mathcal{G},h\times q)$. Consider the $k$-coloring of $\mathcal{G}$ defined by $c_{0}(z)=f(N_{\mathcal{G}^{\prime},s}(z),h(z))$. We claim that $c_{0}$ has similar statistics as $c$: