arXiv Analytics

Sign in

arXiv:1305.6784 [math.PR]AbstractReferencesReviewsResources

Ramanujan graphings and correlation decay in local algorithms

Agnes Backhausz, Balazs Szegedy, Balint Virag

Published 2013-05-29Version 1

Let $G$ be a large-girth $d$-regular graph and $\mu$ be a random process on the vertices of $G$ produced by a randomized local algorithm. We prove the upper bound $(k+1-2k/d)\Bigl(\frac{1}{\sqrt{d-1}}\Bigr)^k$ for the (absolute value of the) correlation of values on pairs of vertices of distance $k$ and show that this bound is optimal. The same results hold automatically for factor of i.i.d processes on the $d$-regular tree. In that case we give an explicit description for the (closure) of all possible correlation sequences. Our proof is based on the fact that the Bernoulli graphing of the infinite $d$-regular tree has spectral radius $2\sqrt{d-1}$. Graphings with this spectral gap are infinite analogues of finite Ramanujan graphs and they are interesting on their own right.

Related articles: Most relevant | Search more
arXiv:2306.11514 [math.PR] (Published 2023-06-20)
Sums of GUE matrices and concentration of hives from correlation decay of eigengaps
arXiv:2103.06847 [math.PR] (Published 2021-03-11)
A tale of two balloons
arXiv:0707.3509 [math.PR] (Published 2007-07-24)
Upper bound of loss probability in an OFDMA system with randomly located users