The measurable Kesten theorem

Introduction

We call $G$ a Ramanujan graph, if $\rho(G)\leq\rho(T_{d})$. Lubotzky, Philips and Sarnak , Margulis and Morgenstein have constructed sequences of $d$-regular Ramanujan graphs for $d=p^{\alpha}+1$. Also, Friedman showed that random $d$-regular graphs are close to being Ramanujan.

All the Ramanujan graph families above have large girth, that is, the minimal size of a cycle tends to infinity with the size of the graph. However, the reason for that is group theoretic and not spectral, and a priori, Ramanujan graphs could have many short cycles.

In this paper we investigate the connection between the densities of short cycles, the spectral radius and the spectral measure for $d$-regular graphs. We apply our methods to give explicit estimate these invariants, then we pass to graph limits and prove limiting results.

A cycle (or $k$-cycle) in a graph is a walk of length $k$ that starts and ends at the same vertex. It is called nontrivial if either for some directed non-loop edge $e$, the number of times the cycle passes through $e$ differs from the number of times it passes through the reversal of $e$, or $k=1$ (see Definition 23). For a finite graph $G$ let $\gamma_{k}(G)$ denote the number of nontrivial $k$-cycles in $G$ divided by the number of vertices $|G|$ of $G$.

Let $G$ be a finite $d$-regular graph with $|G|\geq d^{7}$. Then for any $k\geq 1$ we have

where $\nu_{k}=2\cdot 10^{11}2^{4k}(d-1)^{3k}k.$

Applying this to finite Ramanujan graphs yields that they have few cycles of length $o(\log\log|G|)$.

Let $d\geq 3$ and $\beta=(30\log(d-1))^{-1}$. Then for any $d$-regular finite Ramanujan graph $G$, the proportion of vertices in $G$ whose $\beta\log\log|G|$-neighborhood is a $d$-regular tree is at least $1-c(\log|G|)^{-\beta}$.

This answers a question of Lubotzky [19, Question 10.7.1] who asked for a clarification on the connection between eigenvalues and girth. Note that until now, it was not even known whether a finite Ramanujan graph cannot have a positive density of short cycles.

It is easy to see that infinite Ramanujan graphs can have arbitrarily many short cycles. In fact, every connected, infinite $d$-regular graph can be embedded as a subgraph of a Ramanujan graph with degree at most $d^{2}$ (see Corollary 35). However, it turns out that cycles of bounded size must be sparse in a Ramanujan graph.

Let $G$ be an infinite $d$-regular graph such that every vertex in $G$ has distance at most $R$ from a $k$-cycle. Then

2 Graph limits and spectral measure

The spectral measure $\mu_{T_{d}}$ of the Markov operator on $T_{d}$, also known as the Plancherel measure of $T_{d}$ or the Kesten-McKay measure, has density

Let $(G_{n})$ be a sequence of finite $d$-regular graphs. We say that $(G_{n})$ has essentially large girth, if for all $k$ the denisty of nontrivial cycles satisfies

For a finite graph $G$, let $\mu_{G}$ denote the eigenvalue distribution of the Markov operator on $G$. Then the following are equivalent (see Proposition 14):

$(G_{n})$ converges to $T_{d}$ in Benjamini-Schramm convergence;

$\mu_{G_{n}}$ weakly converges to $\mu_{T_{d}}$.

A sequence $(G_{n})$ of finite $d$-regular graphs is weakly Ramanujan if

that is, if most eigenvalues of $G_{n}$ fall in the minimal possible supporting region. Note that a weakly Ramanujan sequence is not necessarily an expander sequence. In fact, the graphs $G_{n}$ do not even have to be connected.

From 1) $\Longrightarrow$ 3) and the fact that $\mu_{T_{d}}$ is continuous, it follows immediately that every graph sequence of essentially large girth is weakly Ramanujan (in contrast, $\rho$ is only lower semicontinuous with respect to Benjamini-Schramm convergence of graphs). We show that the converse also holds.

Let $(G_{n})$ be a weakly Ramanujan sequence of finite $d$-regular graphs. Then $(G_{n})$ has essentially large girth.

Theorem 4 can also be looked at as a rigidity result, as it says that if we force most of the eigenvalues of the Markov operator of a large finite graph inside the Alon-Boppana bound, then their distribution will be close to $\mu_{T_{d}}$.

In the proof of Theorem 4, it is the use of Benjamini-Schramm convergence that allows us to get rid of the bad eigenvalues and clear up the picture. Limit objects with respect to this convergence are random rooted graphs $(G,o)$ called unimodular random graphs. We will sometimes drop the root $o$ from the notation. The notion has been introduced in : for the definition, see Section 2. Unimodular random graphs tend to behave like vertex transitive graphs in many senses. Theorem 4 now follows from the following.

Let $(G,o)$ be a $d$-regular unimodular random graph that is infinite and Ramanujan a.s. Then $G=T_{d}$ a.s.

This is Kesten’s theorem for vertex transitive graphs ( and ). We give the following two quantitative versions of Theorem 5. For infinite $d$-regular unimodular random graphs

Here $\gamma_{k}(G,o)$ denotes the number of nontrivial $k$-cycles starting at $o$, and $\nu_{k}$ is a constant defined in Theorem 1. Note that for a fixed finite graph $G$ the density $\gamma_{k}(G)$ equals the expected value of $\gamma_{k}(G,o)$ over a uniformly chosen root $o$ of $G$.

To define $\kappa^{*}_{k}(G,o)$, consider all paths of length $k$ from $o$ to a vertex $v$. After attaching a fixed path from $v$ to $o$, these can be used as generators for a random walk on the fundamental group of $G$. Then $\kappa^{*}_{k}(G,o)$ is the geometric average of the spectral radii of these random walks when $v$ is a chosen randomly as the position of the infinite nullcycle (defined in Corollary 20) at time $k$ (see (19), (21) for more details).

Note that if our unimodular random graph $G$ is not a tree, then for $k$ large enough, with positive probability, the Cayley graph of the subgroup of the fundamental group given by above loops as generators has spectral radius less than one. Thus the second bound clearly implies Theorem 5.

The first bound in (1) is proved in Section 5 as Theorem 28; the proof uses results from Sections 3 and 4. It is just the infinite version of Theorem 1. The advantage of this approach is the linear lower estimate on how the spectral radius grows compared to the tree: we believe this to be sharp. The major advantage of the second bound in (1) (proved in Section 6) is that it is sharp in limit as $k\to\infty$, however, $\kappa_{k}^{*}$ seems to be hard to compute.

Theorem 4 is related to a paper of Serre that studies asymptotic properties of graph sequences. Let $d_{k}(G)$ denote the number of primitive, cyclically reduced cycles of length $k$ in the graph $G$. Recall that a cycle is primitive if it is not a proper power of another cycle.

Let $(G_{n})$ be a sequence of finite $d$-regular graphs, such that the limit

exists for every $k$. Then the measures $\mu_{G}$ weakly converge. If the series

converges then the sequence of graphs is weakly Ramanujan and the limiting measure is absolutely continuous with respect to the Lebesgue measure on $\left[-\rho(T_{d}),\rho(T_{d})\right]$.

Theorem 4 now immediately implies the following.

converges, then $\gamma^{\prime}_{k}=0$ for all $k$ and the limiting measure of $\mu_{G_{n}}$ equals $\mu_{T_{d}}$.

It is natural to ask whether a version of Theorem 5 holds for growth instead of spectral radius. In Section 9 we show that the answer is negative:

There exists an infinite $d$-regular unimodular random graph with the same growth as $T_{d}$ but not equal to $T_{d}$.

3 The basic method

There is a common method in the proofs of Theorems 1 and 5 which we can summarize as follows.

The central tool of our analysis is a nullcycle. Recall that a cycle is a walk of finite length that starts and ends at the same vertex.

A nullcycle is a cycle in a graph $G$ so that if we keep deleting backtrackings (steps that are immediately reversed), we get a cycle of length 0.

This property does not depend on the order of erasing backtrackings. Equivalently, a nullcycle is a cycle whose lift in the universal covering tree of the graph is also a cycle. In other words, the walk corresponds to a trivial element in the fundamental group of the graph $G$. The number of nullcycles in a $d$-regular graph starting at a fixed vertex $v$ equals the number of cycles in the $d$-regular tree at a fixed vertex.

To bound the spectral radius, we have to count cycles of a given length. In order to bound the spectral radius away from that of the tree, we need to show that there are exponentially more cycles than nullcycles. Consider the set of cycles of length $nk$ starting at a vertex $v$ in a $d$-regular graph $G$. We say that $w^{\prime}$ is a rewiring of $w$ if they are at the same place at times that are multiples of $k$. This definition is used in Section 6; in Section 4.2 we use a slight variant of this.

Consider the equivalence class $[w]$ of a typical nullcycle $w$ under the rewiring equivalence relation. The essence of our argument is to show that for a typical $w$, the probability that a random element $C$ of $[w]$ is a nullcycle is exponentially small. Essentially, in every segment $[jk,(j+1)k]$, if there are short cycles around in the graph, there is a positive probability that the rewiring $C$ will use them, and this is likely to stop $C$ from being null-homotopic.

In order to show that $C$ is nullhomotopic with exponentially small probability, we need to find a linear number of $j$ so that $G$ has short cycles around $w(jk)$. Fortunately, the random nullcycle $w$ samples the graph $G$ in a homogeneous manner. In particular, if $w(0)$ is a uniformly chosen vertex, then so will be $w(j)$ for every $j$. This is an advantage of using random nullcycles over random cycles. For infinite graphs, the proof of this step uses unimodularity.

A crucial property that we use to get explicit bounds is one that random nullcycles share with simple random walks. Let $G$ be a $d$-regular rooted graph and let $W$ be a uniform random nullcycle of length $o(\sqrt{|G|})$, starting at the root. Then the expected number of visits of $W$ at any vertex of $G$ can be bounded above in terms of $\rho(G)$ (without referring to the length of the cycle). In particular, for a good expander graph, the expected number of returns of a random nullcycle is bounded. We need this property to show that a typical rewiring will not use the same short cycles over and over again. This is a technically difficult point that we tackle in Section 4.

4 Open problems

It is not clear whether the $\log\log|G|$ is optimal in Theorem 2. For all the known examples of graphs that are close to being Ramanujan, the shortest cycles with positive density are actually logarithmic.

Is there a constant $c=c(d)>0$ such that for any $d$-regular Ramanujan graph sequence $(G_{n})$, the probability that the $c\log\left|G_{n}\right|$-neighborhood of a uniform random vertex in $G_{n}$ is a tree converges to $1$?

A standard ergodicity argument says that for an ergodic unimodular random graph $G$, the weak limit of the random walk neighborhood sampling of $G$ gives back the distribution of $G$ a.s. . This suggests the following possible generalization of Theorem 5.

Let $G$ be an infinite $d$-regular rooted Ramanujan graph and let $k>0$. Let $p_{n}$ denote the probability that the random walk of length $n$ on $G$ ends on a $k$-cycle. Is it true that $p_{n}$ converges to ?

That is, is it true that the random walk neighborhood sampling of $G$ converges to $T_{d}$? The answer does not follow from Theorem 5, even when the random walk sampling converges, as the limit is only a stationary distribution on rooted graphs and is not necessarily unimodular. It would also be interesting to see whether Theorem 5 holds for stationary random graphs. The recent paper solves Problem 11 affirmatively in the case when the so-called co-growth of $G$, the exponent of the probability of return for a non-backtracking random walk, is less than $\,1/\sqrt{d-1}$. However, when the co-growth equals $1/\sqrt{d-1}$, the graph is still Ramanujan but the answer seems unclear. We thank Tatiana Smirnova-Nagnibeda for communicating this with us. After the first preprint version of this paper appeared, R. Lyons and Y. Peres, generalized our results and in particular gave a positive answer to Problem 11.

The linear lower estimate in the spectral radius in Theorem 1 seems to be sharp, but we have not been able to settle this with a suitable family of examples. The same is true for unimodular random graphs (see the first bound of (1)).

Does there exists $C>0$ such that for every $r>0$ there exists an infinite $d$-regular unimodular random graph $G$ with

such that the density of loops in $G$ is at least $r$?

One natural idea would be to use a modified universal cover of a finite $d$-regular graph of size $n$ with a loop, where we never open the loop in the cover. It looks reasonable that this cover (which is a finitely supported random rooted tree with loops) should have spectral radius around $\rho(T_{d})+C/n$.

The paper is organized as follows. Section 2 contains the basic definitions and we prove some lemmas that will be used throughout the paper. In Sections 3 and 4 we use properties of cycles in trees to study nullcycles, which are needed for Theorem 1. In Section 5 we prove Theorem 28, a more general version of Theorems 1 and 5. We also show Theorem 29, a more general version of Theorem 2. Finally, in this Section we also prove Theorem 4.

Section 6 contains a sharp bound on the spectral radius in terms of random walks on the fundamental group. Section 7 contains the proof of Theorem 3. This section is independent of the rest.

In Section 8 we give example of Ramanujan graphs with loops, and Section 9 we prove Theorem 8.

Note that one can read Section 5, and 6 independently, after reading Section 2, but reading any of these two will give help when reading the other.

An earlier version of this paper contained a generalization of Kesten’s theorem on groups. As the readership of this result is expected to be different from that of the current paper (and the current paper is already long), we decided to publish it in a separate article, see .

Preliminaries

In this section we define the notions and state some basic results used in the paper.

We follow Serre’s notation for a graph, with a modification on how to define loops. A graph $G$ consists of two sets, a set of vertices denoted by $V(G)$ and a set of edges denoted $E(G)$. For every edge $e\in E(G)$ there are vertices $e^{-}$ (the initial vertex) and $e^{+}$ (the terminal vertex). We allow $e^{-}=e^{+}$: such edge is called a loop. For every edge $e$ there is a reverse edge $\overline{e}\in E(G)$ such that $\overline{e}^{+}=e^{-}$ and $\overline{e}^{-}=e^{+}$. For a loop $e$, we allow $\overline{e}=e$; these are called half-loops. The degree of a vertex $v$ is

So half-loops contribute $1$ to the degree, but loops together with their distinct inverse contribute $2$. For spectral and random walk questions, each (non-half) loop can be replaced by two half-loops. So in this paper we will assume that all loops are half-loops.

A graph is $d$-regular, if all vertices have degree $d$.

A walk of length $n$ is a sequence of directed edges $w=(w_{1},w_{2},\ldots,w_{n})$ such that $w_{i-1}^{+}=w_{i}^{-}$ ($2\leq i\leq n$). The walk is a cycle if $w_{1}^{-}=w_{n}^{+}$. The vertices of the walk are defined by $w(i-1)=w_{i}^{-}$ and $w(n)=w_{n}^{+}$ is the end of the walk. The inverse of a walk $w$ is defined by $w^{-1}=(\overline{w_{n}},\overline{w_{n-1}},\ldots,\overline{w_{1}})$. A cycle is a nullcycle if its lift to the universal cover of $G$ stays a cycle. That is the same as saying that if we keep erasing backtracks from the cycle, we get to the empty walk. For a rooted graph $(G,o)$ we will denote the set of nullcycles of length $n$ by $\mathcal{N}_{n}$.

For a graph $G$ and $x,y\in V(G)$ let $W_{n}(x,y)$ denote the set of walks of length $n$ starting at $x$ and ending at $y$. A random walk of length $n$ starting at $x$ is a uniform random walk starting at $x$. Let $p_{n}(x,y)$ denote the probability that a random walk of length $n$ started at $x$ ends at $y$. We call $p_{n}(x,x)$ the $n$-step return probability.

When $G$ is infinite, we define the spectral radius of $G$, denoted $\rho(G)$, to be the norm of $M$. When $G$ is finite, we want to exclude the trivial eigenvalues and thus define $\rho(G)$ to be the second largest element in the set of absolute values of eigenvalues of $M$. Note that when the connected graph $G$ is bipartitie, then $-d$ is an eigenvalue with multiplicity one; this is not counted in the definition of $\rho(G)$.

In the case when $G$ is infinite and connected, one can express the spectral radius of $G$ from the return probabilities as follows:

The Markov operator $M$ is self-adjoint, so we can consider its spectral measure. This is a projection valued measure $P$ such that $P(O):l^{2}(G)\rightarrow l^{2}(G)$ is a projection for every Borel set $O\subset$. For every $f\in l^{2}(G)$ with $\left\|f\right\|_{2}=1$, the expression

defines a Borel probability measure on $$.

For graph $G$ rooted at $o$, let the spectral measure of $G$ be

where $\delta_{o}\in l^{2}(G)$ is the indicator function of $o$. The best way to visualize this measure is to look at its moments, that satisfy the following equality:

Heuristically, a unimodular random graph is a probability distribution on rooted graphs that stays invariant under moving the root to any direction. However, one has to be careful with this intuition, as direction is not well-defined and indeed, there exist vertex transitive graphs that we want to exclude from the definition. We follow [3, Section 5.2] in our definition restricted to the $d$-regular case where it is somewhat simpler.

A flagged graph is a graph with a distinguished root and a directed edge starting at the root. One can invert the flag by moving the root to the other end of the flag and switching the direction of the flag.

Let $G$ be a probability distribution on rooted $d$-regular graphs. Pick a uniform random edge from the root and put a flag on it. This gives a probability distribution $\widetilde{G}$ on flagged $d$-regular graphs. We say that $G$ is a unimodular random graph, if the distribution $\widetilde{G}$ stays invariant under inverting the flag.

That is, if some of the flagged lifts of a given rooted graph are isomorphic, we count it with multiplicity. Note that vertex transitivity in itself does not imply unimodularity. A simple example is the so-called grandmother graph. This can be obtained by taking a $3$-regular tree and directing it towards a boundary point, then connecting every vertex to the ascendant of its ascendant (its grandmother) and then erasing directions (see Figure 1).

If one does not mind working with edge directed graphs, it is easier to see the lack of unimodularity in the oriented 3-regular tree itself. There is only one type of rooted graph here that obviously appears with probability $1$. The corresponding measure on flagged graphs puts the flag on an outgoing edge with probability $1/3$, but after an inversion we see an outgoing edge with probability $2/3$. See for more about unimodularity.

Mass Transport Principle

The most useful property about unimodular random graphs (that can also be used to define them) is the Mass Transport Principle which is as follows. Let $f$ be a non-negative real-valued function on triples $(G,x,y)$ where $G$ is a $d$-regular rooted graph and $x,y\in G$ such that $f$ does not depend on the location of the root. Then the expectations

where $o$ is the root of $G$. The picture is that if one sets up a paying scheme on the random graph $G$ that is invariant under moving the root, then the expected payout of the root equals its expected income.

Benjamini-Schramm convergence

A $d$-regular graph sequence $(G_{n})$ is defined as a sequence of finite $d$-regular graphs with size tending to infinity. By a pattern of radius $r$ we mean a rooted graph where every vertex has distance at most $r$ from the root. For a finite graph $G$ and a pattern $\alpha$ of radius $r$ let the sampling probability $p(G,\alpha)$ be the probability that the $r$-ball around a uniform random vertex of $G$ is isomorphic to $\alpha$. We say that a graph sequence $(G_{n})$ is Benjamini-Schramm convergent, if $p(G_{n},\alpha)$ is convergent for every pattern $\alpha$. It is easy to see that every graph sequence has a convergent subsequence.

What is a natural limit object of a convergent graph sequence? One can also take pattern densities of a unimodular random graph $G$; there $p(G,\alpha)$ denotes the probability that the $r$-ball around the root of $G$ is isomorphic to $\alpha$. We say that a graph sequence $(G_{n})$ converges to $G$ if

Every Benjamini-Schramm convergent graph sequence has a unique limit unimodular random graph (see [3, Section 2.4]).

For a finite $d$-regular graph $G$ let $\mu_{G}$ denote the eigenvalue distribution of the Markov operator on $G$. Note that for a uniform random vertex $o$ we have $\mu_{G}={\mathbf{E}}\mu_{G,o}$. For an infinite unimodular random graph $G$ we can also define $\mu_{G}={\mathbf{E}}\mu_{G,o}$.

Let $(G_{n})$ be a sequence of finite $d$-regular graphs. Then the following are equivalent: 1) $(G_{n})$ has essentially large girth; 2) $(G_{n})$ converges to $T_{d}$ in Benjamini-Schramm convergence; 3) $\mu_{G_{n}}$ weakly converges to $\mu_{T_{d}}$.

The equivalence of 1) and 2) is immediate from the definition of Benjamini-Schramm convergence.

Assume that $(G_{n})$ converges to the unimodular random graph $G$. We claim that $\mu_{G_{n}}$ weakly converges to the expected spectral measure $\mu_{G}=\mathbf{E}\mu_{G,o}$. To check this, we can look at the $k$th moment

Recall that $p^{G}_{k}(o,o)$ denotes the probability of return of the random walk on $G$ starting at $o$. But for any graph $G$ and vertex $v$ of $G$, the return probability $p^{G}_{k}(v,v)$ only depends on the $k/2$-ball around $o$. Since there are only finitely many patterns of a given radius, this implies

where $v$ is the root of $\alpha$. Now $(G_{n})$ converges to $G$, so

where $u$ is a uniform random vertex in $G_{n}$. So, $\mu_{G_{n}}$ weakly converges to $\mu_{G}$ as claimed. Hence 2) implies 3) follows immediately.

Assume that 1) does not hold, that is, $(G_{n})$ is a graph sequence that does not have essentially large girth. Then there exists $k,\varepsilon>0$ such that the density of $k$-cycles in $G_{n}$ is at least $\varepsilon$ for infinitely many of the $G_{n}$. This implies that for these $n$,

which implies that $\mu_{G_{n}}$ does not converge weakly to $\mu_{T_{d}}$. Hence, 3) does not hold. We proved the required equivalences.

Fundamental group

Let $G$ be a graph rooted at $o$. We call two cycle starting at $o$ homotopic, if one can get one from the other by inserting and erasing backtracks, that is, walks of type $s\overline{s}$ where $s$ is an edge of $G$. Then the set of equivalence classes forms a group under concatenation, called the fundamental group $\pi_{1}(G)$. It is well known that the fundamental group of a graph without half-loops is a free group [24, Theorem 5.1]. Every half-loop adds a cyclic group of order $2$ as a free product. The most important general property of fundamental groups we shall use in this paper is that if $H$ is a subgraph of $G$, then the induced homomorphism from $\pi_{1}(H)$ to $\pi_{1}(G)$ is injective.

We start by estimating the size of $\mathcal{N}_{n}$.

see , formula (19.27). So for even $n$, by symmetry, we may write

A small computation shows that for $d\geq 3$ we have

The upper bound also holds for $n=2$. (We manually check that the lower bound of the lemma holds for $r_{2}=1/d$.) To complete the proof, we bound the lower and upper constants factors

2 Visits of cycles

Let $w_{n,k}^{+}$ be the number of such paths that stay positive after time 0. Then for $k>0$ we have

We may assume that $n$ and $k$ are the same parity. Then

which holds since the ratio of the two sides is increasing along even (respectively odd) $n$ and converges to 1. For $n$ even we now write

By the Ballot theorem (see Section 2.7.1 in ) we have

Let $w^{+}_{n,k}$ denote the number of walks of length $n$ starting at and ending at $k\geq 0$ that stay positive except perhaps at time and $n$. If $X_{m}$ is a random walk excursion of length $n$, then

For $n=2$ the claim is easy to check. For $n\geq 4$ even we have the lower bound using the Catalan number formula

where the last inequality holds since the ratio of the two sides is decreasing and converges to 1. Together with Lemma 16 this gives the bound

Let $a_{m}$ denote the last summand, even for non-integer $m$. Then for all $m\geq 1$ and $\delta\in$ we have $a_{m+\delta}\geq 2^{-3/2}a_{m}$. Thus we can bound the sum by

A random cycle is a cycle chosen from uniform measure from the set of cycles with the same starting point.

where the last inequality follows form Lemma 15. Since the summand is convex as a function of $k$, the $k$ term is bounded above by

The random cycle of length $n$ is a time-inhomogeneous Markov process. Let $p^{n}_{k}(x,y)$ be denote its transition probabilities from $x$ to $y$ at time $k$. It suffices to show that the ratios of $p^{n}_{k}(x,x_{+})/p^{n}_{k}(x,x_{-})$ converge, (where $x_{+},x_{-}$ denotes a child or the parent of $x$, respectively) as any probability of the form

we now use Theorem 19.30 in which for $x$ fixed and $n\to\infty$ gives

where $|x|$ is the graph distance of $x$ from $o$, to get

Note that when $d=2$ we get the reflected simple random walk, as expected.

Let $G$ be a $d$-regular graph, and $(\bar{X}^{n}_{k},k=0\ldots n)$ be the $k^{th}$ step of a uniformly chosen random nullcycle from a vertex $o$ to $o$. Then $\bar{X}^{n}_{k}$ converges in distribution as $n\to\infty$ to a limiting process $(\bar{X}_{k},k\geq 0)$ called the infinite nullcycle. In particular, the fixed-time distributions converge.

Properties of nullcycles

This section establishes some important properties of random nullcycles in graphs. But first we need a simple well-known lemma.

Let $G$ be a connected $d$-regular graph and let $o$ be a vertex. Let $p_{n}(o,A)$ denote the probability that a random walk of length $n$ starting at $o$ ends in the finite vertex set $A$. Then with the spectral radius $\rho(G)$ we have

We prove the claim for finite graphs, the infinite case is similar but simpler. Let $m=|G|,$ the number of vertices of $G$. Let $v_{0}$ denote the function on $G$ that takes value $1/\sqrt{m}$ everywhere. Then $v_{0}M=v_{0}$. When $G$ is not bipartite, let $l_{*}^{2}(G)$ denote the orthogonal subspace of $v_{0}$ in $l^{2}(G)$. When $G$ is bipartite, let $\mathcal{I}$ be an independent subset of $G$ of size $m/2$ containing $o$ and let $v_{1}$ be the function on $G$ that takes values $1/\sqrt{m}$ on $\mathcal{I}$ and $-1/\sqrt{m}$ otherwise. Then $v_{1}M^{n}=(-1)^{n}v_{1}$. Let $l_{\ast}^{2}(G)$ denote the subspace orthogonal to $v_{0}$ and $v_{1}$ in $l^{2}(G)$.

Now $\rho(G)$ equals the norm of $M$ on $l_{*}^{2}(G)$. Let $\delta_{A}$ denote the indicator function of the vertex set $A$. Let $v$ be a projection of $\delta_{o}$ onto $l_{*}^{2}(G)$, and let $v_{*}=\delta_{o}-v$. Then $\|v\|\leq 1$. For $G$ bipartite, we can write $v_{*}=a(v_{0}+v_{1})$, with $a=1/\sqrt{m}$. We have

Since $v_{0}$ and $v_{1}$ are orthonormal, writing $\delta_{A}$ in the orthonormal basis we see that (3) is bounded above by

Similarly, in the non-bipartite case $\langle v_{*}M^{n},\delta_{A}\rangle=|A|/m$. We now have

Here $\|\delta_{A}\|=\sqrt{|A|}$. The claim follows.

For any infinite $d$-regular rooted connected graph $(G,o)$ with $\rho(G)<1$ the number of visits $V_{A}$ to a finite vertex set $A$ of a random nullcycle of length $n$ starting at $o$ satisfies

For any finite $d$-regular graph $G$ we also have

This is at most $2\cdot 10^{7}|A|$ if $\rho(G)\leq 19/20$ and $n^{2}\leq|G|$.

Condition on $|X_{j}|$, the distance from the root, and then sum over all possible options to get

Note that given $|X_{j}|=k$, the distribution of $X_{j}$ is uniform on the $k$-sphere about $o$ in the tree. Thus the distribution on $\bar{X}_{j}$ in the graph $G$ is that of the $k$th step of a nonbacktracking random walk. So let $p_{k}$ denote the probability that the $k$th step of the nonbacktracking walk is in $A$.

the generating function for the proportion of nonbacktracking paths that start from $o$ and end in $A$. For any $z\in(0,1]$ we have

The right hand side is a power series with nonnegative coefficients, so it always makes sense but may equal $+\infty$. Rewriting our bound in terms of $\mathcal{C}$ we get

Let $\mathcal{G}(z)$ be the analogous generating function for simple random walk. It was shown in , (see formula (2.3) in ) that for any $d$-regular graph we have

for our range of parameters $d\geq 2$ and $z\in(0,1]$. We now consider two cases.

1. For $G$ infinite with $\rho=\rho(G)<1$, we use the case $z=1$, noting that the radius of convergence of $\mathcal{G}$ is $1/\rho>1$. Since $\mathcal{G}$ and its derivative are nonnegative, we get the upper bound

The last inequality uses the fact that the probability that simple random walk at time $k$ is in $A$ is bounded above by $|A|\rho^{k}$, so we can replace $\mathcal{G}^{\prime}(z)$ by $\bar{\mathcal{G}}^{\prime}(z)$. Finally, we have

2. For $G$ finite, we use the case $z<1$. Since $\mathcal{G}$ and its derivatives are nonnegative, we get the upper bound

For the last inequality, we use $\rho=\rho(G)$,

and use Lemma 21 to bound the return probabilities. This gives

since for $n\geq 1$ the $(1-1/(2n))^{-n}\leq 2$, and the claim follows.

2 Cycles and nullcycles

We now turn to the connection between ordinary cycles and nullcycles. We recall the definition of nontrivial cycles.

Call a cycle of length $k$ in a graph a nontrivial cycle if either

for some directed non-loop edge $e$, the number of times the cycle passes through $e$ differs from the number of times it passes through the reversal of $e$

Cycles not covered by this definition are called trivial. For example, nullcycles are trivial and simple cycles are nontrivial.

The following theorem is another main ingredient in the proof of Theorem 1. Let $\mathcal{N}_{n}$ denote the set of nullcycles starting at $o$ in the rooted graph $(G,o)$.

Then with $c_{1}=1/16$ and $c_{k}=(d-1)^{-k}/2$ (for $k\geq 2$) we have

where $W_{nk}(o,o)$ is the set of cycles of length $nk$ starting at $o$.

Let us denote $W=W_{nk}(o,o)$, and $\mathcal{N=N}_{nk}$, the subset of nullcycles. We first break $W$ into equivalence classes, called rewiring classes. A loop is called single if its vertex has no other loops. Otherwise, we call it a multiple loop.

When $k=1$ we break up the sum on the right of (4) into a sum over single loops and a sum over multiple loops, counted as $\chi_{1w}+\chi_{2w}=\chi_{w}$. We choose $k$ (and for $k=1$ we choose single or multiple loops), and consider rewiring classes depending on our choice.

Case $k=1$, multiple loops. Two paths are equivalent if for all times $i$ the vertices satisfy $w_{i}=w^{\prime}_{i}$, and $w$ and $w^{\prime}$ agree except at times when they traverse multiple self-loops.

Case $k\geq 2$. The paths $w$ and $w^{\prime}$ are equivalent if for all $0\leq j\leq n-1$ the following holds

If $w_{jk}\neq w_{jk+k}$ then the path segment between these times of $w$ and $w^{\prime}$ is equal.

If $w_{jk}=w_{jk+k}$ and the path segment between these times of $w$ is trivial, then it equals the corresponding path segment in $w^{\prime}$.

If $w_{jk}=w_{jk+k}$ and the path segment between these times of $w$ is nontrivial then it either equals the corresponding path segment in $w$ or is the time-reversal of that. We call $jk$ a proper cycle time of $w$, and the corresponding path segment a proper cycle of $w$.

This is illustrated in the example depicted in figure 3.

For $w\in W$ let $[w]$ denote the equivalence class of $w$, called rewiring class. Note that the rewiring defined here is more complex than the one in Section 1.3. For $w\in\mathcal{N}$ let $p(w)$ denote the probability that a uniform random element of $[w]$ is nullhomotopic.

What remains is to show that for all $w\in\mathcal{N}$ we have

Let $\tau_{i},\,i=1,\ldots,\kappa$ denote the times when $\bar{w}$ visits a reclusive vertex, and let $\phi$ be the number of loops erased from $w$ to get $\bar{w}$. Then an element of $[w]$ is determined by $X_{1},\ldots X_{\kappa}$, the number of loops inserted into $\bar{w}$ at times $\tau_{1},\ldots,\tau_{\kappa}$. A uniform random element of $[w]$ corresponds to a uniform random choice of the $X_{i}$ so that their sum is $\phi$. Let ${\mathsf{tr\,}}w$ denote the function that assigns to every reclusive loop of $[w]$ the number of times modulo $2$ that $w$ passes through it. Then

Case $k=1$, multiple loops. We call a vertex important if it has a loop traversed by $w$. Further, we call a loop important if its vertex is important (even if not traversed by $w$). Note that the set of important loops (or vertices) only depends on the equivalence class of $w$.

For a path, let ${\mathsf{tr\,}}$ denote the function that assigns to each important loop the number of times modulo $2$ that it is traversed. Consider a random element $w$ of $[w]$. For each important vertex $v$ with $k_{v}$ loops, let $\bar{X}_{v}=(X_{v,1},\ldots,X_{v,k_{v}})$ record the number of times $w$ visits its loops. Note $\bar{X}_{v}$ are independent as $v$ varies, and each have a multinomial distribution with probabilities $1/k_{v}$ for each option; each traversal is assigned to one of the loops uniformly at random.

Case $k\geq 2$. For a path, let ${\mathsf{tr\,}}$ denote the antisymmetric edge function that sums $1$ over all forward steps of a path and $-1$ over all backward steps (here ignoring self-loops). Note that the trace of a random element $w$ in $[w]$ can be written as

where the $X_{c}$ are independent random variables uniform on $\{-1,1\}$, and $\bar{w}$ denotes $w$ with all its proper cycles removed. We claim that

where $|w|_{o}$ is the maximum size of a subset of linearly independent proper cycles of $w$. Indeed, consider such a set $\mathcal{C}$, and complete it to a basis for antisymmetric edge functions. Fix all values of $X_{c}$ for $c\notin\mathcal{C}$. Then for $c\in\mathcal{C}$, looking at the a $c$-coordinate of the equation (5), we see that it can hold only if $X_{c}$ equals some fixed value, which has probability $1/2$ or , independently over the coordinates. The claim follows.

Now we have either $\chi_{1w}\geq\frac{7}{8}\chi_{w}$ or $\chi_{2w}\geq\frac{1}{8}\chi_{w}$. In either case, we get

Together with the $k\geq 2$ case, this completes the proof.

The following simple probabilistic lemma was used in the proof of Theorem 24.

Let $X=(X_{1},\ldots,X_{k})$ be a uniform random variable on the set of $k$-tuples of nonnegative integers with even sum $n\geq 2$.

(a) For any integer $k$-vector $x$ with $k\geq 2$ we have

with equality at the first location if $x=0$.

(a) (We thank P. Csikváry for this simplification of our previous proof.) To count the number of $k$ tuples that are equal to $x$ mod $2$, we subtract 1 from each odd entry and divide each resulting entry by 2. We get a bijection between such $k$-tuples and the number of $k$-tuples with entry sum $(n-o)/2$, where $o$ is the number of odd entries of $x$. Thus

This shows the first inequality. For the second, note that the right hand side equals

Each factor is at most $1-\frac{n/2}{n+k-1}$, giving a bound of

(b) Let $\bar{X}$ denote the vector formed by the sums of the entries of $X$ over the parts of our partition. Let $M\subset\{1,\ldots,k\}$ be a subset of indices, one in each part, and let $M^{\prime}$ be its complement. Let $S=\sum_{i\in M}X_{i}$. Then

We compute the ratio of these probabilities for two consecutive values of $s$

the whole expression in (7) is bounded above by $3/4$. Now note that from $s=s_{0}$ down the probability of $S=s$ decreases by at least a factor of $3/4$. So

Condition on the random variables in $X_{M}^{\prime}=(X_{i},i\in M^{\prime})$. Given this information the random variable $X_{M}=(X_{i},i\in M)$ is uniform on the set of $k$-tuples of nonnegative integers with sum $S$.

The inequality follows from part (a). The last conditional probability depends only on the value of $S$. Using part $(a)$ we can break the expression up with $s=s_{0}/2$ as

We increase the prefactor $5$ to $14$ in order to get a trivial bound when (8) fails.

Explicit bounds on the spectral radius

By Theorem 24 and the inequality of arithmetic and geometric means we have

Taking expected value of both sides over the random graph we get

We will use the Mass Transport Principle to show that the expression

does not depend on the position $j$. Let the mass transport be defined as

That is, for every nullhomotopic path $w$ starting at $x$, $x$ sends mass $\chi(w,0,k)$ to the $(n-j)k$-th position of $w$. The second equality follows by rooting the path at $y$ instead of $x$. Trivially, the mass transport does not depend on the root of $G,$ so the Mass Transport Principle gives us

that is, the expected mass sent from the root equals the expected mass received by the root. Plugging in the corresponding equations, we get

and we get that the expression (9) does not depend on $j$. This proves the theorem.

We may assume $\gamma_{k}(G,o)\geq 1$, otherwise the claim is trivial. In this Lemma $G$ is fixed, so the probabilistic language for nullcycles will not cause confusion. So let $w$ be a uniform random element of $\mathcal{N}_{n}$.

and the inequality uses both sides of Lemma 15 (but one side in the special case $n=2k$). So if $G$ has $\gamma_{k}(G,o)$ cycles of length $k$ at $o$, then the event $A$ that $w$ passes through one of them in the first $k$ steps satisfies ${\mathbf{P}}A\geq p\gamma_{k}(G,o)$. Let $V_{o}$ be the number of times the random nullcycle $w$ traverses $o$. By Proposition 22 we have

This implies (using probabilistic notation for averaging over $\mathcal{N}_{n}$)

2 Main bounds on spectral radius

The following theorem implies Theorems 1 and 5.

Let $(G,o)$ be a $d$-regular unimodular random graph and let $k\geq 1$. Let $\gamma_{k}(G,o)$ be the number of nontrivial cycles of length $k$ starting at $o$. Let

Let $G$ be a finite connected $d$-regular graph with $|G|\geq d^{7}$. Then for the root $o$ chosen uniformly at random we have

In particular, for finite Ramanujan graphs with $|G|\geq d^{7}$ we have

Let $nk$ be even and $n\geq 1$. First assume that $G$ which may be finite or infinite satisfies ${\mathbf{P}}(|G|\geq(nk)^{2})=1$. We will use Lemma 27, which requires $\rho(G)\leq 19/20$. We first take care of the other case. For (10) and (11) we need tho show for every such $G$ we have

Since $\gamma_{k}(G)\leq d^{k}$, this inequality follows from

For the first claim (11), we divide (13) by $nk$ and use the bounded convergence theorem. The second claim (10) follows from the fact that for $G$ ergodic $\rho(G)$ is constant.

The bound on $\mathcal{N}_{n}$ of Lemma 15 now shows that

which follows from $\rho(G)^{2}+2/|G|\geq p_{2}(o,o)\geq 1/d$, a consequence of Lemma 21. Note that a lower bound on $|G|$ is needed for (15) since the complete graph with loops has $|G|=d$ and $\rho(G)=0$.

Assume $|G|\geq d^{7}$, and $\log_{d-1}|G|\geq 10k$. Set $n=2\lceil\frac{1}{2k}\log_{d-1}|G|\rceil$ so that

(Here the power $5/6$ from (15) is used to offset the effect of $\lceil\cdot\rceil$, and thus yield a cleaner final bound). By Lemmas 15 and 21, the left hand side of (14) is at most

We use this and divide (14) by $nk$ and get the lower bound

This proves (11) for the case $\log_{d-1}|G|\geq 10k$.

as long as $\log_{d-1}|G|\geq 10$. For $d\geq 4$, (15) can be improved to

and this yields that (17) holds as long as $\log_{d-1}|G|\geq 6$. So both for $d=3$ and $d\geq 4$ we get that (17) holds as long as $|G|\geq d^{7}$. Equation (17) implies (11) if

With the trivial bound $\gamma_{k}(G,o)\leq d(d-1)^{k-1}$, in the case $\log_{d-1}|G|\leq 10k$ this is implied by

3 Bounds for graphs close to the Ramanujan threshold

Let $\alpha>0$, $d\geq 3$ and consider finite, connected $d$-regular graphs $G$ that are close to Ramanujan in the sense that

Fix $\beta,\varepsilon>0$ so that $\beta+\varepsilon<\frac{\alpha\wedge 1}{6\log(d-1)+8\log 2}$, (for example $\beta=\frac{\alpha\wedge 1}{16\log(d-1)}$). Then as $|G|\to\infty$, the proportion of vertices in $G$ whose $\beta\log\log|G|$-neighborhood is not a $d$-regular tree is $o((\log|G|)^{-\varepsilon})$.

Note that if the $k=\beta\log\log|G|$ neighborhood of a vertex $v$ is not a tree, then $v$ is contained in a nontrivial cycle of length $2k$, or its $k$-neighborhood contains a vertex with a loop. We rule out these two cases separately.

so if $k=2\beta\log\log|G|$, then the dominant factor is

and this is $o(\log|G|^{-\varepsilon^{\prime}})$ for some $\varepsilon^{\prime}>\varepsilon$ since

The inequality also holds uniformly for all smaller $k$ (with a uniform constant in the $o(\cdot)$ term), and summing over all such we get that the expected number of nontrivial cycles at $o$ of length at most $2k$ is $o(\log|G|^{-\varepsilon}\log\log|G|)\to 0$. This rules out the first option.

For the second option, we use a simple mass transport argument (see the proof of Theorem 24 for the formal setup). Let each vertex with a loop send mass $k$ to all elements in its $k$-neighborhood. Then the expected amount of mass sent is at most $d(d-1)^{k-1}{\mathbf{E}}\gamma_{1}(G)$. The amount of mass received is the number of vertices with loops in the $k$-neighborhood, lets call this $N$. So we have

By the same argument as before, this is $o(\log|G|^{-\varepsilon})$ with the above choice of $\beta$.

4 Weakly Ramanujan sequences

We are ready to prove that a $d$-regular weakly Ramanujan sequence of finite graphs converges to the $d$-regular tree.

Let $(G_{n})$ be a weakly Ramanujan sequence of finite $d$-regular graphs. Assume by contradiction, that it does not have essentially large girth. Then, by passing to a suitable subsequence, there exists $c>0$ and $L>0$ such that the cycle densities $\gamma_{L}(G_{n})>c$.

By passing to a subsequence, we can also assume that $(G_{n})$ is Benjamini-Schramm convergent. Let $G$ be the limit of $(G_{n})$.

We claim that $G$ is infinite a.s. Assume this is not the case, then there exists $R>0$ such that $G$ has size $R$ with probability $p>0$. This means, that with probability at least $p$, the $R+1$-ball around the root has the same size as the $R$-ball. So, for large enough $n$, the same holds for all $G_{n}$ with $p/2$. That is, at least $\left|G_{n}\right|p/2$ vertices lie in a connected component of size at most $R^{\prime}$, where $R^{\prime}$ is the size of the $R$-ball in the $d$-regular tree. This implies that the number of connected components of $G_{n}$ is at least $\left|G_{n}\right|p/2R^{\prime}$, hence,

This contradicts the assumption that $(G_{n})$ is weakly Ramanujan. So, our claim holds.

We claim that $G$ is Ramanujan a.s. By the proof of Proposition 14, $\mu_{G_{n}}$ weakly converges to the expected spectral measure $\mu_{G}$, which yields $\mu_{G}([-\rho(T_{d}),\rho(T_{d})])=1$, and this implies that $\mu_{G,o}([-\rho(T_{d}),\rho(T_{d})])=1$ a.s. Since the spectral radius equals the radius of the support of the spectral measure $\mu_{G,o}$ for any rooted connected graph $G$ (see [16, Lemma 2.1]), this implies that $\rho(G)\leq\rho(T_{d})$ a.s. and our claim holds.

Now using Theorem 5, $G=T_{d}$ a.s., that is, $(G_{n})$ converges to $T_{d}$ and so by Proposition 14, it has essentially large girth, a contradiction. Our theorem holds.

Spectral radius and the fundamental group – a sharp bound

In this section we analyze the spectral radius of a fixed rooted $d$-regular infinite graph using random walks on its fundamental group.

Let $G$ be a graph, let vertices $x,y\in V(G)$ and $k>0$ let $W=W_{k}(x,y)$ denote the set of walks of length $k$ in $G$ starting at $x$ and ending at $y$. Let $o\in V(G)$, let $u$ be a walk from $o$ to $x$ and let $v$ be a walk from $y$ to $o$. When $W$ is non-empty, let

Now $\kappa_{k}(x,y)$ does not depend on the choice of $o\,,u$ and $v$, because the multi-set

(defined with multiplicites), so the corresponding Markov operator is the conjugate of the operator belonging to $WW^{-1}$ by the fixed element $u$.

Note that the norm $\kappa_{k}$ satisfies

Let $\mathcal{N}_{k}$ denote the set of nullcycles of length $k$ starting at $o$ (see Definition 9). The following lemma relates $\left|\mathcal{N}_{k}\right|/\left|W_{k}(o,o)\right|$, the probability that a random cycle of length $k$ is a nullcycle to the spectral radius $\kappa_{k}$. This relation can be established also with respect to paths connecting two vertices.