Ramanujan graphings and correlation decay in local algorithms

Introduction

Randomized local algorithms are special type of parallelized algorithms that can be used to produce various important structures in graphs (independent sets, dominating sets, matchings, colorings, local samples, etc.) in constant running time (see ,,, , , ,

Ramanujan and Bernoulli graphings

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 bounded maximal degree and Borel measurable edge set $E(\mathcal{G})\subset X\times X$ such that

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$.

A short calculation shows (see ) that $\mathcal{G}$ is a self-adjoint operator on $L^{2}(X)$ of norm at most $d$ where $d$ is the maximal degree in $\mathcal{G}$.

To keep our notation simple, in this paper we will only consider $d$-regular graphings (every vertex has degree $d$). In this case we say that $\mathcal{M}=\mathcal{G}/d$ is the Markov operator corresponding to $\mathcal{G}$. We have that for $f\in L^{2}(X)$ the value of $(\mathcal{M}^{k}f)(x)$ is equal to the expected value of $f$ at the end of a random walk of length $k$ started at $x$. Furthermore if $H\subseteq X$ is a positive measure set then

is the probability that a random walk of length $k$ started at a random point of $H$ ends in $H$.

Let $L^{2}_{0}(X)$ denote the subspace in $L^{2}(X)$ consisting of functions with integral equal to zero. If $\mathcal{G}$ is a $d$-regular graphing then the constant $1$ function is an eigenfunction of $\mathcal{G}$ with eigenvalue $d$ and so its orthogonal complement $L^{2}_{0}(X)$ is invariant under the action of $\mathcal{G}$. We denote the norm of $\mathcal{G}$ on $L^{2}_{0}(X)$ by $\rho(\mathcal{G})$. If $\rho(\mathcal{G})<d$ then we say that $\mathcal{G}$ has spectral gap. Note that the spectral gap is closely related to return probabilities and mixing rates of random walks on $\mathcal{G}$.

The graphing $\mathcal{G}$ is called ergodic if there is no measurable connected component $S\subset X$ of $\mathcal{G}$ such that $0<\nu(S)<1$. Graphings are typically not connected as abstract graphs so ergodicity is a good substitute for the notion of connectivity. It is easy to see that if a $d$-regular graphing $\mathcal{G}$ has spectral gap then it has to be ergodic. Furthermore, an ergodic graphing is either a finite connected graph or its probability space has no atoms.

The following statement on $\varrho(\mathcal{G})$ is a modification of well-known facts about finite graphs (see e.g. [7, Theorem 7.1.]) for graphings.

If $\mathcal{G}$ is an arbitrary $d$-regular graphing then

Let $\mathcal{G}$ be a $d$-regular graphing on an atomless probability space $(X,\nu)$. Then $\rho(\mathcal{G})\geq 2\sqrt{d-1}$.

Motivated by the previous theorem we will use the following definition.

A $d$-regular graphing $\mathcal{G}$ is Ramanujan if $\rho(\mathcal{G})\leq 2\sqrt{d-1}$.

It follows from Theorem 2.1 that a Ramanujan graphing $\mathcal{G}$ is either a finite Ramanujan graph or $\rho(\mathcal{G})=2\sqrt{d-1}$.

We continue with the definition of the Bernoulli graphing of the $d$-regular tree. Let $T_{d}$ denote the $d$-regular infinite tree and let $T_{d}^{*}$ denote the version of $T_{d}$ in which a special vertex $o$ called root is distinguished. The set $Y=^{T_{d}^{*}}$ is a probability space with the product measure. The group of root preserving automorphisms of $T_{d}^{*}$ is also acting on $Y$ by the permutation of the coordinates. This action is obviously measure preserving. We denote by $\Omega_{d}$ the space $Y/{\rm Aut}(T_{d}^{*})$ with the inherited probability measure $\nu_{d}$. We connect two elements in $\Omega_{d}$ by an edge if one can be obtained from the other by replacing the root to a neighboring vertex. The graph $B_{d}$ constructed this way is a $d$-regular graphing (see ) that is called the Bernoulli graphing of $T_{d}$. Note that with probability one the connected component of a random element in $\Omega_{d}$ is isomorphic to $T_{d}$.

The following theorem seems to have been known for a while (see or Theorem 2.1.) We include a simple proof for completeness.

For every $d\geq 2$ the Bernoulli graphing $B_{d}$ is Ramanujan.

To prove Theorem 2.1 and Theorem 2.2 we will need some preparation. The next lemma is an easy consequence of the spectral theorem.

Let $\mathcal{F}$ be a bounded, self-adjoint operator on the Hilbert space $\mathcal{H}$ and assume that $G$ spans $\mathcal{H}$. Then

Using this lemma we are ready to prove Lemma 2.2.

To verify the above calculation note that $\mathcal{M}$ is a self-adjoint operator and thus $(1_{X},\mathcal{M}^{k}1_{H})=(\mathcal{M}^{k}1_{X},1_{H})=(1_{X},1_{H})=\nu(H)$. The other inequality follows from Lemma 2.4 and the fact that functions of the form $g_{H}$ span the space $L^{2}_{0}(X)$. $\square$

The next lemma is well known from probability theory .

Let $S\subset T_{d}^{*}$ be a finite subset and let $r_{k}(S)$ denote the probability that a random walk started at the root ends in $S$. Then $\lim_{k\rightarrow\infty}r_{2k}(S)^{1/2k}=\frac{2\sqrt{d-1}}{d}$, if $S$ contains vertices at even distance from the root. Moreover, $\lim_{k\rightarrow\infty}r_{2k+1}(S)^{1/(2k+1)}=\frac{2\sqrt{d-1}}{d}$, if $S$ contains vertices at odd distance.

Proof of Theorem 2.1: Since $T_{d}$ covers every $d$-regular graph it is clear that for every positive measure set $H\subseteq X$ we have that $p_{k}(H)\geq r_{k}(o)$. The fact that $X$ is atomless implies that $\nu(H)$ can be arbitrary small in Lemma 2.2 and thus we obtain that $r_{k}(o)^{1/k}\leq\rho(\mathcal{G})/d$. By Lemma 2.5 this completes the proof. $\square$

Proof of Theorem 2.2: It follows from Theorem 2.1 that $\rho(B_{d})\geq 2\sqrt{d-1}$. Thus by Lemma 2.4 it remains to show that for some spanning set $G\subset L_{0}^{2}(\Omega_{d})$ the inequality $\limsup_{i\rightarrow\infty}|(v,B_{d}^{i}v)|^{1/i}\leq 2\sqrt{d-1}$ holds whenever $v\in G$. Let $G$ be the set of all functions with integral and norm $1$ on $\Omega_{d}$ that depend only on the labels in a bounded neighborhood of the root.

To prove the claim observe that $c_{k}$ is equal to the correlation of the values of $f$ at the two endpoints of a random walk of length $k$ started at a random point $x\in X$. Using the construction of $\Omega_{d}$ we lift the situation to the probability space $^{T_{d}^{*}}$. By abusing the notation we assume that $f$ is defined on $^{T_{d}^{*}}$ and it is invariant under ${\rm Aut}(T_{d}^{*})$. For an element $\omega\in^{T_{d}^{*}}$ and $v\in T_{d}^{*}$ let $g(v,\omega)$ denote the value of $f$ when the root is replaced to $v$. (The fact that $g(v,\omega)$ is well-defined relies on the fact that $f$ is invariant under ${\rm Aut}(T_{d}^{*})$.) The value of $c_{k}$ has the following description. We choose a random labeling $\omega$ of the vertices $T_{d}^{*}$ with $$, start a random walk of length$k$at the root of$T_{d}^{*}$and on this probability space we take the correlation between$g(o,\omega)$and$g(v,\omega)$where$v$is the endpoint of the walk. Conditioned on the fact that the random walk ends outside$S_{2r}$it is clear that$g(o,\omega)$and$g(v,\omega)$are independent and so the correlation is . It follows that the return probability to$S_{2r}$is an upper bound for$c_{k}$.$\square$

Let $h:\Omega_{d}\rightarrow\{-1,1\}$ be the function such that $h(\omega)=-1$ if the label on the root is in $[0,1/2]$ and $h(\omega)=1$ otherwise. Then the spectral measure of $h$ corresponding to $B_{d}$ is the Plancherel measure of $T_{d}$, i.e. it is concentrated on $[-2\sqrt{d-1},2\sqrt{d-1}]$, and its density is the following: $\frac{d}{2\pi}\frac{\sqrt{4(d-1)-t^{2}}}{d^{2}-t^{2}}$ (it is also called the Kesten–McKay measure, see e.g. ).

Proof. Let $\sigma_{h}^{\prime}$ be the spectral measure of $h$ corresponding to $B_{d}/d$. We use the proof of Theorem 2.2 for the specific function $h$. The argument yields that $(h,(B_{d}/d)^{k}h)$ is equal to the return probability of a random walk of length $k$ started at the root. On the other hand by (3) $(h,(B_{d}/d)^{k}h)$ is equal to the $k$-moment of $\sigma_{h}^{\prime}$. This completes the proof. $\square$

The set $\{\sigma_{f}|f\in L_{0}^{2}(\Omega)~{},~{}\|f\|_{2}=1\}$ corresponding to $B_{d}$ is dense in the set of all probability measures on $[-2\sqrt{d-1},2\sqrt{d-1}]$ with respect to the weak topology.

Proof. For the specific function $h$ defined in Lemma 2.6 we have that the support $\sigma_{h}$ is the full interval $[-2\sqrt{d-1},2\sqrt{d-1}]$. The existence of one such function (using the spectral theorem) implies the statement. Indeed, for small $\varepsilon$, the uniform measure on the interval $[x,x+\varepsilon]$ can be approximated by $\sigma_{Ph/h(x)}$, where $P$ is the spectral projection to the interval $[x,x+\varepsilon]$. $\square$

Random processes on the tree

In this section we describe how to produce random processes on the tree $T_{d}$ from graphings. Furthermore, the correlation decay of the process can be bounded by a function of the largest eigenvalue of the graphing.

the image of an edge in $T_{d}$ is an edge in $\mathcal{G}$,

$\phi$ is injective on the neighborhood of any vertex in $T_{d}$.

for every vertex $v\in V(T_{d})$ the distribution of the image of $v$ under a $\kappa$-random function is $\nu$,

$\kappa$ is invariant under the action of the automorphism group of $T_{d}$.

Proof. We can uniquely bulid up this probability measure in the following way. Let us start with an arbitrary fixed vertex $v$ of $T_{d}$. By the first requirement the image of $v$ has distribution $\nu$. Once the image of $v$ is determined, say $\phi(v)=x$, the remaining vertices of $T_{d}$ have to be mapped to the connected component of $x$. The second requirement guarantees that $\phi$ has to be a randomly chosen covering of this connected component. Note that the graphing axioms imply that the first requirement holds for every vertex of $T_{d}$. $\square$

where $k$ is the distance of $v$ and $w$.

The rest of the section is the proof of the above theorem. We imitate the proof from the paper in the infinite setting. The main idea is that the correlation decay in $\mu_{f}$ can be expressed in terms of non-backtracking random walks on $\mathcal{G}$.

We define a graphing $\mathcal{G}^{(k)}$ on $(X,\nu)$; two vertices are connected in $\mathcal{G}^{(k)}$ if and only if their distance is exactly $k$ in $\mathcal{G}$. More precisely, we need weighted graphings. That is, instead of subsets of $X\times X$, we label the edges with nonnegative integers in a Borel measurable way. These will be the multiplicities of the edges in the graphing. Otherwise the definition is the same as the original one. If $v,w\in T_{d}$ with distance $k$, and $f\in L^{2}_{0}(X)$ with $||f||_{2}=1$, then by the definition of $\mu_{f}$ the reader can easily check that

The arguments in the proof of Theorem 1.1. of are valid for $d$-regular graphings as well. Therefore for $k\geq 1$ we have

i.e., $U_{k}$ is the $k$th Chebyshev polynomial of the second kind for $k\geq 0$, and $U_{-1}\equiv 0$.

The spectral mapping theorem implies that if $\mathcal{F}:\mathcal{H}\rightarrow\mathcal{H}$ is a bounded self-adjoint operator on a Hilbert space $\mathcal{H}$, and $p$ is a polynomial, then $\|p(\mathcal{F})\|\leq\max_{x\in[-\|\mathcal{F}\|,\|\mathcal{F}\|]}|p(x)|$. Since $\mathcal{G}$ is a Ramanujan graphing, its norm on $L^{2}_{0}$ is $2\sqrt{d-1}$. Hence in our case this yields that

To see this let $T_{k}(\cos(\theta))=\cos(k\theta)$ be the defining equation for the $k$-th Chebyshev polynomial of the first kind. It is easy to see that

Both $|U_{k}|$ and $|T_{k}|$ have their maximal values at $1$ and $U_{k}(1)=k+1~{},~{}T_{k}(1)=1$. By substituting $1$ into $q_{k}$ we get the claim.

Randomized local algorithms

As it was described in the introduction, a randomized local algorithm produces a random labeling of the vertices of a bounded degree graph using an initial i.i.d labeling and a local rule denoted by $f$. To give a precise definition we will need the following notation.

A rule of radius $r$ and degree $d$ is a function $f:\mathcal{N}(r,d,S)\rightarrow S_{2}$ where $S_{2}$ is some set. Assume that $G$ is a graph of maximal degree at most $d$ and that $h:V(G)\rightarrow S$ is some labeling. Then we can use $f$ to produce a new labeling $h_{2}:V(G)\rightarrow S_{2}$ such that $h_{2}(v)$ is equal to the value of $f$ on the $S$-labeled rooted neighborhood of radius $r$ of $v$ where the root is placed on $v$. We denote the labeling $h_{2}$ by $h^{f}$.

A randomized local algorithm of radius $r$ and degree $d$ is given by a measurable function $f:\mathcal{N}(r,d,\Omega)\rightarrow L$ (called rule of the algorithm) where $\Omega$ is a probability space and $L$ is a measure space. The input of the algorithm is a graph of maximal degree at most $d$ and the output is the random labeling $h^{f}$ where $h$ is a labeling of $G$ with independent, random elements from $\Omega$.

Note that local algorithms can also be computed on infinite graphs if they have bounded maximum degree. The next example produces independent sets in graphs .

Let $f:\mathcal{N}(1,d,)\rightarrow\{0,1\}$ be the rule such that the value of $f$ is $1$ if and only if the label on the root is the smallest among all labels. It is clear that if $h:V(G)\rightarrow$ is an arbitrary injective function then the support of $h^{f}$ is an independent set in $G$. Since random labelings $h:V(G)\rightarrow$ are injective with probability $1$ we have that the local algorithm with rule $f$ produces a random independent set with probability $1$.

In the rest of this section we focus on the case when $G$ is a $d$-regular graph with girth more than twice the radius of $f$. In this case it is enough to define $f$ on $\Omega$-labeled versions of the neighborhood $S_{r}$ of the root in $T_{d}^{*}$ of radius $r$. In other words we can assume that $f$ is a function of the form $f:\Omega^{S_{r}}\rightarrow L$ that is invariant under the automorphisms of $S_{r}$.

We can also represent $f$ as a function $g:\Omega_{d}\rightarrow L$ on the vertex set of the Bernoulli graphing $B_{d}$. Let $\phi:\rightarrow\Omega$ be an arbitrary measure preserving map and $\psi:\Omega_{d}\rightarrow\Omega^{S_{r}}$ be the map defined by deleting the vertices outside $S_{r}$ and taking the $\phi$ images of the original labels. Let $g=f\circ\psi$. It is clear that the process $\mu_{g}$ on $T_{d}$ is the same as the process produced by the local algorithm on $T_{d}$ with rule $f$. On the other hand if $G$ is any $d$-regular graph of girth at least $2(k+r+1)$ then the distribution of the local algorithm in any ball of radius $k$ is the same as its distribution on $T_{d}$ in a similar ball. It follows for example that to analyze local properties (such as correlation decay) of local algorithms in the large-girth setting, it is enough to consider the algorithm on the tree $T_{d}$. This creates the connection between Bernoulli graphings and local algorithms. As a corollary of Theorem 3.1 and Theorem 2.2 we obtain the following.

Characterization of correlation sequences

Our goal is to give an algebraic characterization (up to closure with respect to pointwise convergence) for possible correlation sequences in factor of i.i.d processes. We return to the proof of Theorem 3.1. Let us apply (3) to $f$ and $\mathcal{G}/(2\sqrt{d-1})$ in the calculation. We obtain that the value of (4) for two vertices of distance $k$ is equal to

where $\sigma_{f}$ is the spectral measure of $f$ with respect to $\mathcal{G}/(2\sqrt{d-1})$. The next theorem follows immediately from Corollary 2.7.

Let $X_{d}$ denote the set of all sequences with $x_{k}=\int d^{-1/2}(d-1)^{(1-k)/2}q_{k}~{}d\eta$ where $\eta$ is a probability measure on $$. Then the closure of possible correlation sequences in factor of i.i.d processes is equal to$X_{d}$.

We finish with an example for a local algorithm on the tree $T_{d}$. We start with the intitial i.i.d labeling $\{X_{u}\}_{u\in T_{d}}$ where $X_{u}=1$ with probability $1/2$ and $X_{u}=-1$ otherwise. For $r\geq 0$ denote by $S_{r}(v)$ the neighborhood of radius $r$ around $v\in T_{d}$. Note that

For every $w\in T_{d}$ we define the random variable $Y_{w}=\frac{1}{\sqrt{|S_{r}(w)|}}\sum_{u\in S_{r}(w)}X_{u}$. It is clear that $\{Y_{w}\}_{w\in T_{d}}$ is the output of a local algorithm. Furthermore we have that

if $k$ is even and $k<2r$. For the last equation we use the fact that $S_{r}(v)\cap S_{r}(w)$ is equal to $S_{r-{k/2}}(z)$ where $z$ is the middle point of of the path connecting $v$ and $w$. Now, as $r$ goes to infinity, the lower bound for the correlation converges to $(d-1)^{-k/2}$.

For odd $k$ with $k\leq 2r+1$ we have two points in the middle and so

This converges to $\frac{2}{d}(d-1)^{-\frac{k-1}{2}}$ as $r\rightarrow\infty$.

This shows that the correlation decay is close to be optimal in this simple example.

Semi-definite functions, spherical representations and Gaussian processes

The goal of this section is to show how correlation sequences of invariant processes on $T_{d}$ can be viewed from a representation theoretic perspective. Moreover, every such correlation sequence produces a unique invariant Gaussian process on $T_{d}$ which is interesting on its own right.

Let $\mathcal{P}_{d}$ denote the set of all positive semi-definite functions $p:T_{d}\times T_{d}\rightarrow$ such that $p(v,v)=1$ and the value of $p(v,w)$ depends only on the distance of $v$ and $w$ for every pair $v,w\in T_{d}$. It is clear that the correlation structure of an arbitrary (real valued) invariant process on $T_{d}$ is an element in $\mathcal{P}_{d}$. On the other hand any element of $\mathcal{P}_{d}$ defines a symmetric representation of $T_{d}$ in some real Hilbert space. To be more precise, there is a function $\phi$ from $T_{d}$ to some separable Hilbert space $\mathcal{H}$ such that $p(v,w)=(\phi(v),\phi(w))$ and that $\{\phi(v)|v\in T_{d}\}$ generates $\mathcal{H}$. It is clear that $\phi$ is unique up to orthogonal transformations and that there is an orthogonal representation $\psi:{\rm Aut}(T_{d})\rightarrow O(\mathcal{H})$ with the property that $\phi(\alpha(v))=\psi(\alpha)(\phi(v))$ for every $v\in T_{d}$ and $\alpha\in{\rm Aut}(T_{d})$. In particular $\phi(o)$ is fixed under ${\rm Aut}(T_{d}^{*})$ where $o$ is any distinguished root in $T_{d}$. Such representations of ${\rm Aut}(T_{d})$ are called spherical in the literature. In other words, a representation of ${\rm Aut}(T_{d})$ is spherical if the subgroup ${\rm Aut}(T_{d}^{*})$ has a fixed vector $x$ of length $1$ such that the images of $x$ under ${\rm Aut}(T_{d})$ generate the underlying Hilbert space. It is clear that each spherical representation $\psi$ of ${\rm Aut}(T_{d})$ gives rise to an element in $\mathcal{P}_{d}$ by $p(v,w)=(\psi(\alpha_{v})(x),\psi(\alpha_{w})(x))$ where $\alpha_{v}(o)=v,\alpha_{w}(o)=w$. (The spherical property guarantees that $p$ is well-defined.) This construction yields a one to one correspondence between spherical representations and elements in $\mathcal{P}_{d}$.

A Gaussian process is a limit of factor of i.i.d. processes if and only if its correlation decay is as in Theorem 5.1.

References