Heat kernels are not uniform expanders
An infinite expander is a graph \(\mathcal{G}\) such that the family of all metric balls in \(\mathcal{G}\) forms a family of expanders. It is an unpublished conjecture of I. Benjamini that such a graph does not exist. The authors of this paper study a random walk analogue of this problem, and they prove that indeed a ``random walk infinite expander does not exist.\N\NTo be precise, let \((\mathcal{G}, o)\) be a rooted graph and let \(\mu_o^n\) be the probability distribution of the \(n\)-th step of the simple random walk starting at \(o\).\NThe authors define the heat kernel on \((\mathcal{G}, o)\) to be \(h\)-expanding for some \(h>0\) if for every \(n\in\mathbb N\) and every \(A \subset \mathcal{G}\) with \(\mu_o^n (A)\leq\frac 1 2\), we have\N\[\N\mu_o^n (\partial A)\geq h \mu_o^n (A),\N\]\Nwhere \(\partial A\) is the set of vertices in \(A\) that are adjacent to the complement of \(A\).\NThe heat kernels on an (unrooted) graph \(\mathcal{G}\) are expanding if there exists \(h > 0\) such that for any choice of root \(o \in\mathcal{G}\), the heat kernel on \((\mathcal{G}, o)\) is \(h\)-expanding.\NThe main result of this paper (Theorem 1.4) states that if \(\mathcal{G}\) is an infinite, connected, bounded-degree graph, then the heat kernel of \(\mathcal{G}\) is not expanding.\N\NThis can be proved fairly easily if \(\mathcal{G}\) is the Cayley graph of a group \(G\) (Theorem 2.4): the idea is to leverage the fact that the group action on the Poisson boundary \(P\) of \(\mathcal{G}\) is amenable in the sense of \textit{R. J. Zimmer} [J. Funct. Anal. 27, 350--372 (1978; Zbl 0391.28011)]. This implies that in \(P\) there is an abundance of almost-invariant subsets \(S_n\). These sets can then be used to construct sets \(A_n\subset G\) that are ``almost invariant for the heat kernel. Namely, for almost every \(p\in P\), letting\N\[\NA_n:= \{\gamma\in G\mid \gamma p\in S_n\}\N\]\Ndoes the job.\N\NThe general case is much more involved. Broadly speaking, the idea is to first prove an analogous result for stationary random graphs and then deduce the main theorem via a compactness argument.\N\NA stationary random graph is a probability measure on the space of (isomorphism classes of) rooted graphs that is invariant under changing the (randomly sampled) root by taking one step of the simple random walk.\NConsidering this randomized setup has a somewhat regularizing effect. Specifically, the authors can then rely on rather refined results on Borel equivalence relations and their graphings. Most importantly, they use the theorem on amenable equivalence relations of \textit{A. Connes} et al. [Ergodic Theory Dyn. Syst. 1, 431--450 (1981; Zbl 0491.28018)] and \textit{V. A. Kaimanovich}'s construction of a Poisson boundary for stationary graphings [Isr. J. Math. 149, 45--85 (2005; Zbl 1080.43003)].\N\NCarefully putting all the pieces together, the authors prove that if \((\mathcal{G},o)\) is an infinite stationary random graph of bounded degree, then the heat kernel of \((\mathcal{G},o)\) is almost surely non-expanding (Theorem 1.8). An important intermediate step uses ``stationary hyperfiniteness: namely, they show that every stationary random graph of bounded degree is stationary hyperfinite.\N\NThe paper is quite concisely written. Many of the key ideas are explained in a self-contained manner, but it also relies on several previous structural results. A non-specialist will probably find the paper fairly challenging.
- Amenability and the Liouville property
- Amenable ergodic group actions and an application to Poisson boundaries of random walks
- Amenable versus hyperfinite Borel equivalence relations
- An amenable equivalence relation is generated by a single transformation
- Asymptotically Invariant Sequences and Approximate Finiteness
- Ergodic theory on stationary random graphs
- Euclidean vs. Graph Metric
- Expanders are not hyperbolic
- scientific article; zbMATH DE number 3911340 (Why is no real title available?)
- scientific article; zbMATH DE number 3487716 (Why is no real title available?)
- scientific article; zbMATH DE number 5057460 (Why is no real title available?)
- Kesten's theorem for invariant random subgroups.
- Large networks and graph limits
- Point realizations of transformation groups
- Processes on unimodular random networks
- Random walk in random groups.
- Selected works of Oded Schramm. In 2 volumes. Edited by Itai Benjamini and Olle Häggström
- The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space
- The combinatoral cost
- The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set
- Trees and amenable equivalence relations
- Up to a double cover, every regular connected graph is isomorphic to a Schreier graph
- What is property A?
This page was built for publication: Heat kernels are not uniform expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7011028)
