%~Mouliné par MaN_auto v.0.32.0 2024-06-17 10:01:00 \documentclass[AHL,Unicode,longabstracts,published]{cedram} \usepackage{graphicx} \usepackage[all]{xy} \usepackage{dsfont} \usepackage{amssymb} \usepackage{mathrsfs} %\usepackage{enumerate} %\usepackage{url} \usepackage{fancyhdr} \usepackage{ifthen} \usepackage{srcltx} \usepackage{comment} \DeclareMathOperator{\Path}{Path} \DeclareMathOperator{\supp}{supp} %\newcommand{\bbC}{\ensuremath{\mathbb{C}}} \newcommand{\bbR}{\mathbb{R}} \newcommand{\bbZ}{\mathbb{Z}} \newcommand{\bbT}{\mathbb{T}} \newcommand{\bbN}{\mathbb{N}} \newcommand{\bbE}{\mathbb{E}} \newcommand{\bbP}{\mathbb{P}} \newcommand{\bbone}{\mathds{1}} \newcommand{\calR}{\mathcal{R}} \newcommand{\calA}{\mathcal{A}} \newcommand{\calH}{\mathcal{H}} \newcommand{\calM}{\mathcal{M}} \newcommand{\calE}{\mathcal{E}} \newcommand{\calF}{\mathcal{F}} \newcommand{\calB}{\mathcal{B}} \newcommand{\calG}{\mathcal{G}} \newcommand{\scH}{\mathscr{H}} \newcommand{\Isom}{\mathrm{Isom}} \newcommand{\backsslash}{\mathbin{\mkern-2mu \char`\\ \mkern-6mu \char`\\ \mkern-4mu}} %\newcommand*\Circlearrowleft{\ensuremath{\rotatebox[origin=c]{90}{$\circlearrowleft$}}} %\newcommand*\Circlearrowright{\ensuremath{\rotatebox[origin=c]{90}{$\circlearrowright$}}} %\newcommand*\llpar{\ensuremath{ (\!(}} %\newcommand*\rrpar{\ensuremath{)\!) }} %\setcounter{tocdepth}{1} %\numberwithin{equation}{section} \sloppy %\newcommand{\showcomments}{yes} \newsavebox{\commentbox} %\newenvironment{mycomment} {\ifthenelse{\equal{\showcomments}{yes}} {\footnotemark\begin{lrbox}{\commentbox}\begin{minipage}[t]{1.25in}\raggedright\sffamily\tiny\footnotemark[\arabic{footnote}]} {\begin{lrbox}{\commentbox}}}{\ifthenelse{\equal{\showcomments}{yes}} {\end{minipage}\end{lrbox}\marginpar{\usebox{\commentbox}}} {\end{lrbox}}} %\AtBeginDocument{ %\newtheorem{myname}[cdrthm]{My beautiful theorem} } \newcounter{casecount} \newenvironment{case}[1]{\refstepcounter{casecount}\begin{proof}[Case~\thecasecount.\;{#1}]}{\let\qed\relax\end{proof}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} %\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} \let\oldtilde\tilde \renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[Heat kernels are not uniform expanders]{Heat kernels are not uniform expanders} \alttitle{Les noyaux de la chaleur ne forment pas une famille d'expanseurs} \subjclass{53C28, 53C26, 32Q45} \keywords{Stationary random graphs, random walks, expander graphs} \author[\initial{M.} \lastname{Fr\k{a}czyk}]{\firstname{Mikołaj} \lastname{Fr\k{a}czyk}} \address{Faculty of Mathematics\\ and Computer Science,\\ Jagiellonian University,\\ ul. ${\L}$ojasiewicza 6,\\ 30-348 Kraków, Poland} \email{mikolaj.fraczyk@uj.edu.pl} \thanks{MF was supported by ERC Consolidator Grant 648017 and partially supported by the Dioscuri programme initiated by the Max Planck Society, jointly managed with the National Science Centre in Poland, and mutually funded by the Polish Ministry of Education and Science and the German Federal Ministry of Education and Research. WvL is supported by NSF DMS-1855371 and an AMS-Simons Travel Grant.} \author[\initial{W.} \lastname{van Limbeek}]{\firstname{Wouter} \lastname{van Limbeek}} \address{Department of Mathematics,\\ Statistics, and Computer Science,\\ University of Illinois\\ at Chicago, Chicago,\\ IL 60607, USA} \email{wouter@uic.edu} \begin{abstract} We study infinite analogues of expander graphs, namely graphs whose subgraphs weighted by heat kernels form an expander family. Our main result is that there does not exist any infinite expander in this sense. This proves the analogue for random walks of Benjamini's conjecture that there is no infinite graph whose metric balls are uniformly expanders. The proof relies on a study of stationary random graphs, in particular proving non-expansion of heat kernels in that setting. A key result is that any stationary random graph is stationary hyperfinite, which is a new property of independent interest. \end{abstract} \begin{altabstract} Notre résultat principal est qu'il n'existe aucun graphe infini dont l'ensemble des sous-graphes pondérés par des noyaux de la chaleur forment une famille d'expanseurs. Cela prouve une analogue, pour les marches aléatoires, de la conjecture de Benjamini selon laquelle il n'existe pas de graphe infini dont les boules métriques sont une famille d'expanseurs. La démonstration repose sur l'étude de graphes aléatoires stationnaires, en particulier la démonstration de la non-expansion des noyaux de la chaleur dans ce cadre. Un résultat clé est que tout graphe aléatoire stationnaire est stationnaire hyperfini, ce qui est une notion nouvelle, d'un intérêt indépendant. \end{altabstract} \datereceived{2022-02-14} \daterevised{2023-05-18} \dateaccepted{2024-01-04} \editors{S. Gou\"ezel and I. Benjamini} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dateposted{2025-02-07} \begin{document} \maketitle \section{Introduction}\label{sec:intro} A sequence of finite graphs $(\calG_n)_n$ of uniformly bounded degrees is an \emph{expander} sequence if $|\calG_n|\to\infty$ and there exists $\varepsilon>0$ such that every $A\subset \calG_n$ with $|A|\leq |\calG_n|/2$ satisfies $|\partial A|\geq \varepsilon |A|$.\footnote{Here $\partial$ denotes the inner vertex boundary.} Expander graphs are therefore sparse robust networks, which makes them of great utility in applications. One therefore wonders whether instead of a sequence, there is a single infinite graph that is sparse yet robust? More precisely, Benjamini defined an infinite, connected, bounded degree graph $\calG$ to be an \emph{expander at all scales} if there exists $\varepsilon>0$ such that every ball $B\subset \calG$ and subset $A\subset \calG$ with $|A\cap B|\leq |B|/2$ satisfy $|\partial A\cap B|\geq \varepsilon |A\cap B|$, and conjectured: \begin{conj}[{Benjamini~\cite{BenjaminiConj}}]\label{conj:benjamini} Expanders at all scales do not exist. \end{conj} See also~\cite{Benjamini1998} for an earlier statement for Cayley graphs and~\cite{BenjaminiErdos} for a variant for families of finite graphs. Explicit expander graphs were first constructed as finite quotients of Cayley graphs of groups $\Gamma$ with Property (T) (or $(\tau)$) by Margulis~\cite{margulis_expander}. In this case, the Cayley graph of $\Gamma$ is the pointed Gromov--Hausdorff limit of expander graphs, but nevertheless sometimes (and conjecturally, always) is not an expander at all scales (it can even be a tree). Since expander graphs do not admit coarse embeddings into Hilbert spaces (Gromov~\cite{gromov2003random}), any graph that can be coarsely embedded into Hilbert space is not an expander at all scales. In particular, graphs with \emph{metric property A} (see~\cite{NowakAMM}) are never expanders at all scales (\cite{Yu00}). Property A holds for Cayley graphs of \emph{exact groups} (Ozawa~\cite{OzawaICM}), which includes e.g. linear groups and hyperbolic groups. Without homogeneity of the underlying graphs, much less is known: Even if one tries to construct the graph in an algebraic manner, say as a Schreier graph. Indeed, up to double cover, any connected regular graph can be realized up to double cover as a Schreier graph~\cite{Leemann22}. Our main purpose is to study the analogue of Conjecture~\ref{conj:benjamini} that replaces metric balls by distributions of random walks to measure robustness. Let $\calG$ be a connected rooted graph of bounded degree with a vertex $x$. We will write $\mu^n_x$ for the distribution of the $n^{\rm th}$ step of the simple random walk starting at $x$ (i.e. the heat kernel). \begin{defi}\label{dfn:expanding_walks} Let $h>0$. We say the heat kernel on a rooted graph $(\calG,o)$ is $h$\emph{-expanding} if for every $n$ and $A\subset \calG$ with $\mu^n_o(A)\leq \frac{1}{2}$, we have \begin{equation}\label{eq:expansion} \mu^n_o(\partial A)\geq h \, \mu^n_o(A). \end{equation} We say that the heat kernel on a rooted graph $(\calG,o)$ is \emph{expanding} if there exists $h>0$ such that it is $h$-expanding. Similarly we say that the heat kernels on an (unrooted) graph $\calG$ are expanding if there exists $h>0$ such that for any choice of root $o\in \calG$ the heat kernel on $(\calG,o)$ is $h$-expanding. \end{defi} \begin{rema}\label{rmk:walks_vs_benjamini} Expansion of the heat kernel is analogous to expanding at all scales: For a bounded degree graph $\calG$, consider the family of measures $\mu_{p,r}$ (for $p\in \calG$ and $r>0$) given by the uniform distribution on the ball $B(p;r)$. Then $\calG$ is an expander at all scales precisely when there exists $h>0$ such that for every $p\in \calG$, $r>0$ and $A\subset \calG$ with $\mu_{p,r}(A)\leq \frac{1}{2}$, we have \[ \mu_{p,r}(\partial A)\geq h \, \mu_{p,r}(A). \] \end{rema} Our main result is the heat kernel analogue of Conjecture~\ref{conj:benjamini}: \begin{theo}\label{thm:main} Let $\calG$ be an infinite, connected, bounded degree graph. Then the heat kernel on $\calG$ is not expanding. \end{theo} This leads to the following interesting question. Let $\scH(n,d)$ be the supremum of the expansion constants of heat kernels up to time $n$ on all infinite connected graphs of degree at most $d$. Note that $0\leq \scH(n,d)\leq 1$, and $\scH(n,d)$ is decreasing as a function of $n$. By a simple diagonal argument applied to graphs maximizing $\scH(n,d)$, Theorem~\ref{thm:main} applied to the limiting graph implies that $\scH(n,d)\to 0$ as $n\to\infty$. \begin{ques} What is the rate of decay of $\scH(n,d)$ as $n\to\infty$? \end{ques} We do not know whether the analogue of Theorem~\ref{thm:main} holds for rooted graphs, especially since the rooted version of Benjamini's conjecture is false: \begin{exam}[A rooted expander at all scales]\label{ex:rooted_expansion} Fix a prime $p$ and an expander family of $p$-congruence quotients $\{G_k\}_k$ of a finitely generated linear group $\Gamma$. Let $\calG$ be the graph with vertex set $\sqcup_k G_k$ and edges given by those in $\{G_k\}_k$ as well as an edge between $x\in G_k$ and its image in $G_{k-1}$. Using that a definite proportion of the points of $\cup_{k\,\leq\,n} G_k$ is contained in $G_n$, it is not hard to see that the family of metric balls centered at a fixed vertex $o\in\calG$ are expanding. See Section~\ref{sec:rooted-expander} for a proof. \end{exam} In the above example, the probability that the $k^{\rm th}$ step of the random walk on $(\calG, o)$ lies in $G_n$ tends to 0 as $k\to\infty$, uniformly in $n$, so the subsets $\cup_{k\,\leq\,n} G_k$ have small boundary as measured by the heat kernel, which proves its non-expansion. So we pose the following: \begin{ques} Does there exist a bounded degree rooted graph $(\calG, o)$ with expanding heat kernel? \end{ques} Since we do not know how to establish non-expansion of the heat kernel for any given root, a key idea in the proof of Theorem~\ref{thm:main} is to sample the root randomly on $\calG$. This leads us to study random walks on random graphs. \subsection*{Stationary random graphs} \label{sec:stat_intro} First defined and studied by Benjamini--Curien~\cite{BenCur}, a \emph{stationary random graph} is a random rooted graph whose distribution is invariant under re-rooting at a uniformly random neighbor of the root (see Section~\ref{sec:stationary} for details). We establish non-expansion of heat kernels on stationary random graphs: \begin{theo}\label{thm:mainSt} Let $(\calG,o)$ be an infinite stationary random graph of bounded degree. Then the heat kernel on $(\calG,o)$ is non-expanding almost surely. \end{theo} The proof relies on a number of results on the general structure of stationary random graphs that could be of independent interest: First, we establish a connection with the theory of measured equivalence relations. Indeed, given a measured equivalence relation, any graphing of it yields a random graph and in fact any stationary random graph is obtained in this way (see Section~\ref{sec:stat_graphing} for details). This allows us to use \emph{Poisson boundaries} for stationary random graphs and their amenability. The construction of these boundaries is originally due to Kaimanovich in the even more general setting of invariant Markov operators on measured groupoids~\cite{Kai05}. Using the equivalence of amenability and \emph{hyperfiniteness} for non-singular equivalence relations, we deduce that any stationary random graph is stationary hyperfinite (see Definition~\ref{dfn:StationaryHyperfinite} and Corollary~\ref{cor:SRGareHyperfinite}). Note this is in sharp contrast with the behavior of unimodular random graphs, introduced in~\cite{ALR2007}, where hyperfiniteness often fails, e.g. for trees (see Example~\ref{ex:hyperfinite_tree}). Stationary hyperfiniteness of stationary random graphs is the key ingredient in the proof of Theorem~\ref{thm:mainSt}. In fact, we prove a stronger statement about hyperfiniteness of certain sequences of weighted graphs. The notion of hyperfiniteness for families $(\calG_i)_i$ of finite graphs was introduced by Elek in~\cite{Elek2006}. Informally, this means that each $\calG_i$ can be cut into uniformly bounded pieces with small boundaries by removing an arbitrarily small proportion of vertices. Hyperfiniteness is strictly stronger than non-expansion and in many ways is the correct analogue of amenability in the graph setting. The strengthened version of Conjecture~\ref{conj:benjamini} asserts that any bounded degree graph contains a sequence of balls that is hyperfinite. Hyperfiniteness can be similarly defined for sequences of weighted graphs (see~\cite{ElekTimar}). Our Corollary~\ref{cor:SRGareHyperfinite} can then be rephrased as follows: for any stationary random graph $(\calG,o)$, the sequence of graphs $(\calG,o)$ weighted by $\mu_o^n$ is hyperfinite. To deduce Theorem~\ref{thm:mainSt}, we use hyperfiniteness of the sequence to show that with large probability, one has a partition into finite pieces with small boundary. From these partitions we assemble large sets with small boundary that witness non-expansion of the heat kernels. \subsection{Outline of the paper} We start by recalling the construction of the Poisson boundary of a group, which enables us to prove Main Theorem~\ref{thm:main} in the special case of Cayley graphs (Section~\ref{sec:poisson}). Next, we discuss stationary random graphs and graphings (Section~\ref{sec:stationary}). In Section~\ref{sec:poissonSRG} we use the amenability of Poisson boundaries of stationary random graphs to deduce that any stationary random graph is stationary hyperfinite. Finally, in Section~\ref{sec:main_proof}, we prove our main theorems, first for stationary random graphs (Theorem~\ref{thm:mainSt}) and then for bounded degree graphs (Theorem~\ref{thm:main}). \subsection*{Acknowledgments} The authors thank Gabor Elek for explaining the connection between the main theorem and Property A. We thank Alex Furman for helpful conversations on amenability of Poisson boundaries. We thank Miklos Abert and Itai Benjamini for valuable comments on an earlier version of this paper. We thank two anonymous referees for many helpful comments. We thank the University of Illinois at Chicago for providing support for a visit by MF. \section{Amenability, Poisson boundaries and random walks on groups} \label{sec:poisson} \subsection{Zimmer amenability of non-singular equivalence relations}\label{sec:zimmer-amenability} Zimmer~\cite{Zimmer78} originally defined amenability for non-singular group actions. We present his definition adopted to the context of \emph{non-singular countable measured equivalence relations} (see~\cite{Adams90} and~\cite{ConnesFeldmanWeiss}). Such a relation consists of a $(X,\nu,\calR)$ where $(X,\nu)$ is a $\sigma$-finite measure space and $\calR$ is a measurable subset of $X\times X$ which is an equivalence relation and for almost every $x\in X$ the class $[x]_\calR$ is countable. The non-singularity of the relation is expressed by the condition that every measurable bijective map $\phi\colon X\to X$ such that $(x,\phi(x))\in \calR$ for almost every $x\in X$ is measure class preserving. We endow $\calR$ with a measure $\nu_{\calR}$ by integrating the counting measure on the fibers of the projection onto the first coordinate. Alternatively, if we integrate along the second coordinate, the resulting measure is of the same class. Zimmer's amenability is a fixed point condition in compact convex invariant sets for isometric actions on Banach spaces: Let $E$ be a separable Banach space and let $\Isom(E)$ be the group of isometries equipped with the strong operator topology. Let $(X,\nu,\calR)$ be countable non-singular equivalence relation. A map $\alpha\colon\calR\to \Isom(E)$ is a measurable cocycle if it is measurable, $\alpha(x,x)=1$ and $\alpha(z,y)\alpha(y,x)=\alpha(z,x)$ for almost every $x\in X$ and every $y,z\in [x]_\calR$ (equivalently for $\nu_{\calR}$-almost every $(x,y),(y,z)\in \calR$). Any cocycle $\alpha\colon \calR\to \Isom(E)$ induces a dual cocycle $\alpha^*\colon \calR\to \Isom(E^*)$ given by $\alpha^*(y,x)(\varphi)(v)=\varphi(\alpha(x,y)v)$ for $v\in E.$ A Borel field of compact convex sets $\{\calA_x\}_{x\,\in\,X}$ of $E^*$ is called $\alpha^*$-invariant if $\alpha^*(y,x)\calA_x=\calA_y$ for $\nu_\calR$-almost every pair $(x,y)\in\calR$. We say that $(X,\nu,\calR)$ is \emph{amenable} if for every separable Banach space $E$, measurable cocycle $\alpha\colon \calR\to \Isom(E)$, and invariant Borel field $\{\calA_x\}_{x\,\in\,X}$ of $E^*$ as above, there exists an invariant Borel section, i.e. an invariant Borel map $\varphi\colon X\to E^*$ such that $\varphi(x)\in \calA_x$ for almost every $x\in X$ and $\alpha^*(y,x)\varphi(x)=\varphi(y)$ for $\nu_{\calR}$-almost every $(x,y)\in\calR$. Similarly, we say that a measure-class preserving action of a countable group $G$ on $(X,\nu)$ is amenable if for any $E$, Borel field $\{\calA_x\}_{x\,\in\,X}$ of $E^*$ as above and any measurable cocycle $\alpha\colon G\times X \to \Isom(E)$, there exists a $G$-invariant measurable section $\varphi\colon X\to E^*$, i.e. $\varphi$ satisfies $\varphi(x)\in \calA_x$ for almost every $x\in X$ and $\alpha(g,x)\varphi(x)=\varphi(gx) $ for $\nu$-almost every $x\in X$ and every $g\in G$. When the action of $G$ is essentially free the amenability of the group action and the orbit equivalence relation are equivalent. The amenability of a non-singular equivalence relation can be related to the notion of hyperfiniteness. A non-singular countable measured equivalence relation $(X,\nu,\calR)$ is \emph{hyperfinite} if there exists a sequence of finite equivalence relations $E_n\subset \calR$ such that $\calR=\bigcup_{n\,\in\,\bbN}E_n.$ \begin{theo}[{Connes--Feldman--Weiss~\cite{ConnesFeldmanWeiss}}]\label{thm:CFW} A non-singular countable measured equivalence relation is amenable if and only if it is hyperfinite. \end{theo} \subsection{Poisson boundary} We start by recalling a few basic facts about Poisson boundaries. Let $G$ be a countable group and let $\mu$ be a probability measure on $G$ such that $\supp(\mu)$ generates $G$. The \emph{path space} is the product space $G^\bbN$. Let us write $\bbP^\mu$ for the measure on $G^\bbN$ obtained as push-forward of $\mu^\bbN$ via the map \[ (x_1,x_2,\,\ldots)\mapsto (1, x_1,x_1x_2,\,\ldots). \] We define the shift operator $T:G^\bbN\to G^\bbN$ as $T((x_i)_{i\,\in\,\bbN})=(x_{i+1})_{i\,\in\,\bbN}$. The shift operator commutes with the action of $G$ by left-multiplication. The \emph{Poisson boundary} $(P,\tau)$ is the quotient of the space $(G^\bbN,\bbP^\mu)$ by the $\sigma$-algebra of $T$-invariant sets. Since the support of $\mu$ generates $G$, one can easily verify that the induced action of $G$ on $(P,\tau)$ is non-singular and that the measure $\tau$ is $\mu$-stationary. It is a theorem of Zimmer~\cite{Zimmer78} that the action of $G$ on the Poisson boundary is amenable (in the sense of~\cite{Zimmer78}). We reproduce the sketch of Zimmer's proof for completeness. The key ingredient of Zimmer's argument is the following lemma. \begin{lemm}[Zimmer {\cite[Theorem~3.3]{Zimmer78}}]\label{lem:QuotientAm} Let $(X,\nu_1)$ be a probability measure space with a non-singular amenable action of the group $G_1\times G_2$ such that $G_2$ is amenable. Let $\calA$ be the $\sigma$-algebra of $G_2$ invariant sets on $X$. Then the quotient of $(X,\nu_1)$ by $\calA$ is a non-singular amenable $G_1$-space. \end{lemm} Actually, Zimmer uses a version of Lemma~\ref{lem:QuotientAm} where $G_2=\bbN$ is not a group, but a semigroup generated by a single transformation (see~\cite[Section~5]{Zimmer78} for details). In order to use this to prove amenability of the Poisson boundary of $G$, we must first replace $\bbP^\mu$ with a quasi-invariant measure which makes the left $G$-action on $G^\bbN$ amenable. For any probability measure $\nu$ on $G$ the convolution $\nu*\bbP^\mu$ is the push-forward of the measure $\nu\times \mu^\bbN$ via the map $(g,x_1,x_2,\,\ldots)\mapsto (g,gx_1,gx_1x_2,\,\ldots).$ We claim that as soon as $\nu$ has full support on $G$, the action $G\curvearrowright (G^\bbN,\nu*\bbP^\mu)$ is non-singular and amenable. Non-singularity is obvious because $\nu$ has full support, and to prove amenability, note that the projection onto the first coordinate $(G^\bbN,\nu*\bbP^\mu)\to (G,\nu)$ is a $G$-equivariant measure-preserving map and $G$ acts amenably on $(G,\nu)$~\cite[4.3.2]{Zimmer}. Therefore, by~\cite[Theorem~2.4]{Zimmer78} the action $G\curvearrowright (G^\bbN, \nu*\bbP^\mu)$ is amenable. Let $\calA$ be the algebra of $T$-invariant sets on $G^\bbN$. The quotient of $(G^\bbN,\nu*\bbP^\mu)$ by $\calA$ is $(P,\nu*\tau)$. By the variant of Lemma~\ref{lem:QuotientAm} for $G_2=\bbN$, the $G$-action on $(P,\nu*\tau)$ is amenable. It remains to produce $\nu$ with full support such that $\nu*\tau=\tau$, for which we can take the sum of convolutions $\nu:=\sum_{n\,\geq\,1} \frac{1}{2^n} \mu^{\ast n}$. This concludes the proof of the amenability of $G\curvearrowright(P,\tau)$. We will need one more well-known property of $(P,\tau)$, namely an ergodic theorem for the random walk: \begin{lemm}\label{lem:ConvConv} For any $f\in L^\infty(P,\tau)$ and $\tau$-a.e. $x\in P$, we have \[ \lim_{n\,\to\,\infty} \int_G f(gx)\, d\mu^{\ast n}(g)=\int_P f(y) \, d\tau(y). \] \end{lemm} We provide a short proof: \begin{proof} Let $\tilde f$ be the pullback of $f$ to $G^\bbN$. The lemma will follow once we show that for $\bbP^\mu$-almost every trajectory $(x_i)_{i\,\in\,\bbN}$, we have \[ \lim_{n\,\to\,\infty}\int_G \tilde f((gx_i)_{i\,\in\,\bbN})d\mu^{\ast n}(g)=\bbE(\tilde f). \] Because $\tilde f$ is shift-invariant, we can rewrite the left-hand side as \begin{multline}\label{eq:Shift} \lim_{n\,\to\,\infty}\int_{G^n}\\ \tilde f(1,g_1,g_1g_2,\,\ldots,\,g_1\ldots g_n,g_1\ldots g_nx_1,g_1\ldots g_nx_2,\,\ldots) d\mu(g_1)\ldots d\mu(g_n). \end{multline} By the martingale convergence theorem, we have that for $\bbP^\mu$-almost every trajectory $(y_i)_{i\,\in\,\bbN}\in G^\bbN$: \[ \tilde{f}\left((y_i)_{i\,\in\,\bbN}\right)=\lim_{n\,\to\,\infty}\bbE\left(\tilde f((y_i')_{i\,\in\,\bbN} \mid y_i'=y_i \text{ for } i\leq n)\right). \] Since the expected value on the right depends only on $y_1,\,\ldots,\,y_n$ we will write $\bbE \tilde f(y_1,\,\ldots,\,y_n):=\bbE(\tilde f((y_i')_{i\,\in\,\bbN}) \mid y_i'=y_i \text{ for } i\leq n))$. Using~\eqref{eq:Shift} we now can deduce that for almost every trajectory $(x_i)_{i\,\in\,\bbN}$ we have \begin{align*} \lim_{n\,\to\,\infty}\int_G \tilde f\left((gx_i)_{i\,\in\,\bbN}\right)d\mu^{\ast n}(g)=&\lim_{n\,\to\,\infty}\bbE \tilde{f}\left(1,g_1,\,\ldots,\,g_1g_2\ldots g_n\right)d\mu(g_1)\ldots d\mu(g_n)\\=&\bbE(\tilde f). \end{align*} \end{proof} \subsection{Global non-expansion of heat kernels on groups} We are now able to prove the main result in the special case of Cayley graphs of finitely generated groups. \begin{theo}\label{thm:mainGp} Let $G$ be a finitely generated group and $\mu$ a finitely supported measure on $G$ whose support generates $G$ as a semigroup. Then the heat kernels on $G$ with distribution $\mu$ are not expanding. \end{theo} \begin{proof}[{Proof of Theorem~\ref{thm:mainGp}}] Let $(P,\tau)$ be the Poisson boundary of $(G,\mu)$. By the above results of Zimmer~\cite{Zimmer78}, the action of $G$ on $(P,\tau)$ is nonsingular, ergodic, and amenable. The idea of the proof is that amenability of the Poisson boundary implies there exist medium-size sets in $P$ that are nearly invariant under the $G$-action. This allows us to define sets in $G$ that are nearly invariant under the random walk. The above idea works well as long as the Poisson boundary is nontrivial, so let us first consider the case that $(P,\tau)$ is trivial. Then $G$ is amenable, so for every $\varepsilon>0$ there exists a F{\o}lner set $F_\varepsilon$ such that $|\partial F_\varepsilon|\leq \varepsilon|F_\varepsilon|$. Using the random walk starting at $e\in G$, we have for every $n$: \[ \sum_{g\,\in\,G} \mu_e^n(gF_\varepsilon)= |F_\varepsilon| \qquad \text{ and } \qquad \sum_{g\,\in\,G} \mu_e^n(\partial gF_\varepsilon)=|\partial F_\varepsilon|\leq \varepsilon|F_\varepsilon|. \] It follows that for every $n$ there exists $g_n$ such that $\mu_e^n(\partial g_n F_\varepsilon)\leq \varepsilon \, \mu_e^n(g_n F_\varepsilon)$. In Lemma~\ref{lem:ProbDecay} we establish a dispersion property of random walks, immediately implying that for sufficiently large $n$ (depending on $\varepsilon$), we have $\mu_e^n(g_n F_\varepsilon)\leq \frac{1}{2}$. This proves that heat kernels on $G$ are not $\varepsilon$-expanding. The remaining case is that $(P,\tau)$ is nontrivial. By amenability, $G\curvearrowright (P,\tau)$ is orbit equivalent to a $\bbZ$-action~\cite{ConnesFeldmanWeiss}. Note that non-trivial Poisson boundaries are purely nonatomic because their atomic part would be stationary and hence invariant by the maximum principle (see also~\cite[Corollary~3.3.1]{Kai05}). The stationarity of $\tau$ would then imply that all $gp$ have the same mass as $p$, which contradicts the finiteness of $\tau$. A result of Jones-Schmidt~\cite{JonesSchmidt} then shows that there exists an almost invariant sequence $\{S_n\}_n$ of subsets of $P$, i.e. we have $\tau(\gamma S_n \Delta S_n)\to 0$ for any $\gamma\in\text{supp}(\mu)$. It follows that $\tau(\partial S_n)\to 0$. Further, Jones--Schmidt in fact show we can choose $S_n$ with $\tau(S_n)=\frac{1}{2}$ (\cite[Lemma~2.3]{JonesSchmidt}). For $p\in P$ and $n\geq 1$, define \[ A_n(p):= \{\gamma\in G\mid \gamma p \in S_n\}. \] We claim that for a.e. $p$, these sets $A_n$ are nearly invariant under the random walk. Indeed, by Lemma~\ref{lem:ConvConv}, we have for almost every $p\in P$: \begin{align*} \lim_{k\to\infty} \mu^k(A_n(p))&=\int_G \bbone_{S_n}(\gamma p) \mu^k(\gamma)\\ &=\int_P \bbone_{S_n}(p) d\tau(p)\\ &=\tau(S_n), \end{align*} where we used Lemma~\ref{lem:ConvConv} on the second line. Similarly one sees $\mu^k(\partial A_n(p))\to \tau(\partial S_n)$ as $k\to\infty$ for every $n\geq 1$ and a.e. $p$. \end{proof} \section{Stationary random graphs and graphings}\label{sec:stationary} \subsection{Stationary random graphs}\label{sec:SRG} Let $d\in\bbN$ and let $\calM_{\leq\,d}$ be the moduli space of rooted isomorphism classes of connected rooted graphs of degree bounded by $d$. We allow multiple edges and loops. The space $\calM_{\leq\,d}$ is equipped with the following metric. For any rooted graphs $(\calG_1,o_1),(\calG_2,o_2)$ we put \[ d\big((\calG_1,o_1),(\calG_2,o_2)\big):=2^{-r} \quad\text{where}\quad r=\inf\left\{n\in\bbN \,\middle|\, B_{\calG_1}(o_1,n)\not\cong B_{\calG_2}(o_2,n)\right\}. \] This metric induces the Gromov--Hausdorff topology on $\calM_{\leq \,d}$. For a rooted graph $(\calG,o)\in \calM_d$, write $(X_n)_{n\,\in\,\bbN}$ for the simple random walk on $\calG$ starting at the root. \begin{defi}[{Benjamini--Curien~\cite{BenCur}}] A \emph{stationary random graph} is a random $\calM_d$-valued variable $(\calG,o)$ such that $(\calG,o)$ and $(\calG,X_n)$ have the same distribution. \end{defi} For example, a Cayley graph rooted at any vertex is a stationary random graph. We have the following definition of stationary hyperfiniteness for stationary random graphs: \begin{defi} A stationary random graph $(\calG, o)$ is \emph{stationary hyperfinite} if for every $\varepsilon>0$, there exists a stationary random subset $S\subset \calG$ with $\bbP(o\in S)\leq \varepsilon$ and such that $\calG\backslash S$ is a union of finite connected components almost surely. \end{defi} This should be compared with classical hyperfiniteness of unimodular random graphs, where $S$ is required to be unimodular, see~\cite{Schramm2011}. In particular, we warn that a unimodular random graph may be stationary hyperfinite yet not hyperfinite as a unimodular random graph: \begin{exam}\label{ex:hyperfinite_tree} For $d>1$, the $2d$-regular rooted tree $(T_{2d},o)$ is a unimodular random graph that is not hyperfinite, but it is stationary hyperfinite because a union of concentric horospheres with a sparse sequence of radii, centered at a random point of the boundary, will partition $T_{2d}$ into finite components. More precisely, identify $T_{2d}$ with the Cayley graph of the free group $F_d$ on $d$ generators and let $b\colon\partial T\times F_d\to \bbZ$ be a Busemann cocycle (it is unique up to additive constant). Choose $\alpha\in \bbR$ irrational and let $\lambda$ be the Lebesgue measure on $\bbT:=\bbZ\backslash \bbR$. Consider the system $(\partial T\ltimes \bbT,\nu\times \lambda)$ with the action $(\xi,\theta)\gamma=(\xi\gamma, \theta+\alpha b(\xi,\gamma))$ for $\gamma\in F_d.$ Let $E_\varepsilon=\partial T\times [0,\varepsilon)$ and put $S_\varepsilon=\{\gamma\in F_d \mid x\gamma\in E_\varepsilon\}$ where $x$ is $(\nu\times\mu)$-random. We have $\bbP (o\in S_\varepsilon)=\varepsilon$ and it is easy to verify that $S_\varepsilon$ is always a union of concentric horospheres with bounded gaps so that $T_{2d}\setminus S_{\varepsilon}$ is a union of finite connected components. Since $\nu\times\lambda$ is $F_d$-stationary, $S_\varepsilon$ is the intersection of $E_\varepsilon$ with the orbit of a random point in a stationary $F_d$-system (where we identified this rooted orbit with a copy of $F_d$), so its distribution is stationary under the action of $F_d$. In particular, it is a stationary random subset of $T_{2d}$. \end{exam} \subsection{Stationary graphings}\label{sec:stat_graphing} One way to produce random graphs is to realize them as equivalence classes in some non-singular measured equivalence relation $(X,\nu,\calR)$ where edges are given by a finite graphing $(\varphi_i)_{\in\,I}$ generating $\calR$. Thanks to this point of view we will be able to attack our problem using the theory of non-singular measured equivalence relations. Let $(X,\nu)$ be a probability measure space and let $\varphi_i:X_i\to X$ be a finite family of non-singular measurable maps defined on subsets $U_i$ of $X$. The triple $(X,\nu,(\varphi_i)_{i\,\in\,I})$ is called a \emph{graphing}. We assume that $(\varphi_i)_{i\,\in\,I}$ is \emph{symmetric}, i.e. for each $i\in I$ the map $\varphi_i^{-1}\colon \varphi_i(U_i)\to U_i$ is also in the set $(\varphi_i)_{i\,\in\,I}$. Let $\calR$ be the orbit equivalence relation generated by maps $(\varphi_i)_{i\,\in\,I}$. For $x\in X$ define its degree as $\deg(x):=|\{i\in I \mid x\in U_i\}|$. Intuitively $\deg(x)$ is the number of arrows emanating from $x$. \emph{In this section, all graphings and equivalence relations are assumed to be countable.} A measured graphing yields a random graph in the following way: For every $x\in X$, let $\calG_x$ be the graph with vertex set given by the equivalence class $[x]_{\calR}$ and place an edge between $y,z\in [x]_{\calR}$ whenever $z=\varphi_i(y)$ for some $i\in I$ (multiple edges are allowed). The graphs $\calG_x$ have degrees bounded by $|I|$ and are undirected since $(\varphi_i)_{i\,\in\,I}$ is symmetric. If we choose a $\nu$-random point $x$, the resulting graph $\calG_x$ is a random rooted graph. The properties of $\calG_x$ will depend on the graphing. For example, if the graphing consists of measure preserving maps then the resulting random graph is unimodular (see~\cite{ALR2007}). We are mainly interested in stationary graphs. Those will be realized as equivalence relations in \emph{stationary graphings}. \begin{defi} A finite graphing $(X, \nu, (\varphi_i)_{i\,\in \,I})$ is \emph{stationary} if for every $f\in L^\infty(X,\nu)$ we have \[ \int_X f(x)d\nu(x)=\int_X \left(\frac{1}{\deg(x)}\sum_{x\,\in\,U_i}f(\varphi_i(x))\right)d\nu(x). \] \end{defi} If $(X, \nu, (\varphi_i)_{i\,\in\,I})$ is a stationary graphing then $\calG_x$ is a stationary random graph. Conversely, any stationary random graph arises in this way: \begin{lemm}\label{lem:BernoulliGraphing} For every stationary random graph $(\calG,o)$ there exists a stationary graphing $(X,\nu,(\varphi_i)_{i\,\in\,I})$ such that $(\calG,o)=(\calG_x,x)$ in distribution. \end{lemm} \begin{proof} The proof is the same as Lovasz's result that unimodular random graphs can be realized by unimodular graphings~\cite[Theorem~18.37]{Lovasz} (see also the proof of~\cite[Proposition~14]{AGV14}), but with $\sigma$ being a stationary distribution on the space of rooted graphs. \end{proof} The random walk on a finite measured graphing $(X,\nu, (\varphi_i)_{i\,\in\,I})$ is the sequence of random variables $(X_n)_{n\,\geq\,0}$ where $X_0$ is a $\nu$-random point of $X$ and for all $n\geq 1$ we have \[ \bbP\left(X_n=y \,\middle|\, X_{n-1}=x\right)=\frac{1}{\deg(x)}\left|\left\{i\in I \,\middle|\, \varphi_i(x)=y\right\}\right|. \] For a stationary graphing each step $X_n$ will have the same distribution $\nu$. We prove that for any measured equivalence relation, its ``tautological bundle'' is amenable. Let $(X,\nu, \calR)$ be a non-singular measured equivalence relation. The tautological bundle is the pair $([X],[\nu])$ where $[X]$ is the set $\calR\subset X\times X$ equipped with measure $[\nu]:=\int_X (\delta_x\times c_x) \, d\nu(x)$ where $c_x$ is the counting measure on the equivalence class $[x]_{\calR}$. Points in the space $[X]$ are pairs $(x,y)$ where $x\in X$ and $y\in [x]_\calR.$ \begin{lemm}\label{lem:TautER} Let $\calR'$ be the equivalence relation on $[X]$ generated by $(x_1,y)\sim (x_2,y)$ for $x_1,x_2\in [y]_{\calR}$. Then $\calR'$ is non-singular and amenable as an equivalence relation. \end{lemm} \begin{proof} We will prove that $\calR'$ is non-singular and hyperfinite, so amenability will follow by Connes--Feldman--Weiss' Theorem~\ref{thm:CFW}. Recall that a measured equivalence relation is hyperfinite if it is the union of finite measured equivalence relations (see Section~\ref{sec:zimmer-amenability}). Let $(\varphi_i)_{i\,\in\,\bbN}$ be a countable graphing generating $\calR$. For each $x\in X$, equip the graph $\calG_x$ with a path metric $d_{[x]}$, declaring the length of the edge $(x,\varphi_i(x))$ to be $i$. This ensures that the balls in $\calG_x$ are finite. For $r>0$, let $\calE_r$ be the equivalence relation on $[X]$ generated by $(x_1,y)\sim (x_2,y)$ for $x_1,x_2\in [y]_{\calR}$ such that $d_{[y]}(y,x_1),d_{[y]}(y,x_2)\leq r.$ The balls in $\calG_y$ are finite for every $y\in X$, so the classes of $\calE_r$ are finite. On the other hand, for every pair $x_1,x_2\in [y]_{\calR}$ there exists $r>0$ such that $x_1,x_2$ are in the $r$-ball centered at $y$. We conclude that $\calR'=\cup_{r>0} \calE_r$, so $\calR'$ is indeed hyperfinite. \end{proof} The following lemma is an easy consequence of hyperfiniteness. \begin{lemm}\label{lem:FiniteComponents1} Let $(X,\nu,(\varphi_i)_{i\,\in\,I})$ be a finite symmetric graphing generating a non-singular amenable measured equivalence relation $\calR$. Then for every $\varepsilon>0$ there exists $M\in \bbN$ and a subset $Z\subset X$ such that $\nu(Z)\geq 1-\varepsilon$ and the equivalence relation $\calE$ on $Z$ generated by the restrictions of $(\varphi_i)_{i\,\in\,I}$ satisfies $|[z]_{\calE}|\leq M$ for $\nu$-almost all $z\in Z$. \end{lemm} \begin{proof} By Connes--Feldman--Weiss' Theorem~\ref{thm:CFW}, there exists an increasing sequence of finite measured equivalence subrelations $\calE_n\subset \calR$ such that $\calR=\bigcup_{n\,\in\,\bbN} \calE_n$. Set \[ Z_n:=\left\{x\in X \,\middle|\, \varphi_i(x)\in [x]_{\calE_n} \text{ for all } i\in I\right\}. \] Clearly $Z_n\subset Z_{n+1}$ and $\bigcup_{n\,\in\,\bbN} Z_n=X$ modulo a null set. Choose $n$ such that $\nu(Z_n)\geq 1-\varepsilon/2$. The function $Z_n\ni z\mapsto |[z]_{\calE_n}|\in \bbN$ is measurable, so there exists $M\in\bbN$ such that $\nu(\{z\in Z_n \mid |[z]_{\calE_n}|\leq M\})\geq 1-\varepsilon$. Set $Z:=\{z\in Z_n \mid |[z]_{\calE_n}|\leq M\}$ and let $\calE$ be the equivalence relation on $Z$ generated by the restrictions of $(\varphi_i)_{i\,\in\,I}$. Clearly $[z]_{\calE}\subset [z]_{\calE_n}$, so every class of $\calE$ has at most $M$ elements. \end{proof} Finally, we discuss hyperfiniteness for stationary graphings. \begin{defi}\label{dfn:StationaryHyperfinite} A symmetric stationary graphing $(X,\nu,(\varphi_i)_{i\,\in\,I})$ is \emph{hyperfinite} if the measured equivalence relation generated by $(\varphi_i)_{i\,\in\,I}$ is hyperfinite. \end{defi} We have the following relationship between stationary hyperfiniteness of a stationary random graph and hyperfiniteness of stationary graphings: \begin{lemm}\label{lem:equiv_hyperfinites} A stationary random graph $(\calG,o)$ of bounded degree is stationary hyperfinite if and only if there exists a finite, symmetric, hyperfinite, stationary graphing $(X,\nu,(\varphi)_{i\,\in\,I})$ such that $(\calG,o)=(\calG_x,x)$ in distribution. \end{lemm} \begin{proof} Suppose first $(X,\nu,(\varphi_i)_{i\,\in\,I})$ is hyperfinite. Let $\varepsilon>0$, choose $Z\subset X$ as in Lemma~\ref{lem:FiniteComponents1} and set $S:=X\backslash Z$. In particular, $\nu(S)\leq \varepsilon$ and $\calR$ has finite equivalence classes on the complement of $P$, so $(\calG_x, x)$ is stationary hyperfinite. Conversely, suppose $(\calG,o)$ is stationary hyperfinite. and choose stationary random subsets $S_n$ such that $\bbP(o\in S_n)\leq \frac{1}{n}$ and $\calG \backslash S_n$ is a union of finite components almost surely. For technical reasons assume that $S_n$ have no symmetries a.s. meaning that $(\calG,o,S_n)\neq (\calG,o',S_n)$ for any two choices of the root $o$ and $o'$. This can be always arranged by adding to $S_n$ a small intensity Bernoulli percolation on $\calG$. We will construct a hyperfinite, stationary graphing realizing the stationary random graph $(\calG, o)$ on a suitable moduli space of decorated graphs: Let $Y^1,Y^\infty$ be the space of connected, rooted graphs of degree at most $d$ decorated with a subset or a sequence of subsets respectively. We represent elements of $Y^1$ as $(\calH,o,A)$ where $\calH$ is a connected (deterministic) graph of degree at most $d$ with root $o$ and $A\subset \calH$. Similarly we represent elements of $Y^\infty$ as $(\calH,o,(A_i)_{\in\,\bbN})$ where $A_i\subset \calH$ for $i\in\bbN$. The standard graphing on $\calM_d$ (re-rooting to a neighbor) lifts to symmetric graphings on $Y^1$ and $Y^\infty$ which correspond to re-rooting a decorated graph to a neighbor of the root, which we will also call the standard graphing. Write $\calR^\infty$ for the re-rooting relation on $Y^\infty$. For $i\in\bbN$, let $\pi_i\colon Y^\infty\to Y^1$ be the projection $(\calH,o,(A_j)_{j\,\in\,\bbN})\mapsto (\calH,o,A_i)$, and note that $\pi_i$ is equivariant with respect to the standard graphings. Write $\mu_i$ for the distribution of $(\calG,o, S_i)$ in $Y^1$. Since $S_i$ is a stationary random subset, $\mu_i$ is a stationary probability measure on $Y^1$. Moreover, since $S_i$ has no symmetries a.s. we have $(\calG,o)=(\calG_x,x)$ in distribution for $\mu_i$-random $x\in Y^1$. Finally, let $\mu$ be any stationary coupling of $(\mu_i)_{i\,\in\,\bbN}$ on $Y^\infty$, i.e. a stationary probability measure on $Y^\infty$ such that $(\pi_i)_*(\mu)=\mu_i$ for all $i$. Any weak-* limit of ergodic averages of the random walk starting at a $(\prod_i \mu_i)$-random point is such a coupling almost surely. We claim that $(Y^\infty,\mu)$ with the re-rooting equivalence relation is hyperfinite. Indeed, let $Z_n:=\{(\calH,o,(A_i)_{i\,\in\,\bbN}) \mid o\not\in A_n\}\subset Y^\infty$. If $x=(\calH,o,(A_i)_{i\,\in\,\bbN})$ then $(\calG_x,x,[x]\cap Z_n)=(\calH,o,\calH\setminus A_n)$. But the distribution of the triple $(\calH,o,A_n)$ is given by $\mu_i$ so for $\mu$-random $x$ we have $(\calG_x,x,[x]\cap Z_n)=(\calG,o,\calG\setminus S_n)$ in distribution. Since $(\calG\setminus S_n)$ is a union of finite connected components a.s., we deduce that the relation $\calE_n$ on $Y^\infty$ generated by the standard graphing restricted to $Z_n$ is finite a.s. Finally, we have $\mu(Z_n)=\bbP (o\not\in S_n)\geq 1-\frac{1}{n}$, so $\calR^\infty=\bigcup \calE_n$ modulo a null set. We deduce that $(Y^\infty, \mu,\calR^\infty)$ with the standard graphing is hyperfinite. \end{proof} \section{Poisson boundaries of stationary graphings}\label{sec:poissonSRG} We recall the notion of Poisson boundary of a stationary graphing $(X,\nu,(\varphi_i)_{i\,\in \,I})$, due to Kaimanovich~\cite{Kai05}. Kaimanovich's construction is more general and applies in the context of measured groupoids. Afterwards, we use this to obtain stationary hyperfiniteness of stationary random graphs. We recall Kaimanovich's construction of Poisson boundaries: As in the classical case of groups, it is the quotient of a path space by the shift operator, but in our case the paths traverse different graphs depending on the initial point, so that the path space is a bundle over $X$. We summarize its properties: \begin{prop}[{Kaimanovich~\cite{Kai05}}] \label{prop:PoissonRSG} Let $(X,\nu,\calR)$ be a non-singular measured equivalence relation. Let $(\varphi_i)_{i\,\in\,I}$ be a finite symmetric stationary graphing generating $\calR$. Then there exists a space $(P(X),\widetilde{\nu})$ with a stationary graphing $(\widetilde{\varphi_i})_{i\,\in\,I}$ and a measurable map $\pi\colon (P(X),\widetilde{\nu})\to (X,\nu)$ such that \begin{enumerate} \item\label{prop4.1.1} $\pi_*(\widetilde{\nu})=\nu$, \item\label{prop4.1.2} $\pi\circ \widetilde{\varphi_i}=\varphi_i\circ \pi$ for all $i\in I$, \item\label{prop4.1.3} The equivalence relation $\widetilde{\calR}$ generated by $(\widetilde{\varphi_i})_{i\,\in\,I}$ is amenable. \end{enumerate} \end{prop} \begin{rema} In~\cite{Kai05}, amenability is defined using the existence of invariant means. It is well-known this is equivalent to amenability in the sense of Zimmer that we use here. \end{rema} Since we need an explicit description of the Poisson boundary for the proof of Corollary~\ref{cor:SRGareHyperfinite} below, we review its construction in the setting of Proposition~\ref{prop:PoissonRSG}. For a bounded degree graph $\calG$, define its path space \[ \Path(\calG):=\left\{(v_n)_{n\,\in\,\bbN}\subset \calG \,\middle|\, v_{n+1}\sim v_n\right\}. \] We endow the space $\Path(\calG)$ with the topology induced from $\calG^\bbN$. The shift operator $T$ acts on $\Path(\calG)$ by $T((v_n)_{n\,\in\,\bbN}):=(v_{n+1})_{n\,\in\,\bbN}.$ Write $C_{a_0,a_1,\,\ldots,\,a_m}$ for the cylinder $\{(v_n)_{n\,\in\,\bbN} \mid v_i=a_i \text{ for } i=0,\,\ldots,\,m\}.$ Equip $\Path(\calG)$ with the measure $\bbP_o$ defined by $\bbP_o(C_{a_0,\,\ldots,\,a_m}):=0$ if $a_0\neq o$ and $\bbP_o(C_{a_0,\,\ldots,\,a_m}):=\prod_{i=0}^{m-1} \deg(a_i)^{-1}$ otherwise. This is the probability measure associated to the simple random walk on $\calG$ starting at the root $o$. For $k\geq 1$ we define $\bbP_o^k:=T^k_*\bbP_o$, which is the distribution of the $k^{\rm th}$ step of the random walk starting at the root $o$. The total path space $\Path(X)$ is defined as \[ \Path(X):=\left\{(x,(x_n)_{n\,\in\,\bbN})\in X\times X^{\bbN}\,\middle|\, x_n\sim x_{n+1} \text{ in } \calG_x \text { for } n\in \bbN\right\}. \] We think of $\Path(X)$ as a fiber bundle over $X$ whose fiber over $x\in X$ is given by $\Path(\calG_x)$. The probability measure $\bbP^k$ on $\Path(X)$ is given by the integral: \[ \left(\Path(X),\bbP^k\right):=\int_X \left(\Path(\calG_x),\bbP_x^k\right) \, d\nu(x). \] We think of a point in the space $\Path(X)$ as a pair $(x, (x_n)_{n\,\in\,\bbN})$ where $x\in X$ and $(x_n)_{n\,\in\,\bbN}$ is a trajectory in $\Path(\calG_x).$ The natural projection map $\pi: \Path(X) \to X$ given by $\pi(x,(v_n)_{n\,\in\,\bbN}):=x$ satisfies $\pi_*\bbP^0=\nu$. The shift operator $T$ on $\Path(X)$ is defined fiberwise: $T(x,(x_n)_{n\,\in\,\bbN}):=(x,(x_{n+1})_{n\,\in\,\bbN})$, so in particular $\pi \circ T=\pi.$ Let $\calA$ be the $\sigma$-algebra of $T$-invariant Borel subsets of $\Path(X)$. Define the Poisson boundary $(P(X),\widetilde{\nu})$ as the Mackey point realization of the quotient of $(\Path(X),\bbP^0)$ by $\calA$, i.e. $P(X)$ is a standard Borel space and there is a map $\Path(X)\to P(X)$ inducing a $\sigma$-algebra isomorphism $\calB(P(X))\to \calA$ (see~\cite{Mackey62} for the existence of the Mackey point realization). This construction mirrors the one used by Zimmer~\cite{Zimmer78} to show amenability of the Poisson boundary of a group. Since $T$ preserves the fibers of the projection map $\pi\colon\Path(X)\to X$, we see $\pi$ factors through $P(X)$. This gives a map $\pi \colon P(X)\to X$ such that $\pi_*\widetilde{\nu}=\nu$. The maps $\widetilde\varphi_i$ commute with $T$ so they descend to maps $\widetilde\varphi_i$ on $P(X)$. We have $\pi\circ \widetilde{\varphi_i}=\varphi_i\circ \pi$. This proves Properties~\eqref{prop4.1.1} and~\eqref{prop4.1.2} in Proposition~\ref{prop:PoissonRSG}. Property~\eqref{prop4.1.3}, i.e. amenability, will then follow from amenability of the tautological bundle and the following lemma that the quotient of an amenable equivalence relation by a single transformation is amenable, which is the analogue of Zimmer's~\cite[Theorem~3.3]{Zimmer78} (see Lemma~\ref{lem:QuotientAm}). \begin{lemm}\label{lem:QuotientAMforER} Let $(X,\nu)$ be a standard Borel probability measure space with a non-singular amenable equivalence relation $\calR$ and suppose $T:X\to X$ is a non-singular measurable map that preserves a graphing of $\calR$. Then the quotient relation $\overline{\calR}$ on the space of $T$-ergodic components $T\backsslash X$ is amenable. \end{lemm} Since the proof is essentially identical to the proof of Lemma~\ref{lem:QuotientAm}, we omit it here. One only needs to substitute equivalence relations for group actions in all relevant definitions (such as cocycles), see e.g.~\cite[Proposition~3.3]{MR1242044} for details. To prove~\eqref{prop4.1.3}, let $\calR_0,\calR_1$ be the equivalence relations on $\Path(X)$ and $P(X)$ respectively that are generated by $(\widetilde \varphi_i)_{i\,\in\,I}$. Set $\bbP':=\sum_{k=0}^\infty 2^{-k-1}{\bbP^k}.$ We will show that $\calR_0$ is a non-singular amenable equivalence relation on $(\Path(X),\bbP')$. Let $([X],[\nu],\calR')$ be the ``tautological bundle'' over $(X,\nu)$ as defined immediately prior to Lemma~\ref{lem:TautER}. The map \begin{align*} \Path(X) &\longrightarrow [X]\\ \left(x,(x_n)_{n\,\in\,\bbN}\right)&\mapsto (x,x_0)\ \end{align*} that forgets the trajectory except the initial point, is non-singular\footnote{The random walk explores the entire graph so any starting point $x_0$ is achieved with positive probability.} and maps equivalence classes of $\calR_0$ to those of $\calR'$. Hence, $([X],[\nu],\calR')$ is a factor of $(\Path(X),\bbP,\calR_0)$. Since it is amenable by Lemma~\ref{lem:TautER}, $(\Path(X),\bbP',\calR_0)$ is an amenable equivalence relation by~\cite[Theorem~2.4]{Zimmer78}. The quotient of $(\Path(X),\bbP',\calR_0)$ by $\calA$ is still the space $(P(X),\widetilde{\nu},\calR_1)$. By Lemma~\ref{lem:QuotientAMforER}, amenability passes to quotients by a single transformation, so we deduce that $\calR_1$ is an amenable equivalence relation. \begin{coro}\label{cor:SRGareHyperfinite} Every stationary random graph of bounded degree is a stationary hyperfinite stationary random graph. \end{coro} \begin{proof} Let $(\calG,o)$ be a stationary random graph of degree at most $d$. Let $(X,\nu,(\varphi_i)_{i\,\in\,I})$ be a stationary graphing with $|I|\leq 2d$ such that $(\calG,o)=(\calG_x,x)$ in distribution. Let $(P(X),\widetilde{\nu},(\widetilde\varphi_i)_{i\,\in\,I})$ be the Poisson boundary constructed in Proposition~\ref{prop:PoissonRSG} and write $\widetilde{\calR}$ for the equivalence relation generated by $(\widetilde\varphi_i)_{i\,\in\,I}$. Finally let $(\calH_y,y)$ be the stationary random graph associated to the stationary graphing $(P(X),\widetilde{\nu},(\widetilde{\varphi}_i)_{i\,\in\,I})$. The equivalence relation $\widetilde{\calR}$ is amenable by Proposition~\ref{prop:PoissonRSG}, and hence hyperfinite by Connes--Feldman--Weiss' Theorem~\ref{thm:CFW}. We deduce that $(\calH_y,y)$ is a stationary hyperfinite stationary random graph. It remains to prove that $(\calH_y,y)=(\calG_x,x)$ in distribution. The map $\pi$ from Proposition~\ref{prop:PoissonRSG} induces a graph cover $\pi\colon (\calH_y, y)\to (\calG_{\pi(y)},\pi(y)).$ The definition of maps $\widetilde\varphi_i$ on the path space $\Path(X)$ (before taking the quotient by the $\sigma$-algebra $\calA$) immediately implies that $\pi\colon (\calH_y, y)\to (\calG_{\pi(y)},\pi(y))$ is a graph isomorphism. Since $\pi_*(\widetilde{\nu})=\nu$ we infer that $(\calH_y,y)=(\calG_x,x)$ in distribution. \end{proof} We remark that Corollary~\ref{cor:SRGareHyperfinite} does not contradict the fact that there are non-hyperfinite unimodular random graphs. Even if the stationary random graph $(\calG,o)$ is unimodular, the graphing that shows stationary hyperfiniteness is not necessarily measure-preserving. \vspace*{20pt} \break \section{Proof of the Main Theorem}\label{sec:main_proof} \subsection{Proof for stationary random graphs}\label{sec:stat_proof} \begin{proof}[{Proof of Theorem~\ref{thm:mainSt}}] Let $(\calG,o)$ be an infinite connected stationary random graph of degree at most $d$ and let $\varepsilon>0$. For technical reasons we require $\sqrt{(d+1)\varepsilon}\leq 1/10.$ By Corollary~\ref{cor:SRGareHyperfinite} there exists a stationary graphing $(X,\nu,(\varphi_i)_{i\,\in\,I})$ such that the relation generated by $ (\varphi_i)_{i\,\in\,I}$ is hyperfinite and $(\calG,o)=(\calG_x,x)$ in distribution. By Lemma~\ref{lem:FiniteComponents1} there exists a subset $Z$ of $X$ and a constant $M>0$ such that $\nu(Z)\geq 1-\varepsilon$ and the classes of the equivalence relation on $Z$ generated by $(\varphi_i)_{i\,\in\,I}$ are of size at most $M$. For $x\in X$ set $\calF_x:=[x]_{\calR}\cap Z$ and $\calE_x:=\calG_x\setminus \calF_x$. Then $\calF_x$ is a subgraph of $\calG_x$ such that $\bbP(x\in \calF_x)=\nu(Z)\geq 1-\varepsilon$ and each connected component of $\calF_x$ has at most $M$ vertices. Recall that $\mu_x^n$ is the distribution of the $n^{\rm th}$ step of a simple random walk on $(\calG_x,x)$. By stationarity we have \[ \int \mu_x^n(\partial \calF_x\cup \calE_x) \, d\nu(x)=\int \bbP(X_n\in \partial \calF_x) \, d\nu(x) +\bbP(x\in \calE_x), \] where as before $X_n$ is the $n^{\rm th}$ step of the random walk associated to $\mu$. We estimate the first term on the right-hand side as follows: \begin{align*} \bbP(X_n\in \partial \calF_x)&=\frac{\bbP\left(X_n\in \partial \calF_x \text{ and } X_{n+1}\in \calE_x\right)}{\bbP\left(X_{n+1}\in \calE_x \,\middle|\, X_n \in \partial \calF_x\right)}\\ &\leq \frac{\bbP(X_{n+1}\in \calE_x)}{d^{-1}}\\ &=d \, \bbP(x\in \calE_x), \end{align*} where on the second line, we estimated the denominator using that any point in $\partial \calF_x$ has an edge with endpoint in $\calE_x$ and that the degree is bounded by $d$, and on the final line we used stationarity again. Combining these estimates and using $\bbP(x\in \calE_x)\leq \varepsilon$, we have \[ \int \mu_x^n(\partial \calF_x\cup \calE_x) \, d\nu(x) \leq (d+1)\varepsilon, \] so that by Fatou's lemma \[ \int \liminf_{n\,\to\,\infty} \mu_x^n(\partial \calF_x) \, d\nu(x)\leq (d+1)\varepsilon. \] It follows that the set $\displaystyle X_\varepsilon:=\{x\in X \mid \liminf_{n\,\to\,\infty} \mu_x^n(\partial \calF_x)\leq \sqrt{(d+1)\varepsilon}\}$ has large mass: \begin{equation}\label{eqn:MeasureOfGoodSet} \nu(X_\varepsilon)\geq 1-\sqrt{(d+1)\varepsilon}. \end{equation} \begin{enonce}[plain]{Claim}\label{claim:expansion} For every $x\in X_\varepsilon$ the heat kernels on $(\calG_x,x)$ are not $(6\sqrt{(d+1)\varepsilon})$-expanding. \end{enonce} \begin{proof} Let $x\in X_\varepsilon$. In Lemma~\ref{lem:ProbDecay} below, we establish a uniform flattening property for the random walk on $\calG_x$, which implies there exists $n\in\bbN$ such that for every $v\in \calG_x$ we have \begin{equation}\label{eq:PtBound} \mu_x^n(\{v\})\leq \frac{\sqrt{(d+1)\varepsilon}}{3M}. \end{equation} Since $x\in X_\varepsilon$, by increasing $n$ if necessary, we can also ensure that $\mu_x^n(\partial \calF_x\cup \calE_x)\leq 2{\sqrt{(d+1)\varepsilon}}$. The last inequality implies that $\mu_x^n(\calE_x)\leq 2{\sqrt{(d+1)\varepsilon}}$ so $\mu_x^n(\calF_x)\geq 1- 2{\sqrt{(d+1)\varepsilon}}>2/3$. Let us enumerate the connected components of $\calF_x$ as $C_1,C_2,\,\ldots.$ Let $k$ be the smallest integer such that $\sum_{i=1}^k \mu_x^n(C_i)\geq 1/2$ and define $S_x:=\bigcup_{i=1}^{k-1} C_i$. By~\eqref{eq:PtBound} we have \[ \frac{1}{2}\geq \mu_x^n(S_x)\geq \frac{1}{2}-\mu_x^n(C_k)\geq \frac{1}{2} -M\frac{\sqrt{(d+1)\varepsilon}}{3M}> \frac{1}{3}. \] On the other hand $\partial S_x\subset \partial F_x$ so $\mu^n_x(\partial S_x)\leq \mu^n_x(\partial \calF_x)\leq 2\sqrt{(d+1)\varepsilon}.$ Hence, \[ \frac{\mu_x^n(\partial S_x)}{\mu_x^n(S_x)}<6\sqrt{(d+1)\varepsilon}. \] This proves the claim. \end{proof} To prove the theorem, set $X_0:=\liminf_{m\,\to\,\infty} X_{m^{-4}}$. By~\eqref{eqn:MeasureOfGoodSet}, the Borel-Cantelli lemma applies to the complement of $X_0$ and shows that $\nu(X_0)=1$. Further by Claim~\ref{claim:expansion} we know that for every $x\in X_0$ the heat kernels on $(\calG_x,x)$ are not expanding. This completes the proof since $(\calG,o)=(\calG_x,x)$ in distribution. \end{proof} In the above proof of Theorem~\ref{thm:mainSt}, we needed uniform flattening of random walks on infinite graphs. This is well-known to experts, see e.g.~\cite[Lemma~3.2]{PeteTimar} for the proof of a stronger estimate for regular graphs. Since we could not locate a proof in full generality in the literature, we provide one here for completeness. \begin{lemm}\label{lem:ProbDecay} Let $(\calG,o)$ be a infinite bounded degree connected rooted graph. Let $(X_n)_{n\,\in\,\bbN}$ be the simple random walk on $\calG$ starting at $o$. Then \[ \displaystyle\lim_{n\,\to\,\infty}\max_{v\,\in\,\calG}\bbP(X_n=v)=0. \] \end{lemm} \begin{proof} Let $d$ be the maximal degree of $\calG$. Let $c_n=\max_{v\,\in\,\calG}\frac{\bbP(X_n=v)}{\deg(v)}$ and write $c:=\limsup_{n\,\to\,\infty}c_n$. We need to show that $c=0$. Suppose to the contrary that $c>0$. Our first observation is that for any $n\in\bbN$ we have \begin{equation}\label{eq:Step} \frac{\bbP(X_{n+1}=v)}{\deg(v)}=\frac{1}{\deg(v)}\sum_{w\,\sim\,v}\frac{\bbP(X_{n}=w)}{\deg(w)}, \end{equation} so $c_{n+1}\leq c_n$. In particular we have $c_n\geq c$ for every $n\in \bbN$. Choose $m\in\bbN$ such that $(m-1)c > 1$ and $n> m$ such that $c_n\leq (1+d^{-2m})c.$ Let $v_0\in \calG$ be such that $\bbP(X_{n+2m}=v_0)=c_{n+2m}$ and choose vertices $v_1,\,\ldots,\,v_m$ such that $d(v_0,v_i)=2i$ for $i=1,\,\ldots,\,m$. Let $W_{2m}$ be the set of walks of length $2m$ starting at $v_0$. We have $|W_{2m}|\leq d^{2m}$ and for each $i$ there is at least one walk that ends in $v_i$. For each walk $\underline{w}=(w_0,w_1,\,\ldots,\,w_{2m})$ we write $\deg(\underline w):=\prod_{i=0}^{2m-1}\deg(w_i).$ Applying formula~\eqref{eq:Step} $2m$ times, we get \begin{align*} c\leq \frac{\bbP(X_{n+2m}=v_0)}{\deg(v_0)}=&\sum_{\underline w\,\in\,W_{2m}} \frac{\bbP(X_n=w_{2m})}{\deg(\underline w)\deg(w_{2m})} \end{align*} Choose walks $\underline{w}^i, i=1,\,\ldots,\,m$ such that $w_{2m}^i=v_i$. Considering these separately, we compute \[ c\leq \sum_{\underline w\,\in\,W_{2m}\,\setminus\left\{\underline w^1,\,\ldots,\,\underline w^m\right\}} \frac{c_n}{\deg(\underline w)}+\sum_{i=1}^m \frac{\bbP(X_n=v_i)}{\deg(\underline{w}^i)\deg(v_i)} \] A simple inductive argument shows that $\sum_{\underline w\,\in\,W_{2m}}\frac{1}{\deg(\underline w)}=1$. Hence \[ c\leq c_n\left(1-\sum_{i=1}^m \frac{1}{\deg(\underline w^i)}\right)+\sum_{i=1}^m \frac{\bbP(X_n=v_i)}{\deg(\underline{w}^i)\deg(v_i)}. \] Rearranging and using $c_n\leq (1+d^{-2m})c$, we have \[ \sum_{i=1}^m\frac{1}{\deg(\underline w^i)}\left(c_n- \frac{\bbP(X_n=v_i)}{\deg(v_i)}\right)\leq c_n-c\leq d^{-2m}c. \] Since the terms in the sum on the left-hand side are nonnegative and $\deg(\underline w^i)\leq d^{2m}$ for all $i$, multiplying both sides by $d^{2m}$ shows \[ \sum_{i=1}^m\left(c_n- \frac{\bbP(X_n=v_i)}{\deg(v_i)}\right)\leq c. \] Since $m$ was chosen such that $mc-c>1$, we obtain \[ \sum_{i=1}^m \frac{\bbP(X_n=v_i)}{\deg v_i} \geq mc_n-c\geq mc-c>1. \] This contradicts $\sum_{v\,\in\,\calG} \bbP(X_n=v)=1$. \end{proof} \subsection{Proof for bounded degree graphs} \label{sec:graph_proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] We argue by contradiction, so suppose $\calG$ is a connected infinite graph of degree at most $d$ such that the heat kernels of $\calG$ are $\varepsilon$-expanding. \begin{lemm}\label{lem:GHlimit} Let $(o_n)_{n\,\in\,\bbN}$ be a sequence of vertices of $\calG$ such that $(\calG,o_n)$ converges to $(\calG',o)$ in Gromov--Hausdorff topology. Then the heat kernels on $(\calG',o)$ are $\varepsilon$-expanding. \end{lemm} \begin{proof} Let $m\in\bbN$ and let $S$ be a subset of vertices of $\calG'$. We need to prove that either $\mu_o^m(S)\geq \frac{1}{2}$ or $\mu_o^m(\partial S)\geq \varepsilon \mu_o^m(S).$ Since $(\calG,o_n)$ converge to $(\calG',o)$, for sufficiently large $n$ the rooted graphs $B_{\calG}(o_n,m)$ and $B_{\calG'}(o,m)$ are isomorphic. Choose $n_0$ such that this holds and fix a root-preserving isomorphism $\iota: B_{\calG}(o_{n_0},m) \to B_{\calG'}(o,m)$, and put $S_0:=\iota^{-1}(S\cap B_{\calG'}(o,m)).$ Then $\mu_o^m(S)=\mu_{o_{n_0}}^m(S_0)$ and $\mu_o^m(\partial S)=\mu_{o_{n_0}}^m(\partial S_0)$ because the distribution of first $m$ steps of a random walk depends only on the $m$-neighborhood of the root. Because the heat kernels on $\calG$ are $\varepsilon$-expanding, we will have either $\mu_o^m(S)\geq \frac{1}{2}$ or $\mu_o^m(\partial S)\geq \varepsilon \mu_o^m(S).$ \end{proof} We will now construct a stationary random graph $(\calG'',o)$ which is almost surely $\varepsilon$-expanding. Fix any initial root $o\in \calG$ and consider the sequence of probability measures $\{\nu_N\}_N$ on $\calM_{\leq\,d}$ supported on graphs isomorphic to $\calG$ with root distributed according to the first $N$ steps of the random walk on $\calG$ starting at $o$, i.e. \[ \nu_N:=\frac{1}{N}\sum_{k=0}^{N-1} \int_{\calG}\delta_{\calG,v} \, d\mu_{o}^{k}(v). \] If we choose a $\nu_N$-random graph and move the root to a random neighbor, the distribution of the resulting graph is the same average with $k$ replaced by $k+1$. It follows that any weak-* limit $\nu$ of $\nu_N$ is the distribution of a stationary random graph supported on Gromov--Hausdorff limits of rooted graphs isomorphic to $\calG$. By Lemma~\ref{lem:GHlimit}, the limit $\nu$ is almost surely $\varepsilon$-expanding, but this contradicts Theorem~\ref{thm:mainSt}. \end{proof} \section{A rooted expander at all scales}\label{sec:rooted-expander} In this section, we prove the claim stated in Example~\ref{ex:rooted_expansion} that the graph given there is a rooted expander at all scales. Recall that this graph is obtained by fixing a prime $p$, and an expander family of $p$-congruence quotients $\{G_k\}_{k\,\geq\,0}$ of a finitely generated linear group $\Gamma$, where $G_0=1$ is trivial. Fix a finite generating set of $\Gamma$, which projects to a finite generating set of $G_k$ for all $k\geq 0$. We also use $G_k$ to denote the Cayley graph of $G_k$ with this finite generating set. Let $\calG$ be the graph with vertex set $\sqcup_k G_k$ and edges given by those in $\{G_k\}_k$ as well as an edge between $x\in G_k$ and its image in $G_{k-1}$. Let the root $o$ be the vertex that corresponds to $G_0$. \begin{prop}\label{prop:rooted_expansion} $\calG$ is a rooted expander at all scales. \end{prop} \begin{proof} Note that by removing edges between vertices in the same level $G_k$ for all $k$, we obtain a tree in which every vertex has degree greater than 1. Such a tree is a (classical) $h$-expander for some $h>0$, i.e. for any finite subset $A\subseteq \calG$, we have $|\partial A|\geq h|A|$. It follows that this is also true for $\calG$. The ball $B(o,n)$ is given by $\cup_{0\,\leq\,k\,\leq\,n} G_k$. Suppose now $A\subseteq B(o,n)$ for some $n\geq 1$ and $|A|\leq |B(o,n)|/2$. Set $A_k:=A\cap G_k$. To estimate the expansion ratio $|\partial A|/|A|$, we consider two cases depending on whether $A$ concentrates in $G_n$ or not: %%% \begin{case}{{$|A_n|\leq h|A|/2$}} %\emph{Case 1} (): Then the boundaries $\partial A$ and $\partial_{\calG} A$ of $A$ as measured in $B(o,n)$ and $\calG$ differ by at most $h|A|/2$ vertices. Hence \[ |\partial A|\geq \left|\partial_{\calG} A\right|-\frac{h}{2}|A|\geq \frac{h}{2}|A|. \] \end{case} \begin{case}{{$|A_n|> h|A|/2$}}: If $|A_n|\leq 3|G_n|/4$, expansion follows from expansion in $G_n$. If $|A_n|\geq 3|G_n|/4$, let $m$ be largest such that $|A_m|\leq 2|G_m|/3$. \end{case} \begin{enonce}[plain]{Claim} $r=n-m$ is bounded (independently of $A$). \end{enonce} \begin{proof} It suffices to show that there exists $r\geq 1$ such that \begin{equation}\label{eq:centerofmass} |B(o,n)-B(o,n-r)|\geq \frac{3}{4}|B(o,n)| \end{equation} since if $A_k\geq 2/3|G_k|$ for all $n-r\leq k\leq n$, then $A$ contains more than half of the vertices of $B(o,n)$, and hence we must have $m\geq n-r$. To obtain Equation~\eqref{eq:centerofmass}, note that since $G_k$ are congruence quotients, there exists $d$ (which is the dimension of the corresponding $p$-adic Lie group $\varprojlim G_k$) such that $|G_k|\asymp p^{dk}$, so that $|B(o,n)|\asymp p^{d(n+1)}$, and \[ |B(o,n)|-|B(o,m)|\asymp p^{dn}-p^{dm}. \] Setting this equal to $3p^{dn}/4$ and solving for $m$, the result follows. \end{proof} Therefore for at least $(3/4-2/3)|G_n|$ vertices in $A_n$, there is a path of length at most $r$ starting at such a vertex and ending outside of $A$. Every one of these vertices contributes to $\partial A$, with at most $p^{dr}$ vertices yielding the same contribution. It follows that \[ |\partial A| \geq \frac{1}{12} p^{-dr} |G_n|. \] Since $|G_n|\gtrsim |B(o,n)|$, it follows that $|\partial A|\gtrsim |A|$. \end{proof} \bibliography{fraczyk} \end{document}