On the Second Eigenvalue and Random Walks in Random d-Regular Graphs August 24, 1988 Revised May 22, 1989

Joel Friedman^{∗} Princeton University

November 26, 1993

Abstract

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ_{2}, of (the adjacency matrix of) a random d-regular graph, G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at the k-th step, for various values of k. Our main theorem about eigenvalues is that

E \{|λ_{2}(G)|^{m}\} ≤ (2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n}))^{m}

for any m ≤ 2⌊log n ⌊\sqrt{2d − 1}/2⌋/ log d⌋, where E \{ \} denotes the expected value over a certain probablity space of 2d-regular graphs. It follows, for example, that for fixed d the second eigenvalue’s magnitude is no more than 2\sqrt{2d − 1}+2 log d+ C′ with probability 1 − n^{−C} for constants C and C′ for sufficiently large n.

1 Introduction

Let G be a d-regular (i.e. each vertex has degree d) undirected graph, and let A be its adjacency matrix. We allow G to have multiple edges, in which case the corresponding entry of A is that multiplicity; we allow (possibly multiple) self-loops, in which case the corresponding entry of A is twice the multiplicity of the self-loop. Since A is symmetric it is diagonalizable with (an orthogonal set of eigenvectors and with) real eigenvalues. It is easy to see that d is the largest eigenvalue in absolute value (with the all 1’s eigenvector). Let λ_{2} = λ_{2}(G) be the next largest eigenvalue in absolute value.

∗The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR–8858788, and the Office of Naval Research under Grant N00014–87–K–0467.

The magnitude of |λ_{2}| has received much attention in the literature: for example, it is useful to give some estimate of the expansion properties of G (see [Tan84],[Alo86]) or the rate of convergence of the Markov process on G (with probabilities 1/d at each edge) to the stable distribution (see [BS87] for more on this and references). The smaller |λ| the better, usually; intuitively it measures the difference (in L_{2} operator norm) between A and the all d/n ’s matrix, and more generally that between A^{m} and the all d^{m}/n ’s matrix.

The main goal of this paper is to estimate the magnitude of |λ_{2}| of a random d-regular graph. We view d as fixed and n → ∞; if d is sufficiently large with respect to n, it is well known that |λ_{2}| = O(\sqrt{d}) with high probability. In order to estimate |λ_{2}|, we study the probability that a random walk on a random graph returns to its originating vertex at the k-th step, for various values of k (for us, k ≈ log n or (log n)^{2} are important). We will actually work with 2d-regular graphs, drawn from a probability space G_{n,2d} to be defined shortly. Our main theorem is

Theorem A For G ∈ G_{n,2d} we have

E \{|λ_{2}(G)|\} ≤ 2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n})

(with an absolute constant in the O( ) notation), where E { } denotes the expected value over G_{n,2d} and where the logarithm is taken base e; more generally we have

E \{|λ_{2}(G)|^{m}\} ≤ (2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n}))^{m}

for any m ≤ 2⌊log n ⌊\sqrt{2d − 1}/2⌋/ log d⌋.

All logarithms in this paper are taken base e. A corollary of this theorem is

Theorem B For any β > 1 we have

|λ_{2}(G)| ≥ (2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n}))β

with probability

≤ \frac{β^{2}}{n^{2⌊\sqrt{2d−1}/2⌋ log β/ log d}} .

In particular, we have that for any C there is a C′ such that for any d there is an n_{0} such that if n ≥ n_{0} then a G ∈ G_{n,2d} has

|λ_{2}(G)| ≤ 2\sqrt{2d − 1} + 2 log d + C′

with probability at least 1 − n^{−C}.

One can compare this to the well-known lower bound

|λ_{2}(G)| ≥ 2\sqrt{2d − 1} + O(\frac{1}{log_{d} n})

for any 2d-regular graph, G, with, say, d ≤ \sqrt{n} (the bound as stated is easy, and has been discovered by many people; for a proof see section 3; a similar result also holds for the second largest positive eigenvector, see [McK81] and Alon and Boppana in[Alo86]). Previously Broder and Shamir, in [BS87] had shown that for fixed d,

E {|λ_{2}(G)|} ≤ 2^{5/4}d^{3/4}(1 + ϵ + o(1))

as n → ∞, and the analog to the second equation in theorem A with m ≤ (2 − ϵ′) log_{d/2} n. Our method refines Broder and Shamir’s estimate of the probability that a random walk in a random graph returns to its original vertex after some specified number of steps; this therefore improves the estimates on |λ_{2}(G)|. Also, Kahn and Szemerédi, in [KS], have independently given a much different approach, which modifies the standard counting argument (the standard counting argument gives no interesting bound), to get |λ_{2}(G)| = O(\sqrt{d}) with probability → 1 as n → ∞. The following conjecture of Alon is still unresolved, which states that for fixed d, as n → ∞, |λ_{2}| ≤ 2\sqrt{2d − 1} + ϵ with high probability for any epsilon > 0.

The standard approach to estimating eigenvalues is to estimate the trace of a high power of the adjacency matrix, i.e. estimate the probability that a random walk of a given length will return to the starting vertex on a random graph. Since

Trace (A^{k}) = ∑_{i=1}^{n} λ_{i}^{k}

for a matrix, A, with eigenvalues λ_{1}, …, λ_{n}, this gives bounds on the magnitude of the largest unknown eigenvalue. This method was used by Wigner in [Wig55] to find the limiting distribution (the “semi-circle law”) of the eigenvalues in a random n × n symmetric matrix with independently chosen entries drawn from a fixed distribution, as n → ∞; implicit in his paper is that when the expected value of the entry is 0 the largest (second largest otherwise) eigenvalue is of magnitude roughly proportional to \sqrt{n}. His approach to estimating the trace of high powers of the matrix, and subsequent refinements (see [Gem80], [FK81] for example) do not work when the distribution of the entries vary too much with n, in particular with matrices of graphs whose edge density decreases too fast with n. In [McK81], McKay derived a semicirlce law for d regular graphs, i.e. the limiting distribution of the eigenvalues, but the method did not give bounds on |λ_{2}| (the limiting distribution only gives information on n−o(n) of the eigenvalues). In [Mar87] and [LPS86], Margulis and (independently) Lubotzky, Phillips, and Sarnak constructed a class of graphs with |λ_{2}| ≤ 2\sqrt{d − 1}. In [BS87], Broder and Shamir gave a method of estimating traces for random graphs which gave |λ_{2}| = O(d^{3/4}) with high probability. In this paper we use Broder and Shamir’s framework for trace estimates; we also make use of the cosine substitution and resulting formulas as in [LPS86], and Alon’s theorem that says expansion implies “small” second eigenvalue, in [Alo86]. We begin by reviewing the terminology and results in [BS87].

The model we take is for a random 2d-regular graph on n vertices. Choose independently d permutations of the numbers from 1 to n, each permutation equally likely. We construct a directed graph, G = (V, E) with vertex set V = {1, …, n} and edges

E = {(i, π_{j}(i)), (i, π_{j}^{−1}(i)) | j = 1, …, d i = 1, …, n} .

G is therefore a graph with possibly multiple edges and self-loops, and which is symmetric in the sense that for every edge in the graph the reverse edge is also in the graph. Although G is directed, we can view it as an undirected graph by replacing each pair of edges (i, π(i)), (π(i), i) with one undirected edge. We denote this probability space of random graphs G_{n,2d}.

Let A be the adjacency matrix of a graph G ∈ G_{n,2d}. Let Π be the alphabet of symbols

Π = {π_{1}, π_{1}^{−1}, π_{2}, …, π_{d}^{−1}} .

We think of π_{1}, …, π_{d} as being the d permutations from which G was constructed, and any word, w = σ_{1} … σ_{k} of Π^{∗} as the permutation which is the composition of the permutations σ_{1}, …, σ_{k}. Let

i →^{w} j ≡ \{ \begin{matrix}1 & if w(i) = j \\ 0 & otherwise \end{matrix} \} .

We have that the i, j-th entry of A^{k} is

∑_{w∈Π^{k}} i →^{w} j .

We wish to estimate the expected value of the above sum for i = j. In evaluating i →^{w} i, we can cancel in w any consecutive pair of letters ππ^{−1} with π ∈ Π. We say that a word w ∈ Π^{k} is irreducible if w has no pair of consecutive letters of the form ππ^{−1}. We denote the set of irreducible words of length k by Irred_{k}. Clearly Irred_{k} has size 2d(2d − 1)^{k−1}. It turns out that to estimate the second eigenvalue it suffices to get an estimate of the form

∑_{w∈Irred_{k}} i →^{w} i = 2d(2d − 1)^{k−1} \frac{1}{n} + error  (1.1)

for all fixed i with a small error term; to estimate the expected second eigenvalue it suffices to estimate the expected value of the left-hand-side of equation 1.1. Intuitively, for k ≥ 1 we expect that words in Irred_{k} will send a fixed vertex to each vertex with more or less equal probability, 1/n. The corresponding eigenvalue estimate is roughly O(n^{1/k}(\sqrt{d} + error^{1/k})). In [LPS86], the error terms for a specific family of graphs were each bounded by (cd)^{k/2} for all k, yielding |λ_{2}| ≤ 2\sqrt{d − 1}. In [BS87] the error term for the expected value over G_{n,2d} was bounded as

O(\frac{k^{4}}{n^{2}} 2d(2d − 1)^{k−1} + \frac{k}{n} (cd)^{k/2}) ,

which for k = 2 log_{d} n is ≤ (cd)^{3k/4}/n.

In this paper we obtain sharper estimates on the error term for the expected value over G_{n,2d}. One that is useful for information on the eigenvalues is (corollary 3.6)

Theorem C There is a constant c such that the error term in equation 1.1 is no more than

2d(2d − 1)^{k−1} (ckd)^{c}(\frac{k^{2\sqrt{2d}}}{n^{1+⌊\sqrt{2d−1}/2⌋}} + \frac{(2d − 1)^{−k/2}}{n} ) .  (1.2)

for all k with k ≤ n^{1/(c\sqrt{d})}/(cd^{3/2}) and d ≥ 4.

(See theorem 2.18 for other estimates on the error term.) From the above theorem we derive estimates on the second eigenvalue.

In section 2 we do the most of the work, which is to prove that the sum in equation 1.1 has an r-th order asymptotic expansion in 1/n for any r ≤ \sqrt{2d − 1}/2 of the form

E \{ ∑_{w∈Irred_{k}} i →^{w} i\} = 2d(2d−1)^{k−1} (\frac{1}{n} f_{0}(k) + \frac{1}{n^{2}} f_{1}(k) + … + \frac{1}{n^{r}} f_{r−1}(k))+error ,

(1.3)

where the error involves a 1/n^{r+1} term and a term like the second term in equation 1.2, and where the f_{i}’s are polynomials of degree 5i + 2 whose coefficients are bounded by (cdr)^{cr^{2}}. In section 3 we show why theorem C follows from equation 1.3, i.e. why f_{0}(k) = 1 and all the other f_{i}’s must vanish, and derive information on the eigenvalues, such as theorem A.

2 An Asymptotic Expansion

The goal of this section is to develop the asymptotic expansion of equation 1.3. We first explain the reason that such an expansion should exist, reviewing the ideas in [BS87]. Throughout this section we will bound error terms by expressions involving various absolute constants. Rather than giving each one a distinct name, we shall denote them all by c; in cases where confusion could arise we shall also use c′.

For w = σ_{1} … σ_{k} ∈ Irred_{k} and i fixed, consider the random variable i →^{w} i. We wish to estimate E{i →^{w} i}. In [BS87] the analysis is as follows. It is helpful to consider the random variables t_{1} = σ_{1}(i), t_{2} = σ_{2}(t_{1}), etc. which trace i’s path through G along w. We simplify the calculation of E{i →^{w} i} over G_{n,2d} by considering only the values of π_{1}, …, π_{d} needed to determine the t_{j}’s and therefore the value of i →^{w} i. So consider the process of selecting an element of G_{n,2d} by first selecting t_{1}, then t_{2}, until t_{k}, and then determining the remaining values of the π_{j}’s.

To determine t_{1} it suffices to know the value of σ_{1}(i), which clearly takes on the values {1, …, n} each with probability 1/n. Next we determine the value of σ_{2}(t_{1}); there are a few cases to consider. If σ_{2} ≠ σ_{1}, then σ_{2} and σ_{1} represent different permutations (since w is irreducible, σ_{2} ≠ σ_{1}^{−1}), and so t_{2} takes on the values {1, …, n} each with probability 1/n. If σ_{1} = σ_{2}, then either t_{1} = i and so t_{2} is forced to be i, or t_{1} ≠ i, in which case t_{2} takes on the values {1, …, n} − {t_{1}} each with probability 1/(n − 1). We can continue to determine t_{3}, …, t_{k} in this fashion, each t_{j}’s value conditional on the values of the previous ones. When t_{j}’s value is exactly determined by the previous values, i.e. σ_{j}(t_{j−1})’s value is known, we say that t_{j} is a forced choice; otherwise we say that t_{j} is a free choice. If t_{j} is a free choice, then clearly t_{j} takes on any one of n − m values with probability 1/(n − m) for some m ≤ j − 1. If a free choice t_{j} happens to be a previously visited vertex (i.e. = i or = t_{m} for some m < j) we say that t_{j} is a coincidence; given that t_{j} is a free choice, t_{j} will be a coincidence with probability ≤ j/(n − j + 1). During this paper we will also call an edge (t_{j−1}, t_{j}) a free choice, forced choice, or coincidence if t_{j} is respectively a free choice, forced choice, or coincidence.

In [BS87], it is observed that two coincidences occur in any given w and i with probability no greater than

\binom{k}{2} (\frac{k − 1}{n − k + 1})^{2} = O(\frac{k^{4}}{n^{2}} ).

This accounts for the first of their error terms. The rest of the work is to analyze the case of one coincidence, since if there are no coincidences then clearly i →^{w} i is 0. We will analyze the case of ≤ r coincidences for any r ≤ \sqrt{2d − 1}/2, and show that the error term in equation 1.1 actually has an r term asymptotic expansion in 1/n, whose coefficients are polynomials in k for any fixed d. The key to the proof is to group together walks in the graph which have the same rough shape, which we call the type of the walk.

Let

i_{0} ⟶^{w_{1}} i_{1} ⟶^{w_{2}} ⋯ ⟶^{w_{j}} i_{j} ≡ \{ \begin{matrix}1 & if w_{k}(i_{k−1}) = i_{k} for k = 1, …, j \\ 0 & otherwise \end{matrix} \} .

Consider

E \{ ∑_{w∈Irred_{k}} i →^{w} i\} = ∑_{{w=σ_{1}...σ_{d}∈Irred_{k} \atop t_{j}∈\{ 1,...,n\}, j=1,...,k−1}} E \{i ⟶^{σ_{1}} t_{1} ⟶^{σ_{2}} ⋯ ⟶^{σ_{k−1}} t_{k−1} ⟶^{σ_{k}} i\} .

We will group the terms of the right-hand-side summation by their geometric configuration. Fix a word w = σ_{1} … σ_{d}, integer i, and sequence of integers t = (t_{1}, …, t_{k−1}) and let t_{k} = i. With these values we associate a directed graph, Γ_{w,i,t}, with edges labeled by Π. The graph’s vertex set is V = {i_{1}, …, i_{m}}, where m is the number of distinct integers among i and t; we think of i_{1} as representing i and, more generally, i_{l} as representing the l-th distinct member of the sequence i, t_{1}, …, t_{k−1}. The edge set, E, has one edge e_{j} for each free choice t_{j}; e_{j} is an edge (i_{a}, i_{b}) where i_{a} i_{b} respectively represent the values of t_{j−1} and t_{j}; in addition e_{j} is labeled with σ_{j}. Γ_{w,i,t} represents the geometric structure of the intended path from i through t and back to i along w; it contains the amount of conditioning on π_{1}, …, π_{d} given that the intended path is actually taken. We say call Γ_{w,i,t} the generalized form of w, i, t.

Consider an abstract generalized form, Γ = (V_{Γ}, E_{Γ}), i.e. a directed graph with vertices named V_{Γ} = {i_{1}, …, i_{m}} and with edges labelled by Π, which is = Γ_{w,i,t} for some (w, i, t) triple, but where we ignore the particular (w, i, t) from which is arises (at least for the time being). Let a_{j}(Γ) denote the total number of occurences of π_{j} and π_{j}^{−1} as labels of edges. a_{j} gives the number of values of π_{j} determined by Γ. For a fixed w we have

∑_{{(i,t)|Γ_{w,i,t}=Γ}} E {i ⟶^{σ_{1}} t_{1} ⟶^{σ_{2}} ⋯ ⟶^{σ_{k−1}} t_{k−1} ⟶^{σ_{k}} i} =

n(n − 1) … (n − |V_{Γ}| + 1) ∏_{j=1}^{d} \frac{1}{n(n − 1) … (n − a_{j}(Γ) + 1)} ,

where the j-th term in the above product is omitted if a_{j}(Γ) = 0. We denote the above by Pr (Γ). We can expand

Pr (Γ) = \frac{1}{n^{coin(Γ)−1}} (1 + \frac{c_{1}}{n} + \frac{c_{2}}{n^{2}} + ⋯)  (2.1)

where the c_{j}’s are constants depending on Γ and coin (Γ) denotes the number of coincidences in Γ (more precisely in any triple (w, i, t) with Γ_{w,i,t} = Γ), which does not depend on (w, i, t). Clearly

∑_{{w∈Irred_{k} \atop i=1,...,n}} E \{i →^{w} i\} = ∑_{Γ} Pr (Γ) ω(Γ, k) ,  (2.2)

where ω(Γ, k) denotes the number of irreducible words, w, of length k compatible with Γ, i.e. for which there are i and t with Γ_{w,i,t} = Γ.

Next we group together generalized forms, Γ, whose underlying graphs have the same rough shape. Consider again, for a fixed word, w, and vertex, i, the process of determining the t_{j}’s. We begin by generating distinct vertices t_{1}, t_{2}, ..., adding vertices and edges to Γ, until we encounter a coincidence. We may then encounter forced choices, which is to say walk in Γ without generating new vertices or edges, until we encounter a free choice, t_{l}. Starting with the edge from t_{l−1} to t_{l}, we depart from the “old” Γ, walking along new edges and vertices until we encounter our next coincidence. We call a point such as t_{l−1} (more precise, the last vertex in a consecutive sequence of forced choices) a departure. We will sometimes also refer to the edge (t_{l−1}, t_{l}) as a departure, if t_{l−1} is. Clearly departures alternate with coincidences throughout the walk. We now group Γ’s by forgetting any vertex which is not a coincidence or a departure. In other words, we forget all degree 2 vertices (except i_{1}); nothing interesting happens at them.

We say that a vertex i_{j} of Γ is a coincidence (departure) if one of its corresponding t_{l}’s is a coincidence (departure); as with coin (Γ), these notions are independent of (w, i, t). In fact, i_{1} is always a coincidence, i_{j} for j > 1 is a coincidence iff its indegree is > 1, and i_{j} for all j is a departure iff its outdegree is > 1. Any vertex of Γ which is not a coincidence or a departure has indegree and outdegree 1, and so the edges of Γ are a union of simple (directed) paths from pairs of the subset of vertices, S, consisting of all coincidences and departures. With Γ we associate its type, T_{Γ}, which is an undirected graph, possibly with multiple edges and self-loops. Its vertex set is {v_{1}, …, v_{l}} where l = |S|, and as before we think of v_{j} as representing the j-th vertex of S in the order i_{1}, …, i_{m}. T_{Γ} has an edge for each simple directed path from pairs of S.

Given an abstract type, T, which is just an undirected graph (corresponding to at least one Γ), we order any group of multiple edges to distinguish each edge from its copies. In other words, for each edge of multiplicity s, represented by distinct edges {e_{1}, …, e_{s}}, we label {e_{1}, …, e_{s}} with distinct integers {1, …, s} in some fashion. This labelling is equivalent to imposing an order on each group of multiple edges. We call a type together with such an ordering or labelling a type with ordered multiple edges, or simply an ordered type. The point is that given an abstract generalized form, Γ, any word w compatible with Γ gives rise to a unique oriented labelling with labels in Π^{∗} of the edges of the corresponding (abstract) ordered type T_{Γ} (an oriented labelling being one where we orient the edge and give it a label, assigning the inverse label to the oppositely oriented direction), and to a unique walk in T_{Γ}. To see this, consider the walk from i_{1} to itself along w, which traces out a unique walk in Γ. This gives rise to possibly many walks in T_{Γ}, but only to one walk such that (1) the edges are labelled and oriented as they are traversed, labelled with the word in Π^{∗} which is simultaneously traced out in Γ, and oriented in the direction traversed, (2) once an edge is labelled it is traversed only when it matches the word in Π^{∗} traced out during the traversal, and (3) multiple edges are traversed in increasing order.

Conversely, let T be an (abstract) ordered type. By a legal walk in T we mean a walk from v_{1} to itself which traverses every edge at least once, and which traverses multiple edges in increasing order. By a legal oriented labelling we mean an oriented labeling of T ’s edges by irreducible words in Π^{∗} of length ≥ 1 such that for any vertex, v, in T the labels on the outwardly oriented edges from v begin with distinct letters. It is easy to see that we have a one-to-one correspondence

{(Γ, w) | General forms, Γ, w ∈ Irred compatible with Γ} ⟷^{1−1} {(T, y, ℓ) | Ordered types T, legal walks y and oriented labellings ℓ for T } .

To calculate the asymptotic expansion, we will sum over types, walks, and oriented labellings, rather than over generalized forms and words.

Given a legal walk, y, on an ordered type, T, we define the multiplicity of the walk to be the function which assigns to each edge of T the number of times it is traversed, disregarding orientation. For a legal oriented labelling, ℓ, of T, we define the lettering of the labelling to be the function which takes a vertex, v, and an incident edge, e, and returns the first letter of e’s label with the outward orientation from v. We define the weight of the labelling to be the function which takes an edge and returns the length of the word with which it it labelled. The notion of coin (T) for types T carries over from that of generalized forms (i.e. as equal to coin (Γ) for one and therefore all Γ’s with T_{Γ} = T). Our strategy will be to fix a type, a multiplicity, and a lettering, and then sum the corresponding terms in equation 2.2.

We are now ready for the nitty-gritty. Lemmas which are not followed by proofs are immediate or easy.

Lemma 2.1 For any type, T = (V, E) we have coin (T) = |E| − |V | + 1.

Lemma 2.2 For a type, T, of coincidence r we have |V | ≤ 2r and |E| ≤ 3r − 1.

Proof In any legal walk in a generalized form, the coincidences and departures alternate, starting and ending with coincidences. Any vertex, v_{l}, of the type, with l ≥ 2, must be either a coincidence or a departure (or both). Thus |V | ≤ 2r. This and lemma 2.1 yield |E| ≤ 3r − 1.

□

Lemma 2.3 The number of types of coincidence r is less than (2r)^{6r−2}. The number of types of coincidence ≤ r is less than (2r)^{6r−1}.

Lemma 2.4 The number of letterings of a type of coincidence r is ≤ (2d)^{6r−2}.

Let T_{r} be the type with two vertices, v_{1}, v_{2}, with one edge from v_{1} to v_{2} and r edges from v_{2} to itself (i.e. self-loops). T_{r} is of coincidence r.

Lemma 2.5 In a type, T, of coincidence r which is not equal to T_{r}, each vertex has degree at most 2r.

Proof Again, consider any legal walk in a generalized form. When a vertex is first encountered it is entered and left, giving it indegree and outdegree 1 up to that point. Then it can be entered by coincidence edges up to r times, and left by departure edges up to r − 1 times. The degree of the corresponding vertex in the type will therefore have degree ≤ 2r + 1. We claim that equality can only occur in the type T_{r}. For equality implies that the corresponding vertex, v, in the type must have r self-edges and that it is the only coincidence and departure in the type; this leaves room for only (possibly) one other vertex, v_{1}, which corresponds to i_{1}. If v is not v_{1}, then this type must be T_{r}, and if v = v_{1}, then v’s degree is 2r.

□

Lemma 2.6 In a fixed type of coincidence r, there are ≤ (2r)^{m} legal walks whose sum of its mutliplicities is m.

Proof If T is not T_{r}, then each vertex has degree ≤ 2r and so there are ≤ (2r)^{m} legal walks of length m in T. In T_{r}, a legal walk consists of one step from v_{1} to v_{2}, then m − 2 steps each taking one of the r self-loops in either of its two directions, and finally returning to v_{1}, for a total of ≤ (2r)^{m−2} legal walks.

□

Consider the function

g(x) = (1 − b_{1}x) … (1 − b_{r}x)(\frac{1}{1 − c_{1}x}) … (\frac{1}{1 − c_{s}x}) ,

where b_{1}, …, b_{r}, c_{1}, …, c_{s} are positive constants. Its i-th derivative is

∑_{{i_{1}+···+i_{r}+j_{1}+···+j_{s}=i \atop i_{k}≤1 for k=1,...,r}} \binom{i}{i_{1}, …, i_{r}, j_{1}, …, j_{s}} (−b_{1})^{i_{1}}(1 − b_{1}x)^{i_{1}−1} … (−b_{r})^{i_{r}}(1 − b_{r}x)^{i_{r}−1} ×

j_{1}! … j_{s}! \frac{c_{1}^{j_{1}} … c_{s}^{j_{s}}}{(1 − c_{1}x)^{j_{1}} … (1 − c_{s}x)^{j_{s}}} .

For any 0 ≤ x ≤ 1/c, where c is an upper bound on the b_{k}’s and c_{k}’s, we have

|g^{(i)}(x)| ≤ (\frac{1}{1 − xc})^{i}i! ∑_{i_{1}+···+i_{r}+j_{1}+···+j_{s}=i} \binom{i}{i_{1}, …, i_{r}, j_{1}, …, j_{s}}b_{1}^{i_{1}} … b_{r}^{i_{r}}c_{1}^{j_{1}} … c_{s}^{j_{s}}

= (\frac{1}{1 − xc})^{i}i!(∑ b_{k} + ∑ c_{k})^{i} ,  (2.3)

by the multinomial theorem. As a consequence we have

Lemma 2.7 For any generalized form Γ of ≤ k edges, Pr (Γ) has an expansion

Pr (Γ) = \frac{1}{n^{coin(Γ)−1}} (p_{0} + \frac{p_{1}}{n} + \frac{p_{2}}{n^{2}} + ⋯ + \frac{p_{r}}{n^{r}} + \frac{ϵ}{n^{r+1}} )  (2.4)

(with p_{0} = 1), where ϵ is an error term bounded by

e^{(r+1)k/n}k^{2r+2}

and the p_{i}’s are constants.

Proof We apply equation 2.3 to equation 2.1, where we have ∑ b_{j} + ∑ c_{j} ≤ k^{2}. By Taylor’s theorem, ϵ is bounded by

\frac{1}{(r + 1)!}(\frac{1}{1 − kξ} )^{r+1} (r + 1)! (k^{2})^{r+1} ,

for some ξ ∈ [ 0, 1/n] for each n.

□

The p_{i} of lemma 2.7 are polynomials in the a_{j} and |V_{Γ}| of equation 2.1, and we wish to bound their size and coefficients.

For any integer a, consider the function

g(x) = \frac{1}{1 − x} \frac{1}{1 − 2x} … \frac{1}{1 − ax} .

A power series for g is given in terms of Stirling numbers. We wish to bound the size of their coefficients as polynomials in a.

Lemma 2.8 g(x)’s power series about x = 0 is of the form

1 + xR_{1}(a) + x^{2}R_{2}(a) + ⋯ + x^{r}R_{r}(a) + ⋯,

where the R_{i}’s are polynomials of degree 2i,

R_{i}(a) = ∑_{j=0}^{2i} c_{i,j}\binom{a}{j} ,

where the c_{i,j}’s are non-negative integers with

c_{i,0} + ⋯ + c_{i,2i} ≤ 8^{i}i! .

Proof Writing

1 + xR_{1}(a) + x^{2}R_{2}(a) + ⋯ = (1 + ax)(1 + xR_{1}(a − 1) + x^{2}R_{2}(a − 1) + ⋯)

and comparing terms yields

R_{r}(a) = R_{r}(a − 1) + aR_{r−1}(a)  (2.5)

for r ≥ 1 (with R_{0}(a) ≡ 1). We get a definition for the R_{r}’s recursive in r. Since R_{0}(a) is 1 it easily follows that R_{r} is a polynomial of degree 2r. Since R_{r}(1) = 1 for all r, setting a = 1 in equation 2.5 yields R_{r}(0) = 0, where we identify R_{r} with the polynomial which agrees with it on all positive integers. Thus c_{r,0} = 0 for all r. For the other coefficients we have

R_{r}(a) − R_{r}(a − 1) = ∑_{k=0}^{2r−2} c_{r−1,k} a\binom{a}{k}

= ∑_{k=0}^{2r−2} c_{r−1,k} (\binom{a}{k + 1}(k + 1) + \binom{a}{k}k)

= ∑_{k=0}^{2r−2} c_{r−1,k} (\binom{a − 1}{k + 1}(k + 1) + \binom{a − 1}{k}(k + 1) + \binom{a − 1}{k}k + \binom{a − 1}{k − 1}k) .

Solving the above difference equation it follows by induction on r that all the c_{r,k}’s are non-negative integers, and that ∑_{k} c_{r,k} ≤ (8r − 6) ∑_{k} c_{r−1,k}.

□

Similarly, we consider

g(x) = (1 − x)(1 − 2x) … (1 − ax) .

Lemma 2.9 g(x)’s power series about x = 0 is of the form

1 − xQ_{1}(a) + x^{2}Q_{2}(a) − ⋯ + (−1)^{r}x^{r}Q_{r}(a) + ⋯,

where the Q_{i}’s are polynomials of degree 2i,

Q_{i}(a) = ∑_{j=0}^{2i} c_{i,j}\binom{a}{j} ,

where the c_{i,j}’s are non-negative integers with

c_{i,0} + ⋯ + c_{i,2i} ≤ 4^{i}i! .

Proof The Q’s satisfy

Q_{r}(a) = Q_{r}(a − 1) + aQ_{r−1}(a − 1),

and a similar analysis yields the lemma.

Corollary 2.10 In equation 2.4, we have

p_{i}(Γ) = ∑_{|I|≤i} c_{i,I} \binom{|V_{Γ}| − 1}{I_{0}}\binom{a_{1}(Γ) − 1}{I_{1}} … \binom{a_{d}(Γ) − 1}{I_{d}} ,  (2.6)

where we have used “tensor” notation with I = (I_{0}, …, I_{d}) (i.e. I_{k}’s are non-negative integers, and |I| = I_{0} + ⋯ + I_{d}), with constants c_{i,I} each of absolute value ≤ 8^{i}i! .

Our goal is to estimate the terms of the sum in the right-hand-side of equation 2.6, when summed over all (Γ, w) pairs of a given type. This is easy once a lettering of the type is fixed.

For a fixed σ, τ ∈ Π, let Irred_{k,σ,τ} denote the set of irreducible words of length k beginning with σ and ending with τ.

Lemma 2.11 For any σ, τ ∈ Π and non-negative integers s_{1}, …, s_{d} we have

f(k) ≡ ∑_{w∈Irred_{k,σ,τ}} \binom{a_{1}(w)}{s_{1}} … \binom{a_{d}(w)}{s_{d}} = (2d − 1)^{k}P (k) + (−1)^{k}Q(k) + R(k)

where P, Q, R are polynomials of degree s = s_{1} + ⋯ + s_{d} with coefficients bounded by (cd)^{cs}.

Proof Consider the 2d × 2d matrix

M = ( \begin{matrix}x_{1} & 0 & x_{2} & x_{2} & ⋯ & x_{d} & x_{d} \\ 0 & x_{1} & x_{2} & x_{2} & ⋯ & x_{d} & x_{d} \\ x_{1} & x_{1} & x_{2} & 0 & ⋯ & x_{d} & x_{d} \\ x_{1} & x_{1} & 0 & x_{2} & ⋯ & x_{d} & x_{d} \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ x_{1} & x_{1} & x_{2} & x_{2} & ⋯ & x_{d} & 0 \\ x_{1} & x_{1} & x_{2} & x_{2} & ⋯ & 0 & x_{d} \end{matrix} )

i.e. the matrix M whoose coefficients are

M_{2i−1,2j−1} = M_{2i,2j} = x_{j}
M_{2i,2j−1} = M_{2i−1,2j} = x_{j} if i ≠ j
M_{2i,2j−1} = M_{2i−1,2j} = 0 if i = j

over all 0 ≤ i ≤ d and 0 ≤ j ≤ d. It is easy to see that

(M^{k})_{i,j} = ∑_{w∈Irred_{k,σ_{i},σ_{j}}} x_{1}^{a_{1}(w)} … x_{d}^{a_{d}(w)}

where σ_{2i−1} is π_{i} and σ_{2i} is π_{i}^{−1}. Hence

f(k) = \frac{1}{s_{1}! … s_{d}!} ((\frac{∂}{∂x_{1}} )^{s_{1}} … (\frac{∂}{∂x_{d}} )^{s_{d}}M^{k}|_{x_{1}=···=x_{d}=1})_{a,b}

for the a, b with σ_{a} = σ, σ_{b} = τ. Let C_{i} = \frac{∂}{∂x_{i}} M, which is a matrix with 4d − 2 1’s and the rest 0’s. All second derivatives of M vanish, and so

\frac{1}{s_{1}! … s_{d}!}(\frac{∂}{∂x_{1}} )^{s_{1}} … (\frac{∂}{∂x_{d}} )^{s_{d}}M^{k} =

∑_{(i_{1},...,i_{s})} ∑_{j_{0}+···+j_{s}=k−s} M^{j_{0}}C_{i_{1}}M^{j_{1}}C_{i_{2}} … C_{i_{s}}M^{j_{s}}

where the first summation is over all tuples (i_{1}, …, i_{s}) which contain s_{1} 1’s, s_{2} 2’s, etc. For fixed (i_{1}, …, i_{s}) we have

∑_{j_{0}+···+j_{s}=k−s} M^{j_{0}}C_{i_{1}} … M^{j_{s}}|_{x_{1}=···=x_{d}=1} = ∑_{j_{0}+···+j_{s}=k−s} C^{j_{0}}C_{i_{1}} … C^{j_{s}}

where

C = M|_{x_{1}=···=x_{d}=1} = ( \begin{matrix}1 & 0 & 1 & 1 & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & 1 & 0 & ⋯ & 1 & 1 \\ 1 & 1 & 0 & 1 & ⋯ & 1 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 0 & 1 \end{matrix} ) .

We claim that C has eigenvalues 2d − 1, −1 with multplicity d − 1, and 1 with multiplicity d. To see this, note that the map T: R^{2d} → R^{2d} given by

T (y_{1}, …, y_{2d}) = (y_{1} + y_{2}, y_{1} − y_{2}, y_{3} + y_{4}, y_{3} − y_{4}, …, y_{2d−1} − y_{2d})

gives

T CT^{−1} = ( \begin{matrix}1 & 0 & 2 & 0 & ⋯ & 2 & 0 \\ 0 & 1 & 0 & 0 & ⋯ & 0 & 0 \\ 2 & 0 & 1 & 0 & ⋯ & 2 & 0 \\ 0 & 0 & 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 2 & 0 & 2 & 0 & ⋯ & 1 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) .

By permuting the basis vectors this becomes the block matrix with d × d blocks

( \begin{matrix}B & 0 \\ 0 & I \end{matrix} ) ,  (2.7)

where I is the identity matrix, and

B = ( \begin{matrix}1 & 2 & 2 & ⋯ & 2 \\ 2 & 1 & 2 & ⋯ & 2 \\ 2 & 2 & 1 & ⋯ & 2 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 2 & 2 & 2 & ⋯ & 1 \end{matrix} ) .

Since B +I is the d×d matrix of all 2’s, whose eigenvalues are 2d (simple) and 0 with multiplicity d − 1, it follows that B’s eigenvalues are 2d − 1 and −1 with multiplicity d − 1. Thus C’s eigenvalues, which by equation 2.7 are the union of those of B and those of I, are 2d − 1 (simple), −1 with multiplicity d − 1, and 1 with multiplicity d.

Thus

∑_{j_{0}+···+j_{s}=k−s} C^{j_{0}}C_{i_{1}} … C^{j_{s}} = ∑_{j} AD^{j_{0}}A^{−1}C_{i_{1}}AD^{j_{1}}A^{−1} … C_{i_{s}}AD^{j_{s}}A^{−1}

where D is the diagonal matrix with diagonal consisting of one 2d − 1, d − 1 −1’s, and d 1’s, and A is an orthogonal matrix diagonalizing C. We can write the sum on the right-hand-side of the above equation as

∑_{j} AD^{j_{0}}E_{1}D^{j_{1}} … E_{s}D_{j_{s}}A^{−1}  (2.8)

with

E_{j} = A^{−1}C_{i_{j}}A .

Since

∥E_{j}∥_{2} = ∥A∥_{2} ∥C_{i_{j}}∥_{2} ∥A^{−1}∥_{2} = ∥C_{i_{j}}∥_{2} ≤ \sqrt{4d − 2} ,

(where ∥ ∥_{2} denotes the L_{2} operator norm) we have that each of E_{j}’s entries are ≤ \sqrt{4d − 2}. Clearly each of A and A^{−1}’s entries are ≤ 1 in absolute value. Therefore, the a, b-th entry of the matrix in equation 2.8,

∑_{j} ∑_{b_{0},...,b_{s}∈[ 1,...,2d]}(A)_{a,b_{1}}(D^{j_{0}})_{b_{0},b_{0}}(E_{1})_{b_{0},b_{1}}(D^{j_{1}})_{b_{1},b_{1}} … (E_{s})_{b_{s−1},b_{s}}(D_{j_{s}})_{b_{s},b_{s}}(A^{−1})_{b_{s},b} ,

is just

∑_{j} ∑_{{ϵ_{0},...,ϵ_{s} \atop ϵ_{l}∈\{2d−1,−1,1\}}} c_{ϵ_{0},...,ϵ_{s}}ϵ_{0}^{j_{0}} … ϵ_{s}^{j_{s}}  (2.9)

where the c_{ϵ_{0},...,ϵ_{s}}’s are constants. Fixing ϵ_{0}, …, ϵ_{s} and letting α, β, γ be the number of respective occurences of 2d − 1, −1, 1 among the ϵ’s, we see that

|c_{ϵ_{0},...,ϵ_{s}}| ≤ (4d − 2)^{s/2}(d − 1)^{β}d^{γ} ≤ 2^{s}d^{3s/2} .  (2.10)

Also,

∑_{j} ϵ_{0}^{j_{0}} … ϵ_{s}^{j_{s}} = ∑_{u+v+w=k−s}(2d − 1)^{u}(−1)^{v}\binom{u + α − 1}{α − 1}\binom{v + β − 1}{β − 1}\binom{w + γ − 1}{γ − 1} .

(2.11)

From

∑_{u=0}^{k} R^{u} = \frac{R^{k+1} − 1}{R − 1}

we derive

∑_{{u+v≤k \atop u,v ≥0}} R^{u}S^{v} = (\frac{R^{k+1} − 1}{R − 1}) + (\frac{R^{k} − 1}{R − 1})S + ⋯ + (\frac{R^{1} − 1}{R − 1})S^{k}

= \frac{R^{k+1}}{R − 1}(1 + \frac{S}{R} + ⋯ + (\frac{S}{R})^{k}) − \frac{1}{R − 1}(1 + S + ⋯ + S^{k})
= \frac{S^{k+2}(R − 1) + R^{k+2}(1 − S) + (S − R)}{(R − 1)(S − 1)(S − R)}

and thus

∑_{{u+v+w=k \atop u,v,w ≥0}} R^{u}S^{v}P^{w} = \frac{S^{k+2}(R − P) + R^{k+2}(P − S) + P^{k+2}(S − R)}{(R − P)(S − P)(S − R)} .

Multiplying the above by R^{α−1}S^{β−1}P^{γ−1}, then differentiating by (\frac{∂}{∂R})^{α−1}(\frac{∂}{∂S})^{β−1}(\frac{∂}{∂P})^{γ−1}, the substituing k − s for k yields

∑_{u+v+w=k−s}(2d − 1)^{u}(−1)^{v}\binom{u + α − 1}{α − 1}\binom{v + β − 1}{β − 1}\binom{w + γ − 1}{γ − 1}  (2.12)

is equal to a sum of six terms, the first of which is

\frac{1}{(α − 1)!} \frac{1}{(β − 1)!} \frac{1}{(γ − 1)!}(\frac{∂}{∂R})^{α−1}(\frac{∂}{∂S} )^{β−1}(\frac{∂}{∂P} )^{γ−1}[\frac{R^{α}S^{k−s+β+1}P^{γ−1}}{(R − P)(S − P)(S − R)}]

evaluated at R = 2d−1, S = −1, P = 1; the other five terms are similar. In the above term, the \frac{∂}{∂P} ’s can be applied to any of the three terms P^{γ−1} (in the numerator) and (R − P) and (S − P) (in the denominator), and similarly for the other partials. We get a sum of 3^{α+β+γ−3} terms, each of the form

\binom{k − s + β + 1}{l}S^{k}θ ,

where l is an integer between 0 and s and θ is a polynomial in R, S, P, independent of k, which satisfies

|θ(R, S, P)||_{R=2d−1,S=−1,P =1} ≤ (2d − 1)^{s} .

The coefficients of the polynomial

\binom{k − s + β + 1}{l}

are clearly dominated by those of

\frac{(k + s)^{l}}{l!} ,

which are clearly less than

max_{j=0,...,l} \frac{s^{j}\binom{l}{j}}{l!} ≤ max_{j=0,...,l} \frac{s^{j}}{j!} ≤ e^{s}.

After doing a similar analysis for the other five terms whose sum equals the expression in equation 2.12, it follows that the expression in equation 2.11 is of the form

(2d − 1)^{k}p(k) + (−1)^{k}q(k) + r(k)

with p, q, r polynomials of degree s whose coefficients are bounded by

3^{s−2}e^{s}(2d − 1)^{s} .

Summing over the 3^{s+1} possibilities for ϵ_{0}, …, ϵ_{s} in equation 2.9, using also equation 2.10, yields

f(k) ≡ ∑_{w∈Irred_{k,σ,τ}} \binom{a_{1}(w)}{s_{1}} … \binom{a_{d}(w)}{s_{d}} = (2d − 1)^{k}P (k) + (−1)^{k}Q(k) + R(k)

where P, Q, R are polynomials in k of degree s whose coefficients are bounded by

2^{s}d^{3s/2}3^{s+1}3^{s−2}e^{s}(2d − 1)^{s} < (36e)^{s}d^{5s/2} .

□

Corollary 2.12 For any σ, τ ∈ Π and non-negative integers s_{1}, …, s_{d} we have

f(k) ≡ ∑_{w∈Irred_{k,σ,τ}}(a_{1}(w))^{s_{1}} … (a_{d}(w))^{s_{d}} = (2d − 1)^{k}P (k) + (−1)^{k}Q(k) + R(k)

where P, Q, R are polynomials of degree s = s_{1} + ⋯ + s_{d} with coefficients bounded by (cds)^{cs} for some absolute constant c.

Proof We use the fact that the constants c_{m} in

x^{n} = ∑_{m=0}^{n} c_{m}\binom{x}{m}

are always positive (see, for example, [Knu73] page 65); it follows that c_{m} ≤ n^{n} by substituting n for x in the above. Applying this to each a_{i}(w)^{s_{i}}, expanding the product, and applying the previous lemma yields the desired result.

□

For a type T = (V_{T} , E_{T}) with E_{T} = {e_{1}, …, e_{t}}, let L_{T,k_{1},...,k_{t}} denote the set of oriented labelling with weights (k_{1}, …, k_{t}). For a labelling, ℓ, we define a_{i}(ℓ) to be the number of occurences of π_{i} and π_{i}^{−1} in ℓ. Any generalized form, Γ, compatible with T and a labelling in L_{T,k_{1},...,k_{t}} has

|V_{Γ}| = |V_{T} | + ∑(k_{j} − 1) = |V_{T} | + |ℓ| − t = |ℓ| + 1 − r ,

by lemma 2.1, where |ℓ| = ∑ a_{i}(ℓ). We can therefore define the p_{i} of equation 2.4 as p_{i}(T, ℓ), for T and ℓ determine the value of p_{i}(Γ) for any compatible Γ.

Lemma 2.13 For any fixed type, T, of coincidence ≤ r, and k_{1}, …, k_{t}, let L = L_{T,k_{1},...,k_{t}}. For any i ≤ r + 1 we have

∑_{ℓ∈L} p_{i}(T, ℓ) = ∑_{K_{1},K_{2},K_{3}}(2d − 1)^{|K_{1}|}(−1)^{|K_{2}|}P_{K_{1},K_{2},K_{3}}(k_{1}, …, k_{t}) ,  (2.13)

where the right-hand-side sum is over all partitions of K = {k_{1}, …, k_{t}} into three disjoint sets K_{1}, K_{2}, K_{3}, where

|K_{j}| = ∑_{k_{s}∈K_{j}} k_{s} ,

and where P_{K_{1},K_{2},K_{3}} are polynomials of degree ≤ 2i whose coefficients are bounded by (cdr)^{cr} for some absolute constant c.

Proof By equation 2.6 we have that the sum on the left-hand-side of equation 2.13 is

∑_{|I|≤i} c_{I} \binom{k_{1} + ⋯ + k_{t} − r}{I_{0}}\binom{a_{1}(ℓ) − 1}{I_{1}} … \binom{a_{d}(ℓ) − 1}{I_{d}}  (2.14)

with |c_{I}| ≤ 8^{i}i!. Let a_{jl}(ℓ) denote the number of π_{j}, π_{j}^{−1} occurences in e_{l}. Since

a_{j}(ℓ) = a_{j1}(ℓ) + … + a_{jt}(ℓ) ,

we can expand equation 2.14 as a sum of (t + 1)^{I_{0}}2^{I_{1}} … 2^{I_{d}} terms of the form

c_{s} (∏_{l=1}^{t} k_{l}^{s_{l}}) (∏_{j=1}^{d} ∏_{l=1}^{t}(a_{jl}(ℓ))^{s_{jl}} )

with coefficients c_{s} bounded by (cdr)^{cr} and with

∑_{l} s_{l} + ∑_{j,l} s_{j,l} ≤ i.

Fix a lettering, and let \overline{L} denote those ℓ ∈ L of that lettering. We can write

∑_{ℓ∈\overline{L}} ∏_{j,l}(a_{jl}(ℓ))^{s_{jl}} = ∏_{l=1}^{t} ∑_{w∈Irred_{k_{l},σ_{l},τ_{l}}} ∏_{j=1}^{d}(a_{jl}(w))^{s_{jl}} ,

with σ_{1}, …, σ_{t}, τ_{1}, …, τ_{t} given by the lettering. By corollary 2.12, the above is

= ∏_{l=1}^{t}[(2d − 1)^{k_{l}}P_{l}(k_{l}) + (−1)^{k_{l}}Q_{l}(k_{l}) + R_{l}(k_{l})] ,

with P_{l}, Q_{l}, R_{l} polynomials of degree ≤ 2 ∑_{l} s_{j,l} and coefficients bounded by (cdr)^{cr} for some absolute constant c. Hence the above is

∑_{K_{1},K_{2},K_{3} partition {k_{1},...,k_{t}}} (2d − 1)^{|K_{1}|}(−1)^{|K_{2}|}Q_{K_{1},K_{2},K_{3}}(k_{1}, …, k_{t}) ,

for polynomials Q_{K_{1},K_{2},K_{3}} of degree ≤ 2 ∑_{j,l} s_{j,l} with coefficients bounded by (cdr)^{cr} for some absolute constant c. Summing the above over the ≤ (2d)^{6r−2} letterings yields the lemma.

□

Our goal is to sum p_{i}(T, ℓ) over all triples (T, y, ℓ) corresponding to pairs (Γ, w) with w ∈ Irred_{k}. So far we can estimate

∑_{ℓ∈L} p_{i}(T, ℓ)

with L = L_{T,k_{1},...,k_{t}}. We start summing over walks. So fix multiplicitites m_{1}, …, m_{t}, and let k = k_{1}m_{1} +⋯+k_{t}m_{t}. Clearly k is the length of w in any (Γ, w) corresponding to a (T, y, ℓ) with multiplicity m_{1}, …, m_{t} and weights k_{1}, … k_{t}.

Lemma 2.14 For fixed type, T, with t edges and of coincidence ≤ r, fixed multiplicities m_{l}, and i ≤ r + 1 we have for any k ≥ m = m_{1} + ⋯ + m_{t}

∑_{{k_{1},...,k_{t} ≥ 1 with \atop k_{1}m_{1}+···+k_{t}m_{t}=k}} ∑_{ℓ∈L_{T,k_{1},...,k_{t}}} p_{i}(T, ℓ) = (2d − 1)^{k+t−m}P_{i}(k) + ϵ

where ϵ vanishes if m_{1} = … = m_{t} = 1 and otherwise

|ϵ| ≤ (2d − 1)^{(k−m)/2}k^{t+2i}(crd + m)^{cr^{2}} ,

and P_{i} a polynomial of degree t + 2i with coefficient bounded by (crd + m)^{cr^{2}} for some absolute constant c.

Proof Applying lemma 2.13 and exchanging summations yields

∑_{k_{1},...,k_{t}} ∑_{ℓ} p_{i}(T, ℓ) = ∑_{K_{1},K_{2},K_{3}} ∑_{{k_{1},...,k_{t} ≥ 1 with \atop k_{1}m_{1}+···+k_{t}m_{t}=k}}(2d−1)^{|K_{1}|}(−1)^{|K_{2}|}P_{K_{1},K_{2},K_{3}}(k_{1}, …, k_{t}) .

Fix a partition, K_{1}, K_{2}, K_{3}. We shall need some sublemmas.

Sublemma 2.15 For any integer r, integer t ≤ 3r − 1, and polynomial P of degree ≤ r + t, we have for any k ≥ t

∑_{{k_{1}+k_{2}+···+k_{t}=k \atop k_{i}≥1}} P (k_{1}, …, k_{t}) = Q(k)

with Q of degree deg(P) + t − 1 with

|Q| ≤ |P |(cdr)^{crt} ,

where | | for a polynomial denotes the largest absolute value among its coefficients.

Proof We proceed by induction on t. For t = 1 there is nothing to prove. We claim that if the sublemma holds for t replaced by t − 1, then it also holds for t. To see this, we write

P (k_{1}, …, k_{t}) = ∑_{l=0}^{deg(P)} \overline{P}_{l}(k_{1}, …, k_{t−1})k_{t}^{l},

with deg(\overline{P}_{l}) ≤ deg(P) − l, and |\overline{P}_{l}| ≤ |P |. Applying the sublemma to each \overline{P}_{l} we get

∑_{{k_{1}+k_{2}+···+k_{t}=k \atop k_{i}≥1}} P (k_{1}, …, k_{t}) = ∑_{l=0}^{deg(P)} ∑_{j=1}^{k−t+1} Q_{l}(k − j)j^{l} ,

with Q_{l} of degree ≤ deg(P)−l+(t−2) and with coefficients bounded by |P |(cdr)^{cr(t−1)}. For each fixed l, the sum over j on the left-hand-side of the above is clearly a polynomial of degree 1+l+deg(Q_{l}) ≤ deg(P)+t−1 and coefficients bounded by |P |(cdr)^{crt}, assuming c is sufficiently large. Summing over l, using deg(P) ≤ r + t ≤ 4r − 1 proves the inductive step.

□

Sublemma 2.16 For any m_{1} = 1, m_{2}, …, m_{t}, partition K_{1}, K_{2}, K_{3} of {k_{1}, …, k_{t}} with k_{1} ∈ K_{1}, t ≤ 3r − 1, and polynomial P of degree ≤ r + t, we have for any k ≥ m = 1 + m_{2} + ⋯ + m_{t}

∑_{{k_{1}m_{1}+k_{2}m_{2}+···+k_{t}m_{t}=k \atop k_{i}≥1}} (2d − 1)^{|K_{1}|}(−1)^{|K_{2}|}P (k_{1}, …, k_{t}) = (2d − 1)^{k+t−m}Q(k) + ϵ

(2.15)

where ϵ vanishes if m_{i} = 1 and k_{i} ∈ K_{1} for all i, and otherwise

|ϵ| ≤ (2d − 1)^{(k−m)/2}k^{deg(P)+t−1}|P |(cdr + m)^{crt} ,  (2.16)

and with Q of degree deg(P) + t − 1 with

|Q| ≤ |P |(cdr + m)^{crt} .  (2.17)

Proof We can assume k_{1}, …, k_{s} are all in K_{1}, that m_{1} = … = m_{s} = 1, and that K_{1} = {k_{1}, …, k_{u}} with m_{s+1}, …, m_{u} all greater than 1. Writing

P (k_{1}, …, k_{t}) = ∑_{l=0}^{deg(P)} \overline{P}_{l}(k_{1}, …, k_{s})\overline{R}_{l}(k_{s+1}, …, k_{t})

with \overline{R}_{l} of degree l, by sublemma 2.15 we can write the sum in equation 2.15 as

∑_{l=0}^{deg(P)} ∑_{j=m−s}^{k−s} ∑_{{k_{s+1}m_{s+1}+···+k_{t}m_{t}=j \atop k_{l}≥1}} (2d−1)^{k_{s+1}+···+k_{u}}(−1)^{|K_{2}|}(2d−1)^{k−j}Q_{l}(k−j)R_{l}(k_{s+1}, …, k_{t}) .

For each fixed l we write the above sum over j as

∑_{j=m−s}^{k−s}( ) = ∑_{j=m−s}^{∞}( ) − ∑_{k−s+1}^{∞}( )

where ( ) denotes the summand (for j) in the preceding equation. Note that the number of solutions to k_{s+1}m_{s+1} + ⋯ + k_{t}m_{t} = j is clearly ≤ \binom{j+t−s−1}{t−s−1}, and that

k_{s+1} + ⋯ + k_{u} ≤ \frac{1}{2}(2k_{s+1} + ⋯ + 2k_{u})
≤ \frac{1}{2}(j − m_{u+1} − ⋯ − m_{t} − (m_{s+1} − 2)k_{s+1} − ⋯ − (m_{u} − 2)k_{u})
≤ \frac{1}{2}(j − m_{u+1} − ⋯ − m_{t} − (m_{s+1} − 2) − ⋯ − (m_{u} − 2))
≤ \frac{1}{2}(j − m + 2(u − s) + s)
≤ \frac{1}{2}(j − m − s) + t .

It follows from the identity

∑_{n=0}^{∞} \binom{n}{τ}ρ^{n} = \frac{ρ^{τ+1}}{(1 − ρ)^{τ}}

that

∑_{j=m−s}^{∞}( ) = (2d − 1)^{k−m}Q̃_{l}(k)

where Q̃ is a polynomial of degree ≤ deg(Q_{l}), and |Q̃_{l}| ≤ |Q_{l}||R_{l}|(crd + m)^{crt} ≤ |P |(crd + m)^{crt}, and that

| ∑_{k−s+1}^{∞}( )| ≤ (2d − 1)^{(k−m)/2}k^{deg(P)+t−s−1}|P |(cdr + m)^{crt}.

Summing over l completes the proof.

□

Sublemma 2.17 For any m_{1}, m_{2}, …, m_{t}, partition K_{1}, K_{2}, K_{3} of {k_{1}, …, k_{t}} with k_{1} ∈ K_{1}, t ≤ 3r − 1, and polynomial P of degree ≤ r + t, we have for any k ≥ m = m_{1} + m_{2} + ⋯ + m_{t}

∑_{{k_{1}m_{1}+k_{2}m_{2}+···+k_{t}m_{t}=k \atop k_{i}≥1}} (2d − 1)^{|K_{1}|}(−1)^{|K_{2}|}P (k_{1}, …, k_{t}) = ϵ

where

|ϵ| ≤ (2d − 1)^{(k−m)/μ}k^{deg(P)+t−1}|P |(cdr + m)^{crt} ,

where μ is the smallest integer among the m_{i} with k_{i} ∈ K_{1}.

Proof We do the same calculation as in the last sublemma, the difference being that this time we have

k_{1} + ⋯ + k_{u} ≤ \frac{1}{μ}(μk_{1} + ⋯ + μk_{u}) ≤ \frac{1}{μ}(j − m) + u

and therefore get the 1/μ factor in the exponent of (2d − 1).

□

To finish the proof of lemma 2.14, we sum over the 3^{t} partitions of {k_{1}, …, k_{t}} into three sets, K_{1}, K_{2}, K_{3}, applying one of the sublemmas (noting that rt ≤ 3r^{2}).

□

Let

P_{i,T,m⃗}(k)

denote the polynomial P_{i} in lemma 2.14, which depends (only) on T and m_{1}, …, m_{t}, where we use m⃗ to abbreviate the sequence (m_{1}, …, m_{t}). For an ordered type T and multiplicities m⃗, let W (T; m⃗) be the number of legal walks in T with multiplicities m⃗ = (m_{1}, …, m_{t}). By lemma 2.6,

∑_{|m⃗|=m} W (T; m⃗) ≤ (2r)^{m}

for types of coincidence ≤ r, where |m⃗| = m_{1} + … + m_{t}. It follows from this and lemma 2.14 that for any type of coincidence ≤ d − 1 the infinite sum

∑_{m_{1}=1}^{∞} ⋯ ∑_{m_{t}=1}^{∞} W (T; m⃗)(2d − 1)^{t−m}P_{i,T,m⃗}(k)

converges for each i to a polynomial of degree 2i + t, which we denote f_{i,T}. For 0 ≤ i ≤ d − 2, let

f_{i}(k) = ∑_{coin(T)≤i+1} f_{i+1−coin(T) , T} (k) ,

which is a polynomial in k of degree ≤ 2i + (3i + 2) = 5i + 2, since t ≤ 3i + 2 for any T of coincidence ≤ i + 1.

Theorem 2.18 Let d and r ≤ \sqrt{2d − 1}/2 be fixed positive integers. For any fixed v ∈ {1, …, n} we have

E \{ ∑_{w∈Irred_{k}} v →^{w} v\} = 2d(2d−1)^{k−1} (\frac{1}{n} f_{0}(k) + \frac{1}{n^{2}} f_{1}(k) + … + \frac{1}{n^{r}} f_{r−1}(k) + error ) ,

where

error ≤ \frac{k^{2r+2}}{n^{r+1}} (1 + 2k^{2r}e^{(r+1)k/n}) + (2d − 1)^{−k/2} ∑_{i=0}^{r−1} \frac{(ckid)^{ci^{2}}}{n^{i+1}}

and where the f_{i} are polynomials of degree ≤ 5i + 2 whose coefficients are bounded by (cdr)^{cr^{2}}, where c is an absolute constant (independent of d and r). For any

k ≤ \frac{1}{cd^{3/2}} n^{1/(c\sqrt{d})}

we have

error ≤ \frac{k^{4r+2}}{n^{r+1}} c + (2d − 1)^{−k/2} \frac{(ckd)^{c}}{n} .

Proof By virtue of the one-to-one correspondence between pairs (Γ, w) and triples (T, y, ℓ) we have

E \{ ∑_{w∈Irred_{k}} i →^{w} i\} = \frac{1}{n} ∑_{T} ∑_{m_{1},...,m_{t}} [W (T; m⃗) ∑_{{k_{1},...,k_{t} ≥ 1 with \atop k_{1}m_{1}+···+k_{t}m_{t}=k}} ∑_{ℓ∈L_{T,k_{1},...,k_{t}}} Pr (T, ℓ)] ,

where Pr (), as with p_{i}, extends from a function on general forms, Γ, to a function on pairs (T, ℓ). The probability that the walk along v starting at i has more than r coincidneces is no more than the number of ways of choosing r + 1 points of the k unknown points times the probability that each of these points is indeed a coincidence. Thus we can replace the summation over all types, T, above, with a summation over all types T of coincidence ≤ r while incurring an error of no more than

2d(2d − 1)^{k−1}\binom{k}{r + 1}(\frac{k}{n − k} )^{r+1} ≤ 2d(2d − 1)^{k−1} \frac{k^{2r+2}}{n^{r+1}}

if k ≤ n/2. Obviously the second summation has non-zero terms only when m = m_{1} + ⋯ + m_{t} is ≤ k; we shall restrict the second sum to being over such m.

The total number of Pr (T, ℓ)’s occuring in the above quadruple summation is the same as the total number of (Γ, w) pairs (and less when we restrict ourselves to types of coincidence ≤ r − 1). For each w ∈ Irred_{k} there are no more than

∑_{j=0}^{r} \binom{k}{j}k^{j} ≤ 2k^{2r}

compatible Γ’s of coincidence ≤ r, because Γ there is at most one Γ for any j ≤ r specified points of coincidence (among the k unknown points t_{1}, …, t_{k} of the walk) once we specify at which of the previous vertices each of the j coincidences arrive. By lemma 2.7 we have for each T of coincidence ≤ r

Pr (T, ℓ) = \frac{p_{0}}{n^{coin(T)−1}} + \frac{p_{1}}{n^{coin(T)}} + ⋯ + \frac{p_{r−1}}{n^{r−1}} + \frac{ϵ}{n^{r}} ,

where ϵ is bounded by

e^{(r+1)k/n}k^{2r+2}.

It follows that

\frac{1}{n} ∑_{coin(T)≤r} ∑_{m≤k} W (T; m⃗) ∑_{k⃗,ℓ} Pr (T, ℓ) = \frac{1}{n}(f̃_{0}(k) + \frac{f̃_{1}(k)}{n} + … + \frac{f̃_{r−1}(k)}{n^{r−1}} + \frac{δ}{n^{r}} )

(2.18)

(we have abbreviated the inner two summations by ∑_{k⃗,ℓ}) where

δ ≤ k^{2r+2}(1 + 2k^{2r}e^{(r+1)k/n}) ,  (2.19)

and

f̃_{i}(k) = ∑_{coin(T)≤i+1} ∑_{|m⃗|≤k} W (T; m⃗) ∑_{k⃗,ℓ} p_{i+1−coin(T)}(T, ℓ) .

We claim that f̃_{i}(k) do not differ much from the infinite sum

f_{i}(k) = ∑_{coin(T)≤i+1} ∑_{m⃗} W (T; m⃗)(2d − 1)^{t−m}P_{i+1−coin(T),T,m⃗}(k) .  (2.20)

By lemma 2.14 we have for any type of coincidence ≤ i + 1, for i ≤ r − 1,

|(2d − 1)^{t−m}P_{i+1−coin(T),T,m⃗}(k) − ∑_{k⃗,ℓ} p_{i+1−coin(T)}(T, ℓ)| ≤ (2d−1)^{(k−m)/2}k^{(3(i+1)−2)+2(i+1)}(crd+m)^{ci^{2}} .

Since there are less than (2i + 2)^{6i+5} types of coincidnece ≤ i + 1, and since for each such type there are ≤ (2i + 2)^{m} ≤ (2d − 1)^{m/2} legal walks with |m⃗| = m, we have

∑_{coin(T)≤i+1} ∑_{m≤k} W (T, m⃗) |(2d − 1)^{t−m}P_{i+1−coin(T),T,m⃗}(k) − ∑_{k_{l}} ∑_{ℓ} p_{i}(T, ℓ)| ≤ (2d−1)^{k/2}(ckid)^{ci^{2}}.

(2.21)

It remains to estimate

|f_{i}(k) − ∑_{coin(T)≤i+1} ∑_{|m⃗|≤k} W (T, m⃗)(2d − 1)^{t−m}P_{i+1−coin(T),T} (k)| ≤

∑_{coin(T)≤i+1} ∑_{|m⃗|>k} W (T, |m⃗|)(2d − 1)^{t−m} |P_{i+1−coin(T),T} (k)| .  (2.22)

By lemma 2.14, each P_{i,T,m⃗} has degree ≤ t + 2i, and coefficients bounded by (cid + m)^{ci^{2}}. Thus we have

|P_{i+1−coin(T),T,m⃗}(k)| ≤ k^{t+2i}(cid + m)^{ci^{2}}

and thus for a type, T, of coincidence ≤ i + 1 we have that the expression in equation 2.22 is bounded by

k^{5i+2}(2d − 1)^{3i+2} ∑_{m=k+1}^{∞}(\frac{2i + 2}{2d − 1})^{m}(cid + m)^{ci^{2}} ≤ (ckid)^{ci^{2}}(\frac{2i + 2}{2d − 1})^{k}

(for i ≤ d − 2). Combining the above with equations 2.18, 2.19, and 2.21 yields the first estimate on the error term. For

k ≤ \frac{1}{c′d^{3/2}} n^{1/(c′\sqrt{d})} ,

assuming i ≤ \sqrt{2d − 1}/2, the sum

∑_{i=0}^{r−1} \frac{(ckid)^{ci^{2}}}{n^{i+1}}

is clearly bounded by the first term. Finally, f_{i}’s coefficients are bounded by

(2i + 2)^{6i+5} ∑_{m=1}^{∞}(cid + m)^{ci^{2}}(\frac{2i + 2}{2d − 1})^{m} ≤ (c′id)^{c′i^{2}}

(for i ≤ d − 2).

□

3 Consequences of the Expansion

We start by computing f_{0}, f_{1}, … in theorem 2.18. Without too much work, one can use methods akin to those of section 2 to argue that f_{0}(k) = 1 and if f_{1}(k) is nonzero, then its leading coefficient is negative (which is as good as proving f_{1}(k) = 0 as far as eigenvalue estimates are concerned). Direct arguments for other f_{l}’s seem harder to come by. We will argue by using previously known facts about the second eigenvalue, which will give the desired values for the f_{l}’s. These values for f_{l} will in turn give much sharper information on the second eigenvalues, as we will show later in this section. We warn the reader that other literature on this subject often work with d regular, not 2d regular, graphs; to maintain consistency when quoting results or using techniques from previous work, we will sometimes state theorems in terms of d regular graphs.

Theorem 3.1 For every d > 2 there is a constant α > 0 such that for a random graph G ∈ G_{n,2d} we have

Pr \{|λ_{2}(G)| ≤ 2d − α\} = 1 − \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ) ,
Pr \{λ_{2}(G) = 2d\} = \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ) .

Proof A graph, G, with n vertices is said to be a γ-magnifier if for all subsets of vertices, A, of size ≤ n/2 we have

|Γ(A) − A| ≥ γ|A|,

where Γ(A) denotes those vertices connected to some member of A by an edge. It is known that any d regular γ-magnifier has

λ_{2}(G) ≤ d − \frac{γ^{2}}{4 + 2γ^{2}}

(see [Alo86]). We say that G is a γ-expander if for all subsets of vertices, A, of size ≤ n/2 we have

|Γ(A)| ≥ (1 + γ)|A|.

A standard counting argument gives the following.

Lemma 3.2 G ∈ G_{n,2d} is not a γ-expander with probability

≤ ∑_{m=1}^{n/2} \binom{n}{m}\binom{n}{⌊(1 + γ)m⌋}(\frac{m + ⌊mγ⌋}{n})^{md} ,

and more precisely

≤ \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ) + ∑_{m=3}^{n/2} \binom{n}{m}\binom{n}{⌊(1 + γ)m⌋}(\frac{m + ⌊mγ⌋}{n})^{md} ,

for γ < 1/3.

Proof For fixed subsets of V, A and B, we have

Pr {Γ(A) ⊂ B} ≤ Pr {π_{i}(a) ∈ B ∀a ∈ A, ∀i ∈ {1, …, d}}
≤ (\frac{|B|}{n} \frac{|B| − 1}{n − 1} … \frac{|B| − |A| + 1}{n − |A| + 1})^{d} ≤ (\frac{|B|}{n})^{d|A|} .

If G is not a γ-expander, then there exist some m ∈ {1, …, n/2}, |A| = m, and |B| = ⌊(1 + γ)m⌋ with Γ(A) ⊂ B. This yields the first estimate. To refine this estimate, notice that the bound given for Pr {Γ(A) ⊂ B} is only tight when A = B. Indeed, if A and B are disjoint, then for Γ(A) to be contained in B we need both π_{i} and π_{i}^{−1} to map A into B for each π_{i}, which roughly doubles the amount of conditioning on each π_{i}. In particular, for |A| = |B| = 1, A ≠ B we have

Pr \{Γ(A) ⊂ B\} ≤ (\frac{1}{n(n − 1)})^{d},

and a similar analysis for the case |A| = 2 and |A ∩ B| = 1 or 0, giving the second estimate.

□

Assuming γ < 1/3 and using the estimate \binom{n}{m} ≤ (ne/m)^{m} we can bound the probability that G ∈ G_{n,2d} is not a γ-expander by

\frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ) + ∑_{m=3}^{n/2}(\frac{m}{n})^{m(d−2)}((1 + γ)^{2d+1+γ}e^{2+γ})^{m} = \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} )

if γ is sufficiently close to 0 and d > 2. If G is a γ-expander, then clearly G^{2}, the graph whose adjacency matrix is the square of G’s, is also a γ-expander, and thus also a γ-magnifier. Therefore

(λ_{2}(G))^{2} ≤ 4d^{2} − \frac{γ^{2}}{4 + 2γ^{2}}

with probability at least

1 − \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ) .

On the other hand, λ_{2}(G) = d if G has an isolated vertex. By the inclusionexclusion principle, this happens with probability

≤ n(\frac{1}{n^{d}} )

and

≥ n(\frac{1}{n^{d}} ) − \binom{n}{2}(\frac{1}{n^{d}} )^{2} .

□

Let G = (V, E) be an undirected d-regular graph. By a non-backtracking walk in G we mean a walk that at no point in the walk traverses an edge and then on the next step traverses the same edge in the reverse direction. For vertices v, w, and integer k, let F_{k}(v, w) be the number of non-backtracking walks of length k from v to w. Let

W_{G}(k) = ∑_{v∈V} F_{k}(v, v) .

Theorem 2.18 gives us the expected value of W_{G}(k) for a random G ∈ G_{n,2d}. In the spirit of [LPS86] we have:

Lemma 3.3 Let the eigenvalues of G’s adjacency matrix be λ_{1}, ⋯, λ_{n}. Then

W_{G}(k) = ∑_{i=1}^{n} q_{k}(λ_{i}) ,

where q_{k} is a polynomial of degree k. It is given by

q_{k}(2\sqrt{d − 1} cos θ) = (\sqrt{d − 1})^{k}(\frac{2}{d − 1} cos kθ + \frac{d − 2}{d − 1} \frac{sin(k + 1)θ}{sin θ} ) .

Proof Regarding F_{k} as an n × n matrix, we easily see that F_{0} = I, F_{1} = A, where A is the adjacency matrix of G,

F_{2} = A^{2} − dI ,

and for any t ≥ 3 we have

F_{t} = AF_{t−1} − (d − 1)F_{t−2} .

It follows that

F_{k} = q_{k}(A)

where q_{k} is some k degree polynomial independent of A, and that

W_{G}(k) = Trace (F_{k}) = Trace (q_{k}(A)) = ∑_{i=1}^{n} q_{k}(λ_{i}) .

One can solve for q_{k} explicitly by noting that for fixed λ, q_{k} = q_{k}(λ) satisfies the simple recurrence

q_{k} = λq_{k−1} − (d − 1)q_{k−2} .

One therefore has

q_{k} = c_{1}(r_{1})^{k} + c_{2}(r_{2})^{k}

for some c_{1}, c_{2}, where r_{1}, r_{2} are the roots of

r^{2} − λr + (d − 1) = 0 .

One can directly solve for r_{1}, r_{2}, c_{1}, c_{2}, but it is easier to substitute λ = 2\sqrt{d − 1} cos θ. One gets

r_{1,2} = \sqrt{d − 1}e^{±iθ} ,

and then after a few more calculations and simplifications one gets

q_{k}(2\sqrt{d − 1} cos θ) = (\sqrt{d − 1})^{k}(\frac{2}{d − 1} cos kθ + \frac{d − 2}{d − 1} \frac{sin(k + 1)θ}{sin θ} ) .

□

The q_{k}(λ)’s are quite easy to use. For example, if λ = d, the first eigenvalue, then clearly

q_{k}(d) = d(d − 1)^{k−1} .

For |λ| ≤ 2\sqrt{d − 1} one has λ = 2\sqrt{d − 1} cos θ for some real θ, and therefore

|q_{k}(λ)| ≤ (\sqrt{d − 1})^{k}(k + 2)  (3.1)

since | sin(k + 1)θ/ sin θ| is always ≤ k + 1. Otherwise, say for λ > 2\sqrt{d − 1}, one can rewrite the identity in lemma 3.3 as

q_{k}(2\sqrt{d − 1} cosh x) = (\sqrt{d − 1})^{k}(\frac{2}{d − 1} cosh kx + \frac{d − 2}{d − 1} \frac{sinh(k + 1)x}{sinh x})

and solve λ = 2\sqrt{d − 1} cosh x. For λ < −2\sqrt{d − 1} one solves for λ = −2\sqrt{d − 1} cosh x and proceeds similarly. For |λ| near 2\sqrt{d − 1}, sin θ or sinh x is very close to 0, and it is convenient to write

\frac{sin(k + 1)θ}{sin θ} = cos kθ + cos θ cos(k − 1)θ + cos^{2} θ cos(k − 2)θ + ⋯ + cos^{k} θ

for estimating. In particular, since as x ≥ 0 increases λ = 2\sqrt{d − 1} cosh x increases, we have that for all λ with 2\sqrt{d − 1} ≤ λ ≤ d − α,

x = cosh^{−1}(\frac{λ}{2\sqrt{d − 1}})

must be

≤ cosh^{−1}(\frac{d}{2\sqrt{d − 1}}) − ϵ

for some positive ϵ. Doing the same for λ negative we therefore get

Lemma 3.4 For any α > 0 there is a δ > 0 such that if |λ| ≤ d − α, then

|q_{k}(λ)| ≤ (k + 2)(d − 1 − δ)^{k} .

Proof Using cosh(x + y) = cosh x cosh y + sinh x sinh y ,

it follows that

cosh kx ≥ cosh x cosh(k − 1)x ≥ cosh^{2} x cosh(k − 2)x ≥ …

Also, cosh kx ≤ e^{kx} ≤ (d−1−δ)^{k} for all x corresponding to |λ| ≤ d−α, |λ| ≥ 2\sqrt{d − 1}. For |λ| ≤ 2\sqrt{d − 1}, the lemma follows from equation 3.1

□

Theorem 3.5 In theorem 2.18, with r ≤ ⌊\sqrt{2d − 1}/2⌋, we have f_{0}(k) = 1 and f_{j}(k) = 0 for j ≥ 1, if d − 2 > \sqrt{2d − 1}/2 (i.e. d ≥ 4).

Proof By theorem 3.1 we have that (remember, the degree is now 2d)

E \{ ∑_{w∈Irred_{k}} v →^{w} v\} = (1 − \frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ))(2d(2d − 1)^{k−1} + O((k + 2)(2d − 1 − δ)^{k})) +

(\frac{1}{n^{d−1}} + O(\frac{1}{n^{2d−2}} ))O(n2d(2d − 1)^{k−1}) .

Taking k even and = ⌊(log n)^{2}⌋ or = ⌊(log n)^{2}⌋ + 1, letting n → ∞, and noticing that (2d − 1 − δ)^{k}/(2d − 1)^{k} and (2d − 1)^{−k/2} are less than any polynomial in n as n → ∞ yields f_{0}(k) = 1 and f_{j}(k) = 0 for any j ≥ 1.

□

To restate the results so far:

Corollary 3.6 For any fixed v, k ≥ 1, and d − 2 > \sqrt{2d − 1}/2 (i.e. d ≥ 4) we have

E \{ ∑_{w∈Irred_{k}} v →^{w} v\} = 2d(2d − 1)^{k−1} (\frac{1}{n} + error_{n,k}) ,

where

error_{n,k} ≤ (ckd)^{c}(\frac{k^{2\sqrt{2d}}}{n^{1+⌊\sqrt{2d−1}/2⌋}} + \frac{(2d − 1)^{−k/2}}{n} ) .

□

Now we use this corollary to estimate the expected sum of the k-th powers of the eigenvalues. Any word in Π^{k} can be reduced by repeatedly cancelling all consecutive occurences of π, π^{−1} in the word, until we get an irreducible word; this irreducible word is independent of how the reducing was done. Notice that

\frac{1}{(2d)^{k}} E \{ ∑_{w∈Π^{k}} v →^{w} v\} = p_{k,0} + ∑_{s=1}^{k} p_{k,s} \frac{1}{2d(2d − 1)^{s−1}} E \{ ∑_{w∈Irred_{s}} v →^{w} v\} ,

where p_{k,s} is the probability that a random word in Π^{k} reduces to an irreducible word of size s. Since ∑_{s} p_{k,s} = 1, we have

\frac{1}{(2d)^{k}} ∑_{v} E \{ ∑_{w∈Π^{k}} v →^{w} v\} = 1 + (n − 1)p_{k,0} + ∑_{s=1}^{k} np_{k,s} error_{n,s}

and therefore

E {∑_{i=2}^{n} λ_{i}^{k}} = (2d)^{k}(n − 1)p_{k,0} + (2d)^{k} ∑_{s=1}^{k} np_{k,s} error_{n,s} .  (3.2)

To estimate the above, first notice that p_{k,s} = 0 if k and s have different parity. In [BS87], the following estimate is given:

Lemma 3.7

p_{2k,2s} ≤ \frac{2s + 1}{2k + 1}\binom{2k + 1}{k − s}(\frac{1}{2d})^{k−s}(1 − \frac{1}{2d})^{2s−1}

Proof See [BS87]; for an exact formula and sharper bounds, see [McK81].

□

Incidentally, from the proof of the above lemma in [BS87] it is clear that also

p_{2k,0} ≥ \frac{1}{2k + 1}\binom{2k + 1}{k}\frac{(2d − 1)^{k}}{(2d)^{2k}} .

It follows that for any graph of degree 2d,

∑_{i=1}^{n} λ_{i}^{2k} ≥ (2d)^{2k}(n − 1)p_{k,0} ≈ (n − 1)2^{2k}(2d − 1)^{k},

so that taking 2k slightly less than 2 log_{d} n yields the lower bound mentioned in the introduction,

|λ_{2}| ≥ 2\sqrt{2d − 1} + O(\frac{1}{log_{d} n}).

Now we take k = 2⌊log n ⌊\sqrt{2d − 1}/2⌋/ log d⌋, so that k is even, and calculate using the simplified bound

p_{2k,2s} ≤ 2^{2k}(\frac{1}{2d})^{k−s} .

It is easy to see that the dominant terms of the summation over s in equation 3.2 are s = 1 and s = k, and therefore

E \{∑_{i=2}^{n} λ_{i}^{k}\} ≤ n^{1+ \frac{log 2}{log d}} (ckd)^{c}k^{2\sqrt{2d}}(2\sqrt{2d}\sqrt{\frac{2d}{2d − 1}})^{k} .

Taking k-th roots, applying Hölder’s (or Jensen’s) inequality, and noticing that

(n^{1+ \frac{log 2}{log d}} )^{1/k} = 1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}}) ,

4 CONCLUDING REMARKS 32

that

(ckd)^{c/k}k^{2\sqrt{2d}/k} = 1 + O(\frac{log d log log n}{log n}),

and that

k ≤ \frac{1}{cd^{3/2}} n^{\frac{1}{c\sqrt{d}}}

for

\frac{log n}{log log n} ≥ c′\sqrt{d}

yields: Theorem 3.8 For G ∈ G_{n,2d} we have

E \{|λ_{2}(G)|\} ≤ 2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n})

(with an absolute constant in the O( ) notation), and more generally

E \{|λ_{2}(G)|^{m}\} ≤ (2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n}))^{m}

for any m ≤ 2⌊log n ⌊\sqrt{2d − 1}/2⌋/ log d⌋.

□

As a corollary we also get: Theorem 3.9 For any β > 1 we have

|λ_{2}(G)| ≥ (2\sqrt{2d − 1}(1 + \frac{log d}{\sqrt{2d}} + O(\frac{1}{\sqrt{d}})) + O(\frac{d^{3/2} log log n}{log n}))β

with probability

≤ \frac{β^{2}}{n^{2⌊\sqrt{2d−1}/2⌋ log β/ log d}} .

4 Concluding Remarks

An interesting question would be to see if an expansion in theorem 2.18 exists for r > \sqrt{2d − 1}/2. In section 2 we defined f_{i}(k) really for any i such that

∑_{m=0}^{∞}(\frac{2i + 2}{2d − 1})^{m}

converges, which is to say any i ≤ d − 2. We only used f_{i}(k) for i ≤ (\sqrt{2d − 1}/2) − 1, because in equation 2.21, we needed to use

(2i + 2)^{m} ≤ (2d − 1)^{m/2}

in order to get a reasonable bound on the error term. If there were some way to bound this error term by a reasonable quantity for larger i, one could extend the expansion, with the n^{−j} coefficient being f_{j−1}(k). Whether or not f_{i}(k) for i ≥ (\sqrt{2d − 1}/2) − 1 is involved in an asymptotic expansion, it might be interesting to evaluate them, since they seem to be a fairly naturally defined quantity.

If one were able to get an expansion up to r-th order for r close to d, one might notice G_{n,2d}’s weakness, that according to theorem 3.1 a graph in G_{n,2d} has a d as a multiple eigenvalue with probability on the order of n^{−(d−1)}. From the arguments in section 3, it would follow that the expansion, if it existed, would fail to vanish by the n^{−d+1} term. However, one might hope for a better second eigenvalue estimate through various approaches. First of all, one might be able to find the graphs which give the non-vanishing terms, such as graphs with isolated vertices for the n^{−d+1} term, and thus show that upon removing them (which does not affect the probability measure very much) one has a better moment estimate. Secondly, one might do better with a different probability distribution, say H_{n,2d}, which is constructed like G_{n,2d} but only allows permutations, π, which consist of one cycle. There are (n − 1)! such permutations, and once a values of such a π have been determined (which do not already give π a cycle), there are

\frac{(n − 1)!}{(n − 1)(n − 2) … (n − a)}

ways of completing π to be a permutation of one cycle. It follows that over H_{n,2d} one has

Pr (Γ) = n(n − 1) … (n − |V_{Γ}| + 1) ∏_{j=1}^{d} \frac{1}{(n − 1)(n − 2) …(n − a_{j}(Γ))} ,

and therefore the asymptotic expansion and second eigenvalue theorems hold for H_{n,2d} as well. However, in H_{n,2d} one can never have an isolated vertex or similar phenomena, and so one would have a much better theorem 3.1 for H_{n,2d}, and a possibility of having a further than d-th order expansion for which all lower order terms vanish.

References

[Alo86] N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986.

[BS87] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 286–294, 1987.

[FK81] Z. Füredi and J. Komlós. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233–241, 1981.

[Gem80] S. Geman. A limit theorem for the norm of random matrices. Ann. of Prob., 8(2):252–261, 1980.

[Knu73] Donald E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, Reading, Massachusetts, second edition, 1973.

[KS] J. Kahn and E. Szemeredi. Personal communication, and to appear.

[LPS86] A. Lubotzky, R. Phillips, and P. Sarnak. Explicit expanders and the ramanujan conjectures. In 18th Annual ACM Symposium on Theory of Computing, pages 240–246, 1986.

[Mar87] G. Margulis. Manuscript in Russian on graphs with large girth, 1987.

[McK81] B. McKay. The expected eigenvalue distribution of a large regular graph. Lin. Alg. Appl., 40:203–216, 1981.

[Tan84] R.M. Tanner. Explicit concentrators from generalized N-gons. SIAM J. Alg. Disc. Methods, 5:287–293, 1984.

[Wig55] E. Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Math., 62(3):548–564, 1955.