Cutoff for Ramanujan graphs via degree inflation
Jonathan Hermon








Cutoff for Ramanujan graphs via degree inflation
    Jonathan Hermon

Faculty of mathematics and computer science, Weizmann Institute of Science, Rehovot, Israel. E-mail: jonathah@weizmann.ac.il.
    
==================================================================================================================================================




Recently Lubetzky and Peres showed that simple random walks on a sequence of d-regular Ramanujan graphs G_n=(V_n,E_n) of increasing sizes exhibit cutoff in total variation around the diameter lower bound d/d-2log_d-1|V_n|. We provide a different argument  under the assumption that for some r(n) ≫ 1 the maximal number of simple cycles in a ball of radius r(n) in G_n is uniformly bounded in n.





  
*Keywords:
Cutoff, Ramanujan graphs, degree inflation.






§ INTRODUCTION
 

Generically, we denote the stationary distribution of an ergodic Markov chain (X_t)_t ≥ 0 by π,  its state space by Ω and its transition matrix by P. We denote by _x^t (resp. _x) the distribution of X_t (resp. (X_t)_t ≥ 0), given that the initial state is x. The total variation distance of two distributions on Ω is μ - ν_=1/2∑_y | μ(y)-ν(y)|. The total variation ϵ-mixing time is (ϵ):= inf{t: max_x _x^t - π_≤ϵ}.    
Next, consider a sequence of chains, ((Ω_n,P_n,π_n))_n ∈,
each with its 
mixing  time t_mix^(n)(·). We say that the sequence exhibits a cutoff if the
following
sharp transition in its convergence to stationarity occurs:

    ∀∈ (0,1/2],   lim_n →∞t_mix^(n)(ϵ)/t_mix^(n)(1-ϵ)=1.

A family of d-regular graphs G_n with d ≥ 3 is called an expander family, if the second largest eigenvalues of the corresponding adjacency matrices are uniformly bounded away from d. Lubotzky, Phillips, and Sarnak <cit.>
defined  a connected finite d-regular graph G with d ≥ 3 to be Ramanujan if the eigenvalues of the transition matrix of simple random walk (SRW) on G all lie in {± 1}∪ [-ρ_d,ρ_d], where ρ_d:=2√(d-1)/d is the spectral radius of SRW on the infinite d-regular tree 𝕋_d. Lubotzky, Phillips, and Sarnak <cit.>, Margulis <cit.> and Morgenstern <cit.> constructed d-regular Ramanujan graphs for all d of the form d=p^m+1, where p is a prime number. Recently, Marcus,  Spielman and Srivastava <cit.> proved the existence of bipartite d-regular Ramanujan graphs for all d ≥ 3.  In light of the Alon-Boppana bound <cit.>, Ramanujan graphs are “optimal expanders" as they have asymptotically the largest spectral-gap.

Let G_n=(V_n,E_n) be a sequence of finite connected d_n-regular graphs. Let P_n be the transition matrix of SRW on G_n. Denote the eigenvalues of P_n by 1=_1(n)>_2(n) ≥⋯≥_|V_n|(n) ≥ -1. We say that the sequence is asymptotically Ramanujan if |V_n| →∞ and 
    max{|_i(n)|:| _i(n) |≠ 1 }≤ρ_d_n^1-o(1) .
 We say that the sequence is asymptotically one-sided Ramanujan if |V_n| →∞, _2(n) ≤ρ_d_n^1-o(1) and lim inf_n →∞min{_i(n): _i(n) ≠ -1 }>-1.  Friedman <cit.> showed that a sequence of d-regular random graphs of increasing sizes is w.h.p. asymptotically Ramanujan.



Our definition of asymptotically Ramanujan graphs is not the standard one. The more standard definition is that  max{|_i(n)|:| _i(n) |≠ 1 }≤ρ_d_n+o(1).


It is elementary to show that for every n-vertex d-regular graph, the 1-ϵ total variation mixing time for the SRW is at least t_d,,n:=d/d-2log_d-1n-C√(n |logϵ|/d), for some constant C>0.[This can be derived from the fact that C can be chosen so that the probability that the probability that the distance of the walk at time t_d,,n   from its starting point is at least ⌊log_d-1(1/4 n)⌋ with probability at most /2 (together with the fact that a ball of radius ⌊log_d-1(1/4 n)⌋ contains at most 1/2 n vertices).] The following precise formulation of this fact is due to Lubeztky and Peres
<cit.>. 


Let G=(V,E) be an n-vertex  d-regular graph with d ≥ 3.  Let c_d:=2√(d(d-1))/(d-2)^3/2 and Φ^-1 be the inverse function of the CDF of the standard Normal distribution.  Then SRW on G satisfies  

    ∀ϵ∈ (0,1),   (1- ϵ -o(1) ) ≥d/d-2log_d-1n+c_dΦ^-1(ϵ)√(log_d-1n) .



Recently, Lubetzky and Peres <cit.> showed that simple random walks on a sequence of non-bipartite  d_n-regular Ramanujan graphs  G_n=(V_n,E_n)  of increasing sizes exhibit cutoff  around the diameter lower bound d_n/d_n-2log_d_n-1|V_n|. In this work we present an alternative argument and prove the same result under the following assumption:



Assumption 1: There exists a diverging sequence r_n such that the maximal number of simple cycles in a ball of radius r_n in G_n is uniformly bounded in n.


Let G_n=(V_n,E_n) be a sequence of non-bipartite, finite, connected, d_n-regular asymptotically one-sided Ramanujan graphs.


  (i) If d_n=d for all n and Assumption 1 holds then the corresponding sequence of simple random walks exhibits cutoff around time d/d-2log_d-1|V_n|. 

  (ii) If d_n diverges and log d_n =o(log_d_n|V_n|) then the corresponding sequence of simple random walks exhibits cutoff around time log_d_n|V_n|.



 If there is no cutoff, then cutoff must fail on some subsequence (n_k) such that either lim_k →∞d_n_k=∞ or d_n_k=d for all k for some fixed d ≥ 3. Thus there is no loss of generality in assuming that either lim_n →∞d_n=∞ or d_n=d for all n. 

Assumption 1 is rather mild as it is quite difficult to construct a family of asymptotically one-sided Ramanujan graphs violating this assumption. In particular, it is satisfied w.h.p. by a sequence of random d-regular  graphs of increasing sizes <cit.>. It follows from <cit.> that if G_n is a sequence of d-regular transitive asymptotically Ramanujan graphs of increasing sizes then lim_n →∞girth(G_n) = ∞, where for a graph G, girth(G) denotes its girth[The girth of a graph G is the length of the shortest cycle in G.] (and so Assumption 1 holds).  



The argument of Lubetzky and Peres <cit.> does not require Assumption 1 (nor the assumption log d_n =o(log_d_n|V_n|)). They studied the Jordan decomposition of the transition matrix of the non-backtracking walk[This is a random walk on the directed edges of the graph, with transition matrix P_NB((x,y)(z,w))=1_z=y,w ≠ x/(y)-1.] and used it to derive cutoff for the non-backtracking walk, which for a regular graph implies cutoff also for the SRW. In this note we study the SRW by looking at it only when it crosses distance k from its previous position, for some large k.  



 §.§ Organization of this note

In  <ref>, as a warm up, we present an extremely simple and short proof for the occurrence of cutoff for SRW on  a sequence of asymptotically  Ramanujan graphs of diverging degree. In  <ref> we present some machinery for bounding mixing times using hitting times. We then apply this machinery to prove Part (ii) of Theorem <ref>. In  <ref> we give an overview of the proof of Part (i) of Theorem <ref>. In  <ref> we prove two auxiliary results. Finally, in  <ref> we conclude the proof of Theorem <ref>.  



§ A WARM UP


It turns out that  for a sequence of asymptotically  Ramanujan graphs of diverging degree the trivial diameter lower bound (of Lemma <ref>) is matched by the  trivial spectral-gap upper bound on the L_2 mixing time obtained via the Poincaré inequality. As a warm up and motivation for what comes we now prove the following theorem.


Let G_n=(V_n,E_n) be a sequence of non-bipartite, finite, connected, d_n-regular asymptotically  Ramanujan graphs with d_n →∞. Then the corresponding sequence of simple random walks exhibits cutoff around time log_d_n|V_n|.

Note that in Part (ii) of Theorem <ref> the graphs are assumed to be only asymptotically one-sided Ramanujan. Before proving Theorem <ref> we need a few basic definitions and facts. Let 
    :=max{|a|:a ≠ 1, a  is an eigenvalue of P }  and  :=1/1-.
 The L_2 distance of _x^t from π is defined as  
    _x^t-π_2,π^2=∑_y π(y) ( P^t(x,y)/π(y))^2-1.
 By Jensen's and the Poincaré inequalities, for all t and x  we have that 
    4 _x^t-π_^2 ≤_x^t-π_2,π^2 ≤^2t_x^0-π_2,π^2 ≤^2t/π(x).
 Hence for SRW on an n-vertex regular graph we have for all t and x that 

    4 _x^t-π_^2 ≤  n ^2t⟹(ϵ) ≤1/2log_1/(n ϵ^-2).


Proof of Theorem <ref>:
 By assumption  = ρ_d_n^1-o(1) =d_n^-1/2(1-o(1)).  Thus 1/2log_1/|V_n| =(1+o(1)) log_d_n|V_n|. The proof is concluded by combining (<ref>) with Lemma <ref>. 



§ REPLACING THE POINCARÉ INEQUALITY BY ITS HITTING TIME ANALOG


In the proof of Theorem <ref> we exploit the general connection between mixing times and escape times from small sets, established in <cit.> (Corollary 3.1 eq. (3.2)): There exists some absolute constant C>0 such that for every reversible chain (with a finite state space), 
    ∀ α, ϵ∈ (0,1),   (ϵ + α) ≤_1-α(ϵ)+C log (1/α),

where _1-α(ϵ):=inf{t:max_x,A: π(A) ≤α_x[T_A^c>t] ≤} and T_B:=inf{t:X_t ∈ B } is the hitting time of the set B. In the proof of Theorem <ref> we replace the naive L_2 bound used in the proof of Theorem <ref> by its  hitting time counterpart: Under reversibility, for all A ⊊Ω,  a ∈ A and t ≥ 0

    π_A(a)(_a[T_A^c>t])^2≤∑_b ∈ Aπ_A(b)( _b[T_A^c>t] )^2=   P_A^t 1_A _2, A^2 ≤ [(A)]^2t,

where π_A is π conditioned on A, P_A is the restriction of the transition matrix P to A (this is the transition matrix of the chain which is “killed" upon escaping A), f_2,A^2:=∑_b ∈ Aπ_A(b)f^2(b) for f ∈^A and (A) is the largest eigenvalue of P_A. 

The following proposition relates (A) to _2, the second largest eigenvalue of P. 



For every reversible Markov chain and any set A,  

    (A) ≤_2+π(A),

 
Similarly to (<ref>), by (<ref>)-(<ref>) we have for every reversible chain on a finite state space with _2<1/2 and every α∈ (0,_2] that

    _1-α(√(α)) ≤1/2 | log_1/2 _2(min_v π(v))|, 
    
       (2 √(α)) ≤1/2 | log_1/2 _2(min_v π(v))|+C log (1/α).

We are now in a position to give a short proof for Part (ii) of Theorem <ref>.

Let G_n=(V_n,E_n) be a sequence of non-bipartite, finite, connected, d_n-regular asymptotically one-sided Ramanujan graphs. Assume that d_n diverges and log d_n =o(log_d_n|V_n|). Let α=α_n=d_n^-1/2=o(1). Let _2=_2(n) be the second largest eigenvalue of the transition matrix of SRW on G_n. By our assumptions  2 _2=d_n^-1/2+o(1)
and so by (<ref>) we have that 
    (2 √(α)) ≤1/2log_1/2 _2|V_n|+C 'log (1/α)=(1+o(1))log_d_n|V_n| .

The proof is concluded using Lemma <ref>.
 


§ DEGREE INFLATION


The simple proof of Part (ii) of Theorem <ref> motivates looking at the following graph.



Given a graph G=(V,E), we define G(k)=(V,E(k)) via 
    E(k):={{u,v } : dist_G(u,v)=k,  u,v ∈ V },
 where dist_G(u,v) denotes the graph distance of u and v w.r.t. G. Denote the transition matrix of SRW on G(k) by K.



 Consider SRW on G, (X_t)_t=0^∞.  Let T_0:=0 and inductively set T_i+1:=inf{t ≥ T_i : dist_G(X_T_i+1,X_T_i)=k }. Consider the chain 𝐘:=(Y_j)_j=0^∞ defined via Y_i:=X_T_i for all i, and denote its transition matrix by W.



It is possible that G(k):=(V,E(k)) is not connected. This could be rectified, say by connecting every vertex to its entire k-neighborhood. However, below we only use the fact that the SRW on G(k) is reversible w.r.t. π_G(k)(x):=_G(k)(x)/(2|E(k)|).

Let G=(V,E) be a d-regular finite Ramanujan graph. Assume that Assumption 1 holds. Let r=r_n be as in Assumption 1. Fix some k=k_n such that 1 ≪ k ≪√( r). 


Let K,W and T_i be as in Definitions <ref> and <ref>.
By Assumption 1, for every x,y ∈ V of distance k from one another 1 ≤ K(x,y)d(d-1)^k-1≤ C_1(d). In Lemma <ref> we show that for such x,y also 1 ≤ W(x,y)d(d-1)^k-1≤ C_2(d). In fact, Assumption 1 could have been replaced by the assumption that max{W(x,y),K(x,y) }≤ (d-1)^-k(1-o(1)) and that T_1 is concentrated around dk/d-2 (uniformly for all initial states).



 §.§ An overview of the proof of Part (i) of Theorem <ref>

Let G,k and r be as above.
Intuitively,  if either the SRW on G(k) or  the chain 𝐘 (from Definitions <ref> and <ref>) exhibit an abrupt convergence to stationarity around time t=t_n, then  also the  SRW on G should exhibit an abrupt convergence to stationarity around time t ·d/d-2k. The term d/d-2k comes from the fact that (by Assumption 1) the expected time it takes the walk on G to get within distance k from its current position is d/d-2k(1+o(1)).

While the chain 𝐘 is more directly related to the SRW on G, it is harder to analyze it directly since it need not be reversible and a-priori it is not clear that its stationary distribution is close to the uniform distribution. Instead we analyze the walk on G(k) and use it to learn about 𝐘 and then in turn about the walk on G.  




In light of Part (ii) of Theorem <ref> (which has already been proven)  a natural strategy for proving Part (i) of Theorem <ref> is to show that  
 _2(K) = ρ_D^1-o(1)=(d-1)^-k/2(1-o(1)), where D is the maximal degree in G(k), K is the transition matrix of  SRW on G(k)   and _2(K) is its second largest eigenvalue. Unfortunately, we do not know how to show this (see the first paragraph of  <ref>). Instead, we obtain such an estimate for _K(A), the largest eigenvalue of K_A, the restriction of K to A, for any “small" set A. By small we mean that its stationary probability is at most α:=(d-1)^-3k^2. 
Indeed,
the key to the proof of Part (i) of Theorem <ref> is to show that _K(A) ≤ (d-1)^-k/2(1-o(1))     for every small set A. Using (<ref>) we get for the walk on G(k) that  _a[T_A^c>(1+o(1))1/klog_d-1|V| ]=(d-1)^-k/2(1-o(1)). We then show that the same holds for 𝐘 (this is obvious when 2k < girth(G); The general case is derived using the fact that, as mentioned in Remark <ref>, c W(x,y) ≤ K(x,y) ≤ CW(x,y) for all x,y). Finally,  using an obvious coupling between  𝐘 and the SRW on G, after multiplying by d/d-2k (1+o(1)) the last bound is transformed into a bound on  _1-α(o(1)) for SRW on G (for some o(1) terms).



§ AUXILIARY RESULTS

 
    In order to control _K(A) (for small A), apart from Proposition <ref> we need the following comparison result. While there are similar comparison techniques for the spectral-gap, we are not aware of a comparison technique which allows one to argue that _2  (the second largest eigenvalue of the transition matrix) of one chain is close to 0 (say, that _2=o(1)) if that of another chain is close to 0.




Let P^(1) and P^(2) be two transition matrices on the same finite state space Ω, both reversible w.r.t. π^(1) and π^(2), respectively. Assume that P^(1)(x,y) ≤ C_1 P^(2)(x,y) and 1/C_2 ≤π^(1)(x)/π^(2)(x) ≤ C_2 for all x,y. Let A ⊊Ω and let _P^(i)(A) be the largest eigenvalue of P_A^(i), the restriction of P^(i) to A (i=1,2).  Then

    _P^(1)(A) ≤ C_1 C_2^2 _P^(2)(A).


Proof:
Denote ⟨ f,g⟩_π_A^(i):=∑_x∈ Aπ_A^(i)(x)g(x)f(x). By the Perron-Frobenius Theorem 
    _P^(1)(A)=max_f ∈_+^A,f ≠ 0⟨ P_A^(1)f,f⟩_π_A^(1)/⟨ f,f⟩_π_A^(1)≤ C_1C_2^2 max_f ∈_+^A,f ≠ 0⟨ P_A^(2)f,f⟩_π_A^(2)/⟨ f,f⟩_π_A^(2) =C_1C_2^2 _P^(2)(A).

Before proving Theorem <ref> we need one more lemma.


Let G=(V,E) be a  d-regular graph (d ≥ 3). Let v ∈ V. For  i,k ∈   let D_i:={u ∈ V : dist_G(u,v)=i },  B_i:=∪_j=0^i D_j (the ball of radius i around v) and 

    t(B_k):=|{{x,y}∈ E:y ∈ B_k-1,x ∈ B_k }|-|B_k|.

 For any s ≥ 0 there exist some  constant C(s,d)>0 and k_s such that if k ≥ k_s, t(B_k) ≤ s and D_k ≠ then 
    1/d(d-1)^k-1≤min_u ∈ D_k _v[T_D_k=T_u] ≤max_u ∈ D_k _v[T_D_k=T_u] ≤C(s,d)/d(d-1)^k-1.
  


 
Let u ∈ D_k. We first prove that _v[T_D_k=T_u] ≥1/d(d-1)^k-1. This follows from a standard argument involving the covering tree of G.  
A non-backtracking path of length ℓ is a sequence of vertices (v_0,v_1,…,v_ℓ) such that {v_i,v_i-1}∈ E and v_i+2≠ v_i for all i. Let 𝒫_ℓ be the collection of all non-backing paths of length ℓ starting from v. Let 𝕋_d be the (infinite) d-regular tree. We may label the ℓth level of 𝕋_d by the set 𝒫_ℓ (in a bijective manner) such that the children of  (v,v_1,…,v_ℓ) are {(v,v_1,…,v_ℓ,v'):(v,v_1,…,v_ℓ,v') ∈𝒫_ℓ+1}. For  γ= (v,v_1,…,v_ℓ) let ϕ(γ):=v_ℓ. Note that if (S_n)_n=0^∞ is a SRW on  𝕋_d (labeled as above) started from (v) (which is the root) then (ϕ (S_n))_n=0^∞ is a SRW on G started from v. Denote the law of (S_n)_n=0^∞ by ℙ_v.   

 Fix some γ:= (v,v_1,…,v_k) ∈𝒫_k such that v_k=u. Finally, observe that 
    _v[T_D_k=T_u] ≥ℙ_v[T_𝒫_k= T_γ  ]=1/|𝒫_k|=1/d(d-1)^k-1.


We now prove that _v[T_D_k=T_u] ≤C(s,d)/d(d-1)^k-1. We prove this  by induction on s. The base case t(B_k)=0 is trivial (it holds with C(1,d)=1). Now consider the case that t(B_k)=s>0. Let z ∈ D_k be such that _v[T_D_k=T_z] =max_u ∈ D_k _v[T_D_k=T_u]. For an edge e:={x,y}∈ E  let G_e:=(V,E ∖{e} ) be the graph obtained by deleting e from G. Let H_e:=(V_e,E_e) be the graph obtained from G_e by connecting x (resp. y)  to the root of a  d-ary tree[The root of a d-ary tree is of degree d-1.] 𝒯_x (resp. 𝒯_y). Denote the law of SRW on H_e by P^(e). Let D_i^(e):={u ∈ V_e : dist_H_e(u,v)=i } and B_k^(e):=∪_i=0^k D_i^(e).   We now show that there is some constant K(s,d) and an edge  e={x,y}∈ E belonging to some cycle in B_k such that x ∈ B_k,y ∈ B_k-1 and

    _v[T_D_k=T_z] ≤ K(s,d)P_v^(e)[T_D_k^(e)=T_z].
   
Once this is established, invoking the induction hypothesis concludes the induction step. 

Consider an arbitrary cycle in B_k with at most one vertex in D_k. Let x be the vertex of the cycle which maximizes _x[T_D_k=T_z]. Let e={x,y},e'={x,y'} be the two edges of the cycle which are incident to x. Without loss of generality, let e be the one through which x  is less likely to be reached. More precisely, assume that
 
    _v[X_T_x-1=y,T_x ≤ T_D_k] ≤_v[X_T_x-1=y',T_x ≤ T_D_k].

Also, by the choice of x we have that
 
    _x[T_D_k=T_z] ≥_y[T_D_k=T_z].

Note that if x ∈ D_k and x ≠ z then _v[T_D_k=T_z] =P_v^(e)[T_D_k^(e)=T_z]. If x=z then by (<ref>) _v[T_D_k=T_z] ≤ 2 P_v^(e)[T_D_k^(e)=T_z]. Now consider the case that x ∉ D_k. Denote T_x,y:=min{T_x,T_y} and T_x^+:=inf{t>0:X_t=x }.  Observe that 
    _v[T_D_k=T_z<T_x,y ] = P_v^(e)[T_D_k^(e)=T_z<T_x,y ].
 Thus in order to conclude the proof of (<ref>) it remains only to show that 
    _v[T_D_k=T_z>T_x,y ]  ≤C̃(s,d) P_v^(e)[T_D_k^(e)=T_z>T_x,y ].
 By  (<ref>) we have that 
    _v[T_x < min{ T_D_k,T_y} ] ≥_v[T_y<T_x <  T_D_k ] ≥1/d_v[T_y <  T_D_k ].

Thus _v[T_x <  T_D_k ] ≥2/ d_v[T_y <  T_D_k ].
By  (<ref>) we get that 
    _v[T_x <  T_D_k =T_z]=_v[T_x <  T_D_k ]_x[  T_D_k =T_z] ≥2/ d_v[T_y <  T_D_k ]_y[  T_D_k =T_z]

=2/d_v[T_y <  T_D_k =T_z]. Hence, there exists some constant M(s,d) such that
 
    _v[T_D_k=T_z>T_x,y] ≤_v[T_D_k=T_z>T_x]+_v[T_D_k=T_z>T_y]   
       ≤ (1+d/2)_v[T_D_k=T_z>T_x] ≤ (d+2)  _v[T_D_k=T_z, T_x < min{ T_D_k,T_y}]   
    
       ≤ M(s,d)  _v[T_x < min{ T_D_k,T_y}]_x[T_D_k=T_z,min{T_x^+,T_y} >  T_D_k] 
    
       ≤ M(s,d)P_v^(e)[T_x < min{ T_D_k^(e),T_y}]P_x^(e)[T_D_k^(e)=T_z<  T_x^+] 
       ≤ M(s,d) P_v^(e)[T_D_k^(e)=T_z>T_x,y ],

 where in the second inequality we have used the fact that _x[min{T_x^+,T_y} >  T_D_k] ≥ c(s,d) for some constant c(s,d)>0[This could be proved by induction on s.]  and that by the choice of x (namely, by (<ref>)) we have that _y[T_D_k=T_z| T_x>  T_D_k  ] ≤_x[T_D_k=T_z ]=_x[T_D_k=T_z| T_x^+>  T_D_k  ] and so 
    _x[T_D_k=T_z|min{T_x^+,T_y} >  T_D_k  ] ≥_x[T_D_k=T_z| T_x^+>  T_D_k  ]  = _x[T_D_k=T_z ].

 We leave the missing details as an exercise. Finally, combining (<ref>) and (<ref>) yields (<ref>).        
 


§ PROOF OF THEOREM <REF>


Part (ii) was proven in  <ref>. Let G_n=(V_n,E_n) be a sequence of non-bipartite, finite, connected, d-regular asymptotically one-sided Ramanujan graphs satisfying Assumption 1. Let  r_n →∞ be as in Assumption 1. Pick some k=k_n →∞ such that k_n^2=o(r_n).  From this point on we often suppress the dependence on n from our notation. Denote the transition matrix of SRW on G (resp. G(k)) by P (resp. K) and its stationary distribution by π (resp. π_G(k)). Let A be an arbitrary set such that π(A) ≤α=α_n:=d^-3k^2.    Denote Q:=P^k+2k^2. 

Before proceeding with the proof, we explain the choice of k+2k^2 in the definition of Q. In order to obtain an upper bound on _K(A) we shall apply Proposition <ref> with P^t (for some t) and K in the roles of P^(2) and P^(1) (respectively) from Proposition <ref>. The obtained estimate is useful only when t ≥ c k^2. Heuristically, this is related to the fact that a SRW on a d-regular tree is much more likely to be at time t at some given vertex of distance O(√(t)) from its starting point, than at some other given vertex at distance ≫√(t) from its starting point (and we want k = O(√(t))).



Recall that ρ_d:=2√(d-1)/d. Let _2 and _2' be the second largest eigenvalues of P and Q, respectively. Since _2= ρ_d^1-o(1), by decreasing k if necessary, we may assume that _2 ≤ρ_d^1-1/3k^2 log d. By Proposition <ref> (using the notation from there) and our choice of α,   
    _Q(A) ≤_2' + α =_2^k+2k^2+ α≤ C_1 ρ_d^k+2k^2.
  

 Let (S_t)_t=0^∞ be SRW on 𝕋_d,  the infinite d-regular tree rooted at o. 
 Denote its transition kernel by  P_𝕋_d. Denote the ith level of 𝕋_d by ℒ_i. Let S̃_t be the level S_t belongs to. Let v ∈ℒ_k. Let T_0^+:=inf{t>0:S̃_t=0}. Then by Lemma <ref> (second inequality)

    |ℒ_k|P_𝕋_d^k+2k^2(o,v)=_0[S̃_k+2k^2 =k  ] ≥_0[S̃_k+2k^2 =k,T_0^+>k+2k^2  ]  
       ≥ c_0 k^-2 2^k+2k^2(d-1)^k^2+k-1d^-(k+2k^2)+1≥ c_1 k^-2 (d-1)^k/2ρ_d^2k^2+k

 Let x,y be a pair of adjacent vertices in G(k).   It is standard that P^t(x,y) ≥ P_𝕋_d^t(o,v) for all t (where v is as above), and so by (<ref>)

    Q(x,y)=P^k+2k^2(x,y) ≥ P_𝕋_d^k+2k^2(o,v) ≥ (d-1)^k/2(1-o(1))ρ_d^2k^2+k=:C_k.

 By Proposition <ref>  (and borrowing the notation from there) in conjunction with (<ref>), (<ref>) and Assumption 1 (which implies that there exists some constant C_0=C_0(d)>0 such that  L:=max_x _G(k)(x)/min_y _G(k)(y)≤ C_0 and that if x,y are of distance k in G then K(x,y) ≤ C_0(d-1)^-k), we have that 
    _K(A) ≤_Q(A)C_0^3(d-1)^-k/C_k=(d-1)^-k/2 (1-o(1)).

Denote the probability w.r.t. SRW on G(k) by ℙ. By (<ref>) we have for all t (uniformly) that 

    max_(a,A):a ∈ A, π(A) ≤αℙ_a[T_A^c>t] ≤√( C_0α |V|) (d-1)^-tk/2(1-o(1))=√(α |V|) (d-1)^-tk/2(1-o(1)) ,

where we have used the fact that  max_x ∈ V π_G(k)(x)/π(x) ≤ C_0, where C_0 is as above. 

Consider SRW on G, (X_t)_t=0^∞.  Let T_0:=0 and inductively, T_i+1:=inf{t ≥ T_i : dist_G(X_T_i+1,X_T_i)=k }. As in Definition <ref>, consider the chain 𝐘=(Y_i)_i=0^∞, where Y_i:=X_T_i   for all i.  Let W be its transition matrix. By Assumption 1 and  Lemma <ref>  there exists some  constant C=C(d) such that for all x,y ∈ V of distance k from one another (in G), 

    1/C ≤ W(x,y)/K(x,y) ≤ C.
 Denote the probability w.r.t. 𝐘 by 𝐏. Then by (<ref>) and (<ref>) 

    max_(a,A):a ∈ A, π(A) ≤α𝐏_a[T_A^c>t]  ≤ C^tmax_(a,A):a ∈ A, π(A) ≤αℙ_a[T_A^c>t] ≤√(α |V|) (d-1)^-tk/2(1-o(1)) ,

uniformly for all t. Denote the distribution of SRW on G by . 
Observe that for all s,t ≥ 0  
    max_(a,A):a ∈ A, π(A) ≤αP_a[T_A^c>  t+s] ≤max_(a,A):a ∈ A, π(A) ≤α𝐏_a[T_A^c>τ(t)]+max_a ∈ VP_a[T_τ(t)> t+s],

where 
    τ(t):= ⌈(d-2)t/dk⌉.

To conclude the proof (using  (<ref>) in conjunction with Lemma <ref>), we now show that (for some o(1) terms) substituting above t=⌈ (1+o(1)) d/d-2log_d-1|V|  ⌉ and s=t/√(k) +t^2/3 (the value 2/3 in the exponent can be replaced by any number in (1/2,1)) yields max_(a,A):a ∈ A, π(A) ≤αP_a[T_A^c>  t+s]=o(1). By (<ref>) it suffices to show that for this choice of s and t we have that max_a ∈ VP_a[T_τ(t)> t+s]=o(1). 

Fix s and t as above. We say that time j is good if X_j has  d-1 neighbors of greater distance from X_T_i(j), where i(j) is the index for which j ∈ [T_i(j),T_i(j)+1).
Let 
    U_i:=|{t ∈ [T_i,T_i+1):t  is not good}|   and   U:=∑_i=0^τ(t) U_i.

By Assumption 1 we have that max_v_v[U_0> ℓ ] ≤ C' e^-c ℓ for all ℓ, for some constants c,C'>0 (this is left as an exercise). By the Markov property, it follows that 
    max_v_v[U> t/√(k)]=o(1).
  

Consider a coupling of the SRW on G (X_j)_j=0^∞ with the SRW on 𝕋_d started from its root o (S_j)_j=0^∞ in which if j is the ℓth good time, then dist_G(X_j+1,X_T_i(j))< dist_G(X_j,X_T_i(j)) iff  dist_𝕋_d(S_ℓ+1,o)< dist_𝕋_d(S_ℓ,o) (unless S_ℓ=o, but there is no harm in neglecting this possibility, as the number of returns to o has a Geometric distribution). Using this coupling we get that for all a ∈ V  we have that

    P_a[T_τ(t)> t+s] ≤_a[U >t/√(k) ]+max_0 ≤ j ≤⌈t/√(k)⌉_o[S_ t+s-j∈∪_i=0^τ(t)+jℒ_i  ]=o(1).

To see that max_0 ≤ j ≤⌈t/√(k)⌉_o[S_ t+s-j∈∪_i=0^τ(t)+jℒ_i  ]=o(1) use the fact that the distance of S_t+s-j from o is concentrated around d-2/d(t+s-j) within a window whose length is of order √(t)    (c.f. <cit.> (2.2)-(2.3) pg. 9) and that by our choice of s we have that d-2/d(t+s-j)-(τ(t)+j) ≫√(t), for all 0 ≤ j ≤⌈t/√(k)⌉. 



Let M be the number of paths of length k+2k^2 in ℤ, starting from 0, which end at k and do not return to 0. Then M ≥ c_0 2^k+2k^2/k^2. 


Let (Z_i)_i=0^∞ be a SRW on . Let T_0^+:=inf{t>0: Z_t=0 }. Then

    _0[Z_k+2k^2=k,T_0^+>k+2k^2 ] ≥_0[ T_0^+> k+2k^2  ≥ T_k ] min_0 ≤ i ≤ k^2_k[T_0>2i,Z_2i=k] ≥ c_0k^-2,

where we have used the fact that  _0[ T_0^+> k+2k^2 ≥ T_k ] ≥ c_1 _0[ T_0^+>T_k ]=c_1/(2k) and that _k[T_0>2i,Z_2i=k] ≥_k[T_{0,2k}>2i]  _k[Z_2i=k | T_{0,2k}>2i  ] ≥ c_2 ·1/2k for all
i ≤ k^2.



§ ACKNOWLEDGEMENTS

The author is grateful to Nathanaël Berestycki, Gady Kozma, Eyal Lubetzky, Yuval Peres, Justin Salez, Allan Sly and Perla Sousi  for useful discussions. 



plain







