On the limit of large girth graph sequences

Introduction

Let $\textrm{{Graph}}_{d}$ denote the set of all finite simple graphs $G$ (up to isomorphism) for which $\deg(x)\leq d$ for every $x\in V(G)$. For a graph $G$ and $x,y\in V(G)$ let $d_{G}(x,y)$ denote the distance of $x$ and $y$, that is the length of the shortest path from $x$ to $y$. A rooted $(r,d)$-ball is a graph $G\in\textrm{{Graph}}_{d}$ with a marked vertex $x\in V(G)$ called the root such that $d_{G}(x,y)\leq r$ for every $y\in V(G)$. By $U^{r,d}$ we shall denote the set of rooted $(r,d)$-balls.

If $G\in\textrm{{Graph}}_{d}$ is a graph and $x\in V(G)$ then $B_{r}(x)\in U^{r,d}$ shall denote the rooted $(r,d)$-ball around $x$ in $G$. For any $\alpha\in U^{r,d}$ and $G\in\textrm{{Graph}}_{d}$ we define the set $T(G,\alpha)\stackrel{{\scriptstyle\mbox{\scriptsize def}}}{{=}}\{x\in V(G):B_{r}(x)\cong\alpha\}$ and let $p_{G}(\alpha)\stackrel{{\scriptstyle\mbox{\scriptsize def}}}{{=}}\frac{|T(G,\alpha)|}{|V(G)|}$. A graph sequence $\textrm{{G}}=\{G_{n}\}_{n=1}^{\infty}\subset\textrm{{Graph}}_{d}$ is weakly convergent if $\lim_{n\to\infty}|V(G_{n})|=\infty$ and for every $r$ and every $\alpha\in U^{r,d}$ the limit $\lim_{n\to\infty}p_{G_{n}}(\alpha)$ exists (see ).

Let $\textrm{{Gr}}_{d}$ denote the set of all countable, connected rooted graphs $G$ for which $\deg(x)\leq d$ for every $x\in V(G)$. If $G,H\in\textrm{{Gr}}_{d}$ let $d_{g}(G,H)=2^{-r}$, where $r$ is the maximal number such that the $r$-balls around the roots of $G$ resp. $H$ are rooted isomorphic. The distance $d_{g}$ makes $\textrm{{Gr}}_{d}$ a compact metric space. Given an $\alpha\in U^{r,d}$ let $T(\textrm{{Gr}}_{d},\alpha)=\{(G,x)\in\textrm{{Gr}}_{d}:B_{r}(x)\cong\alpha\}$. The sets $T(\textrm{{Gr}}_{d},\alpha)$ are closed-open sets. A convergent graphs sequence $\{G_{n}\}^{\infty}_{n=1}$ define a local limit measure $\mu_{\bf G}$ on $\textrm{{Gr}}_{d}$, where $\mu_{\bf G}(T(\textrm{{Gr}}_{d},\alpha))=\lim_{n\to\infty}p_{G_{n}}(\alpha)$. However, not all the probability measures on $\textrm{{Gr}}_{d}$ arise as local limits. A necessary condition for a measure $\mu$ being a local limit is its involution invariance (see Section 2). The goal of this paper is to answer a question of Bollobás and Riordan (Question 6.8 ):

Any involution-invariant measure $\mu$ on $\textrm{{Gr}}_{d}$ concentrated on trees arises as a local limit of some convergent graph sequence.

As it was pointed out in such graph sequences are asymptotically treelike, thus $\mu$ must arise as the local limit of a convergent large girth sequence.

Involution invariance

Let $\vec{\textrm{{Gr}}_{d}}$ be the compact space of all connected countable rooted graphs $\vec{G}$ (up to isomorphism) of vertex degree bound $d$ with a distinguished directed edge pointing out from the root. Note that $\vec{G}$ and $\vec{H}$ are considered isomorphic if there exists a rooted isomorphism between them mapping distinguished edges into each other. Let $\vec{U}^{r,d}$ be the isomorphism classes of all rooted $(r,d)$-graphs $\vec{\alpha}$ with a distinguished edge $e(\vec{\alpha})$ pointing out from the root. Again, $T(\vec{\textrm{{Gr}}_{d}},\vec{\alpha})$ is well-defined for any $\vec{\alpha}\in\vec{U}^{r,d}$ and defines a closed-open set in $\vec{\textrm{{Gr}}_{d}}$. Clearly, the forgetting map $\mathcal{F}:\vec{\textrm{{Gr}}_{d}}\to\textrm{{Gr}}_{d}$ is continuous. Let $\mu$ be a probability measure on $\textrm{{Gr}}_{d}$. Then we define a measure $\vec{\mu}$ on $\vec{\textrm{{Gr}}_{d}}$ the following way.

Let $\vec{\alpha}\in\vec{U}^{r,d}$ and let $\mathcal{F}(\vec{\alpha})=\alpha\in U^{r,d}$ be the underlying rooted ball. Clearly, $\mathcal{F}(T(\vec{\textrm{{Gr}}_{d}},\vec{\alpha}))=T(\textrm{{Gr}}_{d},\alpha)$.Let

where $l$ is the number of edges $e$ pointing out from the root such that there exists a rooted automorphism of $\alpha$ mapping $e(\vec{\alpha})$ to $e$. Observe that

We define the map $T:\vec{\textrm{{Gr}}_{d}}\to\vec{\textrm{{Gr}}_{d}}$ as follows. Let $T(\vec{G})=\vec{H}$, where :

the underlying graphs of $\vec{G}$ and $\vec{H}$ are the same,

the root of $\vec{H}$ is the endpoint of $e(\vec{G})$,

the distinguished edge of $\vec{H}$ is pointing to the root of $\vec{G}$.

Note that $T$ is a continuous involution. Following Aldous and Steele , we call $\mu$ involution-invariant if $T_{*}(\vec{\mu})=\vec{\mu}$. It is important to note , that the limit measure of convergent graphs sequences are always involution-invariant.

We need to introduce the notion of edge-balls. Let $\vec{G}\in\vec{\textrm{{Gr}}_{d}}$. The edge-ball $B^{e}_{r}(\vec{G})$ of radius $r$ around the root of $\vec{G}$ is the following spanned rooted subgraph of $\vec{G}$:

The root of $B^{e}_{r}(\vec{G})$ is the same as the root of $\vec{G}$.

$y$ is a vertex of $B^{e}_{r}(\vec{G})$ if $d(x,y)\leq r$ or $d(x^{\prime},y)\leq r$, where $x$ is the root of $\vec{G}$ and $x^{\prime}$ is the endpoint of the directed edge $e(\vec{G})$.

The distinguished edge of $B^{e}_{r}(\vec{G})$ is $(\vec{x,x^{\prime}})$.

Let $\vec{E}^{r,d}$ be the set of all edge-balls of radius $r$ up to isomorphism. Then if $\vec{\phi}\in\vec{E}^{r,d}$, let $s(\vec{\phi})\in\vec{U}^{r,d}$ be the rooted ball around the root of $\vec{\phi}$. Also, let $t(\vec{\phi})\in\vec{U}^{r,d}$ be the $r$-ball around $x^{\prime}$ with distinguished edge $(\vec{x^{\prime},x})$.

The involution $T^{r,d}:\vec{E}^{r,d}\to\vec{E}^{r,d}$ is defined the obvious way and $t(T^{r,d}(\vec{\phi}))=s(\vec{\phi})$, $s(T^{r,d}(\vec{\phi}))=t(\vec{\phi})$. Since $\vec{\mu}$ is a measure we have

since $T(T(\vec{\textrm{{Gr}}_{d}},\vec{\phi}))=T(\vec{\textrm{{Gr}}_{d}},T^{r,d}(\vec{\phi})$. Therefore by (1),

Labeled graphs

Let $\vec{\textrm{{Gr}}_{d}^{n}}$ be the isomorphism classes of

connected countable rooted graphs with vertex degree bound $d$

with a distinguished edge pointing out from the root

with vertex labels from the set $\{1,2,\dots,n\}$.

Note that if $\vec{G}_{*}$ and $\vec{H}_{*}$ are such graphs then they called isomorphic if there exists a map $\rho:V(\vec{G}_{*})\to V(\vec{H}_{*})$ preserving both the underlying $\vec{\textrm{{Gr}}_{d}}$-structure and the the vertex labels. The labeled $r$-balls $\vec{U}^{r,d}_{n}$ and the labeled $r$-edge-balls $\vec{E}^{r,d}_{n}$ are defined accordingly. Again, $\vec{\textrm{{Gr}}_{d}^{n}}$ is a compact metric space and $T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\alpha}_{*})$, $T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\phi}_{*})$ are closed-open sets, where $\vec{\alpha}_{*}\in\vec{U}^{r,d}$, $\vec{\phi}_{*}\in\vec{E}^{r,d}_{n}$. Now let $\mu$ be an involution-invariant probability measure on $\textrm{{Gr}}_{d}$ with induced measure $\vec{\mu}$. The associated measure $\vec{\mu}_{n}$ on $\vec{\textrm{{Gr}}_{d}^{n}}$ is defined the following way.

Let $\vec{\alpha}\in\vec{U}^{r,d}$ and $\kappa_{1},\kappa_{2}$ be vertex labelings of $\vec{\alpha}$ by $\{1,2,\dots,n\}$. We say that $\kappa_{1}$ and $\kappa_{2}$ are equivalent if there exists a rooted automorphism of $\vec{\alpha}$ preserving the distinguished edge and mapping $\kappa_{1}$ to $\kappa_{2}$. Let $C(\kappa)$ be the equivalence class of the vertex labeling $\kappa$ of $\vec{\alpha}$. Then we define

$\vec{\mu}_{n}$ extends to a Borel-measure.

$\vec{\mu}(T(\vec{\textrm{{Gr}}_{d}},\vec{\alpha}))=\sum_{\vec{\alpha}_{*},\,\mathcal{F}(\vec{\alpha}_{*})=\vec{\alpha}}\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\alpha}_{*}))\,.$

Proof. The second equation follows directly from th definition. In order to prove that $\vec{\mu}_{n}$ extends to a Borel-measure it is enough to prove that

where $\vec{\alpha}_{*}\in\vec{U}^{r,d}_{n}$ and $N_{r+1}(\vec{\alpha}_{*})$ is the set of elements $\vec{\beta}_{*}$ in $\vec{U}^{r+1,d}_{n}$ such that the $r$-ball around the root of $\vec{\beta}_{*}$ is isomorphic to $\vec{\alpha}_{*}$. Let $\vec{\alpha}=\mathcal{F}(\vec{\alpha}_{*})\in\vec{U}^{r,d}$ and let $N_{r+1}(\vec{\alpha})\subset\vec{U}^{r,d}$ be the set of elements $\vec{\beta}$ such that the $r$-ball around the root of $\vec{\beta}$ is isomorphic to $\vec{\alpha}$. Clearly

Let $\kappa$ be a labeling of $\vec{\alpha}$ by $\{1,2,\dots,n\}$ representing $\vec{\alpha}_{*}$. For $\vec{\beta}\in N_{r+1}(\vec{\alpha})$ let $L(\vec{\beta})$ be the set of labelings of $\vec{\beta}$ that extends some labeling of $\vec{\alpha}$ that is equivalent to $\kappa$.

Observe that $|L(\vec{\beta})|=|C(\kappa)|n^{|V(\vec{\beta})|-V(\vec{\alpha})|}$. Hence

Therfore using equation (4) our lemma follows.

The following proposition shall be crucial in our construction.

For any $\vec{\alpha}_{*}\in\vec{U}^{r,d}_{n}$ and $\vec{\psi}_{*}\in\vec{E}^{r,d}_{n}$

$\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\alpha}_{*}))=\sum_{\vec{\phi}_{*}\in\vec{E}^{r,d}_{n},\,s(\vec{\phi}_{*})=\vec{\alpha}_{*}}\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\phi}_{*}))$

$\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\alpha}_{*}))=\sum_{\vec{\phi}_{*}\in\vec{E}^{r,d}_{n},\,t(\vec{\phi}_{*})=\vec{\alpha}_{*}}\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\phi}_{*}))$

$\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\psi}_{*}))=\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},T^{r,d}_{n}(\vec{\psi}_{*}))\,.$

Proof. The first equation follows from the fact that $\vec{\mu}_{n}$ is a Borel-measure. Thus the second equation will be an immediate corollary of the third one. So, let us turn to the third equation. Let $\mathcal{F}(\vec{\psi}_{*})=\vec{\psi}\in\vec{E}^{r,d}$ and let $\kappa$ be a vertex-labeling of $\vec{\psi}$ representing $\vec{\psi}_{*}$. It is enough to prove that

where $C(\kappa)$ is the set of labelings of $\vec{\psi}$ equivalent to $\kappa$. Let $N_{r+1}(\vec{\psi})\in\vec{U}^{r,d}$ be the set of elements $\vec{\beta}$ such that the edge-ball of radius $r$ around the root of $\vec{\beta}$ is isomorphic to $\vec{\psi}$. Then

where $k(\vec{\beta},\vec{\psi}_{*})$ is the number of labelings of $\vec{\beta}$ extending an element that is equivalent to $\kappa$. Notice that $k(\vec{\beta},\vec{\psi}_{*})=|C(\kappa)|n^{|V(\vec{\beta})|-|V(\vec{\psi})|}\,.$ Hence by (5) $\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},\vec{\psi}_{*}))=\frac{|C(\kappa)|}{n^{|V(\vec{\psi})|}}\vec{\mu}(T(\vec{\textrm{{Gr}}_{d}},\vec{\psi}))\,,$ thus our proposition follows.

Label-separated balls

Let $\textrm{{Gr}}_{d}^{n}$ be the isomorphism classes of

connected countable rooted graphs with vertex degree bound $d$

with vertex labels from the set $\{1,2,\dots,n\}$.

Again, we define the space of labeled $r$-balls $U^{r,d}_{n}$. Then $\textrm{{Gr}}_{d}^{n}$ is a compact space with closed-open sets $T(\textrm{{Gr}}_{d}^{n},M),M\in U^{r,d}_{n}$. Similarly to the previous section we define an associated probability measure $\mu_{n}$, where $\mu$ in an involution-invariant probability measure on $\textrm{{Gr}}_{d}$.

Let $M\in U^{r,d}_{n}$ and let $R(M)$ be the set of elements of $\vec{U}^{r,d}_{n}$ with underlying graph $M$. If $A\in R(M)$, then the multiplicity of $A$, $l_{A}$ is the number of edges $e$ pointing out from the root of $A$ such that there is a label-preserving rooted automorphism of $A$ moving the distinguished edge to $e$. Now let

The following lemma is the immediate consequence of Lemma 3.1.

$\mu_{n}$ is a Borel-measure on $\textrm{{Gr}}_{d}^{n}$ and $\sum_{M\in M(\alpha)}\mu_{n}(M)=\mu(A)$ if $\alpha\in U^{r,d}$ and $M(\alpha)$ is the set of labelings of $\alpha$ by $\{1,2,\dots,n\}$.

$M\in U^{r,d}_{n}$ is called label-separated if all the labels of $M$ are different.

For any $\alpha\in U^{r,d}$ and $\delta>0$ there exists an $n>0$ such that

where $T(n,\alpha)$ is the number of $\{1,2,\dots,n\}$-labelings of $\alpha$ with different labels. Clearly, $\frac{T(n,\alpha)}{n^{|V(\alpha)|}}\to 1$ as $n\to\infty$.

The proof of Theorem 1

Let $\mu$ be an involution-invariant probability measure on $\textrm{{Gr}}_{d}$ supported on trees. It is enough to prove that for any $r\geq 1$ and $\epsilon>0$ there exists a finite graph $G$ such that for any $\alpha\in U^{r,d}$

The idea we follow is close to the one used by Bowen in . First, let $n>0$ be a natural number such that

Then we define a directed labeled finite graph $H$ to encode some information on $\vec{\mu}_{n}$. If $A\in\vec{U}^{r+1,d}_{n}$ then let $L_{A}$ be the unique element of $\vec{E}^{r,d}_{n}$ contained in $A$.

The set of vertices of $H$; $V(H):=\vec{U}^{r+1,d}_{n}$. If $A,B\in\vec{U}^{r+1,d}_{n}$ and $L_{A}=L^{-1}_{B}$ (we use the inverse notation instead of writing out the involution operator) then there is a directed edge $(A,L_{A},B)$ from $A$ to $B$ labeled by $L_{A}$ and a directed edge $(B,L_{B},A)$ from $B$ to $A$ labeled by $L_{B}=L^{-1}_{A}$. Note that we might have loops. We define the weight function $w$ on $H$ by

$w(A)=\vec{\mu}_{n}(T(\vec{\textrm{{Gr}}_{d}^{n}},A))$.

$w(A,L_{A},B)=\mu(T(\vec{\textrm{{Gr}}_{d}^{n}},L_{A,B}))\,,$ where $L_{A,B}\in\vec{E}^{r+1,d}_{n}$ the unique element such that $s(L_{A,B})=A,t(L_{A,B})=B$.

By Proposition 3.1 we have the following equation for all $A,B$ that are connected in $H$:

where $l_{A}$ is the multiplicity of $w(A)$.

Since the equations (7), (8), (9) have rational coefficients we also have weight functions $w_{\delta}$ on $H$

such that $|w_{\delta}(A)-w(A)|<\delta$ for any $A\in V(H)$, where the exact value of $\delta$ will be given later.

Now let $N$ be a natural number such that

Step 1. We construct an edge-less graph $Q$ such that:

$V(Q)=\cup_{A\in V(H)}Q(A)$ (disjoint union)

each $Q(A)$ is partitioned into $\cup_{(A,L_{A},B)\in E(H)}Q(A,L_{A},B)$ such that $|Q(A,L_{A},B)|=Nw_{\delta}(A,L_{A},B)$.

Since $w_{\delta}$ satisfy our equations such $Q$ can be constructed.

Step 2. We add edges to $Q$ in order to obtain the graph $R$. For each pair $A,B$ that are connected in the graph $H$ form a bijection $Z_{A,B}:Q(A,L_{A},B)\to Q(B,L_{B},A)$. If there is a loop in $H$ consider a bijection $Z_{A,A}$. Then draw an edge between $x\in Q(A,L_{A},B)$ and $y\in Q(B,L_{B},A)$ if $Z_{A,B}(x)=y$.

Step 3. Now we construct our graph $G$. If $M\in U^{r+1,d}_{n}$ is a rooted labeled tree such that $\mu_{n}(M)\neq 0$ let $Q(M)=\cup_{A\in R(M)}Q(A)$. We partition $Q(M)$ into $\cup^{s_{M}}_{i=1}Q_{i}(M)$ such a way that each $Q_{i}(M)$ contains exactly $l_{A}$ elements from the set $Q(A)$. By the definition of $N$, we can make such partition.

The elements of $V(G)$ will be the sets $\{Q_{i}(M)\}_{M\in U^{r+1,d}_{n}\,,1\leq i\leq s_{M}}$. We draw one edge between $Q_{i}(M)$ and $Q_{j}(M^{\prime})$ if there exists $x\in Q_{i}(M),y\in Q_{j}(M^{\prime})$ such that $x$ and $y$ are connected in $R$. We label the vertex $Q_{i}(M)$ by the label of the root of $M$. Let $Q_{i}(M)$ be a vertex of $G$ such that $M$ is a label-separated tree. Note that if $M$ is not a rooted tree then $\mu_{n}(M)=0$. It is easy to see that the $r+1$-ball around $Q_{i}(M)$ in the graph $G$ is isomorphic to $M$ as rooted labeled balls. Also if $M$ is not label-separated then the $r+1$-ball around $Q_{i}(M)$ can not be a label-separated tree. Therefore

Also, if $M$ is a label-separated tree then

Thus by (6),(11),(13) if $\delta$ is choosen small enough then for any $\alpha\in U^{r+1,d}$

References