A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems

Joel Friedman^{∗}

March 27, 2002 Third Revision: May 3, 2004

Abstract

A d-regular graph has largest or first (adjacency matrix) eigenvalue λ_{1} = d. Consider for an even d ≥ 4, a random d-regular graph model formed from d/2 uniform, independent permutations on {1, …, n}. We shall show that for any ϵ > 0 we have all eigenvalues aside from λ_{1} = d are bounded by 2\sqrt{d − 1} + ϵ with probability 1 − O(n^{−τ}), where τ = ⌈(\sqrt{d − 1} + 1)/2⌉ − 1. We also show that this probability is at most 1 − c/n^{τ′}, for a constant c and a τ′ that is either τ or τ + 1 (“more often” τ than τ + 1). We prove related theorems for other models of random graphs, including models with d odd.

These theorems resolve the conjecture of Alon, that says that for any ϵ > 0 and d, the second largest eigenvalue of “most” random dregular graphs are at most 2\sqrt{d − 1} +ϵ (Alon did not specify precisely what “most” should mean or what model of random graph one should take).

1 Introduction

The eigenvalues of the adjacency matrix of a finite undirected graph, G, are real and hence can be ordered

λ_{1}(G) ≥ λ_{2}(G) ≥ ⋯ ≥ λ_{n}(G),

∗Departments of Computer Science and Mathematics, University of British Columbia, Vancouver, BC V6T 1Z4 (V6T 1Z2 for Mathematics), CANADA. jf@cs.ubc.ca. Research supported in part by an NSERC grant.

where n is the number of vertices in G. If G is d-regular, i.e., each vertex is of degree d, then λ_{1} = d. In [Alo86], Noga Alon conjectured that for any d ≥ 3 and ϵ > 0, λ_{2}(G) ≤ 2\sqrt{d − 1} + ϵ for “most” d-regular graphs on a sufficiently large number of vertices. The Alon-Boppana bound shows that the constant 2\sqrt{d − 1} cannot be improved upon (see [Alo86, Nil91, Fri93]). The main goal of this paper is to prove this conjecture for various models of a “random d-regular graph.”

Our methods actually show that for “most” d-regular graphs, |λ_{i}(G)| ≤ 2\sqrt{d − 1} + ϵ for all i ≥ 2, since our methods are variants of the standard “trace method.”

Our primary interest in Alon’s conjecture, which was Alon’s motivation, is that fact that graphs with |λ_{i}| small for i ≥ 2 have various nice properties, including being expanders or magnifiers (see [Alo86]).

For a fixed n we can generate a random d-regular graph on n vertices as follows, assuming d is even (later we will give random graph models that allow d to be even or odd). Take d/2 permutations on V = {1, …, n}, π_{1}, …, π_{d/2}, each π_{i} chosen uniformly among all n! permutations with all the π_{i} independent. We then form

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

yielding a directed graph G = (V, E), which we may view as undirected. We call this probability space of random graphs G_{n,d}. G can have multiple edges and self-loops, and each self-loop contributes 2 to the appropriate diagonal entry of G’s adjacency matrix^{1}.

The main goal of this paper is to prove theorems like the following, which prove Alon’s conjecture, for various models of a random d-regular graph; we start with the model G_{n,d}.

Theorem 1.1 Fix a real ϵ > 0 and an even positive integer d. Then there is a constant, c, such that for a random graph, G, in G_{n,d} we have that with probability at least 1 − c/n^{τ} we have for all i > 1

|λ_{i}(G)| ≤ 2\sqrt{d − 1} + ϵ,

where τ = τ_{fund} = ⌈(\sqrt{d − 1} + 1)/2⌉ − 1 . Furthermore, for some constant c′ > 0 we have that λ_{2}(G) > 2\sqrt{d − 1} with probability at least c′/n^{s}, where s = ⌊(\sqrt{d − 1} + 1)/2⌋. (So s = τ_{fund} unless (\sqrt{d − 1} + 1)/2 is an integer, in which case τ_{fund} = s − 1.)

1Such a self-loop is a whole-loop in the sense of [Fri93]; see also Section 2 of this paper.

Left open is the question of whether or not this theorem holds with ϵ = 0 (which would yield “Ramanujan graphs”) or even some function ϵ = ϵ(n) < 0. Calculations such as those in [Fri93] suggest that it does, even for some negative function ϵ(n). Examples of “Ramanujan graphs,” i.e., graphs where |λ_{i}(G)| ≤ 2\sqrt{d − 1} except i = 1 (and, at times, i = n when λ_{n} = −d) have been given in [LPS88, Mar88, Mor94] where d is one more than an odd prime or prime power. Theorem 1.1 demonstrates the existence of “nearly Ramanujan” graphs of any even degree. We shall soon address odd d, as well.

Another interesting question arises in the gap between τ_{fund} and s in Theorem 1.1 in the case where (\sqrt{d − 1} + 1)/2 is an integer; it is almost certain that one of them can be improved upon. In the language of Section 4 of this paper, τ_{fund} is the smallest order of a supercritical tangle, and s that of a hypercritical tangle; a gap between τ_{fund} and s can only occur when there is a critical tangle of order smaller than that of any hypercritical tangle.

Previous bounds of the form λ_{2} ≤ f(d)+ϵ include f(d) = (2d)^{1/2}(d−1)^{1/4} of the author (see [Fri03]), which is slight improvement over the Broder-Shamir bound of f(d) = 2^{1/2}d^{3/4} (see [BS87]). Asymptotically in d, the bounds f(d) = C\sqrt{d} of Kahn and Szemerédi (see [FKS89], here C is some constant) and f(d) = 2\sqrt{d − 1}+2 log d+C of the author (see [FKS89, Fri91] and see equation (6) for the more precise bound) are improvements over the first two bounds.

The value of τ_{fund} in Theorem 1.1 depends on the particular model of a random graph. Indeed, consider the model H_{n,d} of a random graph, which is like G_{n,d} except that we insist that each π_{i} be one of the (n−1)! permutations whose cyclic decomposition consists of one cycle of length n. The same methods used to prove Theorem 1.1 will show the following variant.

Theorem 1.2 Theorem 1.1 holds with G_{n,d} replaced by H_{n,d} and τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1 and s = ⌊\sqrt{d − 1}⌋, except that when d = 4 we take s = 2.

Once again, τ_{fund} = s, unless a certain expression, in this case \sqrt{d − 1} (excepting d = 4), is an integer. Note that for H_{n,d}, the value of τ_{fund} is roughly twice as large as that for G_{n,d} for d large.

Next consider two more models of random d-regular graphs; in these two models d may be even or odd. Let I_{n,d}, for positive integers n, d with n even, be the model of a random d-regular graph formed from d random perfect matchings on {1, …, n}.

For an odd positive integer n, let a near perfect matching be a matching of n − 1 elements of {1, …, n}; such a matching becomes a 1-regular graph if it is complemented by a single half-loop^{2} at the unmatched vertex. Taking d independent such 1-regular graphs gives a model, J_{n,d}, of a d-regular graph on n vertices for n odd.

Theorem 1.3 Theorem 1.2 holds with H_{n,d} replaced by I_{n,d} and with no d = 4 exception (i.e., s = 1 for d = 4). Theorem 1.1 holds with G_{n,d} replaced by J_{n,d}.

We can assert the truth of the Alon conjecture on more models of random graphs by using results on continguity and related notions. Consider two families of probability spaces, (Ω_{n}, F_{n}, μ_{n})_{n=1,2,...} and (Ω_{n}, F_{n}, ν_{n})_{n=1,2,...} over the same sets Ω_{n} and sigma-algebras F_{n}; denote μ = {μ_{n}} and ν = {ν_{n}}. We say that μ dominates ν if for any family of measurable events, {E_{n}} (i.e., E_{n} ∈ F_{n}), we have μ_{n}(E_{n}) → 0 as n → ∞ implies ν_{n}(E_{n}) → 0 as n → ∞. We say that μ and ν are contiguous if μ dominates ν and ν dominates μ.

Corollary 1.4 Fix an ϵ > 0 and an integer d ≥ 2. Let L_{n} be any family of probability spaces of d-regular graphs on n vertices (possibly defined for only certain n) that is dominated by G_{n,d}, H_{n,d}, I_{n,d}, or J_{n,d}. Then for G in L_{n} we have that with probability 1 − o(1) (as n → ∞) for all i with 2 ≤ i ≤ n we have

|λ_{i}(G)| ≤ 2\sqrt{d − 1} + ϵ.

There are a lot of results regarding contiguity and (at least implicitly) domination; see [GJKW02, KW01, Wor99] and the references there. For example, if G′_{n,d} is the restriction of G_{n,d} to those graphs without self-loops, then for d ≥ 4 it is known that (1) G′_{n,d} and H_{n,d} are contiguous (by [KW01] and previous work), and (2) G_{n,d} dominates G′_{n,d} (easy, since a self-loop occurs in G_{n,d} with probability bounded away from 1 for fixed d). Thus the Alon conjecture for G_{n,d} implies the same for H_{n,d} (but this contiguity and/or domination approach does not give as tight a bound on the probablity that λ_{2} ≤ 2\sqrt{d − 1} + ϵ fails to hold as is given in Theorem 1.2). Also, G_{n,d} is contiguous with the “pairing” or “configuration” model of d-regular (pseudo)graphs (see [GJKW02]); it follows that the Alon conjecture holds for the latter model, and thus (see [Wor99], especially the beginning of Section 2 and Corollary 4.17) the conjecture holds for n (and d) even for I_{n,d} or the uniform measure on all d-regular (simple) graphs on n vertices.

2Readers unfamiliar with half-loops (i.e., self-loops contributing only 1 to a diagonal entry of the adjacency matrix) can see Section 2 of this paper or [Fri93].

Our method for proving Theorems 1.1, 1.2, and 1.3 is a variant of the well-known “trace method” (see, for example [Wig55, Gem80, FK81, BS87, Fri91]) originated by Wigner, especially the author’s refinement in [Fri91] of the beautiful Broder-Shamir style of analysis in [BS87]. The standard trace method involves taking the expected value of the trace of a reasonably high power^{3} of the adjacency matrix. In our situation we are unable to analyze this trace accurately enough to prove Theorem 1.1, as certain infinite sums involved in our analysis diverge (for example, the infinite sum involving W (T; m⃗) and P_{i,T,m⃗} just above the middle of page 351 in [Fri91], for types of order > d). This divergence is due to certain “tangles” that can occur in a random graph and can adversely affect the eigenvalues (see Sections 2 and 4). To get around these “tangles” we introduce a selective trace. We briefly sketch what a selective trace is in the next paragraph.

Recall that a closed walk about a vertex, v, is a walk in the graph beginning and ending at v. Recall that the trace of the k-th power of the adjacency matrix equals the sum over all v of the number of closed walks about v of length k. The k-th irreducible trace (used in both [BS87] and [Fri91]) is the same sum as the k-th power trace, except that we require the closed walks to be irreducible, i.e., to have no edge traversed and then immediately thereafter traversed in the opposite direction. A selective trace is a sum like an irreducible trace, but where we further require that the walk have no small contiguous piece that “traces out” a “supercritical tangle” (the notions of “tracing out” and “supercritical tangles” will be defined later; roughly speaking, a “supercritical tangle” is a small graph with many cycles). Since these “tangles” occur with probability at most proportional to n^{−τ}, with τ = τ_{fund} as in Theorem 1.1, the selective trace usually agrees with the standard “irreducible” trace.

Analyzing the selective traces involves a new concept of the “new type,” which is a refinement of the “type” of [Fri91].

We caution the reader about the notation used here. In this paper we work with only d-regular graphs. In [BS87] 2d-regular graphs were studied; in [Fri91] the graphs are usually 2d-regular, although for a part of Section 3 the graphs are d-regular. We also caution the reader that here we use the term “irreducible” (as used in [BS87, Fri91] and, for example, in the text [God93]) as opposed to “reduced” (which is quite common) or “non-backtracking” (sometimes used in [Fri91]) in describing walks and related concepts.

3In [BS87, Fri91] this power is roughly c log n, where c depends on d and on aspects of the method.

We hope to generalize or “relativize” the theorems here to theorems about new eigenvalues of random covers (see [Fri03] for a relativized Broder-Shamir theorem). In this paper we occasionally go out of our way to use a technique that will easily generalize to this setting.

The rest of this paper is organized as follows. In Section 2 we review the trace method used in [Fri91] and explain why it requres modification to prove Alon’s conjecture; as a byproduct we establish the part of Theorem 1.1 involving s. In Section 3 we give some background needed for some technical details in later sections. In Section 4 we formalize the notion of a tangle, and discuss their properties; we prove the part of Theorem 1.2 and 1.3 involving s. In Section 5 we describe “types” and “new types,” explaining how they help to estimate “walk sums;” walk sums are generalizations of all notions of “trace” used here. In Section 6 we describe the “selective trace” used in this paper; we give a crucial lemma that counts certain types of selective closed walks in a graph. In Section 7 we explain a little about “d-Ramanujan” functions, giving a theorem to be used in Section 14 that also illustrates one of the main technical points in Section 8. In Section 8 we prove that certain selective traces have an asymptotic expansion (in 1/n) whose coefficients are “d-Ramanujan.” In Section 9 we show that the expansion in Section 8 still exists when we count selective traces of graphs not containing any finite set of tangles of order ≥ 1. In Section 10 we introduce strongly irreducible traces, that simplify the proofs of the main theorems in this paper. In Section 11 we prove a crucial lemma that allows us to use the asymptotic expansion to make conclusions about certain eigenvalues; this lemma sidesteps the unresolved problem of (even roughly) determining the coefficients of the asymptotic expansion (in [Fri91] we actually roughly determine the coefficients for the shorter expansion developed there). In Section 12 we prove the magnification (or “expansion”) properties needed to apply the sidestepping lemma of Section 11. In Section 13 we complete the proof of Theorem 1.1. In Section 14 we complete the proof of Theorems 1.2 and 1.3, giving general conditions on a model of random graph that are sufficient to imply the Alon conjecture. In Section 15 we make some closing remarks.

We mention that the reader interested only in the Alon conjecture for only G_{n,d} (i.e., the first part of Theorem 1.1) need not read Sections 2, 4 (assuming a willing to believe Lemma 4.10), and 14 and Subsections 3.7, 3.8, 5.4, and 6.4. Section 2 explains the problems with the trace method encountered in [Fri91]. Subsections 3.7 and 3.8 and Section 4 concern themselves with the second part of Theorem 1.1 (the close to matching bound on how many graphs fail the 2\sqrt{d − 1} + ϵ bound). Subsection 5.4 explains the new aspects in our approach to the Alon conjecture; this subsection is not essential to the exposition (but probably is helpful). Subsection 6.4 and Section 14 involve the Alon conjecture for H_{n,d}, I_{n,d}, J_{n,d}.

Throughout the rest of this paper we will work with G_{n,d} unless we explicitly say otherwise, and we understand d to be a fixed integer at least 3. At times we insist that d be even (for example, in dealing with G_{n,d} and H_{n,d}).

2 Problems with the Standard Trace Method

In this section we summarize the trace method used in [Fri91], and why this method cannot prove Alon’s conjecture. During this section we will review some of the ideas of [Fri91], involving asymptotic expansions of various types of traces, which we modify in later sections to complete our proof of Alon’s conjecture.

2.1 The Trace Method

We begin by recalling the trace method as used in [Fri91], and why it did not yield the Alon conjecture.

The trace method (see [Wig55, Gem80, FK81, McK81, BS87, Fri91], for example) determines information on the eigenvalues of a random graph in a certain probability space by computing the expected value of a sufficiently high power of the adjacency matrix, A; this expected value equals the expected value of the sum of that power of the eigenvalues, since

Trace (A^{k}) = λ_{1}^{k} + ⋯ + λ_{n}^{k}.

Now Trace (A^{k}) may also be interpreted as the number of closed walks (i.e., walks (see Section 3.1) in the graph that start and end at the same vertex) of length k. Now restrict our discussion to G_{n,d}. A word, w = σ_{1} … σ_{k}, of length k over the alphabet

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

(i.e. each σ_{i} ∈ Π), determines a random permutation, and the i, j-th entry of A^{k}, is just the number of words, w, of length k, taking i to j. But given a word, w, the probability, P (w), that w takes i to i is clearly independent of i. Hence we have

E [Trace (A^{k})] = n ∑_{w∈Π^{k}} P (w)

In [BS87], Broder and Shamir estimated the right-hand-side of the above equality to obtain an estimate on λ_{2}. This analysis was refined in [Fri91]. We review the ideas there.

First, a word, w, is said to be irreducible if w contains no consecutive occurence of σ, σ^{−1}. It is well-known that any word, w, has a unique reduction to an irreducible word^{4} (or reduced word), w′, obtained from w by repeatedly discarding any consecutive occurences of σ and σ^{−1} in w, and P (w) = P (w′). Similarly a walk is said to be irreducible if it contains no occurrence of a step along an edge immediately followed by the reverse step along that edge^{5}. Similarly, every irreducible walk has a unique reduction. Let Irred_{k} be the set of irreducible words of length k, and let IrredTr (A, k) be the number of irreducible closed walks of length k in G^{6}. We shall see that to evaluate the expected value of Trace (A^{m}) it suffices, in a sense (namely that of equation (3) below), to evaluate

E [IrredTr (A, k)] = n ∑_{w∈Irred_{k}} P (w),

4In fact, the irreducible word has length which is its distance to the identity in the Cayley graph over the free group on d/2 elements (see [FTP83], Sections 1 and 7 of chapter 1). Alternatively, see Proposition 2.5 of [DD89] or Theorem 1 of [Joh90] (this theorem says that a free group on a set, X, is in one-to-one correspondence with the set of reduced words, X ∪ X^{−1}, which means that every word over X ∪ X^{−1} has a unique corresponding reduced word; here “reduced” is our “irreducible”).

5In the case of an edge that is a half-loop (see Section 3), a half-loop may not be traversed twice consecutively in an irreducible walk.

6We have admittedly defined IrredTr (A, k) in terms of G, but we shall soon see (Lemma 2.3) that IrredTr (A, k) can be defined as a polynomial in A and d.

for k = m, m − 2, . . .. It is easy to see that for any fixed word, w, we have a power series expansion

P (w) = P_{0}(w) + \frac{P_{1}(w)}{n} + \frac{P_{2}(w)}{n^{2}} + ⋯

(see, for example, Theorem 5.5).

As examples, we note that for a random permutation, π, on {1, …, n}, the probability that the sequence 1, π(1), π^{2}(1), … first returns to 1 at π^{k}(1) (i.e., the probability that 1 lies on a cycle of length exactly k) is 1/n for k = 1, …, n. It follows that P (π_{1}^{m}) = ϕ(m)/n, where ϕ(m) is the number of positive integral divisors of m, assuming m ≤ n. In this example P_{1}(w) = ϕ(m) involves number theoretic properties of m. For a second example, we first remark that π^{m} maps a fixed vertex to a different vertex with probability 1 − (ϕ(m)/n), and to each of the n − 1 different vertices with the same probability. It is then easy to see that

P (π_{1}^{m_{1}}π_{2}^{m_{2}}) = \frac{ϕ(m_{1})ϕ(m_{2})}{n^{2}} + \frac{(n − ϕ(m_{1}))(n − ϕ(m_{2}))}{n^{2}(n − 1)}

provided that m_{1}, m_{2} are at most n. If m_{1}, m_{2} are at least 2, then the P_{i} are non-zero for i ≥ 1 and involve number theoretic functions of m_{1}, m_{2} for i ≥ 2.

So set

g_{i}(k) = ∑_{w∈Irred_{k}} P_{i+1}(w)  (1)

(we easily see P_{0}(w) = 0 for w ∈ Irred_{k} and k ≥ 1 and so g_{−1}(k) = 0 for k ≥ 1).

Definition 2.1 A function, f(k), on positive integers, k, is said to be d-Ramanujan if there is a polynomial p = p(k) and a constant c > 0 such that

|f(k) − (d − 1)^{k}p(k)| ≤ ck^{c}(d − 1)^{k/2}

for all k. We call (d−1)^{k}p(k) the principal term of f, and f(k)−(d−1)^{k}p(k) the error term (both terms are uniquely determined if d > 2).

In [Fri91] it was shown (among other things) that for all i ≤ \sqrt{d − 1}/2 we have that g_{i} as above is d-Ramanujan. This, it turns out, gives a second eigenvalue bound of roughly 2\sqrt{d − 1} + 2 log d + C + O(log log n/ log n) for a universal constant, C. We now explain why.

A standard counting and expansion argument is given in [Fri91] (specifically Theorem 3.1 there) to establish the following lemma.

Lemma 2.2 For fixed even d ≥ 4 there is an η > 0 such that with probability 1 − n^{1−d} + O(n^{2−2d}) we have that a G in G_{n,d} has max(λ_{2}, −λ_{n}) ≤ d − η (also with probability n^{1−d} + O(n^{2−2d}) we have that λ_{2} = d).

Next to λ_{1} = d, one (or both) of λ_{2}, λ_{n} is the next largest eigenvalue in absolute value; Lemma 2.2, by bounding the eigenvalues other than λ_{1}, will eventually be used to show that the g_{i} of equation (1) are essentially determined, for small i, by λ_{1}’s “contribution” to IrredTr (A, k) (see below).

Next we establish the precise relationship between the traces of the A^{k} and the IrredTr (A, k). Let A_{k} be the matrix whose i, j-th entry is the number of irreducible walks of length k from i to j.

Lemma 2.3 The A_{k} are given by

A_{k} = q_{k}(A),

where q_{k} is the degree k polynomial given via

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 θ}) (2)

(which is a type of Chebyshev polynomial); alternatively we have q_{1}(x) = x, q_{2}(x) = x^{2} − d, and for k ≥ 3 we have

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

Also

IrredTr (A, k) = Trace (A_{k}) = ∑_{i=1}^{n} q_{k}(λ_{i}).

The proof is given in [LPS86] and [Fri91] (specifically Lemma 3.3, page 356, in [Fri91]; the F_{k}’s there are the A_{k}’s here). In Section 10 we shall use the fact that for fixed λ, q_{k} = q_{k}(λ) satisfy the recurrence

(σ_{k}^{2} − λσ_{k} + (d − 1))q_{k} = 0,

where σ_{k} is the “shift in k” operator (i.e., σ_{k}q_{k} = q_{k+1})

To go the other way we note:

A^{k} = ∑_{i=k,k−2,k−4,...} N_{k,i}A_{i},  (3)

where N_{k,i} is the number of words of length k that reduce to a given irreducible word of length i. Thus

Trace (A^{k}) = ∑_{i=k,k−2,k−4,...} N_{k,i} IrredTr (A, i) .

Lemma 2.4 For k, i even we have

N_{k,i} ≤ (2\sqrt{d − 1})^{k}(d − 1)^{−i/2}\sqrt{(d − 1)/d}

if i > 0 and

N_{k,0} ≤ (2\sqrt{d − 1})^{k}.

An exact formula for N_{k,i} is given in [McK81]. A weaker estimate than the above lemma was used in [Fri91]. The proof of this estimate is a simple spectral argument used by Buck (see [Buc86, Fri03]). Proof Consider the adjacency matrix, A_{T}, of the infinite d-regular tree, T. Our proof requires the following sublemma.

Sublemma 2.5 A_{T} has norm ≤ 2\sqrt{d − 1}.

Actually, it is well-known that the norm of A_{T} is exactly 2\sqrt{d − 1} (see, for example, page 9 of [Woe00], and the theorems on λ_{1} in Section 3 here). However, the proof below is simple and generalizes to many other situations (and can be used in many cases to determine the exact norm of A_{T}). Proof (of Sublemma 2.5) Let f be a function in L^{2}(T), i.e., a function on the vertices of T whose sum of squares of values is finite. Fix a vertex, v_{0}, of T, to be viewed as the root of T; the children of a vertex, v, are defined to be those vertices adjacent to v and of greater distance than v is to v_{0}. We have

(A_{T} f, f) = ∑_{v} ∑_{w∈ children(v)} 2f(v)f(w)

which, by Cauchy-Schwarz, is

≤ ∑_{v} ∑_{w∈ children(v)} (f^{2}(w)\sqrt{d − 1} + \frac{f^{2}(v)}{\sqrt{d − 1}})

= f^{2}(v_{0})d / \sqrt{d − 1} + ∑_{v≠v_{0}} f^{2}(v)2\sqrt{d − 1}.

≤ ∑_{v} f^{2}(v)2\sqrt{d − 1} = 2\sqrt{d − 1}∥f∥^{2}.

Thus the norm of A_{T} is ≤ 2\sqrt{d − 1}.

□

(To see that the norm of A_{T} is exactly 2\sqrt{d − 1} we find functions, f, (of finite support) for which the applications of Cauchy-Schwarz in the above proof are “usually” tight. Namely, we can take f(v) = (d − 1)^{−dist(v,v_{0})/2} for dist(v, v_{0}) ≤ s and f(v) = 0 otherwise, where s is a parameter which tends to ∞. This technique works for some other graphs.)

We resume the proof of Lemma 2.4. Let v be a vertex of T, and let S be the vertices of distance i to s. Then |S| N_{k,i} is the dot product of A_{T}^{k} χ_{{v}} with χ_{S}, where χ_{U} denotes the characteristic function of U, i.e. the function that is 1 on U and 0 elsewhere. So by Cauchy-Schwarz

|S| N_{k,i} = (A_{T}^{k} χ_{\{v\}}, χ_{S}) ≤ ∥A_{T} ∥^{k}|χ_{\{v\}}| |χ_{S}| = (2\sqrt{d − 1})^{k}\sqrt{|S|}.

We finish with the fact that |S| = 1 if i = 0, and otherwise |S| = d(d − 1)^{i−1}.

□

Notice that clearly N_{k,k} = 1, and so for i = k Lemma 2.4 is off by a multiplicative factor of roughly 2^{k}; according to [McK81, FTP83], the Lemma 2.4 estimate of N_{k,0} is off by roughly a factor of k^{3/2}. The roughness of Lemma 2.4 is unimportant for our purposes.

Now notice that by Lemmas 2.2 and 2.3 we have

E [IrredTr (A, k)] = q_{k}(d)(1 + n^{1−d} + O(n^{2−2d})) + error,

where

|error| ≤ (n − 1) max_{|λ|≤d−η} |q_{k}(λ)|.

It is easy to see (see [Fri91]) that q_{k}(d) = (d − 1)^{k}, and for some α > 0 we have

max_{|λ|≤d−η} |q_{k}(λ)| ≤ (d − 1 − α)^{k}ck,

for an absolute constant c (with any η as in Lemma 2.2). We wish to draw some conclusions about the principal term of the g_{i}’s. We need the following lemma:

Lemma 2.6 For fixed d, r there is a constant, c, such that for k ≥ 1 we have that in G_{n,d}

E [IrredTr (A, k)] = g_{0}(k) + \frac{g_{1}(k)}{n} + \frac{g_{2}(k)}{n^{2}} + ⋯ + \frac{g_{r−1}(k)}{n^{r−1}} + error,

where

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

Proof This follows from the calculations on page 352 of [Fri91]; for each i, the f_{i} in [Fri91] is the polynomial in the principal term of g_{i} (and we mean f_{i} corresponds precisely to g_{i}, not g_{i−1} or g_{i+1}). (Actually we shall later^{7} see that the 4r + 2 in the error term estimate can be replaced by 4r.)

□

We now take k of order log^{2} n and use standard facts about expansion and expansion’s control on eigenvalues (namely our Lemma 2.2) to conclude, as in [Fri91], the following theorem.

Theorem 2.7 Let g_{0}, g_{1}, …, g_{r} be d-Ramanujan for some r ≤ d. Then the principal term of g_{i} vanishes for 1 ≤ i ≤ r, and the principal term of g_{0} is d(d − 1)^{k−1}.

Proof See Theorem 3.5 of [Fri91].

□

We next apply Lemma 2.4 to estimate the expected value of the trace of A^{k} where k is roughly

h(n, r, d) = \frac{(r + 1) log n}{log(d/(2\sqrt{d − 1} ))},  (4)

as in [Fri91], in order to obtain the following theorem.

Theorem 2.8 With the same hypotheses as Theorem 2.7, we have (in G_{n,d})

E [∑_{i=2}^{n} λ_{i}^{k}] ≤ ρ^{k}  (5)

7This stems from the fact that in [Fri91], the e^{(r+1)k/n}k^{2r+2} just above equation (21)

(page 352) could have been replaced with e^{rk/n}k^{2r}.

for all k ≤ h(n, r, d), with h as above, where

ρ = 2\sqrt{d − 1} (d/(2\sqrt{d − 1} ))^{1/(r+1)} (1 + \frac{c log log n}{log n})  (6)

and c depends only on r, d.

Proof First we take k = ⌊h(n, r, d)⌋ and find that ρ can be taken as above. For smaller k we appeal to Jensen’s inequality. See [Fri91] for details.

□

From Theorem 2.18 of [Fri91] we see that we can take r as large as ⌊\sqrt{d − 1} /2⌋. With this value of r, using equation (6), we conclude that equation (5) holds with ρ = 2\sqrt{d − 1} + 2 log d + C + o(1) for an absolute constant, C, where o(1) is a quantity that for fixed d tends to 0 (proportional to log log n/ log n) as n → ∞.

Whenever equation (5) holds, then the expected value of max(|λ_{2}|, |λ_{n}|) is bounded by ρ. The Alon conjecture would be implied if one could obtain ρ ≤ 2\sqrt{d − 1} + ϵ for any ϵ > 0.

2.2 Limitations of the Trace Expansion

In this subsection we will show that for some i ≤ O(\sqrt{d} log d), g_{i} is not d-Ramanujan. We similarly show the part of Theorem 1.1 involving s. Both these facts are due to the possible occurrence of what we call tangles. Tangles and avoiding them are the main themes in this paper.

We begin by describing an example of a tangle, and its effect on eigenvalues and traces. Consider G_{n,d} for a fixed, even d and a variable n which we view as large. Fix an integer m with 1 ≤ m ≤ d/2 (assume d ≥ 4). Consider the event, T , that

π_{i}(1) = 1 for i = 1, … m.

Clearly T occurs with probability 1/n^{m}.

Assume T occurs in a fixed d-regular graph, G = (V, E). Let W be the set of vertices of distance at least 2 to the vertex 1; W is a random set of vertices, but always of size at least n − d − 1. Consider the characteristic functions χ_{{1}}, χ_{W}, where χ_{U} is the function that is 1 on the vertices in U, and 0 elsewhere. Let

R_{A}(v) = \frac{(Av, v)}{(v, v)}

be the Rayleigh quotient associated to the adjacency matrix, A, of G. The following lemma is well-known.

Lemma 2.9 Let A be a real, symmetric matrix. Let u, v be nonzero vectors with v orthogonal to u and Au. Then

λ_{2} ≥ min(R_{A}(u), R_{A}(v)).

Proof Let μ denote the min on the right-hand-side of the above inequality. By the hypothesis of the lemma, (Au, v) = 0; along with the symmetry of A, we have (Av, u) = (v, Au) = 0. If w = αu + βv with α, β scalars, we have

(Aw, w) = (Au, u)α^{2} + (Av, v)β^{2} ≥ μ(u, u)α^{2} + μ(v, v)β^{2} = μ(w, w).

It follows that the Rayleigh quotient of any vector in the span of u and v is at least μ. Since this span is a two-dimensional subspace, the max-min principle implies that λ_{2} ≥ μ.

□

We intend apply the above lemma with u = χ_{{1}} and v = χ_{W}.

R_{A}(χ_{{1}}) ≥ 2m

(since (Aχ_{U}, χ_{U}) counts twice the number of edges with both endpoints in U). Also

(Aχ_{W} , χ_{W}) = (Aχ_{V} , χ_{V}) − 2(Aχ_{V} , χ_{V \W}) + (Aχ_{V \W} , χ_{V \W})
≥ (Aχ_{V} , χ_{V}) − 2(Aχ_{V} , χ_{V \W}) ≥ dn − 2d(d + 1)

so

R_{A}(χ_{W}) ≥ \frac{dn − 2d(d + 1)}{n − d − 1} = d − O(1/n)

viewing m, d as fixed. Since χ_{{1}} and Aχ_{{1}} are supported in the neighbourhood of distance at most 1 from the vertex 1, χ_{W} is orthogonal to both of them. Lemma 2.9 now implies

λ_{2} ≥ min(2m, d − O(1/n)).

Next consider the probability that

π_{i}(r) = r for i = 1, …, m

for at least one value of r. Inclusion/exclusion shows that the probability of this is at least

∑_{r} Prob {π_{i}(r) = r for i = 1, … m} −

∑_{r,s} Prob {π_{i}(r) = r and π_{i}(s) = s for i = 1, … m}

≥ n^{1−m} − \binom{n}{2}n^{−2m}.

We summarize the above observations.

Theorem 2.10 For fixed integer m with 1 ≤ m ≤ d/2, we have that λ_{2} ≥ 2m for sufficiently large n with probability at least n^{1−m} − (1/2)n^{2−2m}.

The proof of the above theorem did not exploit the fact that aside from having m self-loops, the vertex 1 is still adjacent to d − 2m other vertices of a d-regular graph. We seek a stronger theorem that exploits this fact.

Theorem 2.11 For fixed integers m ≥ 1 and d ≥ 4, with 2m − 1 > \sqrt{d − 1} and m ≤ d/2, we have that λ_{2} > 2\sqrt{d − 1} for sufficiently large n with probability at least n^{1−m} − (1/2)n^{2−2m}.

(Notice that Theorem 2.10 would require m > \sqrt{d − 1} for the same conclusion.) We are very interested to know if one can prove Theorem 2.11 when 2m − 1 = \sqrt{d − 1} for integer m and even integer d. We expect not. (The situation where 2m − 1 = \sqrt{d − 1} gives rise to what we will call a “critical tangle,” and 2m − 1 ≥ \sqrt{d − 1} to a “supercritical tangle,” in Section 4.) Proof Note: in Theorems 3.13 and 4.2 we give a proof of a generalization of this theorem requiring far less calculation (but requiring more machinery).

Again, assume that π_{i}(v_{0}) = v_{0} for i = 1, …, m and some v_{0}. It suffices to show λ_{2} > 2\sqrt{d − 1} for sufficiently large n, under the assumption that 2m − 1 > \sqrt{d − 1}.

Let

α(m) = (2m − 1) + \frac{d − 1}{2m − 1}.  (7)

By Cauchy-Schwarz we have α > 2\sqrt{d − 1} (equality does not hold, because 2m − 1 ≠ (d − 1)/(2m − 1) since 2m − 1 > \sqrt{d − 1}).

Let ρ(v) denote v’s distance to v_{0}. For a fixed r, let

f(v) = \{ \begin{matrix}(2m − 1)^{−ρ} & if ρ ≤ r, \\ 0 & otherwise, \end{matrix}

where ρ = ρ(v). It is easy to check that (Af)(v) ≥ αf(v) provided that ρ(v) < r (this includes the case v = v_{0}, since ρ(v_{0}) = 0, but checking v = v_{0} is a bit different from the other cases). It follows that

\frac{(Af, f)}{(f, f)} ≥ \frac{α(f, f)_{r−1}}{(f, f)_{r}} ,  (8)

where

(f, f)_{t} = ∑_{ρ(v)≤t} f^{2}(v).

But 1 = f^{2}(v_{0}) ≤ (f, f)_{r−1} if r ≥ 1, and also

(f, f)_{r} ≤ (f, f)_{r−1} + (d − 2m)(d − 1)^{r−1}(2m − 1)^{−2r}

(since, by induction, the number of vertices at distance r from v is at most (d − 2m)(d − 1)^{r−1}.) So

\frac{(f, f)_{r}}{(f, f)_{r−1}}  (9)

can be made arbitrarily close to 1 by taking r sufficiently large (since (d − 1)(2m − 1)^{−2} < 1).

Let R be the Rayleigh quotient of A. The last paragraph, especially equations (8) and (9) implies that for α′ < α there is an r = r(α′) such that R(f) ≥ α′.

So let N be those vertices of distance 1 or 0 to the support of f; the size, |N|, of N is bounded as a function of d and r. The function f is orthogonal to g = χ_{V \N} and Ag, and counting edges as before we see

R(g) ≥ \frac{d|V | − 2d|N|}{|V | − |N|} = d − O(|N|d/|V |).

It follows that by taking n sufficiently large, we can make λ_{2} ≥ α′; since α > 2\sqrt{d − 1}, we can choose α′ > 2\sqrt{d − 1}, making λ_{2} > 2\sqrt{d − 1}.

□

Theorem 2.11 proves the part of Theorem 1.1 involving s, by taking s = m − 1 with m as small as possible (namely m = ⌊(\sqrt{d − 1} + 1)/2⌋ + 1). The analogous parts of Theorems 1.2 and 1.3 are slightly trickier, since the “tangle” involved has automorphisms; we shall delay their proof (see Theorem 4.13) until we give a more involved discussion of tangles in Section 4.

Notice that our proof is really computing the norm of A_{H} where H is the d-regular graph with the vertex 1 having m self-loops, and which is a (an infinite) tree when these loops are removed. The function f as above shows that A_{H}’s norm is at least α. The statement and proof of Sublemma 2.5 for the d-regular tree applies to the above tree (with 2m − 1 replacing \sqrt{d − 1}, and with α replacing 2\sqrt{d − 1}). In this way our proof of Theorem 2.11 is very much like one proof of the Alon-Boppana theorem (see [Nil91, Fri93]).

The discussion in this section leads to the following theorem.

Theorem 2.12 There is an absolute constant (independent of d), C, such that the g_{i} of equation (1) cannot be d-Ramanujan for all i ≤ C\sqrt{d} log d.

Proof We fix an integer s to be chosen later with

(\sqrt{d − 1} − 1)/2 < s < d/2.

Set s + 1 = m and apply Theorem 2.11. Since α ≥ 2s + 1 with α as in equation (7), for k even we have that λ_{2} ≥ 2s with probability at least n^{−s} + O(n^{−s−1}). Thus

E [λ_{2}^{k}]^{1/k} ≥ (n^{−s} + O(n^{−s−1}))^{1/k}2s.

According to Theorem 2.8, if g_{0}, …, g_{r} are d-Ramanujan for some r ≤ d, then we have

E [λ_{2}^{k}]^{1/k} ≤ ρ,

with ρ as in equation (6), provided that k is even and bounded by h(n, r, d) as in Theorem 2.8. For some constant c we have that for any C and for r = C\sqrt{d} log d, equation (6) gives

ρ = 2\sqrt{d − 1}(1 + cC^{−1}d^{−1/2} + c(log n)^{−1} log log n).

In other words,

(n^{−s}+O(n^{−s−1}))^{1/k}2s ≤ 2\sqrt{d − 1}(1+cC^{−1}d^{−1/2}+c(log n)^{−1} log log n). (10)

Take k even and as close to h(n, r, d) as possible; note that by equation (4),

\frac{log n}{h} = \frac{log(d/(2\sqrt{d − 1} ))}{r + 1} ≤ \frac{log d}{(C\sqrt{d} log d) + 1} ≤ 1/(C\sqrt{d});

hence, taking n → ∞ in equation (10) implies that for a universal constant, c′, we have

e^{−sd^{−1/2}/C}2s ≤ 2\sqrt{d − 1}(1 + cC^{−1}d^{−1/2}) ≤ 2\sqrt{d − 1}(1 + cC^{−1}).

Choosing s = C\sqrt{d} and dividing by 2 yields

C\sqrt{d} /e ≤ \sqrt{d − 1}(1 + cC^{−1}).

Choosing C large enough so that C/e > 1 + (c/C) makes this impossible.

□

We have proven that not all g_{i} are d-Ramanujan for i ≤ r where r = C\sqrt{d} log d. Notice that in our terminology, Theorem 2.18 of [Fri91] says that g_{i} is d-Ramanujan for i ≤ ⌊\sqrt{d − 1} / 2⌋−1; again, for each i the f_{i} in [Fri91] is the polynomial in the principal part of our g_{i}. This leaves the question of whether Theorem 2.12 can be improved to an r value closer to ⌊\sqrt{d − 1} / 2⌋ − 1; we conjecture that it can be improved to r = ⌊(\sqrt{d − 1} + 1)/2⌋, and that the tangle with m = ⌊(\sqrt{d − 1} + 1)/2⌋ + 1 already “causes” this g_{r} (or a lower one) to fail to be d-Ramanujan.

This also leaves open the question of what can be said about the g_{i} that are not d-Ramanujan. Perhaps such g_{i} = g_{i}(k) are a sum of ν^{k}p_{ν}(k) over various ν with some added error term. In this paper we avoid this issue, working with a modified trace (i.e., “selective” traces) for which the corresponding g_{i} are d-Ramanujan.

3 Background and Terminology

In this section we review some ideas and techniques from the literature needed here. We also give some convenient terminology that is not completely standard.

3.1 Graph Terminology

We use some nonstandard notions in graph theory, and we carefully explain all our terminology and notions here.

A directed graph, G, consists of a set of vertices, V = V_{G}, a set of edges, E = E_{G}, and an incidence map, i = i_{G}: E → V × V; if i(e) = (u, v) we will write e ∼ (u, v), say that e is of type (u, v), and say that e originates in u and terminates in v. (If i is injective then it is usually safe to view E as a subset of V × V, and we say that G has no multiple edges.) The adjacency matrix, A = A_{G}, is a square matrix indexed on V, where A(u, v) counts the number of edges of type (u, v). The outdegree at v ∈ V is the row sum of A at v, i.e., the number of edges originating in v; the indegree is the column sum or number of edges terminating in v.

A graph, G, is a directed graph, Ĝ, such that each edge of type (u, v) is “paired” with an “opposite edge” of type (v, u); in other words, we have a map opp = opp_{G}: EĜ → EĜ, such that opp(opp) is the identity, and if e ∈ EĜ has e ∼ (u, v), then opp(e) ∼ (v, u); in other words, the edges EĜ come in “pairs,” except that a self-loop, i.e., an e ∈ EĜ with e ∼ (v, v), can be paired with itself (which is a “half-loop” in the terminology of [Fri93]) or paired with another self-loop at v (which is a “whole-loop”). Half-loops about v contribute 1 to the adjacency matrix entry at v, v (i.e., contribute 1 to A(v, v)), and whole-loops contribute 2. In this paper we primarily work with whole-loops, needing half-loops only in the model J_{n,d}. We refer to the (undirected) edges, E_{G}, of a graph, G, as the set of “pairs” of edges, {e, opp(e)}. G’s vertex set and adjacency matrix are just those of the directed graph, Ĝ, i.e., V_{G} = VĜ and A_{G} = AĜ.

A numbering of a set, S, is a bijection ι: S → {1, 2, …, s}, where s = |S|. A partial numbering of a set, S, is a numbering of some subset, S′, of S (we allow S′ to be empty, in which case none of S is numbered). We can speak of a graph, directed or not, as having numbered or partially numbered vertices and/or edges. A numbering can be viewed as a total ordering.

Each letter π ∈ Π = {π_{1}, π_{1}^{−1}, …, π_{d/2}^{−1}} has its associated inverse, π^{−1} ∈ Π, and every word w = σ_{1} … σ_{k} over Π has its associated inverse, w^{−1} = σ_{k}^{−1} … σ_{1}^{−1}. If W is any set of words over Π, then a W-labelling of an undirected graph, G, is a map or “labelling” L: EĜ → W such that L(opp(e)) = (L(e))^{−1} for each e ∈ EĜ. For example, any graph G ∈ G_{n,d} automatically comes with a Π-labelling, namely (i, π_{j}(i)) is labelled π_{j}, and (i, π_{j}^{−1}(i)) is labelled π_{j}^{−1}.

An orientation of an undirected graph, G, is the distinguishing for each e ∈ E_{G} of one of the two directed edges corresponding to e.

The following definition is special to this paper.

Definition 3.1 Fix sets V, E and a set of words, W, over Π, with W^{−1} = W. A structural map is a map s: E → W × V × V. A structural map defines a unique W-labelled, oriented graph, G, with V_{G} = V and E_{G} = E, as follows: for each e ∈ E with s(e) = (σ, u, v), we form a directed edge of type (u, v) labelled σ and declare it distinguished, and pair it with a directed edge of type (v, u) labelled σ^{−1}.

3.2 Variable-Length Graphs and Subdivisions

In this paper we will work with graphs that have large or infinite parts of them being paths or regular trees. In this case we can easily eliminate all the vertices in these parts by working with “variable-length graphs.” This leads to simpler calculations (in Theorem 3.6, that is crucial to Lemma 9.2, and in Theorem 6.6). This also gives us a notion of regular tree of non-integral degree, in Theorem 3.13.

Recall (see [SW49, AFKM86, HMS91, Fri93]) that a VLG or variablelength graph (respectively, directed VLG or directed variable-length graph) is a graph (respectively, directed graph) with an assignment of a positive integer to each edge called the edge’s length^{8}. The length of a walk in a VLG is the sum of the lengths of its edges (each length is counted the number of times the edge appears in the walk).

A graph can be regarded as a VLG with all edge lengths 1. A VLG whose edge lengths are all 1 can be identified with its underlying graph.

A bead in a directed graph (respectively graph) is a vertex with indegree and outdegree 1 (respectively, degree 2) and without a self-loop. A beaded path is a path where every vertex except possibly the endpoints are beads.

Definition 3.2 Let G be a directed VLG. To subdivide an edge, e, from u to v and of length ℓ, in G is to replace e with a beaded path of length ℓ from u to v in G (introducing ℓ − 1 new vertices). A subdivided form of G is a graph, G_{sbd}, obtained by subdividing all edges of G. The same definition is made for VLG’s, omitting the word “directed” everywhere, provided no half-loops are of length 2 or greater^{9}.

8In Shannon’s terminology of [SW49], Chapter 1, Section 1, the edges have various “times” (as opposed to “lengths”) such as a dot versus a dash in Morse code.

It should be clear that countings walks of certain types in a directed VLG, G, should translate to an appropriate similar counting in G_{sbd}, and vice versa. We next define an opposite of subdivision, supression, and a vast generalization of supression, realization.

Definition 3.3 Let G be a strongly connected directed graph, with W ⊂ V_{G}. The realization of G to with vertex set W denoted G|_{W}, is the directed VLG on vertices W with the following set of edges. We create G|_{W} one edge from u to v (for u, v ∈ W) of length k for each walk from u to v in G of length k that contains no W vertices except as the first and last vertices. (So self-loops or edges in G involving W vertices appear in G|_{W}, since we regard self-loops or edges as walks with no vertices except the first and last vertices.)

The notion of realization appears constrained coding theory (called “fusion” in [HMS91], for example, and not given a name in [AFKM86]; see also [Fri93]). We remark that if V_{G} \ W contains a cycle, then G|_{W} has infinitely many edges.

Definition 3.4 Let G be a strongly connected directed graph, with U ⊂ V_{G} a subset of beads in G such that U contains no cycle. The supression of U (in G), denoted G [U]_{sup}, is the realization of G with vertex set V_{G} \ U.

The subdivision (by the supressed vertices) of a supression returns the original directed graph.

We remark that if G is a Π-labelled graph, then any supression in G has a natural Π^{+}-labelling, where Π^{+} is the set of words on Π of length ≥ 1.

3.3 λ_{1} of a VLG

Let G be a VLG (directed or undirected). For u, v ∈ V_{G} and a non-negative integer, k, let c_{G}(u, v; k) denote the number of walks of length k from u to v in G. We will use standard Perron-Frobenius theory (see Sections 1.3 and 7.1 in [Kit98] or Chapters 1 and 6 in [Sen81]), which includes the rest of this paragraph. Assume that G is strongly connected, i.e., for each u, v ∈ V_{G} we have c_{G}(u, v; k) > 0 for some k. Let d = d_{G} be the period of G, i.e., the greatest common divisor of the lengths of all closed walks in G. Then all limits

9This restriction will be explained just before Proposition 3.7. Actually, we can define a notion of subdivision for all half-loops of odd length, but in this paper we use half-loops only of length 1.

lim sup_{k→∞}(c_{G}(u, v; k))^{1/k}, lim_{k→∞}(c_{G}(v, v; kd))^{1/kd}

exist and are all equal (so independent of u, v); we define this common limit to be λ_{1}(G), the Perron value of G. It is easy to see that c_{G}(v, v; k) ≤ λ_{1}^{k}, using that c_{G}(v, v; k_{1})c_{G}(v, v; k_{2}) ≥ c_{G}(v, v; k_{1} + k_{2}). If G is a finite graph, then λ_{1}(G) is just the usual Perron-Frobenius (largest) eigenvalue of A_{G}.

In directed graphs, supression, realization, and subdivision preserve walk counts (i.e., the c(u, v; k)’s) between appropriate vertices (those present in the two graphs in question). Therefore these operations also preserve λ_{1}.

If G is not strongly connected, we can define λ_{1}(G)to be the supremum of λ_{1} of all the strongly connected components of G, or equivalently as the supremum over all (c_{G}(v, v; k))^{1/k}.

One can equivalently define λ_{1}(G) with c̃_{G} replacing c_{G}, where c̃_{G}(u, v; k) is the number of walks of length at most k. This is a sensible definition of λ_{1}(G) when we allow non-integral edge lengths^{10}. One can also extend all these defitions to graphs with positively weighted edges, where the weight of a walk becomes the product of its edge weights, and where c_{G} or c̃_{G} sums the weights of the walks.

3.4 Shannon’s Algorithm and Formal Series

Shannon gives the following algorithm (see [SW49], Chaper 1, Section 1) for computing λ_{1}(G) (or the “valence” or “capacity”) of a finite graph: let Z_{G} = Z_{G}(z) be the matrix whose i, j entry is the sum of z^{ℓ} over all edge lengths, ℓ, of edges from i to j, with z a formal parameter. Then λ_{1}(G) is the reciprocal of the smallest real root in z of

det(I − Z_{G}(z)) = 0.  (11)

In this section we explain variants of this theorem/algorithm that hold for infinite VLG’s. We first give some conventions that we will use with formal power series.

10Why should a “dash” in Morse code be precisely an integral multiple of a “dot”?

By a non-negative power series we mean a series f(z) = ∑_{k=0}^{∞} a_{k}z^{k}, with a_{k} non-negative reals. We say that f is the generating function of the a_{k}. At times we view f as a formal power series, but we will also have cause to evaluate f at non-negative reals (as a possibly diverging infinite sum); it is easy to see that if f(z_{0}) converges for a positive z_{0}, then f is continuous on [0, z_{0}], and if f(z_{0}) diverges then f(y_{0}) gets arbitrarily large as y_{0} approaches z_{0}.

For such an f, f’s radius of convergence is

ρ(f) = lim sup_{k→∞} a_{k}^{1/k}.

The function f has a singularity at z = ρ, and f(z_{0}) = ∑ a_{k}z_{0}^{k} diverges for z_{0} > ρ. If the singularity at z = ρ is a pole (e.g., when f(z) is a rational function), then f(z) → +∞ as z → ρ from the left.

N.B.: We do not identitfy a formal power series with any of its analytic extensions unless we specifically say so. For example, f(z) = 1 + z + z^{2} + ⋯ has only the value +∞ for real z > 1 unless we explicitly say to the contrary.

For a VLG, G, we set

M_{G}(z) = I + Z_{G}(z) + Z_{G}^{2}(z) + ⋯

We have

(M_{G}(z))_{u,v} = ∑_{k=0}^{∞} c_{G}(u, v; k)z^{k}.  (12)

We say that a non-negative power series, f(z) = ∑ a_{k}z^{k}, majorizes another one, g(z) = ∑ b_{k}z^{k}, if

a_{1} + ⋯ + a_{j} ≥ b_{1} + … + b_{j}

for all j ≥ 1. If so, then f(z_{0}) ≥ g(z_{0}) for any z_{0} ∈ [0, 1] (with appropriate convensions on the value +∞). Given VLG’s, G and H, we say that G majorizes H if Z_{G}(z) majorizes Z_{H}(z) entry by entry; equivalently, there is an endpoint preserving injection from E_{H} to E_{G} that does not increase edge lengths. If so, clearly M_{G}(z) majorizes M_{H}(z) entry by entry.

Theorem 3.5 Let G be a strongly connected VLG, directed or undirected, on a countable number of vertices and edges. The following are equal:

1. 1/λ_{1}(G), and

2. the radius of convergence of any entry of M_{G}(z).

If G has a finite number of vertices, then the above two numbers also equal the following two:

3. the supremum of positive z such that Z_{G}(z) converges (in each entry) and has largest (i.e., Perron-Frobenius) eigenvalue less than 1, and

4. the supremum of positive z such that Z_{G}(z) converges and det(I − Z_{G}(y)) > 0 for all y with 0 < y < z.

If G has a finite number of vertices, and if the entries Z_{G}(z) are all rational functions of z, then the four above quantities equal

5. the first positive solution to det(I − Z_{G}(z)) = 0.

Finally, all entries of Z_{G}(z) will be rational functions of z whenever G is finite (i.e., has finitely many vertices and edges) or is a VLG realization of finite graph.

Proof (1)=(2): Clear from equation (12).

(2)=(3): Let B be a non-negative matrix. According to Perron-Frobenius theory, all the eigenvalues of B are of absolute value at most λ_{1}(B), with equality only when the eigenvalue has the same algebraic and geometric multiplicity. It now follows from Jordan canonical form that a finite dimensional, non-negative matrix, B, has largest (Perron-Frobenius) eigenvalue less than 1 iff I + B + B^{2} + ⋯ converges.

(3)=(4): If λ_{1}(Z_{G}(z_{0})) < 1, then λ_{1}(Z_{G}(y_{0})) < 1 for all y_{0} < z_{0}, and hence det(I − Z_{G}(y_{0})) > 0 for such y_{0}. Consider the first z_{0} for which λ_{1}(Z_{G}(z_{0})) < 1 fails to hold (such a z_{0} exists by the continuity of λ_{1} as a function of its entries). Either Z_{G}(z_{0}) does not converge, or else by continuity of λ_{1} we have λ_{1}(Z_{G}(z_{0})) = 1 and hence det(I − Z_{G}(z_{0})) = 0.

(4)=(5): By the above paragraph, if suffices to show that Z_{G}(z) cannot have a pole (in any of its entries) at the first z_{0} for which λ_{1}(Z_{G}(z_{0})) < 1 fails to hold. But if Z_{G}(z) has a pole in some entry at z = z_{0}, then for some v ∈ V_{G} and positive integer, k, Z_{G}^{k}(z)_{v,v} has a pole at z = z_{0}, by the strong connectivity of G. But λ_{1}^{k}(Z_{G}(z)) ≥ Z_{G}^{k}(z)_{v,v} for any z, and the latter tends to +∞ as z → z_{0} from the left.

Last part of the theorem: Let G′ be a realization of a finite VLG, G, on the set U ⊂ V_{G}. For u_{1}, u_{2} ∈ U, we shall calculate the (u_{1}, u_{2})-entry of Z_{G′}(z). We claim this entry is the (u_{1}, u_{2})-entry of Z_{G}(z), plus the (u_{1}, u_{2})-entry

v^{T}(I + ZḠ(z) + Z2 ; Ḡ(z) + ⋯)w = v^{T}(I − ZḠ(z))^{−1}w,

where Ū is the induced subgraph of G on the vertex set Ū = V_{G} \ U, where v is the vector whose entries correspond to the edges from u_{1} to the vertices of Ū and similarly for w. Since v, w, ZḠ(z) all have polynomial entries, we conclude that the (u_{1}, u_{2})-entry of Z_{G′}(z) is a rational function.

□

Now we give two examples to show that Shannon’s algorithm does not literally apply as is to infinite graphs. Let G be a directed VLG with one vertex and a_{k} = ⌊2^{k}/(k + 1)^{2}⌋ edges of length k for all k ≥ 1. Then Z_{G}(z) is a 1 × 1 matrix with sole entry is f(z) = ∑_{k} a_{k}z^{k}. In this case we have f(1/2) ≤ (π^{2}/6) − 1 < 1 and f(z) diverges for any positive z ≥ 1/2. It is not hard to see that λ_{1}(G) = 2 (by Theorem 3.5, since 1 + f + f^{2} + ⋯ converges for f < 1, which is the case when z ≤ 1/2, and clearly diverges when z > 1/2 where the series even for f diverges). But the expression det(I −Z_{G}(z)) fails to have a zero at z = 1/2.

Next consider an undirected VLG, G, whose vertex set is the integers, with each vertex having one self loop. Then det(I − Z_{G}(z)) expanded in a power series has an infinite z coefficient; if we simply multiply the diagonals together (since this is a diagonal matrix), we get the infinite product of (1 − z), which is 0 for any z > 0 (yet λ_{1}(G) = 1). While G is not connected, we can add edges between i and i + 1 for all i; this yields a connected graph with similar problems.

Finally we mention that Theorem 3.5 must be modified when G is not strongly connected. Indeed, consider a directed VLG on three nodes, such that the first node has a single self-loop, and the only other edges are edges from the second node to the third, with a_{k} such edges of length k. Then the most natural way to define λ_{1}(G) is in terms of counting closed walks, so that λ_{1}(G) = 1. But if ∑ a_{k}z^{k} diverges for any z_{0} < 1, then Theorem 3.5 fails.

3.5 Limiting Graphs

Let G_{i} be a sequence of finite VLG’s on the same vertex set, V, and the same edge set, E. Let E be partitioned into two sets, E_{1}, E_{2}, such that the following holds:

1. for each e ∈ E_{1}, the length of e in G_{i} is independent of i, and

2. for each e ∈ E_{2}, the length of e in G_{i} tends to infinity as i → ∞.

The limit of the G_{i} is the graph, G_{∞}, which is any G_{i} with its E_{2} edges discarded.

This simple remark is crucial for an important finiteness lemma (Lemma 9.2).

Theorem 3.6 With notation as above,

lim_{i→∞} λ_{1}(G_{i}) = λ_{1}(G_{∞}).

Proof By counting closed walks we see that λ_{1}(G_{i}) ≥ λ_{1}(G_{∞}); this establishes the theorem with “≥” replacing “=”. To see “≤” replacing “=”, assume that λ_{1}(A_{G_{∞}}(z_{0})) < 1 for some z_{0} ∈ [0, 1]. Clearly A_{G_{i}}(z_{0}) → A_{G_{∞}}(z_{0}) as i → ∞. So the continuity of λ_{1} on its entries implies A_{G_{i}}(z_{0}) < 1 for i sufficiently large, and so 1/z_{0} ≥ lim sup λ_{1}(G_{i}). Now take a supremum over z_{0} with λ_{1}(A_{G_{∞}}(z_{0})) < 1.

□

3.6 Irreducible Eigenvalues

Let G be an undirected graph with corresponding directed graph Ĝ. Let G_{Irred} be the graph with vertices EĜ and an edge from e_{1} to e_{2} iff e_{1}e_{2} forms an irreducible path in G; i.e., e_{1} and e_{2} are not opposites (i.e., paired) in G, and e_{1} terminates in the vertex where e_{2} originates. (Therefore, if e is a halfloop in G, then there is no edge from e to itself in G_{Irred}.) Then walks in G_{Irred} give “irreducible” (or “reduced” or “non-backtracking”) walks in G. A closed walk of length k in G_{Irred} gives a closed walk in G (with specified starting vertex) that is strongly irreducible, meaning that the closed walk is irreducible and the last step in the closed walk is not the inverse of the first step. We define the irreducible eigenvalues of G to be those of G_{Irred}, and we define the largest or Perron-Frobenius eigenvalue of G_{Irred} to be λ_{Irred} = λ_{Irred}(G), the largest irreducible eigenvalue of G.

For G an undirected VLG, we may define G_{Irred} as a VLG and hence define λ_{Irred}(G) = λ_{1}(G_{Irred}). In any graph, an irreducible walk that enters a beaded-path must directly traverse this path to its end (any backward step makes the walk reducible). It easily follows that if we subdivide edges in a VLG that are not half-loops (i.e., whole-loops or edges between distinct vertices), then counts of irreducible walks of a given length between V_{G} vertices remain the same^{11}. As a consequence we get the following simple but important proposition.

Proposition 3.7 We have λ_{Irred} of a VLG is invariant under the subdivision of any set of edges devoid of half-loops; in particular, λ_{Irred} is invariant under passing to a subdivided form of any VLG with all half-loops of length one. Similarly, λ_{Irred} of a graph is invariant under any supression.

We now state a theorem for use later in this paper; the theorem requires a definition.

Definition 3.8 A connected graph, G, is loopy if |E_{G}| ≥ |V_{G}|, or equivalently if G contains an irreducible closed walk, or equivalently if G is not a tree. G is 1-loopy if G is connected and the removal of any edge from G leaves a graph each of whose connected components are loopy.

Theorem 3.9 For a connected graph, G, the following are equivalent:

1. G is 1-loopy,

2. G_{Irred} is strongly connected, and

11We do not know any simple or very natural way to subdivide half-loops of even length in a VLG while keeping λ_{Irred} invariant. A half-loop of length ℓ should be traversable zero or one time in a row (but not twice or more in a row) in an irreducible walk. For odd lengths, ℓ, this can be achieved by adding a path (of length (ℓ − 1)/2) with a halfloop at the end. Morally speaking, subdividing an edge in a VLG, G, can be viewed as subdividing the corresponding edge pair in underlying directed graph, Ĝ, and then gluing them together with an “opposite” pairing (that glues the newly introduced vertices together); for half-loops, we should glue a single directed self-loop of length ℓ to itself, via reflection about the middle); for even length half-loops, that fact that reflection leaves the middle vertex fixed creates problems if we wish to remain in the catergory of undirected graphs…

3. G is not a cycle and all vertices in G have degree at least 2.

In particular, if G is connected and d-regular for d ≥ 3, then G_{Irred} is strongly connected.

Condition (3) in the above theorem was pointed out to us by a referee. Proof (2)⇒(1): Consider a directed edge, e ∼ (u, v), of G, and let e′ be e’s opposite (we permit e = e′, i.e., the case of a half-loop). If the removal of e leaves the connected component of v being a tree, then there is no irreducible walk from e to e′. On the other hand, if this connected component is not a tree, then a cycle in this component about v of minimum length is irreducible, which then extends to an irreducible walk from e to e′. To summarize, if G is not 1-loopy, then G_{Irred} is not strongly connected; otherwise, each edge has an irreducible path to its opposite, i.e., each edge is connected to its opposite in G_{Irred}.

(1)⇒(2): Assume G is 1-loopy. If e_{1}, e_{2} are two distinct, unpaired directed edges originating in the same vertex, v, then an irreducible path from e_{1} to its opposite followed by e_{2} shows that e_{1} and e_{2} are connected by an irreducible path. Thus any two edges that share a vertex are strongly connected in G_{Irred}.

Finally if e_{1}, e_{2} are two undirected edges without a common vertex, then a shortest path connecting them gives an irreducible path from some orientation of e_{1} to some of e_{2}. By the above we can follow them with irreducible paths to the edge of opposite orientation. Thus any two edges that do not share a vertex are strongly connected in G_{Irred}. So G_{Irred} is strongly connected.

(1)⇒(3) Since an isolated vertex is loopy, a 1-loopy graph has all vertices of degree at least 2. Also a 1-loopy graph cannot be a single cycle, since removing any one edge would give a tree.

(3)⇒(1) Any tree either (i) is an isolated vertex, or (ii) is a path with two vertices of degree one, or (iii) has at least three vertices of degree 1 (this follows by considering two vertices, u, v, of maximum distance in a tree, and then taking a vertex of maximum distance to the unique path joining u to v). Consider the tree, T, obtained as the non-loopy connected component by removing an edge, e, from a graph G that is non-loopy. If T is the only connected component, e has both its endpoints in T, and if not then T has only one endpoint in T; in either situation, considering the cases (i)–(iii), it is easy to check that G is a cycle or has at least one vertex (a vertex in T) of degree 1.

□

3.7 λ_{1} and Closed Walks for Infinite Graphs

In this subsection we recall some facts about λ_{1} and closed walks of graphs, either indicating the proofs or giving references. This section is geared to infinite graphs, since most of the facts are very easy when the graph is finite.

Let G be a graph of bounded degree, i.e. there is an r such that the degree of each vertex is at most r. Then A_{G}, G’s adjacency matrix, is a bounded linear operator (bounded by r) on L^{2}(G), the square summable functions on G’s vertices. The next theorem shows that ∥A_{G}∥, the norm of the operator ∥A_{G}∥, equals λ_{1}(G) as was defined by counting closed walks about a vertex of at most some given length.

Theorem 3.10 Assume G is connected. For any vertex, v, of G and positive integer, k, recall that c(v, k) is the number of closed walks of length k in G about v. Then c(v, k) ≤ ∥A_{G}∥^{k}, and

lim_{r→∞}[c(v, 2r)]^{1/(2r)}

exists and equals ∥A_{G}∥.

Since the limit above equals λ_{1}(G), we see that λ_{1}(G) = ∥A_{G}∥. Proof See [Buc86].

□

We also need the following simple fact.

Theorem 3.11 For every ϵ > 0 there is an f ≠ 0 such that ∥Af∥ ≥ (λ_{1} − ϵ)∥f∥, where f has finite support.

Proof By definition of norm, there is a g ≠ 0 with ∥Ag∥ ≥ (λ_{1} − (ϵ/2))∥g∥. For any ν > 0 we may write g = g_{1} + g_{2} where g_{1} is of finite support and ∥g_{2}∥ ≤ ν. It is easy to see (using the fact that A is bounded) that if ν is sufficiently small we can take f = g_{1} to satisfy the above theroem.

□

Figure 1: A graph, ψ, and Tree_{d}(ψ) with d = 4.

3.8 A Curious Theorem

Definition 3.12 Let ψ be a finite connected graph with each vertex of degree at most d for an integer d > 2. By Tree_{d}(ψ) we mean the unique (up to isomorphism) undirected graph, G, that has an inclusion ι: ψ → G such that G is d-regular and such that G becomes a forest when we remove (the image under ι of) ψ’s edges.

We have seen an example of this construction in Section 2, where ψ is one vertex with m self-loops, in the proof of Theorem 2.11. See Figure 1 for another example.

In the category of d-regular graphs with a ψ inclusion, Tree_{d}(ψ) is none other than the universal cover.

The methods used to prove Theorems 1.1, 1.2, and 1.3 suggest the following curious theorem.

Theorem 3.13 Let d ≥ 3, and let ψ be a finite connected graph with each vertex of degree ≤ d. Then

λ_{1}(Tree_{d}(ψ)) = 2\sqrt{d − 1} ⟺ λ_{Irred}(ψ) ≤ \sqrt{d − 1},
λ_{1}(Tree_{d}(ψ)) > 2\sqrt{d − 1} ⟺ λ_{Irred}(ψ) > \sqrt{d − 1}.

The same is true for any real d > 2, provided that λ_{1}(Tree_{d}(ψ)) is interpreted with an appropriate analytic continuation in d (described below).

Before proving the theorem, we describe the analytic continuation to which we refer.

Let T̃ be an undirected rooted tree, where every vertex has d−1 children, with d > 1 an integer (for now). (T̃ has degree d − 1 at the root and degree d elsewhere, so T̃ is not regular.) Let a_{n} for n = 2, 4, … be the number of walks in T̃ from the root to itself that never pass through the root except at the beginning and end. It is easy to see that

S = S_{d}(z) = ∑_{n=2}^{∞} a_{n}z^{n},

satisfies the recurrence S = z^{2}(d − 1)(1 + S + S^{2} + ⋯) (since the walks counted by S take one step, in d − 1 possible ways, to a child of the root, followed by some number (possibly zero) of S walks, followed by the step back to the root); so S(1 − S) = z^{2}(d − 1), so that near z = 0

S = S_{d}(z) = \frac{1 − \sqrt{1 − 4(d − 1)z^{2}}}{2} .  (13)

One can alternatively say that if H is the realization of T̃ with vertex set {v_{0}}, where v_{0} is the root, then the 1 × 1 matrix Z_{H}(z) has entry S(z). Similarly, if T̃ were modified to have d − r children at the root (but every other vertex with d − 1 children, as before), then Z_{H}(z) would have entry (d − r)S(z)/(d − 1).

By λ_{1}(Tree_{d}(ψ)) for d > 1 real (assuming each degree in ψ is ≤ d) we mean λ_{1} of the VLG formed from ψ with an additional self-loop about each vertex of degree r that has “formal weight” (d − r)S_{d}(z)/(d − 1) (this can be viewed as adding an infinite set of self-loops of given weights and lengths corresponding to this power series^{12}, or can simply be viewed as a term to add to the diagonal of Z_{G}(z)). When d in an integer, the realization of Tree_{d}(ψ) with vertex set V_{ψ} is exactly this VLG, and by Proposition 3.7 we know λ_{Irred} remains the same. Proof By [God93], exercise 13 page 72, we know that λ_{Irred}(A) is given by 1/y of the smallest root, y, of

det(I − yA + y^{2}(D − I)) = 0,

12In other words, we view a power series ∑ a_{n}z^{n} as the sum of terms representing a_{n} edges of length n (even when a_{n} is not an integer).

where D is the diagonal matrix whose entry at vertex v is the degree of v, and I is the identity matrix. Now

Z_{G}(z) = zA + \frac{dI − D}{d − 1} S(z).

It is then easy to verify that

I − Z_{G}(z) = (1 − S(z))(I − yA + y^{2}(D − I))

for y = y(z) = z/(1 − S(z)) (note that y(z) is an increasing function in z for as long as z(1 + S + S^{2} + ⋯) converges). But S(z_{1}) ≤ 1/2 for all positive real z_{1} ≤ z_{0}, where z_{0} = 1/(2\sqrt{d − 1}), and also y(z_{0}) = 1/\sqrt{d − 1}. So I − y_{1}A + y_{1}^{2}(D − I) becomes non-invertible for a y_{1} < y(z_{0}) precisely when Z_{G}(z_{1}) has eigenvalue 1 for a z_{1} ∈ [0, z_{0}]. Now apply the equality of quantities (1) and (3) in Theorem 3.5.

□

Note that the proof shows that if 1/y_{1} = λ_{Irred}(A) and 1/z_{1} is Tree_{d}(ψ), then y_{1} = y(z_{1}) provided 1/z_{1} > 2\sqrt{d − 1}.

4 Tangles

In Section 2 we saw that a vertex with m self-loops in a G_{n,d} graph, with m “large,” gives rise to a “large” second eigenvalue (i.e., larger than 2\sqrt{d − 1} for sufficiently large m, as n → ∞). Here we generalize this observation to what we call a “tangle.” Our proof of the Alon conjecture via a trace method must somehow overcome all “hypercritical” tangles.

Definition 4.1 Given two Π-labelled graphs, G and H, we say G contains H (or H occurs in G) if there is an inclusion^{13} ι: H → G that preserves the labelling; the number of times a graph, H, occurs in G is the number of distinct^{14} such ι. A tangle (or G_{n,d}-tangle) is a Π-labelled connected graph, ψ, that is contained in some element of G_{n,d}.

13By an inclusion we mean a graph homomorphism that is a injection on the vertices and on the edges.

14For example, if H = G consists of one edge joining two distinct vertices, u, v, then the identity is considered distinct from the morphism interchanging the vertices. By the same principle, if H has exactly k automorphisms, then the number of times H occurs in a graph is always a multiple of k.

For example, in Section 2 we studied the tangle with one vertex and m self-loops labelled π_{1}, …, π_{m}. We define H_{n,d}- and I_{n,d}- and J_{n,d}-tangles similarly, with the following modifications to the meaning of the π_{i}’s. For H_{n,d}, each of the d/2 independent π_{i}’s is uniform over all permutations whose cyclic decomposition consists of a single cycle. For I_{n,d}, each of d independent π_{i}’s are uniform over all perfect matchings, i.e., over all permutations that are involutions without fixed points. For J_{n,d}, each of d independent π_{i}’s are uniform over all involutions with exactly one fixed point.

Theorem 4.2 Fix a positive integer, d ≥ 3, and a graph ψ. Any graph, G, on n vertices, that contains ψ has second eigenvalue at least ρ − o(1), where o(1) is a function of n tending to 0 as n → ∞, and where ρ is the norm of the adjacency matrix of Tree_{d}(ψ).

This generalizes Theorem 2.11. Proof Fix ϵ > 0; we will show that for n sufficiently large any such G has λ_{2}(G) ≥ ρ − ϵ. First, there is a finitely supported f ≠ 0 on Tree_{d}(ψ) with ∥Af∥ ≥ ∥f∥(ρ − ϵ), where A is the adjacency matrix of Tree_{d}(ψ). If V_{ψ} is the set of vertices on which f is non-zero, then replacing f with the nonnegative first Dirichlet eigenfunction on V_{ψ} (see [Fri93]) we may assume f is non-negative, nonzero, and that Af ≥ f(ρ − ϵ) (with equality everywhere except at the boundary of V_{ψ}). There is a covering map (see [Fri93] and [Fri03]) π: Tree_{d}(ψ) → G; set π_{∗}f to be the function on G defined by

(π_{∗}f)(v) = ∑_{π(w)=v} f(w).

If A_{G} is the adjacency matrix of G, then clearly

A_{G}(π_{∗}f) ≥ (ρ − ϵ)(π_{∗}f).

So, on the one hand, R(π_{∗}f) ≥ ρ − ϵ, where R is the Rayleigh quotient for A_{G}. On the other hand, the support, N, of π_{∗}f is of size no greater than that of f, and this size is bounded (independent of G and n). So the same reasoning as in the proof of Theorem 2.11 shows that

R(g) ≥ d − o(1), where g = χ_{V \Ñ},

where Ñ is the set of vertices of distance 0 or 1 to N. Since π_{∗}f is orthogonal to both g and A_{G}g, we are done (by Lemma 2.9).

□

Definition 4.3 A tangle, ψ, is critical (respectively, supercritical, hypercritical) if λ_{Irred}(ψ) equals (respectively, is at least, exceeds) \sqrt{d − 1}.

According Theorems 3.13 and 4.2, a fixed hypercritical tangle can only occur in a graph with sufficiently many vertices if the graph has λ_{2} > 2\sqrt{d − 1}.

Now that we know how tangles affect eigenvalues, we want to know how often the tangles occur. This discussion, and the particular application to H_{n,d}, I_{n,d}, and J_{n,d}, will take the rest of this section.

Definition 4.4 A leaf on a graph is a vertex of total degree 1 (whether the graph is directed or not). We say that a graph is pruned if it has no leaves. A simple pruning is the act of removing one leaf and its incident edge from a graph; pruning is the repeated performance of some sequence of simple prunings; complete pruning is the act of pruning until no more pruning can be done.

For example, completely pruning a tree results in a single vertex with no edges; completely pruning a cycle leaves the cycle unchanged.

Proposition 4.5 Given a graph, G, there is a unique pruned graph H obtainable from completely pruning G. Furthermore, H is completely pruned iff each edge of H lies on an irreducible cycle.

Proof Let e_{1}, …, e_{t} denote the edges pruned in one pruning of G, in the order in which they are pruned. Let G′ be a different complete pruning of G, which we assume does not contain all the e_{i}. Let j be the smallest integer such that e_{j} lies in G′. On the one hand, the removal of e_{1}, …, e_{j−1} from G, or any subgraph of G, allows e_{j} to be pruned from G, or any subgraph of G, including G′. On the other hand, the prunability of e_{j} from G′ contradicts the completeness of the pruning that formed G′. It follows that any complete pruning contains all the edges of any other, and so any two are the same.

We now address the last statement of the theorem. If H has a leaf, then the edge incident upon this leaf does not lie in an irreducible cycle. Conversely, if H has no leaves, and if e is an edge with endpoints u, v, consider the graph, H′, obtained by removing e from H. If u and v are connected in H′, then a minimal length path that joins them, along with e, gives an irreducible cycle containing e. Otherwise, since u’s connected component is not a tree (or else H would have leaves), this component has an irreducible cycle, and a shortest walk from u to this cycle, once around the cycle, and back to u gives an irreducible cycle beginning and ending at u. Similarly there is such a cycle about v. The cycle about u, followed by e, followed by the w cycle, and back through e (in the other direction), gives an irreducible cycle containing e.

□

A morphism of tangles is a morphism of Π-labelled graphs, i.e., a graph morphism that preserves the edge labelling.

Definition 4.6 The order of a tangle, ψ, is ord(ψ) = |E_{ψ}|−|V_{ψ}| (so while a whole-loop is counted as one edge, for the model J_{n,d}, to be considered soon, a half-loop is also counted as one edge^{15}). More generally, for a graph, G, or any structure with an underlying graph, G (such as a “form” or “type” to be defined in Section 5), its order is ord(G) = |E_{G}| − |V_{G}|.

Theorem 4.7 Let ψ be a tangle of non-negative order. Then the expected number of occurrences of ψ in an element, G, of G_{n,d} is n^{−r} + O(n^{−r−1}), where r is the order of ψ. The probability that at least one occurrence occurs is at least n^{−r}/c − n^{−2r}/(2c^{2}) + O(n^{−r−1}), with r as before and where c is the number of automorphisms of the complete pruning of ψ.

Notice that the number of automorphisms of the complete pruning of a tangle, ψ, is at least as many as that of ψ, and it may be strictly greater^{16}. The proof following will imply that the probability of ψ’s occurrence is also at most n^{−r}/c + O(n^{−r−1}), which matches the lower bound to first order, provided that r ≥ 1. Proof Let V_{ψ} = {u_{1}, …, u_{s}}, and for a tuple m⃗ = (m_{1}, …, m_{s}) of distinct integers between 1 and n, let ιm⃗ denote the event that the map, ι, mapping u_{i} to m_{i}, is an occurrence of ψ in G. If a_{i} is the number of ψ’s edges labelled π_{i}, then each event ιm⃗ involves setting a_{i} values of π_{i}, all of which occur with probability

15Rougly speaking, the reason for this is that a whole-loop and half-loop are both 1/n + O(1/n^{2}) probability events.

16Indeed, a structural induction argument (i.e., by pruning one leaf) shows that any automorphism of the complete pruning of ψ has at most one extension to ψ. On the other hand, if ψ is a cycle of length q with all edges in one “direction” labelled π_{1}, then ψ has q automorphisms; yet if we add one edge labelled π_{2} to ψ at any vertex, the new graph has only the trivial automorphism.

\frac{(n − a_{1})!}{n!} ⋯ \frac{(n − a_{d/2})!}{n!}.  (14)

Since the sum of the a_{i} is |E_{ψ}|, this probability is n^{−|E_{ψ}|}. Since there are n!/(n − |V_{ψ}|)! = n^{|V_{ψ}|} + O(n^{|V_{ψ}|−1}) different ιm⃗’s, the expected number of occurrences is n^{−r} + O(n^{−r−1}), where r = ord(ψ).

Next notice that if ψ′ is a pruning of a tangle, ψ, then the probability that ψ occurs is 1+O(n^{−1}) times the probability that ψ′ occurs (adding each pruned edge adds a condition that occurs with probability between 1 and (n − c_{1})/(n − c_{2}) with c_{1}, c_{2} constants). Hence we may assume ψ is pruned.

An automorphism of ψ can be viewed as a permutation on V_{ψ}, which is the same as a permutation, σ, on {1, …, s} (identifying a u_{i} ∈ V_{ψ} with i). Such a permutation, σ, acts by permuting the components of the m⃗’s. Say that ιm⃗ is equivalent to ιk⃗ if m⃗ and k⃗ differ by a permutation, σ, associated to an automorphism of ψ; i.e., if ιm⃗ and ιk⃗ correspond to the same subgraph of G. Let R be a set of representatives in the equivalence classes of all m⃗’s.

By inclusion/exclusion, the probability that ψ occurs at least once is at least

∑_{m⃗∈R} Prob \{ιm⃗\} − \frac{1}{2} ∑_{\begin{matrix}k⃗≠m⃗ \\ k⃗,m⃗∈R \end{matrix}} Prob \{ιm⃗ ∩ ιk⃗\} .  (15)

The first summand is (1/c)n^{−r} + O(n^{−r−1}), by the argument given for the expected number. For the second summand, we may write ιm⃗ ∩ ιk⃗ as ιq⃗(ψ′), where q⃗ is a vector comprised of the distinct components of m⃗ and k⃗, and where ψ′ is the tangle obtained by gluing two copies of ψ along certain vertices (corresponding to where the components of m⃗ and k⃗ coincide). If m⃗ is disjoint from (i.e., nowhere coincides with) k⃗, then ψ′ is two disjoint copies of ψ; for fixed k⃗ ∈ R we have

∑_{m⃗∈R m⃗ disjoint from k⃗} Prob {ιm⃗ | ιk⃗} = n^{−r}/c + O(n^{−r−1}),

the summation being over conditional probabilities, since the conditioning of ιk⃗ and summing over m⃗ disjoint only affects equation (14) by changing n!/(n − a_{i})! terms into (n − c_{i})!/(n − c_{i} − a_{i})! terms for constants c_{i}, which is a second order change. Hence

∑_{k⃗,m⃗∈R k⃗,m⃗ disjoint} Prob {ιm⃗ ∩ ιk⃗} = ∑_{k⃗∈R} Prob {ιk⃗} ∑_{m⃗∈R m⃗ disjoint from k⃗} Prob {ιm⃗ | ιk⃗}

= ∑_{k⃗∈R} Prob {ιk⃗} (n^{−r}/c + O(n^{−r−1})) = n^{−2r}/c^{2} + O(n^{−2r−1}).

To understand the situation where m⃗ and k⃗ overlap somewhere, we pause for some lemmas.

Lemma 4.8 Let ι: ψ → G be an inclusion of graphs, with G connected. Then the order of G is at least that of ψ.

Proof Let G_{ψ} be G with the vertices of ι(ψ) identified, and all ι(ψ) edges discarded. Then G_{ψ} is connected, and so has order at least −1; on the other hand, clearly the order of G_{ψ} is the order of G minus that of ψ minus 1 (for the vertex that is the identification of all ι(ψ) vertices). Hence

ord(G) = ord(G_{ψ}) + ord(ψ) + 1 ≥ −1 + ord(ψ) + 1 = ord(ψ).
□

Lemma 4.9 Let G be a pruned graph and let e ∈ E_{G}. If G\{e} (i.e., G with e removed) has two connected components, then each connected component has order at least 0.

Proof Consider a connected component, G′, of G\{e}. If G′ did not contain a cylce, then G′ would be a tree, and then G would not be completely pruned. So G′ contains a cycle, and we may apply Lemma 4.8 to deduce that G′ has order at least 0

□

Lemma 4.10 Let ι: ψ → G be an inclusion of pruned graphs. Then the order of G is at least that of ψ, and G’s order is strictly greater than ψ’s if ι(ψ) is properly contained in G.

Proof A connected component of a graph that is pruned (and non-empty) has non-negative order. So we may assume ι(ψ) meets every connected component of G. It suffices to prove the case where ι(ψ) meets one connected component of G, i.e., the case where G is connected. Choosing an edge, e, that is missed by ι(ψ), we have that ι includes ψ into G \ {e} (i.e., G with e removed); we apply Lemma 4.8 to those components of G \ {e} containing part of ι(ψ), and to the possibly one other component of G \ {e} we apply Lemma 4.9. It follows that the order of ψ is at most that of G \ {e}; but the order of G \ {e} is one less than that of G.

□

Lemma 4.11 Let ι_{1}, ι_{2} : ψ → H be two inclusions of a tangle, ψ, in a connected (labelled) graph, H, such that ι_{1}(ψ) ∪ ι_{2}(ψ) = H. Assume that ι_{1}(ψ) ≠ H. Then the order of H is greater than that of ψ.

Proof Ignoring ι_{2}, the preceeding lemma applies to ι_{1} to immediately yield this lemma.

□

Lemma 4.11 shows that

∑_{k⃗,m⃗ not disjoint k⃗,m⃗∈R, k⃗≠m⃗} Prob {ιm⃗ ∩ ιk⃗} = O(n^{−r−1}),

since the summation can be broken down into a finite number of sums over tangles of order at least r + 1. Thus

∑_{m⃗∈R} Prob \{ιm⃗\} − \frac{1}{2} ∑_{\begin{matrix}k⃗≠m⃗ \\ k⃗,m⃗∈R \end{matrix}} Prob \{ιm⃗ ∩ ιk⃗\} .

= n^{−r}/c + O(n^{−r−1}) − n^{−2r}/(2c^{2}) + O(n^{−2r−1}) + O(n^{−r−1}),

which completes the proof of Theorem 4.7.

□

It is easy to see that the above proof of Theorem 4.7 uses very little about the model of random graph, and therefore generalizes as follows.

Theorem 4.12 Let K_{n} be a model of d-regular random graphs on n vertices labelled {1, …, n}, defined for some values of n. Further assume that (1) K_{n} is invariant under renumbering {1, …, n}, and (2) any tangle, ψ, has expected number of occurrences n^{−r} + O(n^{−r−1}) where r is the order of ψ. Then Theorem 4.7 holds for K_{n}.

Theorem 4.13 For G drawn from H_{n,d} or I_{n,d}, we have that λ_{2}(G) > 2\sqrt{d − 1} with probability at least n^{−s}/2 + O(n^{−s−1}) where s = ⌊\sqrt{d − 1}⌋, except for when d = 4 in H_{n,d}, where we may take s = 2. The same holds for J_{n,d} with probability n^{−s} + O(n^{−s−1}), where s = ⌊(\sqrt{d − 1} + 1)/2⌋ (and no exceptional values of d).

Proof For J_{n,d}, the tangle consisting of 1 vertex with a number of self-loops (in this case half-loops), proves the theorem for J_{n,d} just as it did for G_{n,d} in Theorem 2.11.

Consider the tangle, ψ, with two vertices and m edges joining the two vertices labelled π_{1}, π_{2}, …; ψ is an H_{n,d}-tangle provided that m ≤ d/2, and an I_{n,d}-tangle if m ≤ d. λ_{Irred}(ψ) is clearly m − 1, s = ord(ψ) = m − 2, and the automorphism group of ψ is of order 2. So if m − 1 > \sqrt{d − 1} and if G contains this tangle, then we have λ_{2}(G) > 2\sqrt{d − 1} for n sufficiently large. If we take s = ⌊\sqrt{d − 1}⌋, then m − 1 > \sqrt{d − 1}; we require m ≤ d for I_{n,d}, amounting to

⌊\sqrt{d − 1}⌋ + 2 ≤ d,

which is satisfied for all d ≥ 3. For H_{n,d} we require

⌊\sqrt{d − 1}⌋ + 2 ≤ d/2,

which is satisfied for all d ≥ 7. Since d is even and ≥ 4 in H_{n,d}, we finish by examining the cases d = 4 and d = 6.

For d = 4 consider the tangle, ψ, with vertices v_{1}, v_{2}, v_{3}, v_{4}, edges labelled π_{1}, π_{2} from v_{1} to v_{2}, from v_{2} to v_{3}, and from v_{3} to v_{4}. Then ord(ψ) = 2 and λ_{Irred}(ψ) > λ_{Irred}(ψ′) where ψ′ is the subgraph of ψ induced on v_{1}, v_{2}, v_{3}. But in the proof of Theorem 6.10 we compute λ_{Irred}(ψ′) = \sqrt{3}. Hence ψ is hypercritical of order 2, so we may take s = 2 in the theorem in the case of d = 4 and H_{n,d}.

For d = 6, the proof of Theorem 6.10 gives a tangle of order 2 with λ_{Irred} > \sqrt{5} (see equation (30) and the discussion around it). So we may take s = 2 in our theorem when d = 6 in H_{n,d}.

□

Figure 2: A form and its associated type.

5 Walk Sums and New Types

In this section we give some general techniques that are used in estimating the expected values of all the various traces that are used in this paper. The main idea, originated in [BS87] and strengthened in [Fri91], is to group contributions to the trace in the following way. Consider the word, w, and vector, t

w = (σ_{1}, …, σ_{10}) = (π_{2}^{−1}, π_{1}, π_{3}, π_{1}^{−1}, π_{3}, π_{3}, π_{1}^{−1}, π_{3}, π_{1}^{−1}, π_{2}),
t⃗ = (t_{0}, …, t_{10}) = (5, 2, 4, 3, 7, 4, 3, 7, 4, 2, 5)

(see Figure 2). This represents a possible or potential irreducible closed walk of length 10, from 5 to 2 along the edge labelled π_{2}^{−1}, from 2 to 4 along π_{1}, etc. Graphically we depict this potential walk by the subgraph it traces out, called its “form” (see Figure 2). The pair (w; t⃗) represents a possible contribution to IrredTr (A, 10). For any word, w, of length k and vector, t⃗, of length k + 1, let P (w; t⃗) be the probability that σ_{i}(t_{i−1}) = t_{i} for all i, i.e., that the cycle does occur. Then the expected value of IrredTr (A, 10) is just a sum of appropriate P (w; t⃗)’s, what we will call a “walk sum.”

In the form of Figure 2, we see that the numbers of the vertices 5, 2, 4, 3, 7, are irrelevant, since our random graph model is “symmetric,” or invariant under renumbering the vertices. So we may replace the vertex 5 by an abstract symbol v_{1}, 2 by v_{2}, etc. (for reasons to made clear later, we do want to remember the order in which the vertices were traversed); this replacement is not necessary, but makes clear that there is no particular preference for any numbering of the vertices.

In our example of Figure 2, (w; t⃗), a loop about the vertex 4 is traversed twice before we return to the starting vertex 2. Broder and Shamir realized that the other vertices, those of degree 2 that are not the starting vertex (here the vertices 2, 3, 7) are less interesting features of the “form.” By supressing these “less interesting” vertices we get the “type” of the form (see Figure 2); in [Fri91], walk sums were grouped by their form, and the sums for each form were grouped by the type of the form. A type is a graph with certain features, but when a form gives rise to a type then the edges of the type inherit Π^{+} labels from the form, and inherit “lengths,” which are the lengths of the Π^{+} labels (recall that Π^{+} is the set of nonempty words over Π). For example, the edge (5, 4) of the type in Figure 2 inherits a length of 2 and a label of π_{2}^{−1}π_{1} from the form next to it; edge (4, 4) inherits a length of 3 and a label of π_{3}π_{1}^{−1}π_{3}.

This paper introduces a “new type,” used in analyzing walk sums corresponding to selective traces. A new type is a type with some additional information, primarily fixing the lengths of certain type edges and requiring all other lengths to be sufficiently large.

5.1 Walk sums

By a weakly potential (k, n)-walk, (w; t⃗), we mean a pair consisting of a word w = σ_{1} … σ_{k} of length k over Π, and a vector, t⃗ = (t_{0}, …, t_{k}), with each t_{i} ∈ {1, …, n}; we sometimes refer to k as the length and n as the size of the weakly potential walk. Given such a (w; t⃗), let E(w; t⃗) denote the event that the π_{i} are chosen so that σ_{i}(t_{i−1}) = t_{i} for all i = 1, …, k. Let P (w; t⃗) denote the probability that E(w; t⃗) occurs.

A potential (k, n)-walk is a weakly potential (k, n)-walk that is feasible, meaning that P (w; t⃗) ≠ 0, or equivalently that the following two feasibility conditions hold: (1) for any i, j such that σ_{i} = σ_{j}, we have

t_{i−1} = t_{j−1} ⇔ t_{i} = t_{j},

and for any i, j such that σ_{i} = σ_{j}^{−1}, we have

t_{i−1} = t_{j} ⇔ t_{i} = t_{j−1}.

For example, if t⃗ = (1, 1, 2) and w = π_{1}π_{1}, then (w, t⃗) is a weakly potential walk but not a potential walk. A potential (k, n)-closed walk is a potential walk, (w, t⃗) as above with t_{k} = t_{0}.

All our variants of traces, irreducible and not irreducible, selective and not, can be viewed as sums of P (w; t⃗) over appropriate w’s and t⃗ ’s. In this subsection we formalize this notion and make preliminary remarks about such sums and asymptotic expansions.

Definition 5.1 A walk collection, W = W(k, n), is a collection, for any two positive integers k and n, of (k, n)-potential walks (w; t⃗) as above, i.e. w is a word over Π of length k, and t⃗ = (t_{0}, …, t_{k}) is a k + 1 dimensional vector over {1, …, n}, and (w; t⃗) is feasible. The walk sum associated to W is

WalkSum(W, k, n) = ∑_{(w;t⃗)∈W(k,n)} P (w; t⃗).

The main goal of this paper is to organize the various (w, t⃗) pairs into groups over which we can easily sum P (w; t⃗). One simple organizational remark is that symmetries in the (w; t⃗) pairs often simplify matters. Specifically, given an permutation, τ, of the integers, and a vector t⃗ as above, let

τ(t⃗) = (τ(t_{0}), …, τ(t_{k})).

Say that s⃗ and t⃗ differ by a symmetry if s⃗ = τ(t⃗) for some τ; in this case clearly P (w, s⃗ ) = P (w, t⃗ ) for any word w of length k. We use s⃗ ∼ t⃗ to denote that s⃗ and t⃗ differ by a symmetry.

Definition 5.2 A walk collection, W, is SSIIC if it is

1. symmetric, i.e. (w, t⃗) ∈ W(k, n) implies that (w, s⃗) ∈ W(k, n) for all s⃗ ∼ t⃗ such that s_{i} ≤ n for all i,

2. size invariant, i.e. if (w, t⃗) is a potential (k, n)-walk, then for any n′ > n, (w, t⃗) ∈ W(k, n) iff (w, t⃗) ∈ W(k, n′),

3. irreducible, meaning that (w, t⃗) ∈ W implies that w is irreducible, and

4. closed, meaning that (w, t⃗) ∈ W implies that t_{0} = t_{k}.

The walk sums of interest here, namely traces that are irreducible or strongly irreducible and possibly selective, will all be SSIIC. We now make a series of remarks about walk sums that apply to all SSIIC walk sums; some of the remarks apply more generally.

Definition 5.3 Let t⃗ be as above, i.e., a positive integer valued vector. Define the equivalence class of t⃗ to be

[t⃗] = {s⃗ | s⃗ ∼ t⃗},

i.e., the set of all positive integer values vectors differing from t⃗ by a symmetry. Define the n-th equivalence class of t⃗

[t⃗]_{n} = {s⃗ | s⃗ ∼ t⃗ and all s_{i} ≤ n}

(we may omit the n subscript if n is understood).

Let n be fixed, and set

E_{symm}(w; t⃗) = E_{symm}(w; t⃗)_{n} = ∑_{s⃗∈[t⃗]_{n}} P (w; s⃗)

= n(n − 1) ⋯ (n − v + 1)P (w; t⃗),

where v is the number of distinct elements of t⃗. A symmetric walk sum is just the sum of certain E_{symm}(w, t⃗)’s, and we can write

WalkSum(W, k, n) = ∑_{(w;[t⃗])∈W(k,n)} E_{symm}(w; t⃗),

where the summation over (w; [t⃗]) ∈ W(k, n) means that we sum over one t⃗ in each equivalence class and over all w.

Each t⃗ = (t_{0}, …, t_{k}) has an s⃗ ∼ t⃗ where the size of s⃗ ’s entries are at most k + 1. So for each k there are a finite number of equivalence classes, W(k), of (w; t⃗) such that w is of length k and t⃗ is of some finite size. We refer to W(k) as the set of potential walk classes of length k (or potential closed walk classes when we restrict to those t⃗ ’s with t_{k} = t_{0}). So if W is size invariant we may write

WalkSum(W, k, n) = ∑_{(w;[t⃗])∈W(k)} E_{symm}(w; t⃗)_{n},

where the right-hand-side summation has a fixed, finite number of summands independent of n (for fixed k).

Our next step is to comment about E_{symm}(w, t⃗)_{n}. Notice that if the conditions σ_{i}(t_{i−1}) = t_{i} involve determining a_{j}values of π_{j}, then

P (w; t⃗) = ∏_{i=1}^{d/2} \frac{1}{n(n − 1) ⋯ (n − a_{j} + 1)} = ∏_{i=1}^{d/2} \frac{(n − a_{j})!}{n!}.  (16)

Let e = a_{1} + ⋯ + a_{d/2}. We have

E_{symm}(w, t⃗)_{n} = n(n − 1) … (n − v + 1) ∏_{i=1}^{d/2} \frac{1}{n(n − 1) ⋯ (n − a_{j} + 1)}.

Notice that in the power series expansions about x = 0 of

(1 − x)(1 − 2x) … (1 − mx) and (1 − x)^{−1}(1 − 2x)^{−1} … (1 − mx)^{−1},

the x^{i} coefficient is a polynomial (of degree at most 2i) in m. It follows that there exist polynomials p_{0}, p_{1}, … in the variables a_{1}, …, a_{d/2}, v such that

E_{symm}(w, t⃗)_{n} = n^{v−e} ∑_{i=0}^{∞} n^{−i}p_{i}(a_{1}, …, a_{d/2}, v)  (17)

for n sufficiently large.

Definition 5.4 We define the expansion polynomials,

p_{i} = p_{i}(a_{1}, …, a_{d/2}, v),

to be the polynomials that give the expansion in equation (17). Throughout the paper, a_{i}denotes the number of π_{i} values determined by the relevant structure (in this case the potential walk, (w, t⃗)).

We remark that since e = a_{1} + ⋯ + a_{d/2}, we have that v is determined from the a_{i} if v − e is fixed and known; in such situations, the expansion polynomials may be regarded as functions of the a_{i} alone.

Theorem 5.5 For any w, t⃗ and any integer q ≥ 0 we have

E_{symm}(w, t⃗)_{n} = n^{v−e}(p_{0} + \frac{p_{1}}{n} + ⋯ + \frac{p_{q}}{n^{q}} + \frac{error}{n^{q+1}})  (18)

where

|error| ≤ exp((q + 1)k/(n − k)) k^{2q+2},

and the p_{i} are the expansion polynomials.

The proof is contained between Lemma 2.7 and Corollary 2.10 of [Fri91], although the proof there has a minor error. We will correct it here and review the entire proof, since we will later need variants of this theorem for H_{n,d}, I_{n,d}, J_{n,d}. If

g(x) = (1 − b_{1}x) ⋯ (1 − b_{r}x)(1 − c_{1}x)^{−1} ⋯ (1 − c_{s}x)^{−1},  (19)

where the b_{i} and c_{j} are positive constants, then g’s i-th derivative satisfies the bound

|g^{(i)}(x)|/i! ≤ (1 − xc_{max})^{−i} (∑ b_{j} + ∑ c_{j})^{i}

where c_{max} is the maximum of the c_{j} (by equation (6) in [Fri91] on page 339). This estimate, using Taylor’s theorem, expanding in x = 1/n about x = 0, gives the error term for Theorem 5.5 of

(1 − ζc_{max})^{−q−1} (∑ b_{j} + ∑ c_{j})^{q+1} ,

for some ζ ∈ [0, 1/n]. Since

− log(1 − ζc_{max}) = (ζc_{max}) + (ζc_{max})^{2}/2 + ⋯ ≤ ζc_{max}/(1 − ζc_{max})
≤ (k/n)/(1 − (k/n)) = k/(n − k),

we conclude that the error term is at most

exp((q + 1)k/(n − k)) (∑ b_{j} + ∑ c_{j})^{q+1} .  (20)

In the case of Theorem 5.5, the ∑ b_{j} represents the sum of 0, 1, …, v − 1, which is at most \binom{k}{2}, and the ∑ c_{j} represents the sum over j of all sums of 0, 1, …, a_{j} − 1, which is at most \binom{k}{2}. Since 2\binom{k}{2} ≤ k^{2}, we get an error term at most exp((q + 1)k/(n − k))k^{2q+2}. (See [Fri91] for more details.)

□

Definition 5.6 Given a pair, (w, t⃗), as above, its order is e − v, with e, v as above.

Lemma 5.7 Given a word, w, of length k over Π, we have

∑_{t⃗ such that (w,t⃗) is of order ≥r} P (w, t⃗) ≤ n\binom{k}{r + 1} (\frac{k}{n − k} )^{r+1} ,

which for k ≤ n/2 is at most ck^{2r+2}n^{−r} for some constant c depending only on r.

Proof This can be found in [Fri91], second displayed equation and discussion before on page 352; this is the same idea used in the r = 1 case proven in [BS87]. (The extra factor of n appears here but not in [Fri91], since we do not fix the initial vertex of the walk. Also note that the “order,” used here, is one less than the “number of coincidences,” used in [Fri91].) For the ease of reading, we shall discuss these ideas in our notation.

We may evaluate P (w, t⃗) by considering the steps of the walk w = σ_{1} … σ_{k} one by one; i.e., we fix a v_{0} ∈ {1, …, n} and consider the random walk v_{1} = σ_{1}(v_{0}), v_{2} = σ_{2}(v_{1}), etc. We inductively consider the probability that (v_{0}, …, v_{s}) is equivalent to (t_{0}, …, t_{s}) for s = 1, …, k. Assuming (v_{0}, …, v_{s}) is equivalent to (t_{0}, …, t_{s}), and assuming we wish to have (v_{0}, …, v_{s+1}) equivalent to (t_{0}, …, t_{s+1}), one can divide the choice and outcome of the random variable v_{s+1} = σ_{s+1}(v_{s}) into three cases: (1) v_{s+1} has already been determined by previous information (i.e., the value σ_{s+1}(v_{s}) has been determined in a previous step); (2) v_{s+1} has not been determined and (2a) v_{s+1} must occur as one of the v_{0}, …, v_{s} (i.e., when t_{s+1} occurs previously in t_{0}, …, t_{s}), or (2b) v_{s+1} must must be different from v_{0}, …, v_{s} (i.e., when t_{s+1} does not occur previously). We call case (1) a forced choice, case (2) a free choice, with case (2a) a coincidence, and case (2b) a generic choice.

For example, if w = π_{1}π_{1}π_{2}π_{3} and t⃗ = (1, 1, 1, 2, 1), then v_{1} is a coicidence (since t_{1} occurs previously as t_{0} and π_{1}(v_{0}) has not been determined), v_{2} is a forced choice (since π_{1}(v_{0}) = v_{0} = v_{1} has been determined), v_{3} is a generic choice (t_{3} does not occur in t_{0}, t_{1}, t_{2}), and v_{4} is a coincidence.

A choice v_{s+1} = σ_{s+1}(v_{s}) is deterministic if it is a forced choice; a choice occurs with probability 1 − O(s/n) if it is a generic choice, and with probability 1/n + O(s/n^{2}) if it is a coincidence. We see that a word of order t has exactly t + 1 coincidences. If follows that each word of order at least r and length k has some r + 1 positions of k that can be marked as coincidences. Fixing a marking, each coincidence of the marking occurs with probability at most k/(n − k) (since v_{s+1} must assume one of the at most s + 1 ≤ k values v_{0}, …, v_{s}, and at most k values of the permutation σ_{s+1} could have been determined up to that point). Finally v_{0} can be chosen in n ways. We conclude the lemma.

□

Lemma 5.8 For any irreducible word, w, over Π, of length k, there are at most

∑_{j=0}^{r} \binom{k}{j}k^{j} ≤ ck^{2r}  (21)

equivalence classes [t⃗] whose order with w is ≤ r − 1.

Proof See the third displayed equation of page 352 of [Fri91] and the discussion preceding. For completeness and ease of reading, we repeat the argument here.

If w has order j − 1, then it has j coincidences occurring in k places. Again, in each coincidence, v_{s+1} = σ_{s+1}(v_{s}), v_{s+1} is being chosen from at most k values. This gives the left-hand-side of equation (21). For the righthand-side we notice that

∑_{j=0}^{r} \binom{k}{j}k^{j} ≤ ∑_{j=0}^{r} k^{2j} ≤ k^{2r}(1 + k^{−2} + k^{−4} + ⋯) ≤ k^{2r}(4/3)

for k ≥ 2.

□

Theorem 5.9 Let W be SSIIC and let r ≥ 1. Then for all k ≤ n/2 we have

WalkSum(W, k, n) = f_{0}(k) + \frac{f_{1}(k)}{n} + ⋯ + \frac{f_{r−1}(k)}{n^{r−1}} + \frac{error}{n^{r}},

where

f_{i}(k) = ∑_{j=0}^{r−1} ∑_{(w;[t⃗]) order j,∈W(k)} p_{i−j}(w; [t⃗])

(with p_{i} the expansion polynomials, which can be viewed as a function of (w; [t⃗]) since (w; [t⃗]) determines the a_{i} and v) and where for some c depending only on r,

|error| ≤ ck^{4r}(d − 1)^{k}.

Proof By Lemma 5.7, we introduce an error of at most ck^{2r+2}n^{−r} per word by ignoring potential walks of order at least r. Each word, w, has at most ck^{2r} associated potential walk classes of order at most r − 1 (by Lemma 5.8), and truncating the associated asymptotic expansion, as in equation (18), of each associated potential walk class results in an error of at most ck^{2r} (by Theorem 5.5). So each word, w, of length k involved in W contributes an error of at most ck^{4r}, and there are at most d(d−1)^{k−1} such words (for k ≥ 1) since W consists of only irreducible words.

□

5.2 The Loop

Here we analyze walk sums associated with simple loops. This gives some ideas and a lemma to be used in Section 8.

5.2.1 The Singly Traversed Simple Loop

Let w be an irreducible word over Π of length k and t⃗ a k + 1 tuple over {1, …, n} as in the previous subsection. If t_{0} = t_{k} and the t_{i}’s are otherwise distinct, we say (w; t⃗) is a singly traversed simple loop or STSL for short; we define W_{STSL} to be the collection of all STSL’s. When E(w; t⃗) occurs and (w; t⃗) ∈ W_{STSL}, the closed walk from t_{0} following w traces out a “simple loop” once, that begins and ends at t_{0}, moving through distinct edges and vertices throughout the closed walk.

Clearly W_{STSL} is SSIIC, so according to Theorem 5.9 we have an asymptotic expansion in 1/n with coefficients f_{i}(k) for the associated walk sum. We now briefly indicate why the f_{i} are d-Ramanujan. This is a mildly tedious exercise, covered (in much greater generality) in [Fri91]. We quote the main points here.

First, note that there is exactly one equivalence class [t⃗] of t⃗ ’s that appear in W_{STSL}. So we may write E_{symm}(w) for E_{symm}(w; t⃗) for any t⃗ of the equivalence class, and we may write p_{i}(w) for the p_{i}(w; t⃗) in Theorem 5.9 or 5.5 (note also that v = k in the notation of Theorem 5.5).

Let for σ, τ ∈ Π, let Irred_{k,σ,τ} denote the irreducible words of length k beginning with σ and ending with τ. For w ∈ Π^{k} let a_{i}(w)denote the number of π_{i} and π_{i}^{−1} occurring in w. Since an STSL has no forced choices, the definition of a_{i} here agrees with that in Definition 5.4.

Lemma 5.10 Let p = p(a_{1}, …, a_{d/2}, k) be a polynomial. For every σ, τ there are polynomials Q_{1}, Q_{2}, Q_{3} of k of degree at most the degree of p such that

∑_{w∈Irred_{k,σ,τ}} p(a_{1}(w), …, a_{d/2}(w), k) = (d − 1)^{k}Q_{1}(k) + (−1)^{k}Q_{2}(k) + Q_{3}(k).

Proof This is immediate from Lemma 2.11 of [Fri91] or Corollary 2.12 (note that our d is 2d in [Fri91]).

□

Note that the formula for the above lemma comes about from the fact that d−1, −1, 1 are the eigenvalues of G_{Irred} where G is the graph with one vertex and d/2 whole-loops (with G_{Irred} defined as in Subsection 3.6).

Corollary 5.11 We have each f_{i}(k) as in Theorem 5.9 for W = W_{STSL} is d-Ramanujan.

Proof Recall that an (w, t⃗) ∈ W_{STSL} is of order 0, and there is only one equivalence class of t⃗ for STSL’s. So we have

f_{i}(k) = ∑_{σ≠τ^{−1}} ∑_{Irred_{k,σ,τ}} p_{i}(a_{1}(w), …, a_{d/2}(w), k),

where the p_{i} are the expansion polynomials. The result now follows from Lemma 5.10, with error term bounded by a polynomial in k.

5.2.2 Simple Loops

Consider any irreducible (w, t⃗) that traces out a simple loop, i.e., the vertices and edges visited form one closed walk, but now we don’t require that the loop is traversed only once. Corresponding to this geometric picture of a simple loop we can form the associated walk collection of simple loop closed walks; such closed walks, being irreducible, must traverse the loop traced out some number of times.

So let W_{SL} be the set of (w, t⃗) pairs with

1. w = σ_{1}… σ_{k} irreducible,

2. σ_{1} ≠ σ_{k}^{−1}, 3. t_{0}, …, t_{r−1} distinct for some r dividing s,

4. t_{i+r} = t_{i} for 0 ≤ i ≤ k − r, and

5. w = u^{s} for some word u with rs = k. W_{SL} is the walk collection of simple loop walks.

Clearly we have

WalkSum(W_{SL}, k, n) = ∑_{s|k} WalkSum(W_{STSL}, s, n).  (22)

We easily conclude the following theorem. Theorem 5.12 The f_{i}(k) corresponding to W_{SL} are d-Ramanujan, and have the same principal term as the f_{i}(k) corresponding to W_{STSL}. Proof Consider the f_{i}(k) corresponding to W_{STSL}. By Corollary 5.11, all the f_{i} are d-Ramanujan. By equation (22), it suffices to show that

f̃_{i}(k) = ∑_{s|k} f_{i}(s)

are also d-Ramanujan. Fixing an i and setting f_{i}(k) = p(k)(d − 1)^{k} + r(k) as the decomposition of f_{i} into principal and error terms, we see

f̃_{i}(k) = p(k)(d − 1)^{k} + r̃(k),

where

|r̃(k)| ≤ | ∑_{s≤k/2} p(s)(d − 1)^{s}| + ∑_{s≤k} cs^{c}(d − 1)^{s/2}

for some c as in Definition 2.1. It is clear that the right-hand-side above is bounded by (d − 1)^{k/2} times a polynomial in k.

□

5.3 Forms, Types, and New Types

In this subsection we will classify potential walks, (w; t⃗), or more generally potential walk classes, according to some characteristics of the subgraph that the walk traces out.

Definition 5.13 A form, Γ, is an oriented, Π-labelled graph, G_{Γ} = (V_{Γ}, E_{Γ}), with edges and vertices numbered. A specialization of a form, Γ, is an injection ι: V_{Γ} → {1, …, n}.

With each potential walk, (w; t⃗), we can associate a form, Γ = Γ(w; t⃗), with a specialization, ι, as follows. (The form, Γ, is not unique, but is unique up to unique isomorphism, as described below; the specialization is unique given the form.)

1. Set V_{Γ} = {v_{1}, …, v_{r}} to be any numbered (v_{i} numbered i) set of size r, where r = |V_{Γ}| is the number of distinct elements among the t_{i} (where t⃗ = (t_{0}, …, t_{k}))

2. ι(v_{i}) is the i-th distinct element of the sequence t_{0}, t_{1}, …, t_{k},

3. Set E_{Γ} = {e_{1}, …, e_{m}} to be any numbered set of size m (e_{i} numbered i), where m = |E_{Γ}| is the number of distinct triples {(σ_{i}, t_{i−1}, t_{i})}_{i=1,2,...,k}, where we identify a triple (σ, s, t,) with (σ^{−1}, t, s),

4. if (σ_{j}, t_{j−1}, t_{j}) is the r-th distinct tuple in {(σ_{i}, t_{i−1}, t_{i})}_{i=1,2,...,k} (with the previous identification), then s(e_{r}) = (σ_{j}, ι^{−1}(t_{j−1}), ι^{−1}(t_{j})) defines the structural map (see Definition 3.1) of G_{Γ}.

(see the example in Figure 2 explained at the beginning of this section).

In other words, the form is the subgraph traced out by (w, t⃗), with some additional information (we remember the order in which the vertices and edges are visited, and the direction each edge is first traversed). We say that forms Γ_{1} and Γ_{2} are isomorphic if they are isomorphic as oriented, numbered, Π-labelled graphs. Because of the numbering, there is at most one isomorphism between any two forms (or a form and itself). We say that (w, t⃗) is of form Γ or associated to Γ, written (w, t⃗) ∈ Γ, if one (or any) of the forms associated to (w, t⃗) is isomorphic to Γ. Given (w, t⃗), there is always an associated form, Γ, with V_{Γ} = {t_{0}, …, t_{k}} and associated specialization, ι, being the identity; however, we usually view V_{Γ} as any numbered set of the right size, since all of our random graph models are symmetric.

If (w, t⃗) ∈ Γ, then define

E [Γ]_{n} = E_{symm}(w, t⃗)_{n}

which depends only on Γ, and not on the particular (w, t⃗) to which Γ is associated; indeed,

E [Γ]_{n} = \frac{n!}{(n − v)!} ∏_{i=1}^{d/2} \frac{(n − a_{i})!}{n!},  (23)

where v = |V_{Γ}|, and a_{i}is the number of edges in Γ labelled with π_{i} and π_{i}^{−1} (this is exactly the a_{i}(w) of equation (16) of any word, w, associated to Γ).

Hence, if W is symmetric and size invariant, we may write

WalkSum(W, k, n) = ∑_{Γ} W_{Γ}(W, k)E [Γ]_{n} ,  (24)

where W_{Γ}(W, k)is the number of potential walk classes in W(k) associated to Γ, and we sum over one Γ in each isomophism class of forms.

Definition 5.14 A legal walk in a form, Γ, is a walk starting in v_{1} that visits all the vertices of G_{Γ} in order (of their numbering), all the edges in order, and any edge is first traversed in the direction of its orientation. Each legal walk of length k generates a walk class in the natural way.

The following easy proposition is worth stating formally; it follows from the definitions.

Proposition 5.15 W_{Γ}(W, k) is the number of legal walks on Γ of length k.

Definition 5.16 The order of a form, Γ, is ord(Γ) = |E_{Γ}| − |V_{Γ}|, subject to the Definition 4.6 convention that any self-loop, whole-loop or half-loop, counts as a single edge. (The order of a form equals the order of any potential walk to which it is associated.)

The “form” allows us to group together potential walks that determine the same information on the graph; this can facilitate the task of studying a walk sum. A futher tool is the grouping of forms together by their “type,” which we now briefly motivate in rough terms to be made precise. A type arises from a form with all its maximal beaded paths collapsed to edges (by the appropriate supression). Each collapsed edge inherits an edge length and Π^{+} labelling from the “form,” but in the type we forget this data. As long as we collect forms of a given type by the first and last letters of all the collapsed edge labellings, we can apply Lemma 5.10 at each collapsed edge to study sums of the expansion polynomials in the a_{i}’s (and v) over forms in such collections.

Before defining a “type,” we recall that for a form, Γ = Γ(w; t⃗), with specialization, ι, the potential walk (w; t⃗) pulls back under ι^{−1} to a walk on G_{Γ}; we remark that the vertex and edge numberings of Γ serve to remember in which order the vertices and edges were traversed in the walk.

Definition 5.17 A type, T, is a connected, oriented graph G_{T} = (V_{T} , E_{T}), with vertex and edge numberings such that all vertices except possibly the first one are of degree at least 3. A labelling of a type means a Π^{+}-labelling (recall Π^{+} is the set of words over Π of length at least 1).

To each form, Γ, we associate a type, T = T (Γ), as follows. Let W be the set of beads of G_{Γ} numbered greater than 1. We claim W cannot contain a cycle, for then this cycle would be disconnected from the vertex numbered 1. So we may form the supression of W in G_{Γ}. This supression inherits a vertex and edge numbering from G_{Γ} (ordering a vertex before another in the supression if it is numbered less in G_{Γ}, and ordering edges in the supression by any associated edge in E_{Γ}). Of course, the Π-labelling of Γ gives rise to a Π^{+}-labelling of G_{T (Γ)}.

In other words, the beads of a form are “less important” features, and the type is just the form with these “less important” features supressed.

A Π^{+}-labelled type uniquely determines a form, and vice versa. We wish to group together forms corresponding to one type (inducing different Π^{+}- labellings), the prototypical example being STSL’s or SL’s discussed earlier in this section. To do this it will be helpful to remember a small part of the labelling, namely the starting and ending letter of each Π^{+}-label.

Definition 5.18 A lettering of a type, T, is the assignment to each directed edge a starting letter in Π and an ending letter in Π (such that opposite directed edges are lettered with the starting letter of one being the inverse of the ending letter of the other). Given a form, Γ, with T = T (Γ), or equivalently a Π^{+}-labelling of T, the associated lettering assigns to each edge the starting and ending letter of the Π^{+}-label assigned to it in its orientation.

It turns out that the notion of a type is too coarse to attack the Alon conjecture (but sufficient for the results of [Fri91]). The problem is that some types, when their edges take on certain Π^{+}-labellings, contain supercritical tangles. When such tangles occur (which they can when their order is roughly O(\sqrt{d})), we must distinguish where there tangles occur. This is what a “new type” does, where the type edges are partitioned into “long” and “fixed” (in length) edges, and where supercritical tangles lie on type edges that are “fixed.” We then modify our walk sums to be “selective” (see Section 6), a notion which requires us to know where these tangles occur in the type.

Definition 5.19 A B-new type is a collection, T̃ = (T; E_{long}, E_{fixed}; k⃗^{fixed}), of (1) a lettered type, T, (2) a partition of E_{T} into two sets, E_{long}, E_{fixed},

(3) for each e_{i} ∈ E_{fixed} an edge length, k_{i}^{fixed}, with 0 < k_{i}^{fixed} < B, and (4) a Π^{+}-labelling of E_{fixed} with each e_{i} ∈ E_{fixed} labelled with a word of length k_{i}^{fixed}. A Π^{+}-labelling of T (or, equivalently, a form, Γ), is said to be of B-new type T̃ if each E_{long} label is of length at least B, and each label corresponding to e_{i} ∈ E_{fixed} is of length k_{i}^{fixed} and agrees with the label specified by T̃. T̃ is said to be based on T.

Theorem 5.20 For each r > 0 there are finitely many types (up to isomorphism) of order at most r. For each type, T, and each B > 0 there are finitely many B-new types based on T.

Proof The first statement is just Lemma 2.3 of [Fri91], except that “coincidence” is used instead of “order” (and the coincidence is the order plus one). The second statement is clear since there are finitely many (1) letterings, (2) partitions of E_{T}, (3) choices of k_{i}^{fixed} with e_{i} ∈ E_{fixed}, and (4) labellings of each E_{fixed} edge, e_{i}, with a length k_{i}^{fixed} < B.

□

5.4 Motivation of Types and New Types

So far we have defined walk sums; we have seen that symmetric, size invariant walk sums can be organized into forms, by equation (24); we have seen that forms can be grouped by type and new type. In this section we briefly explain how and why we use types and new types.

Fix a symmetric, size invariant walk collection, W. Organizing forms by type, we may write equation (24) as

WalkSum(W, k, n) = ∑_{T} ∑_{Γ∈T} W_{Γ}(W, k)E [Γ]_{n} ,

where Γ ∈ T means the form Γ is of type T, and the summation in T ranges over all types. Typically we need only sum over T of at most some order, so the sum in T will effectively be a finite sum.

So fix a T and define E [T]_{n,k} to mean

E [T]_{n,k} = ∑_{Γ∈T} W_{Γ}(W, k)E [Γ]_{n} .

Let T ’s edges be E_{T} = {e_{1}, …, e_{b}}. For a vector, k⃗ = (k_{1}, …, k_{b}), let T (k⃗ ) denote the set of forms, Γ, of type T, such that for all i the length of the beaded path in Γ corresponding to the edge e_{i} in T has length k_{i}. For each e_{i} ∈ E_{T} fix an integer m_{i} ≥ 1. Let W_{Γ}(m⃗) = W_{Γ}(m_{1}, …, m_{b}) denote the number of legal W walks in Γ that traverse edge e_{i} exactly m_{i} times. Clearly

W_{Γ}(m⃗) = W_{T} (m⃗),

i.e., W_{Γ}(m⃗) depends only on m⃗ and the type, T, of Γ. This allows us to write

E [T]_{n,k} = ∑_{m⃗} W_{T} (m⃗) ∑_{k⃗·m⃗=k} ∑_{Γ∈T (k⃗ )} E [Γ]_{n} .

Since each E [Γ]_{n} has a 1/n expansion, by adding expansions we get an asymptotic expansion

∑_{Γ∈T (k⃗ )} E [Γ]_{n} = n^{−ord(T)}(q_{0}(k⃗ ) + q_{1}(k⃗ )/n + ⋯),

where we ignore error terms in this subsection; of course,

q_{i}(k⃗ ) = ∑_{Γ∈T (k⃗ )} p_{i}(a_{1}(Γ), …, a_{d/2}(Γ)).

Perhaps the main technical point of Section 8 (see Theorem 8.5 here, and Lemma 2.14 in [Fri91]) is that the P_{m⃗ ,i} defined by

P_{m⃗ ,i}(k) = ∑_{k⃗·m⃗=k} q_{i}(k⃗ )

are d-Ramanujan, and roughly speaking P_{m⃗ ,i}’s principal part and error term decay at most like (d−1)^{m/2} where m = m_{1}+⋯+m_{k} (actually, the principal part is shown in Lemma 2.14 in [Fri91] to decay at most like (d − 1)^{−m}). The way this is done is very roughly as follows. First, we fix a lettering of T and apply Lemma 5.10 to each edge, e_{i}, of T, whose length is set to k_{i}. This shows that the q_{i}(k⃗ ) is a sum of d-Ramanujan functions whose arguments are all sums of a subset of the k_{i}. As an example, consider a function, g(k_{1} + ⋯ + k_{b}) with g being d-Ramanujan. The maximum value of k_{1} + ⋯ + k_{b}, given k⃗ · m⃗ = k with fixed m⃗ and k, is k − m + b, which is achieved when and only when k_{i} = 1 whenever m_{i} ≥ 2 (assuming at least one m_{i} = 1; otherwise g(k_{1} + ⋯ + k_{b}) is bounded by ck^{c}(d − 1)^{k/2} since k_{1} + ⋯ + k_{b} ≤ k/2). This k − m + b is where the decay exponential in m comes from (see Section 8 and/or Section 2 in [Fri91] for details).

It follows that there is an asymptotic expansion

E [T]_{n,k} = n^{−ord(T)}(Q_{0}(k) + Q_{1}(k)/n + ⋯),

where

Q_{i}(k) = ∑_{m⃗} W_{T} (m⃗)P_{m⃗ ,i}(k).  (25)

Since the error term of the P_{m⃗ ,i} decay like (d − 1)^{−m/2} (roughly speaking), the above sum for Q_{i}(k) turns out to be d-Ramanujan provided that

|W_{T} (m⃗)| ≤ c(d − 1 − ϵ)^{m/2}  (26)

for some ϵ > 0.

If all Q_{i} were d-Ramanujan for all T, then we’d have a fairly simple proof of the Alon conjecture. The results of [Fri91] are based on the fact that equation (26) for all types up to a certain order (of roughly O(\sqrt{d})); past order O(\sqrt{d}), equation (26) generally fails to hold. Furthermore, by Theorem 2.12 we see for certain that at least one Q_{i} fails to be d-Ramanujan for an i bounded by O(log d\sqrt{d}).

The new approach in this paper is as follows. Consider a constant positive integer B, and consider

Q_{i}(k) = ∑_{m⃗} W_{T} (m⃗) ∑_{k⃗·m⃗=k} q_{i}(k⃗ ).

We can divide this sum by fixing some of the k_{i}’s at fixed values less than B (call these k_{t+1}, …, k_{b}), and then summing over the remaining k_{i}’s (namely k_{1}, …, k_{t}) subject to the remaining k_{i}’s being at least B (or “long”). This is where a “new type” comes from. Next we fix a constant S < B and define a “selective trace” to be the sum of irreducible closed walks of a given length that have no subpath of length S tracing out a graph of λ_{Irred} at least \sqrt{d − 1}. If

M_{1} = m_{1} + … + m_{t}, M_{2} = m_{t+1} + … + m_{b},

then the corresponding “selective” version of W_{T} (m⃗) (that depends on the new type, i.e., on knowing the particular k_{i} that are fixed and their values) is bounded by roughly (d − 1 − ϵ)^{(BM_{1}+M_{2})/2} (for appropriately large S and B). But consider the P_{m⃗ ,i} for the “new type,” i.e., the sum

∑_{\begin{matrix}k⃗·m⃗=k \\ k_{1},...,k_{t}≥B \end{matrix}} q_{i}(k⃗ )

with k_{t+1}, …, k_{b} at their fixed values; it turns out they decay like (d − 1)^{−(BM_{1}+M_{2})/2}. Thus, after summing over all new types, the corresponding selective analogues of the Q_{i}(k) are d-Ramanujan.

Unfortunately, a selective trace does not generally equal the original trace unless the graph in question is free of certain tangles. Still, in Sections 9 and later we show how the asymptotic expansions with d-Ramanujan coefficients of selective traces can be used to control a random graph’s eigenvalues.

6 The Selective Trace

In this section we define a selective trace, and discuss some of its properties.

6.1 The General Selective Trace

Fix a graph, G = (V, E), coming from G_{n,d}, so that V = {1, …, n} and G is Π-labelled.

By a path^{17} of length k in G we shall mean a vertex, v ∈ V, and a word of length k, w = σ_{1} … σ_{k}, over Π (i.e., with each σ_{i} ∈ Π). Such a path determines a subgraph in G of those vertices and edges traversed. We say a path traverses a tangle, ψ, if the subgraph traversed by the path contains the tangle, ψ.

17By a path one often means a sequence of vertices. In case there are multiple edges in the graph, one needs to note also which edge is traversed. Finally, in the case of wholeloops in an undirected graph, one needs to remember in which “direction” each whole-loop is being traversed. In the present situation, all the above information is contained simply in the initial vertex and the permutations, π_{i} or π_{i}^{−1}, being taken on each step of the path.

Definition 6.1 Let Ψ = {ψ_{1}, …} be a (finite or infinite) collection of tangles. For positive integer, S, the set of (S, Ψ)-selective closed walks (respectively, walks) are those irreducible closed walks (respectively, walks) that have no subpath of length at most S that traverses a tangle in Ψ. The kth irreducible (S, Ψ)-selective trace of G, IrSelTr_{S,Ψ}(G; k), is the number of (S, Ψ)-selective closed walks of length k.

Intuitively, the selective trace modifies the standard irreducible trace on those graphs that have a tangle in Ψ, and avoids those closed walks that in some short part trace out such a tangle.

6.2 A Lemma on Selective Walks

What is the point of the selective trace? We can answer this question in two ways. First, since hypercritical tangles give large eigenvalues, any trace with an arbitrarily long asymptotic expansion in 1/n with d-Ramanujan coefficients must avoid hypercritical tangles (according to Theorems 3.13 and 4.2); a trace must be selective or its asymptotic expansion coefficients will not all be d-Ramanujan. Second, there is a crucial technical theorem, Theorem 6.6, about counting irreducible contributions to a selective trace. This lemma makes certain infinite sums converge for the selective trace that would have to diverge for the standard trace— for example, the infinite sum involving W (T; m⃗) and P_{i,T,m⃗} just above the middle of page 351 in [Fri91], for types of order > d; for the same reason, this crucial theorem makes the 1/n expansion for a selective trace have d-Ramanujan coefficients when they don’t for a trace that is not selective— indeed, the (2d − 1)^{k/2} bound in equation (24) of [Fri91] depends critically on 2i+2 ≤ \sqrt{2d − 1}, and this equation corresponds to the error in the n^{−i} term in the expansion of the expected value of the irreducible trace (recall that 2d in [Fri91] corresponds to our d). We shall finish this subsection with the crucial technical theorem, Theorem 6.6, after setting up the necessary terminology.

A relabelling of a tangle, ψ, is a tangle, ψ′, that differs from ψ only in its edge labels.

Definition 6.2 A set, Ψ, of tangles is called closed under pruning (respectively, relabelling) if ψ ∈ Ψ implies ψ′ ∈ Ψ for any pruning (respectively, relabelling), ψ′, of ψ.

Note: In the definition above, ψ and ψ′ must be G_{n,d}-tangles (or tangles in whatever model is discussed)— a vertex with two self-loops labelled both labelled π_{1} is not a G_{n,d}-tangle and is therefore not considered a relabelling of the tangle where the self-loops are labelled π_{1} and π_{2}.

Definition 6.3 For a positive integer, τ, let Ψ_{ord}(τ) be the set of tangles whose order is at least τ. For positive integers τ_{1} ≤ τ_{2}, let Ψ_{ord}(τ_{1}, τ_{2}) be the set of all tangles whose order is at least τ_{1} and at most τ_{2}. We also write Ψ_{ord}(τ, ∞) for Ψ_{ord}(τ).

Since pruning a tangle does not affect its order, Ψ_{ord}(τ_{1}, τ_{2}) is closed under pruning; clearly Ψ_{ord}(τ_{1}, τ_{2}) is closed under relabelling.

Consider a form, Γ, of type T, in which T ’s edges, e_{i}, have length k_{i} (as beaded paths arising from Γ). For each e_{i} ∈ E_{T} fix an integer m_{i} ≥ 1. Let Ψ be a set of tangles closed under relabelling. Let W_{Γ}(m⃗; S, Ψ) be the number of legal closed walks (in particular, beginning at the first vertex) in Γ that traverse each e_{i} exactly m_{i} times (in either direction) and that are (S, Ψ)-selective. Since Ψ is closed under relabelling, W_{Γ} depends only on the length, k_{i}, of e_{i} in Γ, not on the particular Π^{+} labels of length k_{i}. So we may write

W_{Γ}(m⃗; S, Ψ) = W_{T} (m⃗, k⃗; S, Ψ).

Now given the above setting, call an edge, e_{i}, of T long if k_{i} > S, and short otherwise. If a walk contains some ψ ∈ Ψ in any consecutive S steps, then by possibly pruning these consecutive steps along long edges at the beginning and end, we get a consecutive walk over short edges that contains a pruning of ψ. In particular, if B > S and T̃ = (T; E_{long}, E_{fixed}; k⃗^{fixed}) is a B-new type based on T, then W_{T} depends on only T̃, m⃗, S, and Ψ provided that k_{i} = k_{i}^{fixed}; hence we may write

W_{T} (m⃗, k⃗; S, Ψ) = WT̃(m⃗; S, Ψ).

Definition 6.4 We say that a collection of tangles, Ψ, is r-supercritical if it contains all supercritical tangles of order at most r.

Next we give two examples of very natural r-supercritical tangle sets.

Definition 6.5 Let τ_{fund} be the smallest order of a supercritical tangle, and let Ψ_{fund} = Ψ_{ord}(τ_{fund}). Let Ψ_{eig} the be set of all supercritical tangles.

Ψ_{fund} and Ψ_{eig} are clearly r-supercritical for any r; Ψ_{ord}(τ_{fund}, r) and Ψ_{eig}[r] = Ψ_{eig} ∩ Ψ_{ord}(τ_{fund}, r) are also clearly r-supercritical. We arrive at our crucial technical theorem, that is the key to the selective trace.

Theorem 6.6 Let T by any type, with specified edge set partition E_{long},E_{fixed}, and a Π-lettering specified. Let the edges be indexed so that

E_{long} = {e_{1}, …, e_{t}}, E_{fixed} = {e_{t+1}, …, e_{b}}.

Then there is a c, an ϵ > 0, and an S_{0} such that the following is true for all S ≥ S_{0}. Let Ψ be a set of tangles containing all supercritical tangles included in a form of type T; e.g., by Lemma 4.8 we may take Ψ to be any r-supercritical set for r = ord(T). Let

W_{T̃,S}(M_{1}, M_{2}) = ∑_{\begin{matrix}m_{1}+...+m_{t}=M_{1} \\ m_{t+1}+···+m_{b}=M_{2} \\ m_{i}≥1 \end{matrix}} WT̃(m⃗; S, Ψ),

for a B-new type, T̃, with B > S and with T̃ having edge set partition E_{long}, E_{fixed}. Then

W_{T̃,S}(M_{1}, M_{2}) ≤ c(\sqrt{d − 1} − ϵ)^{(S_{0}+1)M_{1}+M_{2}} ≤ c(\sqrt{d − 1} − ϵ)^{BM_{1}+M_{2}}.

Proof The general approach we take is based on the following crude estimate. Let {f_{i}(z)}_{i∈I} be a collection of non-negative power series, and let g(z) be a power series that majorizes each f_{i}(z). Suppose that g(z_{0}) converges for some z_{0} ∈ (0, 1). Then the z^{k} coefficient of any of the f_{i}(z)’s is bounded by g(z_{0})z_{0}^{−k}.

Specifically, we shall show that there is an S_{0} such that the following holds. Let B > S_{0}, and let T̃ be a B-new type subject to the conditions of the theorem. Let G be a VLG whose underlying graph is T, whose E_{fixed} edges take their lengths from T̃, and whose E_{long} edges all have length B. Let f(z) = ∑ c_{k}z^{k}, where c_{k} is the number of (S_{0}, Ψ)-selective irreducible walks of length k in G. We shall show that there is a z_{0} > (d − 1)^{−1/2} and a g = g(z) such that (1) g majorizes f, (2) g depends only on T, and (3) g(z_{0}) converges. In that case

W_{T̃,S}(M_{1}, M_{2}) ≤ g(z_{0})z_{0}^{−BM_{1}−M_{2}},

which completes the theorem.

Let G_{below} be the set of VLG’s, H, whose underlying graph is a subgraph of T containing only E_{fixed} edges, with the property that λ_{Irred}(H) < \sqrt{d − 1}. Let G_{extreme} be the set of elements of G_{below} that are not majorized by a different member of G_{below}. We claim that G_{extreme} is finite; indeed, if H_{1}, H_{2}, … were a distinct sequence of VLG’s in G_{extreme}, then by passing to a subsequence we could assume that for every e ∈ E_{fixed} either the length of e in H_{i} is constant or the length tends to infinity; but then H_{1} would majorize all H_{i} with i sufficiently large.

Let G_{extreme} = {H_{1}, …, H_{m}}, and let h_{i}(z) = ∑ c_{i,k}z^{k}, where c_{i,k} is the number of irreducible walks of length k in H_{i}. These c_{i,k} are given as the number of walks of length k − 1 in (H_{i})_{Irred}; it follows that h_{i}(z) has radius of convergence greater than (d − 1)^{−1/2}. Also, if c̃_{i,k} = c_{i,0} + ⋯ + c_{i,k} is the number of irreducible walks in H_{i} of length at most k, then

h̃_{i}(z) = ∑_{k} c̃_{i,k}z^{k} = \frac{1}{1 − z} h_{i}(z)

also has radius of convergence greater than (d − 1)^{−1/2}. Let z_{0} > (d − 1)^{−1/2} be a value at which all h̃_{i} converge.

For any S set

h̃_{i}^{S}(z) = ∑_{k>S} c̃_{i,k}z^{k},

and set

h̃^{S}(z) = ∑_{i=1}^{m} h̃_{i}^{S}(z) and h(z) = ∑_{i=1}^{m} h_{i}(z).

Consider an S_{0} sufficiently large so that h̃^{S_{0}}(z_{0}) < 1/d (later we impose other lower bounds on S_{0}’s value).

Let B > S_{0}. Let G be a VLG whose underlying graph is (the graph underlying) T, and whose E_{long} edges have length at least B. Let d_{k} (respectively, d̂_{k}) be the number of irreducible walks in G of length k that are (S_{0}, Ψ)- selective (respectively, and never traverse an E_{long} edge). Let f(z), f̂(z) be the generating functions of d_{k}, d̂_{k}, respectively.

The functions f(z), f̂(z) are clearly majorized by the f(z), f̂(z) in the case where B = S_{0} + 1 and all E_{long} edges have length S_{0} + 1. We shall assume this to be the case.

First, we claim that f is majorized by

(1 − f̂(z)dz^{S_{0}+1})^{−1}f̂(z).

This is because any walk in G can be broken into alternating subwalks that remain in E_{fixed} and steps along E_{long} edges; each time an E_{long} edge is taken its length is at least S_{0} + 1, and there are at most d such E_{long} edges from which to choose after finishing the E_{fixed} walk^{18}. To prove the theorem it therefore suffices to show that f̂(z_{0})dz_{0}^{S_{0}+1} is less than one for sufficiently large S_{0}.

Next, we claim that f̂(z) is majorized by

(1 − dh̃^{S_{0}}(z))^{−1}h(z).

Assuming this, it is clear that for sufficently large S_{0} we have f̂(z_{0})dz_{0}^{S_{0}+1} < 1 and the theorem is proven. For k ≥ S_{0}, let b_{k} be the number of (S_{0}, Ψ)- selective irreducible walks, w = (v_{0}, e_{1}, v_{1}, …, e_{j}, v_{j}), in G of length k through only E_{fixed} edges such that w′ = (v_{0}, e_{1}, v_{1}, …, e_{j−1}, v_{j−1}) is of length less than S_{0}. The walk w′ is contained in a subgraph of G that is majorized by one of the H_{i}. Clearly

b_{S_{0}} ≤ ∑_{i=1}^{m} c_{i,S_{0}}.

When k > S_{0}, then from v_{j−1} the walk has at most d possible directions to take (or at most d − 1 possible directions if j > 1), and so

b_{k} ≤ ∑_{i=1}^{m} c̃_{i,k}.

Thus ∑ b_{k}z^{k} is majorized by dh̃^{S_{0}}(z). But any walk over E_{fixed} edges can be broken into a series of walks of the form w as above, plus a final walk of length less than S_{0}. The generating function for such walks is clearly majorized by h(z).

□

18Of course, there are at most d − 1 such E_{long} edges from which to choose except possibly at the very first step of a walk.

6.3 Determining τ_{fund} for G_{n,d}

In order to use the selective trace, we must determine τ_{fund}. We begin by doing so for the model G_{n,d}; next subsection we use similar techniques for the models H_{n,d}, I_{n,d}, and J_{n,d}.

More generally, for a given τ, consider the task of finding the tangle, ψ, in G_{n,d}, of order at most τ with λ_{Irred}(ψ) as large as possible. To simplify this task, notice that pruning leaves the order and λ_{Irred} invariant (an irreducible closed walk can never visit a leaf, so pruning a leaf doesn’t affect the number of irreducible closed walks); hence we may restrict our search to those ψ’s that are completely pruned.

Lemma 6.7 Let G be a graph with edge e = {u, v} with u ≠ v. Let G_{e} be the contraction of G along e, i.e. the graph obtained by discarding e and identifying u with v. Then λ_{Irred}(G) ≤ λ_{Irred}(G_{e}).

Proof Consider an irreducible closed walk, c, about u in G. Then we can associate to this closed walk one in G_{e}, ι(c), by discarding all occurrences of e. This association, ι, is an injection, since given a G_{e} irreducible closed walk about u of the form ι(c), we can infer when e was taken (since e = {u, v} with u ≠ v) in the G closed walk, giving rise to (at most) a single G closed walk. Since this injection does not increase the length of the closed walks, we conclude that the number of irreducible closed walks about u in G of length ≤ k is no more than the number in G_{e}. Hence the conclusion of the lemma.

□

Since edge contraction reduces the number of vertices and of edges by one each, edge contraction leaves the order invariant. So in looking for a λ_{Irred} tangle of a given order, we may always assume the tangle has no edge contraction that leaves it a tangle^{19}.

We now claim (by Lemma 6.7) that for G_{n,d} and τ ≤ (d/2) − 1, a vertex with τ + 1 whole-loops has the largest λ_{Irred} of all tangles of order τ (recall that each self-loop is counted as one edge, according to Definition 4.6). For this graph we clearly have λ_{Irred} = 2τ + 1; hence τ_{fund} is the smallest integer τ with 2τ + 1 ≥ \sqrt{d − 1}, provided that this τ is ≤ (d/2) − 1. But we easily verify that this τ,

19In H_{n,d}, two vertices joined by between 2 and d/2 edges is a tangle (with apropriate Π-labelling), but contracting any edge gives self-loops, which are not feasible in H_{n,d}.

Therefore edge contraction can take graphs that can be tangles to graphs that cannot, at least for certain random graph models.

τ_{fund} = ⌈(\sqrt{d − 1} + 1)/2⌉ − 1 = ⌈(\sqrt{d − 1} − 1)/2⌉

is indeed at most (d/2) − 1 for all d ≥ 4. We have just established the following theorem.

Theorem 6.8 For the model G_{n,d}, we have τ_{fund} = ⌈(\sqrt{d − 1} + 1)/2⌉ − 1.

6.4 Determining τ_{fund} for H_{n,d}, I_{n,d}, and J_{n,d}

For H_{n,d} we have to remember that tangles can’t have self-loops. Thus contractions can only be done along non-multiple edges, and τ_{fund} will not generally be the same for H_{n,d} and G_{n,d}.

Lemma 6.9 Let u, v be vertices of distance two in a graph, G, i.e., there are no edges joining u and v, but there is a w with edges to each of u, v. Let G′ be the graph obtained by identifying u and v and deleting one of the edges from w to u (or to v) (so that the order of G′ is the same as that of G). Then λ_{Irred}(G) ≤ λ_{Irred}(G′).

Proof Let U be the vertex in G′ which is the identification of v and u. Let the edges from u to w be enumerated e_{1}, …, e_{s}, and those from v to w enumerated f_{1}, …, f_{t}. The edges from U to w are g_{1}, …, g_{r}, where r = s + t − 1.

First consider the case when V_{G} = {u, v, w}, and consider the irreducible closed walks about w (which are necessary of even length). Such a closed walk begins in w and takes two steps, visiting either u or v, in, respectively, s(s − 1) or t(t − 1) ways. After coming back from a u vertex, another step of length 2 can either (1) visit a u vertex, in (s − 1)^{2} ways, or (2) visit a v vertex, in t(t − 1) ways; similarly for coming back from a v vertex. Thus “coming back from a u vertex” and “coming back from a v vertex” forms a Markov chain, and the total number of irreducible closed walks of length k about w is

I_{1}(k) = [ s(s − 1) t(t − 1) ] [ \begin{matrix}(s − 1)^{2} & t(t − 1) \\ s(s − 1) & (t − 1)^{2} \end{matrix} ]^{(k−2)/2} [ \begin{matrix}1 \\ 1 \end{matrix} ] (27)

We wish to compare this to the number of irreducible G′ closed walks about w, of which there are clearly

I_{2}(k) = r(r − 1)^{k−1} = (s + t − 1)(s + t − 2)^{k−1}.

For starters, we see

I_{2}(2) − I_{1}(2) = 2(s − 1)(t − 1)

which is non-negative, since both s, t ≥ 1. Now since the maximum row sum in the 2 × 2 matrix of equation (27) is

s^{2} + t^{2} − 2(s + t) + 1 + max(s, t),

we have

I_{1}(k + 2) ≤ I_{1}(k)m_{1}, where m_{1} = s^{2} + t^{2} − 2(s + t) + 1 + max(s, t)

for all k. But

I_{2}(k + 2) = I_{2}(k)m_{2}, where m_{2} = (s + t − 2)^{2},

and

m_{2} − m_{1} = 2st − 2(s + t) + 3 − max(s, t) = 1 + 2(s − 1)(t − 1) − max(s, t),

which is positive unless s or t is 1. Thus, provided that s ≥ 2 and t ≥ 2, we have

λ_{Irred}(G) ≤ \sqrt{m_{1}} < \sqrt{m_{2}} = λ_{Irred}(G′),

and

I_{1}(k) ≤ I_{1}(2)m_{1}^{(k−2)/2} < I_{2}(2)m_{2}^{(k−2)/2}I_{2}(k) = I_{2}(k)  (28)

for all even k. If t = 1 we calculate

I_{1}(k) = s(s − 1)^{k−1} = I_{2}(k),  (29)

and similarly when s = 1.

We shall use the above calculation below. We can now assume that V_{G} has a vertex, x, different from u, v, w.

There is a natural bijection of edges, ι from E_{G}\({e_{i}}∪{f_{i}}) to E_{G′} \{g_{i}}. Extend ι to a map on all of E_{G} by defining ι(e_{i}) and ι(f_{i}) to be a formal symbol S. For any irreducible G closed walk about x specified by its edges, c = (c_{1}, …, c_{k}) with c_{i} ∈ E_{G}, we associate a sequence

ι(c) = (ι(c_{1}), …, ι(c_{ℓ})).

We claim that the number of c with a given image ι(c) is no more than the number of E_{G′} closed walks corresponding to ι(c) by changing all g_{i} edges into S’s. Indeed, consider a block of consecutive S’s in ι(c), i.e. ι(c_{a}) = ι(c_{a+1}) = ⋯ = ι(c_{b}) = S, and ι(c_{a−1}) ≠ S and ι(c_{b+1}) ≠ S; ι(c) cannot begin or end with an S, since the closed walk begins at x, and so we can assume a ≥ 2 and b ≤ ℓ − 1. By looking at ι(c_{a−1}) and ι(c_{b+1}) we can determine whether or not the S-block begins in u, v, or w, and ends in u, v, or w. If the S-block begins in w and ends in w, then equations (28) and (29) show that there are no fewer G′ sequences for the corresponding S-block than G sequences. Next compare those S-blocks that begin in a u and end in a w. The number of such sequences in G is

[ s 0 ] [ \begin{matrix}(s − 1)^{2} & t(t − 1) \\ s(s − 1) & (t − 1)^{2} \end{matrix} ]^{(b−a)/2} [ \begin{matrix}1 \\ 1 \end{matrix} ] ,

whereas the number in G′ is (s + t − 1)(s + t − 2)^{b−a} (since the non-S edge ι(c_{a−1}) can be followed by any U to w edge in G′); so the G′ number is no less than the G number for b − a = 0 (since t ≥ 1), and each time b − a is increased by 2, the former number gets multiplied by an m_{2}, the latter gets multiplied by no more than m_{1}, where m_{1} < m_{2}, provided that s ≥ 2 and t ≥ 2; the s = 1 or t = 1 case is easily checked to result in equality. The same arguement holds for v to w S-blocks. For an S-block starting and ending in u, we wish to compare

[ s 0 ] [ \begin{matrix}(s − 1)^{2} & t(t − 1) \\ s(s − 1) & (t − 1)^{2} \end{matrix} ]^{(b−a−1)/2} [ \begin{matrix}s − 1 \\ 0 \end{matrix} ] ,

with (s + t − 1)(s + t − 2)^{b−a}. Again, it suffices to compare when b − a = 1, which is immediate, and to check s = 1 or t = 1 separately. We argue for S-blocks starting in either u or v and ending in either u or v similarly.

□

Theorem 6.10 For the model H_{n,d}, we have τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1.

Proof As before, we consider a τ and search for those ψ of order at most τ with λ_{Irred}(ψ) as large as possible. By Lemma 6.9, and by contractions (in Lemma 6.7), we may restrict our search to those ψ with two or more edges between every pair of nodes.

First assume that τ + 2 ≤ d/2. If ψ has two vertices, then ψ has τ + 2 edges joining the two vertices (since there are no self-loops in H_{n,d}). In this case λ_{Irred}(ψ) = τ + 1. We claim that this is as large a λ_{Irred} as possible (again, assuming τ + 2 ≤ d/2). Indeed, if ψ has r > 2 vertices, then the maximum degree of a vertex is |E| minus the edges not involved with that particular vertex, which is at least 2 for each pair of the r − 1 other vertices. So the maximum degree is at most

|E| − \binom{r − 1}{2}2 ≤ (|V | + τ) − \binom{r − 1}{2}2 = τ + r − (r − 1)(r − 2).

Since λ_{Irred} is no greater than the maximum degree minus 1, we have

λ_{Irred} ≤ τ + r − (r − 1)(r − 2) − 1 = τ + 1 − (r − 2)^{2}.

It follows that if r > 2, λ_{Irred} is strictly less than τ + 1.

To achieve λ_{Irred}(ψ) = τ + 1 with our ψ having two vertices, we required τ + 2 ≤ d/2. To get λ_{Irred}(ψ) = τ + 1 to equal or exceed \sqrt{d − 1}, we require τ + 1 = ⌈\sqrt{d − 1} ⌉, for which we must have

⌈\sqrt{d − 1} ⌉ + 1 ≤ d/2.

Since d/2 is an integer, this is equivalent to

\sqrt{d − 1} + 1 ≤ d/2,

which we easily see holds for all even d > 2 except d = 4, 6.

We conclude that τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1 for even d ≥ 8. It suffices to analyze the cases d = 4, 6.

For each order, τ, and d = 4, 6, we must examine those tangles of order τ and determine the largest possible λ_{Irred}(ψ). Let us note that if ψ is a tangle of order −1, then it is a tree and has λ_{Irred}(ψ) = 0. If ψ is a completely pruned tangle of order 0, then ψ is a closed walk and has λ_{Irred}(ψ) = 1.

If d = 4, then consider the tangle of order 1 with three vertices, consisting of one “middle” vertex joined by two edges to each of two vertices. (This is a tangle by labelling the left to middle edges and the middle to right edges π_{1}, π_{2}.) We easily compute λ_{Irred} = \sqrt{3}, as this graph is bipartite and the number of irreducible walks of length 2m from the middle vertex, all such walks being closed walks, is clearly 4 · 3^{m−1}. So for d = 4, τ_{fund} = 1.

For d = 6, consider the tangle, ψ = (V, E) with V = {v_{1}, v_{2}, v_{3}} with three edges connecting v_{1} to v_{2} (labelled π_{1}, π_{2}, π_{3}) and two edges connecting v_{2} to v_{3} (labelled π_{1}, π_{2}). We claim that λ_{Irred}(ψ) > \sqrt{5}. Say that a closed walk about v_{2} ends in “state A” if the last vertex before v_{2} was v_{1}, and otherwise in “state B” (i.e. the second to last vertex is v_{3}). From state A, taking two additional irreducible steps, there are 4 ways to reach another state A, and two ways to reach another state B. From state B, taking two irreducible steps, there is one way to reach another state B and six ways to reach another state A. It easy follows that λ_{Irred}(ψ) is the square root of the largest eigenvalue of

[ \begin{matrix}4 & 2 \\ 6 & 1 \end{matrix} ] .  (30)

But λ_{1} of this matrix is (5 + \sqrt{57})/2, and this λ_{1} is just λ_{Irred}(ψ). It follows that λ_{Irred}(ψ) > \sqrt{6} > \sqrt{5}, and hence τ_{fund} ≤ 2.

We wish to rule out τ_{fund} = 1 when d = 6. Since we are considering only completely pruned graphs, ψ, each vertex has degree ≥ 2. Such a graph, ψ, of order 1 has all vertices of degree 2 except for one of degree 4 or two of degree 3. In the case where there are vertices, u, v, of degree 3, therefore joined by three disjoint beaded paths, then λ_{Irred}(ψ) is greatest when the beaded paths are each of length 1 (by setting up an obvious map from irreducible closed walks about u from the general graph to the one with beaded paths of length 1); hence λ_{Irred}(ψ) ≤ 2 in this case, since the graph of two vertices joined by three edges has λ_{Irred} = 2. Similarly, in the case with u of degree 4, therefore having two beaded closed walks from u, λ_{Irred}(ψ) is greatest when the lengths of the two closed walks are two (they cannot be one since H_{n,d} does not permit self-loops); hence λ_{Irred}(ψ) ≤ \sqrt{3} in this case. Hence τ_{fund} > 1 and therefore τ_{fund} = 2.

We conclude that τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1 also when d = 4, 6.

□

Theorem 6.11 For the model I_{n,d}, we have τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1 for all d ≥ 3.

Proof We argue as with H_{n,d}. The only difference is that in I_{n,d}, two vertices can have as many as d edges between them in a tangle (as opposed to d/2 edges in an H_{n,d} tangle). So the argument in the previous thoerem shows that the two-vertex tangles give that τ = ⌈\sqrt{d − 1} ⌉−1 equals τ_{fund} provided that τ + 2 ≤ d (as opposed to τ + 2 ≤ d/2 for H_{n,d}). But we easily verify that

⌈\sqrt{d − 1} ⌉ + 1 ≤ d

for all d ≥ 3 (indeed, we have equality for d = 3, and each time we increase d ≥ 3 by one, \sqrt{d − 1} increases by less than one).

□

Theorem 6.12 For the model J_{n,d}, we have τ_{fund} = ⌈\sqrt{d − 1} ⌉ − 1 for all d ≥ 3.

Proof As in I_{n,d}, for any τ ≤ d − 2 there is a tangle G_{τ} that is a pair of vertices with τ +2 edges joining them. G_{τ} has order τ and λ_{Irred} = τ +1; since when τ + 2 = d we have λ_{Irred}(G_{τ}) = d − 1 ≥ \sqrt{d − 1} giving a supercritical tangle, we need worry only about whether or not there is a tangle of order τ ≤ d − 2 that can beat the λ_{Irred} of G_{τ}. Again, as with I_{n,d}, Lemma 6.9 can be applied to graphs with half-loops, and so by the same argument as for I_{n,d} we have that only graphs on one or two vertices can possibly beat G_{τ}. So consider a graph on vertices u, v with a half-loops about u, c half-loops about v, and b edges from u to v. An irreducible path traverses edges of four different states: (1) half-loops about u, (2) edges from u to v, (3) edges from v to u, and (4) half-loops about v. Now we write a transition matrix about the states: for example in state (1) we may either continue on one of a − 1 half-loops in state (1) or continue on one of b edges in state (2). We find the transition matrix

[ \begin{matrix}a − 1 & b & 0 & 0 \\ 0 & 0 & b − 1 & c \\ a & b − 1 & 0 & 0 \\ 0 & 0 & b & c − 1 \end{matrix} ] ,

and λ_{Irred} of our graph is this matrice’s largest eigenvalue. The order of the graph is a + b + c − 2 (recall, each half-loop contributes one to the order of a graph). But the row sum is never greater than a + b + c − 1 (and always less unless a or c vanishes), and so if this graph has order τ its λ_{Irred} is no more than τ + 1. Hence no J_{n,d} tangle of order τ beats G_{τ}, provided that τ ≤ d − 2. Thus τ_{fund} is the smallest number with τ_{fund} + 1 ≥ \sqrt{d − 1}.

□

7 Ramanujan Functions

In this section we discuss Ramanujan functions in order to (1) explain their significance, and (2) give some intuition on some very technical issues surrounding the asymptotic expansion for irreducible traces (as in Section 8).

Definition 7.1 A function, f(k), on positive integers, k, is said to be d-Ramanujan of order α > 0 if there is a polynomial p = p(k) and a constant c > 0 such that

|f(k) − (d − 1)^{k}p(k)| ≤ ck^{c}α^{k}

for all k. We call (d−1)^{k}p(k) the principal term of f, and f(k)−(d−1)^{k}p(k) the error term (both terms are uniquely determined if α < d − 1). A function is super-d-Ramanujan if it is d-Ramanujan of order 1.

A d-Ramanujan function as defined before, in Definition 2.1, is just a d-Ramanujan of order \sqrt{d − 1}.

Let N(k) be the number of irreducible cycles of length k in a d-regular graph. Then in [LPS86] it is shown that if N(k) is d-Ramanujan, then any eigenvalue, λ ≠ ±d, of the graph satisfies |λ| ≤ 2\sqrt{d − 1}. The discussion there also shows that in any case, if λ is the eigenvalue of largest absolute value < d, then N(k) is d-Ramanujan of order α with

α = \frac{|λ| + \sqrt{λ^{2} − 4(d − 1)}}{2}

(and not for any smaller an α). Any discussion of irreducible traces and eigenvalues is bound to be tied to d-Ramanujan functions.

One important property of d-Ramanujan functions of order α is that they are closed under addition. Another very important property is that they are closed under convolution, which we now formally explain. This property will be used in Section 14, and refined versions of it will be used in Section 8.

Theorem 7.2 Let f_{1}, f_{2} be d-Ramanujan of order α with α < d − 1. Then their convolution,

g(k) = (f_{1} ∗ f_{2})(k) = ∑_{j=1}^{k−1} f_{1}(j)f_{2}(k − j)

is also d-Ramanujan of order α.

The techniques in Section 8 prove a more precise version of this theorem (keeping track of the sizes of the the error term and the coefficients of the principal part); for this reason we keep the argument below concise. Proof For i = 1, 2 let

f_{i}(k) = (d − 1)^{k}p_{i}(k) + e_{i}(k)

where p_{i} are polynomials and the |e_{i}(k)| are bounded by ck^{c}α^{k} for some k. We may also write

f_{i}(k) = (d − 1)^{k}(p_{i}(k) + ẽ_{i}(k)), where ẽ_{i}(k) = (d − 1)^{−k}e_{i}(k).

Since convolution is bilinear, we easily see

f ∗ g = e_{1} ∗ e_{2} + (d − 1)^{k}(p_{1} ∗ p_{2} + p_{1} ∗ ẽ_{2} + p_{2} ∗ ẽ_{1}).

It suffices to show that

e_{1} ∗ e_{2}, (d − 1)^{k}(p_{1} ∗ p_{2})(k), (d − 1)^{k}(p_{1} ∗ ẽ_{2})(k), (d − 1)^{k}(p_{2} ∗ ẽ_{1})(k)

are d-Ramanujan of order α.

According to Sublemma 2.15 of [Fri91], p_{1} ∗ p_{2} is a polynomial. Next

(p_{1} ∗ ẽ_{2})(k) = ∑_{j=1}^{k−1}(d − 1)^{−j}p_{1}(k − j)e_{2}(j) = Σ_{1} − Σ_{2}

where

Σ_{1} = ∑_{j=1}^{∞} p_{1}(k − j)(d − 1)^{−j}e_{2}(j),

Σ_{2} = ∑_{j=k}^{∞} p_{1}(k − j)(d − 1)^{−j}e_{2}(j).

Writing

p_{1}(k − j) = ∑ a_{r,s}k^{r}j^{s},

we see that Σ_{1} is a polynomial, and Σ_{2} is bounded by ck^{c}α^{k}(d − 1)^{−k} (see Section 8, especially Lemma 8.8, for details). This shows (d − 1)^{k}(p_{1} ∗ ẽ_{2}) is d-Ramanujan of order α. Similarly, so is (d − 1)^{k}(p_{2} ∗ ẽ_{1}); e_{1} ∗ e_{2} is easily also seen to be so (with zero principal term).

□

8 An Expansion for Some Selective Traces

In this section we prove the first crucial expansion theorem. Our second such theorem, Theorem 9.3, will extend these ideas.

Theorem 8.1 Let r be a positive integer, and let Ψ be a set of tangles containing all supercritical tangles of order less than r. Then there is an S_{0} = S_{0}(r) such that for all S ≥ S_{0} the following holds. We have

E [IrSelTr_{S,Ψ}(G; k)] = f_{0}(k) + \frac{f_{1}(k)}{n} + ⋯ + \frac{f_{r−1}(k)}{n^{r−1}} + \frac{error}{n^{r}},

where the f_{i} are d-Ramanujan and the error term satisfies the bound given in Theorem 5.9.

We begin by explaining why this theorem is an easy consequence of Theorem 5.9 and the following theorem.

Theorem 8.2 Fix a lettering, L, of type T, and fixed non-negative integers ℓ_{1}, …, ℓ_{d/2}. Let

R_{T,L}(k_{1}, …, k_{b}) = ∑_{(w_{1},...,w_{b})} ∏_{j=1}^{d/2}(a_{j}(w_{1}) + … + a_{j}(w_{b}))^{ℓ_{j}}

where the sum is over all tuples of words (w_{1}, …, w_{b}) such that each w_{i} is irreducible and of length k_{i} and is compatible with L. Let T̃ be a B-new type based on T, and let

f(k) = ∑_{m_{i}≥1} ∑_{k_{1}m_{1}+...+k_{b}m_{b}=k k_{i}≥B if e_{i}∈E_{long} k_{i}=k_{i}^{fixed} if e_{i}∈E_{fixed}} WT̃(m⃗; S, Ψ)R_{T,L}(k_{1}, …, k_{b})  (31)

(with W as in Theorem 6.6). Then f is d-Ramanujan for all B ≥ B_{0} = B_{0}(T).

Assume Theorem 8.2 for the moment. Let W (respectively, W_{T} and WT̃) be the walk collections corresponding to irreducible, (S, Ψ)-selective walks (respectively, and that are associated to the type T and T̃). These walk collections are all SSIIC. According to Theorem 5.9

WalkSum(W, k, n) = f_{0}(k) + \frac{f_{1}(k)}{n} + ⋯ + \frac{f_{r−1}(k)}{n^{r−1}} + \frac{error}{n^{r}},

where

f_{i}(k) = ∑_{j=0}^{r−1} ∑_{(w;[t⃗]) order j,∈W(k)} p_{i−j}(a_{1}(w; [t⃗]), …, a_{d}(w; [t⃗])). (32)

It suffices to show that these f_{i} are d-Ramanujan. We know there are finitely many types of order at most r − 1. Now fix S_{0} to be the max over B_{0}(T) over types, T, of order at most r − 1 (and B_{0} as in Theorem 8.2). For any S ≥ S_{0}, choose B = S + 1; of course, B ≥ B_{0}(T) for any type, T, of order at most r − 1. We know there are finitely many B-new types based on any type. So the sum involving W in equation (32) decomposes as a finite sum over W_{T} ’s or WT̃’s. Furthermore, each expansion polynomial p_{i−j}, involving a fixed new type, T̃, is just a function of a_{1}, …, a_{d/2} over appropriate forms, and each a_{i} of the form is just the sum of the a_{i} along each edge of the form. Therefore Theorem 8.2 just says that each f_{i}, when summing over a WT̃, is d-Ramanujan. Summing over all WT̃ shows that the f_{i} corresponding to W are also d-Ramanujan. Proof (of Theorem 8.2) Clearly it suffices to prove the following theorem with R_{T,L} replaced by

∑_{(w_{1},...,w_{b})} ∏_{i=1}^{b} ∏_{j=1}^{d/2} a_{j}^{ℓ_{ij}}(w_{i}),

with ℓ_{ij} any set of non-negative integers.

Our Lemma 5.10 reduces the above theorem to the following.

Theorem 8.3 With notation as in Theorem 8.2, let K_{1}, K_{2}, K_{3} be a partition of k_{1}, …, k_{b}, and let |K_{i}| for i = 1, 2, 3 denote the sum of the k_{j} in K_{i}. Then for fixed non-negative integers ℓ_{1}, …, ℓ_{b}, Theorem 8.2 holds with R_{T,L} replaced by

R_{T,L}(k_{1}, …, k_{b}) = (d − 1)^{|K_{1}|}(−1)^{|K_{2}|}k_{1}^{ℓ_{1}} ⋯ k_{b}^{ℓ_{b}}.  (33)

More generally, Theorem 8.2 holds with R_{T,L} replaced by

R_{T,L}(k_{1}, …, k_{b}) = (d − 1)^{|K_{1}|}k_{1}^{ℓ_{1}} ⋯ k_{u}^{ℓ_{u}}β(k_{u+1}, …, k_{b}),  (34)

where the edges are ordered so that

{i|e_{i} ∈ E_{long} and k_{i} ∈ K_{1}} = {1, …, u},

and where β is a function such that

|β(k_{u+1}, …, k_{b})| ≤ c(|k_{u+1}| + ⋯ + |k_{b}|)^{c}

for some constant c.

The R of equation (33) is all that is needed for G_{n,d}; it will be convenient (if not necessary) to use the R of equation (34) for J_{n,d} (see Section 14). Proof It suffices to deal with the R of equation (34). Let

K̃_{i} = {k_{j} ∈ K_{i} | e_{j} ∈ E_{long}}.

We may assume E_{long} = {e_{1}, …, e_{t}} and K̃_{1} = {k_{1}, …, k_{u}}; set

\begin{matrix}M_{1} = m_{1} + ⋯ + m_{t}, & M_{2} = m_{t+1} + ⋯ + m_{b}, \\ j_{1} = k_{1}m_{1} + ⋯ + k_{t}m_{t}, & and j_{2} = k_{t+1}m_{t+1} + ⋯ + k_{b}m_{b}. \end{matrix}

Clearly it suffices to prove the theorem for

f(k) = ∑_{m⃗} WT̃(m⃗; S, Ψ) ∑_{\begin{matrix}k_{1}m_{1}+···+k_{b}m_{b}=k \\ k_{i}≥B for i≤t \end{matrix}}(d − 1)^{|K̃_{1}|}k_{1}^{ℓ_{1}} … k_{u}^{ℓ_{u}}β(k_{u+1}, …, k_{t}),

understanding that k_{t+1}, …, k_{t} are fixed by k⃗^{fixed}.

Definition 8.4 The (coefficient) norm, |p|, of a polynomial, p (which is possibly multivariate), is the largest absolute value among its coefficients.

Working with this notion of a norm is a bit “weak,” (i.e., sometimes much stronger statements would hold with other norms), but this notion is sufficient for our purposes.

Let

fm⃗(k) = ∑_{k⃗·m⃗=k}(d − 1)^{|K̃_{1}|}k_{1}^{ℓ_{1}} … k_{u}^{ℓ_{u}}β(k_{u+1}, …, k_{t}).

Theorem 8.5 For any vector of positive integers, m⃗, we have fm⃗ is d-Ramanujan with principal term (d−1)^{k}pm⃗(k) and error term em⃗(k) satisfying

|pm⃗| ≤ c(d − 1)^{(−BM_{1}−M_{2}+c)/2},

and

|em⃗(k)| ≤ ck^{c}(d − 1)^{(k−BM_{1}−M_{2}+Bc)/2},

where c depends only on the ℓ_{i} and β.

Proof Fix a value of m⃗. Without loss of generality we may assume m_{1} = ⋯ = m_{s} = 1 and m_{s+1}, …, m_{u} ≥ 2. For now assume that s ≥ 1; we will later indicate the minor changes needed for the situation s = 0 (i.e. when there are no m_{i} belonging to K̃_{1} that equal one). Let

gm⃗(r) = ∑_{\begin{matrix}k_{s+1},...,k_{b} s.t. \\ k_{s+1}m_{s+1}+···+k_{b}m_{b}=r \\ k_{i}≥B for i≤t \end{matrix}}(d − 1)^{k_{s+1}+···+k_{u}}β(k_{u+1}, …, k_{t}).

Lemma 8.6 If T̃ is a B-new type, then

|gm⃗(r)| ≤ cr^{c}(d − 1)^{(r−BM_{1}−M_{2}+Bc)/2}

for some constant c depending only on T̃.

Proof Since each k_{i} is at most r,

β(k_{u+1}, …, k_{t})

is bounded by cr^{c}, and it suffices to prove the estimate for gm⃗ replaced with

∑_{\begin{matrix}k_{s+1}m_{s+1}+···+k_{b}m_{b}=r \\ k_{i}≥B for i≤t \end{matrix}}(d − 1)^{k_{s+1}+···+k_{u}}.

But there are only \binom{r+b−s−1}{b−s−1} ways of writing r as the sum of b − s positive integers. So it suffices to show

(d − 1)^{k_{s+1}+···+k_{u}} ≤ (d − 1)^{(r−BM_{1}−M_{2}−Bc)/2}.

Now we have

r = k_{s+1}m_{s+1} + ⋯ + k_{b}m_{b},

so

2k_{s+1} + ⋯ + 2k_{u} = r − (k_{s+1}m_{s+1} + ⋯ + k_{b}m_{b}) + (2k_{s+1} + ⋯ + 2k_{u})

= r − (m_{s+1} − 2)k_{s+1} − ⋯ − (m_{u} − 2)k_{u} − m_{u+1}k_{u+1} − ⋯ − m_{b}k_{b}.

Since m_{i} ≥ 2 for i between s + 1 and u, and since k_{i} ≥ B for i ≤ t (and k_{i} ≥ 1 for all i), we conclude

2k_{s+1} + ⋯ + 2k_{u} ≤ r − (m_{s+1} − 2)B − ⋯ − (m_{u} − 2)B

−m_{u+1}B − ⋯ − m_{t}B − m_{t+1} − ⋯ − m_{b}
= r − (m_{s+1} + ⋯ + m_{t})B + 2(u − s)B − (m_{t+1} + ⋯ + m_{b})
= r − (M_{1} − s − 2(u − s))B − M_{2}.

Hence

k_{s+1} +⋯+k_{u} ≤ (2k_{s+1} +⋯+2k_{u})/2 ≤ (r −(M_{1} −s−2(u−s))B −M_{2})/2.

But u, s are bounded by the number of edges in T̃.

□

We will need another lemma.

Lemma 8.7 For any non-negative integers ℓ_{1}, …, ℓ_{s} there is a polynomial Q such that for all k ≥ s we have

∑_{k_{1}+···+k_{s}=k integers k_{i}≥1} k_{1}^{ℓ_{1}} … k_{s}^{ℓ_{s}} = Q(k).

Proof This is a special case of Sublemma 2.15 of [Fri91] (proven in a straightforward induction on s).

□

Now let

j_{11} = k_{1}m_{1} + ⋯ + k_{s}m_{s} = k_{1} + ⋯ + k_{s}, j_{12} = k_{s+1}m_{s+1} + ⋯ + k_{t}m_{t}

(so that j_{11} + j_{12} = j_{1}). In the notation of the above two lemmas, letting j′ = j_{12} + j_{2}, we have

fm⃗(k) = ∑_{j_{11}+j′=k}(d − 1)^{j_{11}}Q(j_{11})gm⃗(j′)

= ∑_{r=1}^{k−s}(d − 1)^{k−r}Q(k − r)gm⃗(r);  (35)

here we sum until r = k − s since Lemma 8.7 requires k ≥ s (and Q(k − r) vanishes for k < s), and we sum from r = 1 to simplify the expression, despite the fact that gm⃗(r) clearly vanishes for

r < B(m_{s+1} + ⋯ + m_{t}) + m_{t+1}k_{t+1} + ⋯ + m_{b}k_{b}.

The sum in equation (35) is clearly Σ_{1}(k) − Σ_{2}(k), where

Σ_{1}(x) = ∑_{r=1}^{∞} (d − 1)^{k−r}Q(x − r)gm⃗(r),
Σ_{2}(x) = ∑_{r=k−s+1}^{∞} (d − 1)^{k−r}Q(x − r)gm⃗(r),

assuming these sums converge.

We claim Σ_{1}(k) will be the principal part of fm⃗(k), and Σ_{2}(k) will be the error term. First we need the following lemma.

Lemma 8.8 For any positive integer, D, there is a C_{2} such that the following holds. Let g(r) be a function defined on non-negative integers, r, such that |g(r)| ≤ C_{1}r^{D}ρ^{r}, with ρ < 1. Let Q = Q(x) be any polynomial of degree at most D. Then (1) the infinite sum

h(x) = ∑_{r=1}^{∞} Q(x − r)g(r)

is convergent (in coefficient norm), (2) the degree of h is that of Q, and (3) we have

|h| ≤ C_{1}C_{2}(1 − ρ)^{−2D}|Q|.

The same is true for the sum

h_{u}(x) = ∑_{r=u+1}^{∞} Q(x − r)g(r),

for any positive integer u, except that we replace the last claim with the estimate

|h_{u}| ≤ C_{1}C_{2}u^{2D}(1 − ρ)^{−2D}ρ^{u}|Q|

(however, the C_{2} in this equation might need to be larger than that in the estimate for h).

Proof First we observe that since

∑_{r=0}^{∞} \binom{r}{j}ρ^{r} = \frac{ρ^{j+1}}{(1 − ρ)^{j}} ,

we have

∑_{r=0}^{∞} r^{j}ρ^{r} = \frac{q_{j}(ρ)}{(1 − ρ)^{j}} ,

where q_{j} is some polynomial of degree at most j + 1.

We first prove the claims on h. By the binomial theorem, and the fact that Q’s degree is bounded, it suffices to examine only the cases where Q(x − r) is replaced by x^{i}r^{j} for i + j ≤ D. In this case h(x) becomes

∑_{r=1}^{∞} x^{i}r^{j}g(r) = x^{i} ∑_{r=1}^{∞} r^{j}g(r),

and we have

∑_{r=1}^{∞} r^{j}|g(r)| ≤ ∑_{r=0}^{∞} r^{j}C_{1}r^{D}ρ^{r} = \frac{C_{1}ρ^{j+D+1}}{(1 − ρ)^{j+D}} .

This establishes the claim on h. The claim on h_{u} is reduced to h via

h_{u}(x) = ∑_{r=1}^{∞} Q̃(x − r)g̃(r),

where Q̃(x) = Q(x−u) and g̃(r) = g(r+u). So g̃ satisfies the same estimate as does g, except with an extra factor of (r + u)^{D}r^{−D}ρ^{u} ≤ Cu^{D}ρ^{u}; the binomial theorem implies that |Q̃| is at most |Q|u^{D} times a constant depending on D.

□

We continue with the proof of Theorem 8.5. We have

(d − 1)^{−k}Σ_{1}(k) = ∑_{r=1}^{∞} Q(k − r)[(d − 1)^{−r}gm⃗(r)] = ∑_{r=1}^{∞} Q(k − r)g̃(r),

where g̃(r) = (d − 1)^{−r}gm⃗(r). Now Q is fixed in the theorem, so |Q| can be regarded as a constant. Also, since

|gm⃗(r)| ≤ cr^{c}(d − 1)^{(r−BM_{1}−M_{2}+Bc)/2},

according to Lemma 8.6, we have

|g̃(r)| ≤ cr^{c}(d − 1)^{(−BM_{1}−M_{2}+Bc)/2}.

It follows that (d − 1)^{−k}Σ_{1}(k) = h(k), where h is a polynomial with

|h| ≤ c(d − 1)^{(−BM_{1}−M_{2}+Bc)/2},

assuming that d > 2 (so that 1 − ρ with ρ = (d − 1)^{−1/2} is strictly positive). Furthermore, Lemma 8.8 also implies that

|Σ_{2}| ≤ c(d − 1)^{k}(k − s + 1)^{2D}(d − 1)^{−(k−s)/2}(d − 1)^{(−BM_{1}−M_{2}+Bc)/2}

≤ c′k^{2D}(d − 1)^{(−BM_{1}−M_{2}+Bc+k)/2}.

Now we see that Σ_{1}(k) + Σ_{2}(k) is the decomposition of fm⃗(k) into principal and error terms, as claimed before, and that these terms satisfy the bounds stated in Theorem 8.5.

Finally we indicate the minor changes when s = 0. In this case we take Q to be the function Q(0) = 1 and Q vanishing elsewhere. Then fm⃗(k) = gm⃗(k), so Lemma 8.6 shows that fm⃗ is d-Ramanujan with zero principal part.

□

We continue with the proof of Theorem 8.3. We are studying

f(k) = ∑_{m⃗} WT̃(m⃗; S, Ψ)fm⃗(k).

Set

F (M_{1}, M_{2}; k) = ∑_{\begin{matrix}m_{1}+...+m_{t}=M_{1} \\ m_{t+1}+···+m_{b}=M_{2} \end{matrix}} WT̃(m⃗; S, Ψ)fm⃗(k),

so that

f(k) = ∑_{M_{1},M_{2}>0} F (M_{1}, M_{2}; k).

Theorem 6.6 combined with Theorem 8.5 gives that for fixed M_{1}, M_{2} we have that F (M_{1}, M_{2}; k) is d-Ramanujan with principle term (d−1)^{k}P_{M_{1},M_{2}}(k) and error term E_{M_{1},M_{2}}(k) where

|P_{M_{1},M_{2}}| ≤ (d − 1)^{(−BM_{1}−M_{2}+c)/2}c(\sqrt{d − 1} − ϵ)^{BM_{1}+M_{2}},
|E_{M_{1},M_{2}}(k)| ≤ ck^{c}(d − 1)^{(k−BM_{1}−M_{2}+Bc)/2}c(\sqrt{d − 1} − ϵ)^{BM_{1}+M_{2}},

and the degree of P_{M_{1},M_{2}} is bounded independent of M_{1}, M_{2}. So we sum over all M_{1}, M_{2} to conclude that f is d-Ramanujan.

□

9 Selective Traces In Graphs With (Without) Tangles

Let us review our general approach to the Alon conjecture. We are interested in expansions in 1/n of the expected value of the k-th irreducible trace. Unfortunately these expansions have some coefficients that fail to be d-Ramanujan, and, as explained in Section 2, this prevents us from proving the Alon conjecture. Replacing irreducible traces with selective traces gives d-Ramanujan coefficients up to any desired power of 1/n. However, selectivity, in the presence of appropriate tangles, modifies the irreducible trace in a way that seems hard to control. Thus we don’t know how to use the results of the last section to conclude the Alon conjecture.

The last main idea of the proof is to get an expansion for the expected value of selective traces counted only when appropriate tangles are present (i.e., the selective trace multiplied by a characteristic function over those graphs in G_{n,d} with appropriate tangles). The methods of the last section generalize, rather tediously, to such expansions. These expansions will also have d-Ramanujan coefficients up to any desired power of 1/n. It follows that we also get such expansions for the expected value of the selective trace counted only when appropriate tangles are not present; for this count, the selective trace and irreducible trace are the same. This information turns out to be enough to prove the Alon conjecture (with an auxilliary lemma proven in Section 11).

Before doing the above, it is crucial to know that a certain set of tangles is finite.

Definition 9.1 Recall that Ψ_{eig} is the set of supercritical tangles, i.e., whose λ_{Irred} is at least \sqrt{d − 1}. Recall that Ψ_{eig}[r] is the subset of elements of Ψ_{eig} of order at most r. Let Ψ_{min}[r] be the set of tangles of Ψ_{eig}[r] that are minimal with respect to inclusions, i.e., that don’t have another element of Ψ_{eig}[r] properly included in it.

Lemma 9.2 The set Ψ_{min}[r] is finite.

This means that containing a supercritical tangle of order at most r is equivalent to containing one of a finite set of tangles. Proof Assume that Ψ_{min}[r] is not finite. With each tangle we associate a type which is the labelled graph obtained by supressing the degree two vertices. Since there are finitely many types of order at most r, there must be an infinite number of Ψ_{min}[r] tangles of some type, T. By passing to a subsequence we may assume there is an infinite sequence of Ψ_{min}[r] elements, {ψ_{i}}, such that for each edge of T the associated labelling is either constant or has length tending to infinity; furthermore, the length must tend to infinity along at least one T edge. Let ψ_{∞} be the limiting tangle, where we discard all edges with length tending to infinity.

We claim λ_{Irred}(ψ_{i}) = λ_{1}(T_{Irred}^{i}), where T_{Irred}^{i} is the VLG with underlying directed graph T_{Irred}, and where e = (v_{1}, v_{2}) ∈ E_{T_{Irred}} has length equal to the length, ℓ(v_{1}), of v_{1} in ψ_{i} (recall v_{1} can be viewed as a directed edge of T); indeed, with a vertex path v_{1}, …, v_{r} in T_{Irred} with v_{j} = (u_{j}, u_{j+1}) for u_{j} ∈ V_{T}, we associate the walk u_{1}, …, u_{r+1}, which has ψ_{i} length equal to the sum of the ℓ(v_{i}). For a closed walk, where u_{r+1} = u_{1}, its length (in T_{Irred}^{i}) ℓ(v_{1}) + ⋯ + ℓ(v_{r}), which corresponds to a unique (ψ_{i})_{Irred} closed walk of the same length, arising from the subdivided v_{j}. This correspondence is clearly a length preserving bijection between T_{Irred}^{i} closed walks and (ψ_{i})_{Irred} closed walks. Hence λ_{Irred}(ψ_{i}) = λ_{1}(T_{Irred}^{i}).

Similarly λ_{Irred}(ψ_{∞}) = λ_{1}(T_{Irred}^{∞}) with T_{Irred}^{∞} defined similarly. Now by Theorem 3.6, λ_{1}(T_{Irred}^{i}) → λ_{1}(T_{Irred}^{∞}), and so λ_{Irred}(ψ_{∞}) ≥ \sqrt{d − 1}. Also ψ_{∞}’s order is less than that of the ψ_{i} (because of the edge removal(s)). Hence ψ_{∞} is again a Ψ_{eig}[r] tangle. But ψ_{∞} properly contains (all) ψ_{i}, which contradicts the supposed minimality of the ψ_{i}. Hence Ψ_{min}[r] is finite.

□

We illustrate the above lemma with an example. Let ψ_{i} be a sequence of tangles whose underlying graph is the same except for one beaded cycle of length i about some vertex. This infinite collection of tangles would prove troublesome to the methods of this section. However either (1) λ_{Irred}(ψ_{i}) < \sqrt{d − 1} for some i, at which point only finitely many of the ψ_{i} are relevant, or (2) the limiting tangle, ψ_{∞}, has λ_{Irred}(ψ_{∞}) ≥ \sqrt{d − 1}, in which case a ψ_{i} inclusion implies a ψ_{∞} inclusion.

Theorem 9.3 Let Ψ be a finite set of pruned (nonempty) tangles of order at least 1. Let χ_{Ψ} be the indicator function of the event that G ∈ G_{n,d} contains a (i.e., at least one) tangle from Ψ, i.e.,

χ_{Ψ}(G) = \{ \begin{matrix}1 & if G contains a tangle from Ψ, \\ 0 & if not. \end{matrix}

Let Ψ′ be a set of tangles including all supercritical tangles of order less than r. Then for any r there is an S_{0} = S_{0}(r, Ψ, Ψ′) such that for all S ≥ S_{0} we have an expansion

E [χ_{Ψ}IrSelTr_{S,Ψ′}(G; k)] = f_{0}(k) + \frac{f_{1}(k)}{n} + ⋯ + \frac{f_{r−1}(k)}{n^{r−1}} + \frac{error}{n^{r}}, (36)

where the f_{i} are d-Ramanujan and the error term satisfies

|error| ≤ ckr̃(d − 1)^{k}

with c and r̃ depending only on r, Ψ, and Ψ′.

We believe this theorem is true even if Ψ contains cycles, i.e., tangles of order 0. But to prove this would be more difficult, since the last part of Lemma 9.6 would not be true (see the remark that follows this lemma).

Before giving the proof of Theorem 9.3, we give an important corollary of it and Theorem 8.1.

Corollary 9.4 With notation and conditions as in Theorem 9.3, we have that

E [(1 − χ_{Ψ})IrSelTr_{S,Ψ′}(G; k)]

also has an expansion of the form given by the right-hand-side of equation (36).

Proof (of Theorem 9.3) We want to generalize walk sums, forms, types, etc. into structures that incorporate the presence of a Ψ tangle. We shall first explain why we run into inclusion/exclusion and tangle automophisms (as in Theorem 4.7).

Define a potential tangle specialization as a pair, (Ω, σ), of a tangle, Ω, and an inclusion σ: V_{Ω} → {1, …, n}. Let χ_{Ω,σ} denote the indicator function of the event that Ω is contained in G ∈ G_{n,d} via the map σ. Let χ_{(w;t⃗)} be the indicator function of the event, E(w; t⃗), of the potential walk (w; t⃗). We plan to study sums involving various χ_{(w;t⃗)}χ_{Ω,σ}.

For now consider χ_{Ω,σ} alone. Since the word “form” was used earlier to mean “look at the graph traced out and forget the specific values of the vertices,” it makes sense to view Ω itself as the “form” of (Ω, σ), and let

E [Ω]_{n} = ∑_{σ} E [χ_{Ω,σ}] = \frac{n!}{(n − v)!} ∏_{i=1}^{d/2} \frac{(n − a_{i})!}{n!},

where, as usual, the a_{i} are the number of Ω edges labelled π_{i} and v is the number of vertices in Ω. The problem is that E [Ω]_{n} gives the expected number of times Ω is included into a random graph; when computing traces and walk sums, we do wish to count; but when looking at tangle inclusions, when don’t wish to count— we want to compute only the function χ_{Ψ}, i.e., we want a 1 when a Ψ tangle is present, and a 0 otherwise.

Given two tangles, ψ, ψ′, let N(ψ, ψ′) denote the number of inclusions of ψ into ψ′. Of course, N(ψ, ψ) is the number of automorphisms of ψ. Also, E [Ω]_{n} is just the expected value of N(Ω, G) for a G ∈ G_{n,d} (viewing G as a tangle). Let ψ ≤ ψ′ (respectively, ψ < ψ′) denote that ψ has an inclusion (respectively, proper inclusion) into ψ′. By a Ψ-tangle we mean any tangle isomorphic to an element of Ψ. A derived tangle of Ψ is a tangle that is the nonempty union of Ψ-tangles. Let Ψ^{+} be a collection of one derived tangle of Ψ in every tangle isomorphism class.

Proposition 9.5 There exist reals numbers {μ_{Ω}}_{Ω∈Ψ^{+}} such that for any Ω′ ∈ Ψ^{+} we have

∑_{Ω≤Ω′} N(Ω, Ω′)μ_{Ω} = 1.

Proof This is just generalized Möbius inversion: Ψ^{+} is a partially ordered set, and given Ω′ there are only finitely many Ω with Ω < Ω′. Furthermore N(Ω′, Ω′) is positive for all Ω′. So we can inductively solve for μ_{Ω}.

□

It follows that

E [χ_{Ψ}IrSelTr_{S,Ψ′}(G; k)] = ∑_{(w,t⃗)∈W} E [χ_{(w;t⃗)}χ_{Ψ}]  (37)

= ∑_{(w,t⃗)∈W} ∑_{(Ω,σ),Ω∈Ψ^{+}} E [χ_{(w;t⃗)}χ_{Ω,σ}] μ_{Ω}, (38)

where W is the walk collection corresponding to the irreducible (S, Ψ′) selective walks.

Lemma 9.6 Let W_{<r} be those elements of W of order less than r, and similarly for Ψ_{<r}^{+}. In equation (38), by replacing the summation over W and Ψ^{+} by summation over W_{<r} and Ψ_{<r}^{+}, the difference is at most C(d − 1)^{k}n^{−r}k^{2r}. Furthermore, the set Ψ_{<r}^{+} is finite for each r.

We remark that if Ψ could contain a tangle of order 0, i.e., one whose underlying graph is a cycle, then Ψ_{<1}^{+} would be infinite, containing arbitrarily large disjoint unions of tangles whose underlying graph is a cycle. Proof We know that we can ignore (w; t⃗ )’s of order at least r by using Theorem 5.9 and the fact that |χ_{Ψ}| ≤ 1 in equation (37). This leaves us with a sum over W_{<r} and Ψ^{+}, and it is left to see what happens when Ψ^{+} is replaced by Ψ_{<r}^{+}.

For the (Ω, σ)’s, notice that every tangle in Ψ^{+} of order at least r must contain a tangle of order between r and r + s − 1, where s is the maximum number of edges in a Ψ-tangle; this follows because taking the union of any graph with a Ψ-tangle increases the number of edges by at most s. Lemma 4.10 shows that there are only finitely many elements of Ψ^{+} of order at most r + s − 1 (and that any such element is the union of at most r + s − 1 elements of Ψ). Theorem 4.7 now shows that there is a C = C(r) such that a graph contains a Ψ^{+}-tangle of order at least r with probability at most Cn^{−r}. Let Ψ_{<r}^{+} be the subset of tangles of order less than r in Ψ^{+}. Then

χ_{Ψ}(G) = h(G) + ∑_{Ω∈Ψ_{<r}^{+}} N(Ω, G)μ_{Ω},

where h(G) is a function bounded by a 1 plus the finite sum of all |μ_{Ω}| over Ω ∈ Ψ_{<r}^{+}. Truncating the sum in equation (38) to Ω ∈ Ψ_{<r}^{+} therefore introduces an error of at most

∑_{(w,t⃗)∈W} E [χ_{(w;t⃗)}h(G)] ≤ d(d − 1)^{k−1}Cn^{−r} max(h).

□

According to Lemma 9.6, it suffices to fix an Ω ∈ Ψ_{<r}^{+} and to show that

∑_{(w,t⃗)∈W_{<r}} ∑_{σ} E [χ_{(w;t⃗)}χ_{Ω,σ}]  (39)

has an expansion like the right-hand-side of equation (36). So fix an Ω ∈ Ψ_{<r}^{+}; we now define the “form” of (w; t⃗), but we incorporate into the form the information of how Ω, σ overlaps with (w; t⃗) by allowing Ω and Γ to share vertices and edges.

Definition 9.7 An Ω-specialization of a form, Γ, is an inclusion ι: V_{Γ} ∪ V_{Ω} → {1, …, n}. An Ω-isomorphism of forms is an isomophism of forms Γ_{1} → Γ_{2} which is the identity from V_{Γ_{1}} ∩ V_{Ω} to V_{Γ_{2}} ∩ V_{Ω}. We introduce the notation

E [Γ; Ω]_{n} = \frac{n!}{(n − v)!} ∏_{i=1}^{d/2} \frac{(n − a_{i})!}{n!},

where v = |V_{Γ} ∪ V_{Ω}| and a_{i} is the number of π_{i} labels occurring in Γ ∪ Ω.

Given (w; t⃗) and Ω, σ as above, we set [t⃗; σ] to be the set of all pairs, (s⃗, τ), such that there is a permutation of the integers taking t⃗ to s⃗ and σ to τ; we set [t⃗; σ]_{n} to the same, with the additional requirement that the components of s⃗ and the image of τ lie in {1, …, n}. If we let Γ be the form of w, sharing vertices and edges with Ω where σ and t⃗ “overlap,” then

E [Γ; Ω]_{n} = ∑_{(s⃗,τ)∈[t⃗;σ]_{n}} E [χ_{(w;s⃗)}χ_{Ω;τ}] .

It follows that the expression in equation (39) is just

∑_{Γ∈W_{<r}} W_{Γ}(W, k)E [Γ; Ω]_{n} ,  (40)

summed over one Γ from each Ω-isomophism class (compare equation (24)).

We now go through the rest of Sections 5, 6, and 8, indicating how to modify our results to allow deal with sums in equation (40). Let us begin by remarking that the expansion of Theorem 5.5 generalizes easily here, in that

E [Γ; Ω]_{n} = n^{v−e}(p_{0} + \frac{p_{1}}{n} + ⋯ + \frac{p_{q}}{n^{q}} + \frac{error}{n^{q+1}})

where the p_{i} = p_{i}(a_{1}, …, a_{d/2}, v) are the expansion polynomials, and

|error| ≤ e^{qk/(n−k)}(v(v − 1)/2 + a_{1}(a_{1} − 1)/2 + ⋯ + a_{d/2}(a_{d/2} − 1)/2)^{q}

(by equation (20) ). Since our potential walk is of length k, we have

v ≤ k + |V_{Ω}|,

and

∑ a_{i} ≤ k + |E_{Ω}|.

Since Ω is fixed, it follows that the error is bounded by ck^{2r−2} in the range k ≤ n/2, since the order of Γ ∪ Ω is at least 1 (since Γ ∪ Ω is pruned and contains an element of Ψ).

We next claim that given w (and our fixed Ω), the number of equivalence classes [t⃗; σ] corresponding to w and Ω is bounded by Ck^{2r+|V_{Ω}|}; indeed, Lemma 5.8 shows there at most Ck^{2r} t⃗ classes. The additional |V_{Ω}| choices of σ values can be chosen from at most k + |V_{Ω}| − 1 “old” values plus one “new” value each time, for a total number of equivalence classes of at most Ck^{2r} times (k + |V_{Ω}|)^{|V_{Ω}|}, which is the claimed bound.

We obtain that the sum in equation (40) is

∑_{Γ∈W_{<r}} W_{Γ}(W, k)[\frac{p_{0}(Γ; Ω)}{n^{ord(Γ;Ω)}} + ⋯ + \frac{p_{r−1−ord(Γ;Ω)}(Γ; Ω)}{n^{r−1}} + \frac{error(Γ; Ω)}{n^{r}}] (41)

with p_{i}(Γ) = p_{i}(a_{1}(Γ; Ω), …, v(Γ; Ω)) the expansion polynomials, with

∑_{Γ∈W_{<r}} W_{Γ}(W, k)error(Γ; Ω) = O(k^{4r−2+|V_{Ω}|})(d − 1)^{k}.

To attack the expansion polynomial sums in equation (41), we introduce straightforward generalizations of types and new types.

Definition 9.8 An Ω-type is an oriented graph G_{T} = (V_{T} , E_{T}), with vertex and edge partial numberings such that (1) Ω is a subgraph of G_{T}, (2) all vertices of G_{T} except possibly the first one and possibly V_{Ω} vertices are of degree at least 3, and (3) all vertices and edges not in Ω are numbered.

To a form, Γ, we associate its Ω-type, T, by taking Γ ∪ Ω and supressing the degree 2 vertices in V_{Γ} \ V_{Ω}. T ’s edges are partially numbered since we number the edges in they order they must be traversed by a corresponding walk, and we don’t number an edge if the walk doesn’t traverse the edge (such edges are the edges of E_{Ω} \ E_{Γ}).

Definition 9.9 A B-new Ω-type is a collection T̃ = (T; E_{long}, E_{fixed}; k⃗^{fixed}),

(1) a lettered Ω-type, T, (2) a partition of E_{T} into two sets, E_{long}, E_{fixed},

(3) for each e_{i} ∈ E_{fixed} an edge length, k_{i}^{fixed}, with 0 < k_{i}^{fixed} < B, and (4) a Π^{+}-labelling of E_{fixed} with each e_{i} ∈ E_{fixed} labelled with a word of length k_{i}^{fixed}. Furthermore, we require that E_{Ω} is contained in E_{fixed}, and that each E_{Ω} edge has length 1 in T̃ and is labelled with its Ω label in T̃.

So conditions (2)–(4) are just as for a new type (See Definition 5.19), and condition (1) here involves an Ω-type instead of a type.

Again, it is easily seen that there are finitely many (isomorphism classes) of Ω-types of a given order, and finitely many B-new Ω-types belonging to a type, T, for a given B (and T). It suffices to show that for B and S sufficiently large with B > S we have that for any B-new Ω-type, T̃, and any polynomial, p, in the a_{i}’s we have

∑_{Γ∈T̃} W_{Γ}(W, k)p(a_{1}(Γ; Ω), …, a_{d/2}(Γ; Ω))

is d-Ramanujan.

For integers {m_{i}} indexed over e_{i} edges of E_{T}, set

WT̃(m⃗; S, Ψ′)

to the number of walk classes of new type T̃, traversing the edge e_{i} m_{i} times, that are irreducible (S, Ψ′) selective cycles and that respect the T partial numbering and orientation; we assume m_{i} ≥ 1 or m_{i} = 0 according to whether or not e_{i} is numbered (i.e., e_{i} is to be traversed on our walk); assuming T̃ is a B-new type with B > S, this number does not depend on the “long” (i.e., E_{long}) edge lengths. Index the edges so that E_{long} = {e_{1}, …, e_{t}} and E_{fixed} = {e_{t+1}, …, e_{b′}}, with {e_{t+1}, …, e_{b}} the numbered edges (so m_{b+1} = ⋯ = m_{b′} = 0). We claim that the proof of Theorem 6.6 shows that

W_{T̃,S}(M_{1}, M_{2}) = ∑_{\begin{matrix}m_{1}+...+m_{t}=M_{1} \\ m_{t+1}+···+m_{b}=M_{2} \end{matrix}} WT̃(m⃗; S, Ψ′),

satisfies the bound

W_{T̃,S}(M_{1}, M_{2}) ≤ cB(\sqrt{d − 1} − ϵ)^{cM_{1}+M_{2}}.

for S ≥ S_{0} for some c, S_{0}, and ϵ depending only on T̃. This is because the argument of Theorem 6.6 is unaffected by the two essential new features that T has over types, which are the possible presence of (1) some more degree 2 vertices (other than just the vertex numbered 1), and (2) some edges whose lengths are fixed at 1 (namely E_{Ω} edges). But each a_{i} = a_{i}(Γ; Ω), which is the number of edges labelled π_{i} in Γ ∪ Ω, has

a_{i}(Γ; Ω) = a_{i}(Γ) + a_{i}(Ω \ Γ),

and a_{i}(Ω \ Γ) is fixed in a new Ω-type, T̃ (by the edge partial numbering). Thus for any polynomial p and new typoid, T̃, there is a polynomial p̃ such that

p(a_{1}(Γ; Ω), …, a_{d/2}(Γ; Ω)) = p̃(a_{1}(Γ), …, a_{d/2}(Γ)).  (42)

But it is easy to see that Theorem 8.2 holds if we extend the definition of type and new type to allow any fixed number of vertices of degree 2. Furthermore the condition that Γ belongs to T̃ is the same as Γ belonging to this extended notion of new type. We conclude that either side of equation (42) is d-Ramanujan.

□

10 Strongly Irreducible Traces

We wish to use Theorem 9.3 to estimate eigenvalues. However, it is easier to use strongly irreducible traces rather than irreducible traces. We explain this and develop the properties of the strongly irreducible trace in this section.

Definition 10.1 A word w ∈ Π^{∗} is strongly irreducible if w is irreducible and w = σ_{1} … σ_{k} with σ_{1} ≠ σ_{k}^{−1}.

For any of our irreducible traces, selective irreducible traces, irreducible walk sums, etc., we can form its “strongly irreducible” version where we discard contributions from words that are not strongly irreducible. In any graph, labelled or not, one can speak of strongly irreducible closed walks as those closed walks that are irreducible and whose last step is not the opposite of its first step.

Definition 10.2 The k-th strongly irreducible trace of a graph, G, is the number of strongly irreducible closed walks of length k for a positive integer k; we denote it SIT(G, k) or SIT(A, k) if A is the adjacency matrix of G. If G has half-loops, we consider each half-loop to be a strongly irreducible closed walk (of length 1) and include it in our count for SIT(G, 1) or SIT(A, 1).

Half-loops are only a concern for us in the model J_{n,d}; the reason that we count half-loops as strongly irreducible is to make Lemma 10.4 hold.

With a closed walk of length k in G_{Irred} about a directed edge, e, of G, we may associate the strongly irreducible closed walk in G about the vertex in which e originates. It follows that if μ_{i} are the eigenvalues of G_{Irred}, we have

SIT(G, k) = ∑_{i=1}^{nd} μ_{i}^{k}  (43)

for all k ≥ 2; for k = 1 we must add the number of half-loops to the righthand-side of the above equation, since there is no edge in G_{Irred} from a vertex to itself when the vertex corresponds to a half-loop.

We will study the relationship between IrredTr (G, k) and SIT(G, k) and its consequences. The most important consequence is the following theorem.

Theorem 10.3 For |λ| ≤ d, let

μ_{1,2}(λ) = \frac{λ ± \sqrt{λ^{2} − 4(d − 1)}}{2},

and set

q̃_{k}(λ) = μ_{1}^{k}(λ) + μ_{2}^{k}(λ) + (1 + (−1)^{k})(d − 2)/2.  (44)

If G is a d-regular graph with no half-loops and adjacency matrix eigenvalues λ_{1} ≥ ⋯ ≥ λ_{n}, then

SIT(G, k) = ∑_{i=1}^{n} q̃_{k}(λ_{i}).  (45)

Furthermore, if instead G has no whole-loops, then the same is true with q̃_{k} replaced by q̂_{k} where

q̂_{k}(x) = \{ \begin{matrix}q̃_{k}(x) & if k is even or k = 1, \\ q̃_{k}(x) − x & if k ≥ 3 is odd. \end{matrix}

Furthermore, we shall see that q̃_{k}, like the q_{k} of Lemma 2.3, are polynomials of degree k that may alternatively be expressed as a simple linear combination of Chebyshev polynomials (plus the ±1 eigenvalue contribution for the q̃_{k}). (In a sense, equation (45) says that to each eigenvalue, λ, of G, there correspond eigenvalues μ_{1,2}(λ) of multiplicity one each and eigenvalues 1 and −1 of multiplicity (d − 2)/2 each in G_{Irred}.)

Lemma 10.4 Let G be a d-regular graph on n vertices with h half-loops. Then for all integers k ≥ 2 we have^{20}

IrredTr (G, k) = SIT(G, k) + (d − 2) ∑_{i=1}^{⌊(k−1)/2⌋}(d − 1)^{i−1}SIT(G, k − 2i)

+ \{ \begin{matrix}0 & if k is even, \\ (d − 1)^{(k−3)/2}h & if k is odd. \end{matrix}

Therefore for all k ≥ 4 (and for k = 3 when h = 0) we have

IrredTr (G, k) − (d − 1)IrredTr (G, k − 2) = SIT(G, k) − SIT(G, k − 2) (46)

Proof The last equation follows from the previous one, with a little care when k = 3; indeed, for k = 3 we have SIT(G, k − 2) = SIT(G, 1) = 2w + h, where w, h are the number of whole- and half-loops. So

IrredTr (G, 3) = SIT(G, 3) + (d − 2)SIT(G, 1) + h,

and

IrredTr (G, 1) = SIT(G, 1) = Trace (A) = 2w + h.

Hence

IrredTr (G, 3) − (d − 1)IrredTr (G, 1) − SIT(G, 3) + SIT(G, 1) = h.

Thus equation (46) holds with k = 3 if h = 0. We similarly show that this equation holds regardless of h for k ≥ 4.

So it suffices to prove the first equation of the lemma. Each irreducible closed walk about a vertex, v, begins by traversing a path, p, to a vertex, w, then follows a strongly irreducible (nonempty) closed walk about w, and then backtracks over p (and this statement is only true if we count half-loops as strongly irreducible); each irreducible closed walk has a uniquely determined such p and w. So we may count irreducible closed walks of length k in G by counting how many paths of length i there are from w that when combined with a strongly irreducible closed walk about w of length k − 2i yield an irreducible closed walk, C, of length k. The strongly irreducible closed walk’s length, k − 2i, must be positive, or else C isn’t irreducible. If C is of length at least 2 or is a whole-loop, then there are d − 2 possibilities for the first edge of the path (since two edges are ruled out by C in either case), and d − 1 possibilities for all edge choices thereafter. For a half-loop there are d − 1 possibilities for the first edge (since only the single half-loop edge is ruled out). So the contribution per strongly irreducible closed walk of length k −2i is 1 for i = 0, (d−2)(d−1)^{i−1} for i ≥ 1, except in a half-loop, where the contribution per half-loop is (d − 1)^{i}, i.e., an additional (d − 1)^{i−1} beyond the standard contribution. Since k is odd and i = (k − 1)/2 in the case of a half-loop, the additional amount beyond the standard contribution is (d − 1)^{(k−3)/2} per half-loop.

20For k = 2 the summation in the formula to follow is ignored, since it ranges from i = 1 to i = ⌊(k − 1)/2⌋ = 0.

□

We return to the proof of the theorem. First assume that G has no half-loops. We will prove by induction on k ≥ 1 that

SIT(G, k) = ∑_{i=1}^{n} q̃_{k}(λ_{i}),  (47)

where q̃_{k} are polynomials of degree k. Clearly

SIT(G, 1) = Trace(A),

and so q̃_{1} exists as desired with q̃_{1}(λ) = λ. Of the closed walks of length 2, all irreducible closed walks are strongly irreducible, so q̃_{2}(λ) = λ^{2} − d. Lemmas 10.4 and 2.3 now imply (by induction on k) that polynomials q̃_{k}(λ) exist of degree k satisfying equation (47), and that the q̃_{k}, for k ≥ 2, are annihilated by

(σ_{k}^{2} − 1)(σ_{k}^{2} − λσ_{k} + (d − 1)),  (48)

where σ_{k} is the “shift in k” operator, i.e., σ_{k}(f(k)) = f(k + 1) (here we use the fact that the q_{k} are annihilated by σ_{k}^{2} − λσ_{k} + (d − 1), mentioned below Lemma 2.3). Since μ_{1,2}(λ), ±1 are the four roots in σ_{k} of equation (48), we have

q̃_{k}(λ) = c_{1}μ_{1}^{k} + c_{2}μ_{2}^{k} + c_{3} + c_{4}(−1)^{k},

where the c_{i} = c_{i}(λ) assuming that the four roots are distinct. There are now two ways to finish the theorem.

The first method to finish the theorem is to calculate q̃_{3}, q̃_{4} and verify equation (44) holds for k = 2, 3, 4, 5, i.e., that c_{1} = c_{2} = 1 and c_{3} = c_{4} = (d − 2)/2 work in those cases. Then by uniqueness (i.e., the nonvanishing of a Vandermonde determinant), those c_{i}’s must be the unique c_{i}’s that work for all k.

Another way to finish the theorem is to use the fact that c_{1}(d) = 1 (see the remark after Lemma 5.10), and then argue that c_{1}(λ) = c_{2}(λ) = 1 by analytic continuation. First, the c_{i}’s are the unique solutions to a 4 × 4 system of equations with coefficient analytic in λ; hence the c_{i} are, indeed, analytic in λ. Next, notice that μ_{1}(λ) at λ = d analytically continues to μ_{2}(λ) at λ = d by one loop about 2\sqrt{d − 1}; thus is suffices to prove that c_{1} = 1 near d. Next notice that different λ’s give different μ’s (indeed, r^{2} − λ_{1}r + (d − 1) = 0 and r^{2} − λ_{2}r + (d − 1) = 0 for the same r implies r(λ_{2} − λ_{1}) = 0), so if λ ≠ d is an eigenvalue of multiplicity k in a graph, then c_{1}(λ) times k must be an integer. But there is a sequence, z_{n} → 1, with c_{1}(z_{n}) an integer or halfinteger (namely a cycle of length n where each edge has multiplicity d/2 has z_{n} = (d/2) cos(2π/n) as an eigenvalue of multiplicty two). So by continuity c_{1}(z_{n}) = 1 for sufficiently large n, and thus c_{1} is identically 1.

It suffices to determine c_{3}, c_{4}, which from q̃_{1}, q̃_{2} we find are (the constant functions) c_{3} = c_{4} = (d − 2)/2.

Finally, if G has only half-loops (no whole-loops), then the k even formula and k = 1 formula are unchanged. We easily see by induction on odd k ≥ 3 that the polynomial q̂_{k} = q̃_{k}(x)−x works (we use the fact that h, the number of half-loops, is the trace of A_{G}, i.e., h = ∑ λ_{i}).

□

Theorem 10.5 Fix an integer d > 2 and a real ϵ > 0. There is an η > 0 such that if G is a d-regular graph with |λ_{i}| ≤ d − ϵ for all i > 1, then the μ_{i} of equation (43) satisfy μ_{1} = d − 1 and |μ_{i}| ≤ d − η for all i > 1.

Proof The μ_{i} must be ±1 or roots of the equation in μ

μ^{2} − μλ_{i} + (d − 1) = 0,

or

μ = \frac{λ_{i} ± \sqrt{λ_{i}^{2} − 4(d − 1)}}{2}.

For i = 1 we have λ_{1} = d and the corresponding μ’s are μ = d − 1, 1. The other μ’s are either 1 or come from λ_{i} with i > 1. But for |λ_{i}| ≤ d − ϵ it is easy to see that the corresponding μ’s are bounded away from d − 1.

□

We can form a selective, strongly irreducible trace by taking

SSIT_{S,Ψ′}(G; k)

to be the number of strongly irreducible closed walks of length k that are (S, Ψ′)-selective. Notice that there are no more strongly irreducible closed walks than irreducible closed walks in any lettered type, and the strong irreducibility of a potential walk can be determined from its image in the corresponding lettered type. Hence the expansion theorems of Sections 6– 9, especially Theorem 9.3, carry over to SSIT replacing IrSelTr, by simply replacing

W_{T̃,S}(M_{1}, M_{2})

by the same number of walk classes of the new Ω-type, T̃, except requiring that the walks are strongly irreducible.

11 A Sidestepping Lemma

Lemma 11.1 Fix integers r, r̃, d with d > 2, polynomials p_{0}, …, p_{r}, a constant, c, and an integer D. Assume that for each n we have complex-valued random variables θ_{1}, …, θ_{m} such that m = Dn. Assume that 1 − θ_{i} is of absolute value at most 1, and is purely real if its absolute value is greater than (d − 1)^{−1/2}. Furthermore assume that for all integers k ≥ 1 we have

E [∑_{i}(1 − θ_{i})^{k}] = ∑_{j=0}^{r−1} p_{j}(k)n^{−j} + O(kr̃n^{−r} + k^{c}(d − 1)^{−k/2}).  (49)

Then for sufficiently large n we have

E [∑_{i} χ_{{|θ_{i}|>log^{−2} n}}(1 − θ_{i})^{k}] = O(Dn^{1−(r/3)} + k^{c}(d − 1)^{−k/2})  (50)

for all k with 1 ≤ k ≤ n^{γ} for some constant γ > 0, where the constant γ and the constant in the O( ·) notation depends only on r, r̃, d and the maximum degree of the p_{i}.

After this section we will apply this lemma with the (d − 1)(1 − θ_{i}) being the eigenvalues of G_{Irred}, with k proportional (for fixed r) to log n.

If σ_{k} denotes the “shift with respect to k,” i.e., σ_{k}(f(k)) = f(k + 1), then some fixed power of σ_{k} − 1 annihilates the p_{j}(k), and also

(σ_{k} − 1)^{i}(1 − θ)^{k} = (−θ)^{i}(1 − θ)^{k}.

This allows us to say a lot about the θ_{i} by applying some power of σ_{k} − 1 to equation (49). For the irreducible trace, the (1 − θ_{i})^{k} are replaced by certain Chebyshev polynomials of θ_{i}, and applying powers of σ_{k} − 1 to them seems more awkward; this is why we have introduced strongly irreducible traces.

In [Fri91], we worked with irreducible traces, not strongly irreducible traces. There we had the (1 − θ_{i})^{k} replaced by Chebyshev polynomials of 1 − θ_{i}; however (1) we knew that θ_{1} = 0 and θ_{i} was bounded away from 0 with probability 1 − O(n^{1−d}), and (2) we could only prove the asymptotic expansion up to r which was roughly propotional to d^{1/2}. So we could directly apply the analogue of equation (49) with k roughly log^{2} n to determine that p_{0}(k) = 1 and the higher p_{j} vanish (up to j roughly proportional to d^{1/2}). In this paper the arbitrary length of the asymptotic expansion for a type of trace comes at the cost of having far less control over the θ_{i}, and we have no ability to determine the p_{j} exactly. Fortunately Lemma 11.1 allows us to control the θ_{i} bounded away from 0, and fortunately we will see that the θ_{i} for i > 1 are bounded away from 0 with probability 1 − O(n^{−τ_{fund}}).

We wish to comment that one expects polynomials p_{j} = p_{j}(k) to arise from the binomial expansion. Namely (by Taylor’s theorem),

(1 − θ)^{k} = ∑_{i=0}^{s−1} \binom{k}{i}(−θ)^{i} + \binom{k}{s}(−θ)^{s}(1 − ξ)^{k−s},  (51)

for some ξ ∈ [0, θ]. So for those θ ≤ n^{−β} for some constant β > 0, we may take s roughly r/β and get an error term in ξ bounded by roughly O(n^{−r}); we get a similarly bounded error term when taking expected values of (1−θ)^{k}χ_{E} where E is the event that θ ≤ n^{−β}. In this way, equation (51) could give rise to the terms of an asymptotic expansion. Proof (of Lemma 11.1). Let s be a fixed even integer such that the maximum degree of the p_{j} is at most s − 1. We apply (σ_{k} − 1)^{s} to equation (49) to conclude that

E [∑_{i}(−θ_{i})^{s}(1 − θ_{i})^{k}] = O(kr̃n^{−r} + k^{c}(d − 1)^{−k/2})

for any k, where the constant in the O( ·) notation depends on d and s. We conclude that for log^{2} n ≤ k ≤ n^{r/(2r̃)} we have

E [∑_{i} θ_{i}^{s}(1 − θ_{i})^{k}] = O(n^{−r/2}).

Applying this for k = ⌊n^{γ}⌋ and k = ⌊log^{2} n⌋, where γ = r/(2r̃), and subtracting we conclude

E [∑_{i} θ_{i}^{s}((1 − θ_{i})^{⌊log^{2} n⌋} − (1 − θ_{i})^{⌊n^{γ}⌋})] = O(n^{−r/2}).

Since θ_{i} is real unless 1 − θ_{i} = (d − 1)^{−1/2}, we conclude that

E [∑_{i} |θ_{i}|^{s}(|1 − θ_{i}|^{⌊log^{2} n⌋} − |1 − θ_{i}|^{⌊n^{γ}⌋})]

= O(n^{−r/2}) + O(n(d − 1)^{−(log^{2} n)/2}) = O(n^{−r/2}).

Now for any θ_{i} ≤ log^{−2} n we have (1−θ_{i})^{log^{2} n} is at least roughly 1/e for large n; also for θ_{i} ≥ n^{−α} for a constant α > 0 we have (1 − θ_{i})^{n^{γ}} is near 0 for large n provided α < γ, and also θ_{i}^{s} ≥ n^{−sα}. We conclude that

E [∑_{i}(χ_{{n^{−α}≤θ_{i}≤log^{−2} n}})n^{−sα}] = O(n^{−r/2}),

and hence, since θ_{i} is real for |θ_{i}| < log^{−2} n for n large,

E [χ_{n^{−α}≤θ_{i}≤log^{−2} n}] = O(n^{sα−(r/2)}).  (52)

Let α > 0 be fixed with sα < r/6, and set

A_{1}[i, n] = The event that θ_{i} < n^{−α},
A_{2}[i, n] = The event that n^{−α} ≤ θ_{i} ≤ log^{−2} n,
A_{3}[i, n] = The event that log^{−2} n < |θ_{i}|.

Equation (52) implies that

Prob {A_{2}[i, n]} = O(n^{−r/3}).

Since the number of θ_{i} is linear in n, we conclude that

E [∑_{i} χ_{A_{2}[i,n]}(1 − θ_{i})^{k}] = O(n^{1−(r/3)}).  (53)

By the comment just before the proof, we have (using Taylor’s theorem)

E [χ_{A_{1}[i,n]}(1 − θ_{i})^{k}] = ∑_{j=0}^{j≤2r/α} \binom{k}{j}E [χ_{A_{1}[i,n]}(−θ_{i})^{j}] + O(k^{1+(2r/α)}n^{−2r}).

Summing over i in the above involves summing over i in the expected values and multiplying the error term by a number linear in n. So let

q(k, n) = ∑_{i} ∑_{j=0}^{j≤r/α} \binom{k}{j}E [χ_{A_{1}[i,n]}(−θ_{i})^{j}] ,

which is a polynomial of fixed degree in k whose coefficients depend on n (and the θ_{i} which are given for each value of n). Fix a γ for which

O(k^{1+(2r/α)}n^{1−2r}) = O(n^{−r/3})

for all k ≤ n^{γ}, i.e., fix a γ with

γ(1 + (r/α)) ≤ 5r/3 − 1.

Then for all k ≤ n^{γ} we have

E [∑_{i} χ_{A_{1}[i,n]}(1 − θ_{i})^{k}] = q(k, n) + O(n^{−r/3}).  (54)

Now combine

E [∑_{i}(1 − θ_{i})^{k}] = ∑_{j=1}^{3} E [∑_{i} χ_{A_{j}[i,n]}(1 − θ_{i})^{k}]

with equations (54) and (53) to conclude that for k ≤ n^{γ} we have

E [∑_{i}(1 − θ_{i})^{k}] = q(k, n) + E [∑_{i} χ_{A_{3}[i,n]}(1 − θ_{i})^{k}] + O(n^{1−(r/3)}).

On the other hand, equation (49) just says

E [∑_{i}(1 − θ_{i})^{k}] = p(k, n) + O(kr̃n^{−r} + k^{c}(d − 1)^{−k/2}),

where p(k, n) is the polynomial in k given as the sum of the p_{j}(k)/n^{j}. Therefore

E [∑_{i} χ_{A_{3}[i,n]}(1 − θ_{i})^{k}]
= p(k, n) − q(k, n) + O(n^{1−(r/3)}) + O(kr̃n^{−r} + k^{c}(d − 1)^{−k/2})  (55)

for all k ≤ n^{γ}. Since A_{3}[i, n] implies |1 − θ_{i}| ≤ (1 − log^{−2} n) and thus |1 − θ_{i}|^{k} ≤ e^{O(log^{−2} n)} for k ≥ log^{4} n, we have

E [∑_{i} χ_{A_{3}[i,n]}|1 − θ_{i}|^{k}] = O(n^{−r/3})  (56)

for k ≥ log^{4} n for n sufficiently large. We conclude that

p(k, n) − q(k, n) = O(n^{1−r/3})  (57)

for all k with log^{4} n ≤ k ≤ n^{γ}.

Sublemma 11.2 Let g(k) be a polynomial in k of degree ≤ s − 1 such that |g(i)| ≤ 1 for integers i = a, a + 1, …, b for some integers a, b with a ≤ b. Then |g(i)| ≤ 2^{s} − 1 for integers i with

a − \frac{b − a}{s − 1} ≤ i ≤ a.

Proof We have (σ_{k} − 1)^{s}g = 0, and therefore

g(x) = ∑_{i=1}^{d} \binom{s}{i}(−1)^{i−1}g(x + hi)

for any x and h. Given i < a, let h = a − i and x = i in the above; x + h, x + 2h, …, x + sh are integers between a and b provided that

i + (a − i)s ≤ b,

so i ≥ (as − b)/(s − 1) or i ≥ a − (b − a)/(s − 1). If so, then

|g(i)| ≤ ∑_{i=1}^{d} \binom{s}{i}|g(x + hi)| ≤ ∑_{i=1}^{d} \binom{s}{i} = 2^{s} − 1.

□

Recall equation (57) and the fact that p and q are polynomials in k (for fixed n) of bounded degree. So applying the above sublemma for a = 2⌈(log^{4} n)/2⌉ and b = 2⌊n^{γ}/2⌋ implies that p(k, n)−q(k, n) = O(n^{1−(r/3)}) for 1 ≤ k ≤ log^{4} n. Equation (57) now holds for all 1 ≤ k ≤ n^{γ}. We conlude that equation (56) holds for all 1 ≤ k ≤ n^{γ}. Adding this to equation (53) yields the desired equation (50).

□

12 Magnification Theorems

In this section we use standard counting arguments to prove theorems implying “magnification” or “expansion” for “most” random graphs; here “most” means all graphs excepting a set of probability O(n^{−τ_{fund}}). These theorems will then be used with Lemma 11.1 to prove Theorems 1.1, 1.2, and 1.3.

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

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

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

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

(see [Alo86]; see [Dod84, SJ89, JS89] for related “edge magnification” results).

Definition 12.1 Say that a d-regular graph on n vertices is a γ-spreader if for every subset, A, of at most n/2 vertices we have

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

Theorem 12.2 Let G be a d-regular γ-spreader. Then for all i > 1 we have

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

Proof Since the graph is d-regular, we have |Γ(B)| ≥ |B| for all subsets of vertices, B. Taking B = Γ(A) yields

|Γ^{2}(A)| ≥ |Γ(A)| ≥ (1 + γ)|A|.

Hence G^{2}, the graph on V_{G} whose edges are paths in G of length 2 (and whose adjacency matrix is A_{G}^{2}), is a d^{2}-regular γ-magnifier. Now apply Alon’s result on magnification and eigenvalues to G^{2}, whose eigenvalues are λ_{i}^{2}(G).

□

We now establish that for all our models, a graph will be a γ-spreader for some fixed γ = γ(d) > 0 with probability 1 − O(n^{−τ_{fund}}).

Theorem 12.3 For any ϵ > 0 and even d ≥ 4 there is a γ > 0 such that G ∈ G_{n,d} is a γ-spreader with probability 1 − O(n^{−τ_{fund}}).

Later we shall prove this theorem for other models of random graphs, by very similar calculations. This theorem is easy for d sufficiently large; but when d = 4 (or later possibly d = 3) one has to calculate fairly carefully. Proof Fix A, B ⊂ {1, …, n}, and consider the event that Γ(A) ⊂ B. We will impose the condition that a = |A| ≤ n/2 and |B| = a + ⌊γa⌋.

Fix constants, γ, C with 0 < γ < 1/C. Consider the situation where |A| < C. In this case |B| = |A| = a. But since G is d-regular and we have d|A| edges leaving A, these edges comprise all edges incident upon B (since |B| = |A|). Thus A ∪ B is a union of connected components of G. But this cannot occur if G has no supercritical tangles of size at most 2C (since each connected component of G has λ_{Irred} = d − 1). For a constant C there are only a constant number of tangles of size at most 2C. Thus, by forsaking a probability of O(n^{−τ_{fund}}), we may assume that a = |A| ≥ C for any fixed constant, C (provided that we then take γ < 1/C) for sufficiently large n.

So consider a random permutation, π = π_{i}, and consider the event that π and π^{−1} map A to B. Let C_{1} = A ∩ B, C_{2} = A \ B, C_{3} = B \ A, and let c_{i} = |C_{i}|. We view π as determined by a perfect matching of a bipartite graph on inputs, I, and outputs, O, with I, O being copies of {1, …, n} (and i ∈ I mapped to π(i) ∈ O). Viewing π as a bipartite matching, it consists of (1) r edges from C_{1} to C_{1} (i.e., the I vertices corresponding to C_{1} to those O vertices corresponding to C_{1}), (2) c_{1} −r edges from C_{1} to C_{3}, (3) c_{1} −r edges from C_{3} to C_{1}, (4) c_{2} edges from C_{2} to C_{3}, and (5) c_{2} edges from C_{3} to C_{2}. (This is true since a C_{2} vertex, either input or output, must be paired with a C_{3} vertex, and a C_{1} vertex must be paired with either a C_{1} or C_{3} vertex.) So the event that π and π^{−1} map A to B with c_{1}, c_{2}, c_{3}, r, A, B all held fixed has probability

p(c_{1}, c_{2}, c_{3}, r) = [\binom{c_{1}}{r}^{2}r!] [\binom{c_{3}}{c_{1} − r}(c_{1} − r)!]^{2} ×

[\binom{c_{3} − c_{1} + r}{c_{2}}c_{2}!]^{2} [n(n − 1) ⋯ (n − 2c_{1} − 2c_{2} + r + 1)]^{−1}

(The first expression in square brackets corresponds to choosing r C_{1} to C_{1} edges; the second expression corresponds to choosing c_{1} − r C_{1} to C_{3} edges, and is squared to include choosing the C_{3} to C_{1} edges; etc.) The probability taken over all A, B of a given c_{1}, c_{2}, c_{3} (and with r fixed) is therefore at most

\binom{n}{c_{1}, c_{2}, c_{3}, n − c_{1} − c_{2} − c_{3}}p^{d/2}(c_{1}, c_{2}, c_{3}, r).  (58)

It suffices to show that this expression is O(n^{−s}) with s = τ_{fund} + 4, provided that a is sufficiently large (and at most n/2), since then we can sum equation (58) over the at most n^{4} relevant values of c_{1}, c_{2}, c_{3}, r. We should remind ourselves that c_{1}, c_{2}, c_{3}, r range over integers with

c_{1} + c_{2} = a, c_{1} + c_{3} = a + ⌊γa⌋, r ≤ c_{1}.

Furthermore, considering the expression defining p, we have c_{3} − c_{1} + r ≥ c_{2}. We now write

b = b(c_{1}, c_{2}, c_{3}, r, n) = \binom{n}{c_{1}, c_{2}, c_{3}, n − c_{1} − c_{2} − c_{3}}  (59)

= \frac{n!}{c_{1}! c_{2}! c_{3}! (n − c_{1} − c_{2} − c_{3})!}

and

p = p(c_{1}, c_{2}, c_{3}, r, n) = \frac{(c_{1}! c_{3}!)^{2} (n − 2c_{1} − 2c_{2} + r)!}{((c_{1} − r)! (c_{3} − c_{1} − c_{2} + r)!)^{2} r! n!}.  (60)

We make some general remarks about analyzing the factorials in the above two equations:

1. All factorials in the above equations are of the form (μn)! for some μ ∈ [0, 1]. Stirling’s formula m! ∼ (m/e)^{m}\sqrt{2πm} implies that

\frac{1}{n} log[(μn)!] = μ log(n/e) + μ log μ + O (\frac{log n}{n}) ,  (61)

where the constant in the O( ·) is independent of n and μ ∈ [0, 1].

2. In analyzing b and p above, we may ignore the μ log(n/e) term in equation (61). This is because b, p are balanced in that the sum of the numbers to which factorials are applied is the same in the numerator and denominator; in other words, the μ log(n/e) terms in the numerator will exactly cancel those in the denominator.

3. Let f(θ) = −θ log θ. We claim that for θ_{1}, θ_{2} ∈ [0, 1] we have

|f(θ_{1}) − f(θ_{2})| ≤ max(f(|Δθ|), f(1 − |Δθ|)), with Δθ = θ_{2} − θ_{1}.

Indeed, since f′′(θ) = −1/θ < 0 for θ > 0, f is concave in [0, 1], and so g(θ) = f(θ+Δθ)−f(θ) is decreasing in θ for Δθ fixed; so |g|’s maximum over an interval is taken at its endpoints, and since f(0) = f(1) = 0, the above claim is established.

Next, a Taylor expansion shows that −ϵ log ϵ ≥ −(1 − ϵ) log(1 − ϵ) for sufficiently small ϵ > 0. Hence there is an ϵ_{0} such that

|f(θ_{1}) − f(θ_{2})| ≤ f(|θ_{1} − θ_{2}|)  (62)

for all θ_{1}, θ_{2} ∈ [0, 1] with |θ_{1} − θ_{2}| ≤ ϵ_{0}.

Let ν_{i}, ρ, α, δ (i = 1, 2, 3) be the non-negative reals given by

c_{i} = ν_{i}n, r = ρn, a = αn, ⌊γa⌋ = δn.

We have that

ν_{1} + ν_{2} = α, ν_{1} + ν_{3} = α + δ, ρ ≤ ν_{1}, ρ ≥ ν_{1} + ν_{2} − ν_{3}.

We conclude that

|ν_{2} − ν_{3}| ≤ δ, |ν_{1} − ρ| ≤ δ.

It follows from equation (61), remark (2) below it, and equation (62), that we may replace ν_{3} with μ_{2} and ρ with ν_{1} in calculating (log b)/n and incur an additive error term of at most O(δ log δ). Thus we get

\frac{log b}{n} = h(ν_{1}, ν_{2}) + O (|δ log δ| + \frac{log n}{n}) ,

where

h(ν_{1}, ν_{2}) = −ν_{1} log ν_{1} − 2ν_{2} log ν_{2} − (1 − ν_{1} − 2ν_{2}) log(1 − ν_{1} − 2ν_{2}). (63)

Similarly we calculate

\frac{− log p}{n} = h(ν_{1}, ν_{2}) + O (|δ log δ| + \frac{log n}{n}) ,

i.e., we have the exact same equation (!) for log b replaced by − log p (this “coincidence” happens for the other models as well). Hence

\frac{log(bp^{2})}{n} = −h(ν_{1}, ν_{2}) + O (|δ log δ| + \frac{log n}{n}) .

Since ν_{1} + ν_{2} = α, we have either (or both) ν_{i} are ≥ α/2. Hence

h(ν_{1}, ν_{2}) ≥ −(α/2) log(α/2).

Now we claim that for any constant C > 0 there is a constant γ > 0 such that for all α ∈ [0, 1/2] we have

−α log α ≥ −C(γα) log(γα).  (64)

Indeed, for γ < 1 fixed we have

g(α) = \frac{(γα) log(γα)}{α log α} = γ + \frac{γ log γ}{log α}  (65)

is increasing for α ∈ [0, 1/2]. Hence it suffices to choose a γ > 0 sufficiently small so that

g(1/2) = \frac{(1/2) log(1/2)}{(γ/2) log(γ/2)} ≥ C,

so that

g(α) ≥ g(1/2) ≥ C,

which along with equation (65) yields equation (64).

It follows that for sufficiently small γ > 0 we have

\frac{log(bp^{2})}{n} ≥ −(α/2) log(α/2) + O (|δ log δ| + \frac{log n}{n}) ,

and, since δ ≤ γa/n = γα, this expression is

≥ −(α/4) log(α/2) + O (\frac{log n}{n}) .

Hence for any constant, C_{1}, there is a C_{2} such that if a ≥ C_{2} (i.e., α ≥ C_{2}/n) then

\frac{log(bp^{2})}{n} ≤ \frac{−C_{1} log n}{n}

for all n sufficiently large. In other words bp^{d/2}, i.e., the expression in equation (58), is at most n^{−C_{1}}; this, by the discussion after equation (58), completes the proof.

□

Theorem 12.4 Theorem 12.3 holds in the models H_{n,d}, I_{n,d}, and J_{n,d}.

Proof In H_{n,d} each permutation occurs with probability at most n times its probability in G_{n,d}. Therefore the same analysis goes through, except that p is multiplied by at most a factor of n. This changes the expression for n^{−1} log(bp^{2}) by an O(n^{−1} log n) factor, so the same proof carries over.

For I_{n,d} we again set C_{i} and c_{i} as before. A perfect matching in {1, …, n} will have (1) r vertices of C_{1} paired amongst themselves, (2) c_{1} −r vertices of C_{1} paired with C_{3} vertices, and (3) c_{2} vertices of C_{2} paired with C_{3} vertices. This data determines the pairing for r+2(c_{1}−r)+2c_{2} vertices. The expression for b, representing the number of ways the C_{i} can be chosen, is the same as before. We now derive an expression for p, the probability that a single perfect matching matches all A vertices to those in B.

For an even integer, m, let m odd factorial be

m!_{odd} = (m − 1)(m − 3) ⋯ 3 = \frac{m!}{2^{m/2}(m/2)!},

which is just the number of perfect matchings of m elements. Stirling’s formula yields

m!_{odd} ∼ \sqrt{2} (m/e)^{m/2}

(so that for our purposes m!_{odd} can be regarded as replacable by the square root of m!).

We have

p = p(\{c_{i}\}, r, n) = [\binom{c_{1}}{r}r!_{odd}] [\binom{c_{3}}{c_{1} − r}(c_{1} − r)!]

× [\binom{c_{3} − c_{1} + r}{c_{2}}c_{2}!] \frac{(n − 2c_{1} − 2c_{2} − r)!_{odd}}{n!_{odd}} .

We get that − log p is

\frac{h(ν_{1}, ν_{2})}{2} + O (|δ log δ| + \frac{log n}{n}) ,

with h as in equation (63). Since b is unchanged, by analyzing as before we see that there is a fixed γ > 0 such that for any constant C_{1} there is a C_{2} such that bp^{3} = O(n^{−C_{1}}) provided that a ≥ C_{2}.

Next we consider J_{n,d}. Let G be a random graph in J_{n,d}, so V_{G} = {1, …, n}. Consider the graph G′ formed by adding one new vertex, w = n + 1, to G and replacing each half-loop about a vertex, v, in G by an edge from v to w. Then G′ is precisely distributed as an element of I_{n+1,d}; indeed, a perfect matching on V_{G′} matches w to some element of V_{G} = {1, …, n} and then randomly matches the remaining n − 1 elements of V_{G}.

Now we know that G′ is a γ-spreader with probability 1 − O(n^{−τ_{fund}}). But for any A ⊂ V_{G}, Γ_{G′}(A) consists of at most one more vertex than Γ_{G}(A). Hence for |A| ≤ |V_{G}|/2 and G′ being a γ-spreader, we have

|Γ_{G}(A) \ A| ≥ γ|A| − 1 ≥ γ′|A|,

where γ′ = γ − (1/c′), provided that |A| ≥ c′. Hence G is a γ-spreader on sets, A, of size max(c, c′) ≤ |A| ≤ n/2. On smaller sets, A, we have G is a γ′-spreader with probability 1 − O(n^{−τ_{fund}}), assuming γ′ ≤ 1/ max(c, c′), by the argument given before for G_{n,d}. (Notice that the τ_{fund} for I_{n,d} and J_{n,d} are the same.) Hence a random graph in J_{n,d} is a γ′-spreader with probability 1 − O(n^{−τ_{fund}}).

□

13 Finishing the G_{n,d} Proof

Here we quickly finish the proof of Theorem 1.1, which proves Alon’s conjecture for G_{n,d}.

Fix a value of r to be specified later. Let Ψ′ = Ψ_{eig}[r − 1] be the set of supercritical tangles of order less than r, and let Ψ = Ψ_{min}[r − 1] (which we recall is the set of minimal Ψ′ = Ψ_{eig}[r − 1] elements with respect to inclusion); we know that Ψ is finite by Lemma 9.2, and we recall that if G contains a Ψ′ tangle then it contains an element of Ψ. The probability that χ_{Ψ}(G) = 1, i.e., that G contains at least one element of Ψ, is at most O(n^{−τ_{fund}}), since every one of the finitely many tangles in Ψ occurs with probability proportional to 1/n to the order of tangle (Theorem 4.7), and each tangle order is at least τ_{fund}. Given that χ_{Ψ}(G) = 0, we have that G contains no supercritical tangle of order less than r, and hence no irreducible closed walk can fail to be (S, Ψ′)-selective for any S. Hence for all S and k we have

χ_{Ψ}(G) = 0 implies SSIT_{S,Ψ′}(G; k) = SIT(G; k).

Thus

E [(1 − χ_{Ψ})SSIT_{S,Ψ′}(G; k)] = E [(1 − χ_{Ψ})SIT(G; k)] .

Now according to Theorem 10.3 we have

SIT(G; k) = ∑_{i=1}^{n} μ_{1}^{k}(λ_{i}) + μ_{2}^{k}(λ_{i}) + (1 + (−1)^{k})(d − 2)/2,

for even k ≥ 2, where

μ_{1,2}(λ) = \frac{λ ± \sqrt{λ^{2} − 4(d − 1)}}{2}.

In other words, there are nd numbers ν_{i}, such that SIT(G; k) is the sum of the k-th powers of these numbers. Also for each i we have ν_{i} is not real only if it is of absolute value \sqrt{d − 1}. Combining this and Theorem 9.3 we see that

θ_{i} = 1 − (1 − χ_{Ψ})ν_{i}/(d − 1)

are random variables that satisfy the conditions of Lemma 11.1 for each i (and G). It follows that

E [(1 − χ_{Ψ}) ∑_{i=1}^{n} ∑_{j such that |μ_{j}(λ_{i})|≤(d−1)(1−log^{−2} n)} μ_{j}(λ_{i})^{k}] = O(Dn^{1−(r/3)} +k^{c}(d−1)^{−k/2})

(66)

for all k with 1 ≤ k ≤ n^{γ} for some constant γ > 0 depending only on r.

According to Theorems 12.2 and 12.3 there is an ϵ > 0 such that with probability 1 − O(n^{−τ_{fund}}) we have |λ_{i}| ≤ d − ϵ for all i ≠ 1; in this case there is an ϵ′ = ϵ′(ϵ) > 0 such that |μ_{j}(λ_{i})| ≤ (d − 1) − ϵ′ for all j = 1, 2 and i ≠ 1.

We claim that for any G and an even integer k we have

∑_{i s.t. μ_{1,2}(λ_{i}) not real} ∑_{j=1}^{2} μ_{j}(λ_{i})^{k} ≥ −2(n − 1)(d − 1)^{k/2}

indeed, if μ_{j}(λ_{i}) is not real, it is of absolute value \sqrt{d − 1}; if μ_{j}(λ_{i}) is real then its k-th power is non-negative.

Now let A be the event that χ_{Ψ} = 0 and that |μ_{j}(λ_{i})| ≤ (d − 1) − ϵ′ for all j = 1, 2 and i ≠ 1. Let B = B(η) be the event that for some j and some i ≠ 1 we have |μ_{j}(λ_{i})| ≥ e^{η}\sqrt{d − 1} for an arbitrary fixed η > 0. A∩B implies that for even integer k we have

∑_{i=2}^{n} ∑_{j=1}^{2} μ_{j}(λ_{i})^{k} ≥ (e^{η}\sqrt{d − 1})^{k} − 2(n − 2)(d − 1)^{k/2}.

It follows, using equation (66), that for even k,

Prob \{A ∩ B\} (e^{η}\sqrt{d − 1})^{k} ≤ E [ ∑_{i s.t. μ_{1,2}(λ_{i}) real} ∑_{j=1}^{2} μ_{j}(λ_{i})^{k}]

= E [∑_{i=2}^{n} ∑_{j=1}^{2} μ_{j}(λ_{i})^{k}] − E [ ∑_{i s.t. μ_{1,2}(λ_{i}) not real} ∑_{j=1}^{2} μ_{j}(λ_{i})^{k}]

≤ O(Dn^{1−(r/3)}(d − 1)^{k} + k^{c}(d − 1)^{k/2}) + 2(n − 1)(d − 1)^{k/2}.

We now take

k = 2 ⌈\frac{r log n}{3 log(d − 1)}⌉ .

We have

(k/2) − 1 ≤ \frac{r log n}{3 log(d − 1)} ≤ k/2.

Hence

n^{−r/3} ≤ (d − 1)^{−(k/2)+1},

and so

Prob {A ∩ B} ≤ c max(k^{c}, n)e^{−kη}
≤ cne^{−kη} = cnn^{−αr},

where α = (2/3)η/ log(d − 1), i.e. α is a positive constant (depending only on η and d). Choosing r so that αr − 1 > τ_{fund}, we have

Prob {A ∩ B} = O(n^{−τ_{fund}}).

But we have already seen (Theorems 12.2 and 12.3) that

Prob {A^{c}} = O(n^{−τ_{fund}}),

where A^{c} is the complement of A. Hence

Prob {B} = Prob {B ∩ A} + Prob {B ∩ A^{c}} = O(n^{−τ_{fund}}).

For any ϵ > 0 there is an η > 0 such that |λ| ≥ 2\sqrt{d − 1} + ϵ implies |μ_{i}(λ)| ≥ e^{η}\sqrt{d − 1} for at least one i, which is the event B = B(η) above. It follows that for any ϵ > 0 we have

Prob \{|λ_{i}| ≥ 2\sqrt{d − 1} + ϵ for some i > 1\} = O(n^{−τ_{fund}}).

This (and Theorem 2.11) proves Theorem 1.1.

14 Finishing the Proofs of the Main Theorems

We now complete the proofs of Theorems 1.2 and 1.3, i.e., we establish the Alon conjecture for H_{n,d}, I_{n,d}, and J_{n,d}.

The proofs of the theorems are as the proof for G_{n,d}. We only need to establish the following results for the different models of random graph:

1. Labelling: The model comes with edges labelled from a set Π such that to each π ∈ Π we associate a π^{−1} ∈ Π such that (π^{−1})^{−1} = π (in other words, the elements of Π are paired, with the possibility that an element is paired with itself).

2. Coincidence: If k of the random edges have been determined, and if we fix any two vertices, v, w, in the graph, then the probability that an edge of a given label takes v to w is at most c/(n − ck) for some constant c. We have only briefly mentioned coincidences in this paper, but our Lemmas 5.7 and 5.8, proven in [Fri91], require a property like this.

3. Expansion with Error: Consider a Π-labelled graph, H, with vertices a subset of {1, …, n}, that can occur as a subgraph of a graph in our model. The probability that H occurs must depend only on the number of edges, a_{π}, of each label, π (of course, a_{π} = a_{π^{−1}}). Furthermore, this probability times the number subsets of {1, …, n} of size V_{H} is, for every positive integer r,

E_{symm}(H)_{n} = (∑_{i=0}^{r−1} \frac{p_{i}(a⃗)}{n^{i}}) + \frac{error}{n^{r}},

where p_{i} are polynomials in a⃗ (where a⃗ is the collection of all a_{π}) and where

|error| ≤ ck^{r′}

for all k ≤ n/c, where c_{1}, r′ depend only on r. Furthermore, p_{i} = 0 if i is less than the order of H.

4. Simple Word Sum: Let Irred_{k,σ,τ} be those words that begin with σ, end in τ, and are irreducible (meaning no consecutive occurrence of π and π^{−1}). Then for any polynomial, p = p(a⃗) (with a⃗ as above), we require

∑_{w∈Irred_{k,σ,τ}} p(a_{1}(w), …, a_{d/2}(w), k) = (d − 1)^{k}Q_{1}(k) + E(k) (67)

for a polynomial, Q_{1}, and a function E with |E(k)| ≤ ck^{c} for some constant c (i.e., the above sum is super-d-Ramanujan).

5. τ_{fund} determination: We must determine τ_{fund} for the model.

6. Spreading: There is a constant γ > 0 such that the probability that a random graph has |λ_{i}| ≥ d − γ for some i ≠ 1 is of order at most n^{−τ_{fund}}.

We have already shown spreading and determined τ_{fund} for all three models. The labelling of the models is quite simple: H_{n,d} is labelled like G_{n,d}; I_{n,d} is labelled with Σ = {σ_{1}, …, σ_{d}} where σ_{i}^{−1} = σ_{i} (each σ_{i} represents a perfect matching); J_{n,d} is labelled with Σ ∩ T with Σ as before and T = {τ_{1}, …, τ_{d}} with τ_{i}^{−1} = τ_{i}, and where the σ_{i} represent the near perfect matching and the τ_{i} represents the single completing half-loop for σ_{i}.

Coincidence is easily checked for all three models.

We address the issue of Simple Word Sum. The word sum for H_{n,d} is the same as for G_{n,d}. For I_{n,d}, the technique of Lemma 2.11 of [Fri91] reduces the matter to the irreducible eigenvalues of a vertex with d half-loops; since these eigenvalues are the eigenvalues of a d × d matrix which is 0 on the diagonal and 1’s elsewhere, the eigenvalues are d − 1 with multiplicity 1 and −1 with multiplicity d − 1. Hence the simple word sum of equation (67) is given by

(d − 1)^{k}Q_{1}(k) + (−1)^{k}Q_{2}(k)  (68)

where Q_{i} are polynomials. For J_{n,d} we can break the sum by how many halfloops are involved. For a fixed set of half-loops involved in the irreducible word, the sum is a convolution of functions of the form in equation (68), which by Theorem 7.2 is again super-d-Ramanujan.

We now establish Expansion with Error for the three models. Equation (16) has the H_{n,d} analogue

P (w; t⃗) = ∏_{i=1}^{d/2} \frac{(n − a_{i} − 1)!}{(n − 1)!}.

Now recall the proof of Theorem 5.5, especially equations (19) and (20). For H_{n,d}, we have

E_{symm}(H)_{n} = n(n − 1) ⋯ (n − v + 1) ∏_{i=1}^{d/2} \frac{(n − a_{i} − 1)!}{(n − 1)!}.  (69)

= n^{v−e}g(1/n),

with g as in equation (19) with b_{1}, …, b_{v} being 0, 1, …, v − 1 and c_{1}, …, c_{e} being the collection of the sequences 1, 2, …, a_{i}. Hence for a walk of length at most k we have

∑ b_{j} + ∑ c_{j} ≤ \binom{k}{2} + \binom{k + 1}{2} = k^{2}.

Accordingly Expansion with Error holds for H_{n,d} with expansion polynomials determined by equation (69), and with error term bounded by

e^{rk/(n−k)}k^{2r};

this bound is ≤ ck^{r′} for all k ≤ n with r′ = 2r and c = e^{r}.

Similarly for I_{n,d} we have the analogue

P (w; t⃗) = ∏_{i=1}^{d} \frac{(n − a_{i})!_{odd}}{n!_{odd}} .

The analysis goes through essentially as before; in the error bound we have ∑ b_{j} is again \binom{k}{2}, but this time the ∑ c_{j} is as large as

1 + 3 + 5 + ⋯ + (2k − 1) = k^{2}

(taking one a_{i} = 2k and the rest 0). So Expansion with Error holds for I_{n,d} with error term bounded by

e^{rk/n} (k^{2} + \binom{k}{2})^{r} ≤ e^{rk/n}(2k)^{2r}.

For J_{n,d}, consider a random 1-regular graph, G′, consisting of a near perfect matching plus one complementing half-loop on the vertex set {1, …, n}. Notice that the number of such graphs is n(n − 1)!_{odd}. Hence the probability of occurrence of a specified half-loop and a other matchings in G′ is

\frac{(n − 1 − 2a)!_{odd}}{n(n − 1)!_{odd}} = \frac{1}{n(n − 2) ⋯ (n − 2a)},

and the probability of a specified matchings (with no specified half-loop) is

\frac{(n − 2a)(n − 1 − 2a)!_{odd}}{n(n − 1)!_{odd}} = \frac{1}{n(n − 2) ⋯ (n − 2a − 2)}.

So for any specification of half-loops in H, i.e., any fixing of each a_{τ_{i}} to 0 or 1, E_{symm}(H)_{n} is a polynomial in the a_{σ_{i}}’s; this makes E_{symm}(H)_{n} a polynomial in the a⃗, namely

∑_{I⊂{1,...,d}}(p_{I}(a_{σ_{1}}, …, a_{σ_{d}}) ∏_{i∈I} a_{τ_{i}} ∏_{i∉I}(1 − a_{τ_{i}})).

We also see that, in the terminology above, ∑ b_{j} = \binom{k}{2} and ∑ c_{j} ≤ 2\binom{k−1}{2}. Hence Expansion with Error holds for J_{n,d} as well.

This establishes the six required results mentioned at the beginning of this section for the models H_{n,d}, I_{n,d}, and J_{n,d}. Theorems 1.2 and 1.3 follow.

15 Closing Remarks

We make a number of final remarks.

Stronger conjectures: As mentioned before, numerical experiments indicate that the average (and median) λ_{2} for a random graph is 2\sqrt{d − 1} + ϵ(n), where ϵ(n) is a negative function (tending to 0 as n → ∞). By the results of Friedman and Kahale (extending the Alon-Boppana result), −ϵ(n) ≤ O(log^{−2} n) (see [Fri93]). However, the trace method, even with selective traces, seems to require some fundamental new idea in order to have any hope of achieving ϵ(n) that is zero or negative.

Critical d: As mentioned before, when there is a critical tangle of order strictly less than that of any hypercritical tangle, then our techniques leave a gap in that we can only prove λ_{2} > 2\sqrt{d − 1} with probability at least c/n^{s} where s > τ_{fund}. This case is extremely interesting, since it seems that there should be a theorem that closes this gap, and such a theorem would either get around a poorly bounded W_{T̃,S}(M_{1}, M_{2}) or improve the very interesting Theorem 3.13 (or do something else).

Relative Alon Conjecture: Following [Fri03], it seems quite possible to relativize the main theorems in this paper. Namely, fix a “base” graph, B, (or, more generally, a “base” pregraph, in the sense of [Fri93]). Fix an ϵ > 0. Then we believe that most random coverings of B of degree n have all “new” eigenvalue ≤ ϵ + ρ, where ρ is the spectral radius of the universal cover of B.

Similarly, we can ask for ϵ to be zero or even a negative function of n. See [Fri03, FT02] for further discussion and a result in this direction.

Alternate Proof with Trace (see the end of Section 2): It may be possible to analyze the expected irreducible trace over all of G_{n,d}. As remarked in Theorem 2.12 and the discussion thereafter, the coefficients of g_{i}(k) there could no longer be d-Ramanujan. It may be possible to analyze selective traces without discarding contributions from tangled graphs. In other words, if we better understood how selectivity affected irreducible traces, we might not need Section 9 (and certain parts of our understanding of these traces might improve). Clearly selectivity in G can be expressed in terms of walks in an induced subgraph of a “higher block presentation” of G (see [LM95, Kit98]). However, it is not clear what can be said about the eigenvalues of induced subgraphs of a higher block presentation; the author has only some weak results in this directions (see [Fri]).

Glossary

This glossary contains a term or a piece of notation, followed by a colon (:), followed by a brief description, followed by the page number(s) where the term/notation is explained.

a_{j}: the number of π_{j} and π_{j}^{−1} appearing in a word or form, 44, 45, 49, 52

bead: a vertex with indegree and outdegree 1 (or, for undirected graphs, degree 2) with no self-loops, 21

c_{G}(u, v; k): the number of walks of length k from u to v in G, 22

closed walk: a walk beginning and ending at the same vertex, 5

critical: a tangle with λ_{Irred} = \sqrt{d − 1}, 34

E[Γ]_{n}: The expected value of the number of closed walks corresponding to a potential walk class (which depends only the the form of the potential walk), 52 expansion polynomials: The polynomials p_{i} = p_{i}(a_{1}, …, a_{d/2}, v) giving

the 1/n expansion of E_{symm}(w, t⃗), 45

form: an oriented, Π-labelled graph with edges and vertices numbered that is meant to represent the graph traced out by a potential word, forgetting about the particular choices in {1, …, n} of the vertices, 51

generating function: a power series, Σ_{k}a_{k}z^{k}, formed from coefficients a_{k}, 23

G_{Irred}: edge graph of G with edges joined only when they form an irreducible path, 27

G_{n,d}: space of random graphs formed from d/2 permutations, 2

graph: a directed graph with a origin/terminal reversing pairing of its edges, 19

half-loop: a self-loop paired with itself (in a graph), 20

H_{n,d}: random graph space formed by d/2 permutations that are cycles of length n, 3

hypercritical: a tangle with λ_{Irred} > \sqrt{d − 1}, 34

I_{n,d}: random graph model of d perfect matchings (n even), 3

IrredTr (A, k): the number of closed irreducible walks of length k in the graph underlying A, 8

irreducible: a walk (resp. word) that has no consecutive steps of an edge (resp. letter) and its inverse, 5

IrSelTr_{S,Ψ}(G; k): k-th irreducible (S, Ψ)-selective trace of G, i.e., the number of irreducible closed walks of length k in G such that no subpath of length at most S traces out a tangle in Ψ, 58

J_{n,d}: random graph model formed from d permutations each with exactly one fixed point (n odd), 4 λ_{i}(G): i-th largest eigenvalue of the adjacency matrix of a finite graph, 1

λ_{1}(G): the sup over all values (c_{G}(v, v; k))^{k}, 22

λ_{Irred}(G): the largest eigenvalue of G_{Irred}, 27

new type: a type with some additional information specified, such as a partition of the types edges into a “long” and a “fixed” edge set, 54

Ω-type: a generalization of type that incorporates information of an included tangle, Ω, 87

p_{i} = p_{i}(a_{1}, …, a_{d/2}, v): the expansion polynomials, 45

supercritical: a tangle with λ_{Irred} ≥ \sqrt{d − 1}, 34

τ_{fund}: smallest order of a supercritical tangle, 2, 3

type: a graph representing a number of forms, where we forget certain features of the form, such as its Π-labelling and all or almost all its degree two vertices, 53

variable-length graph (VLG): a graph, directed or undirected, with a positive integral “length” associated to each edge, 21

VLG: variable-length graph, 21

W_{Γ}, W_{T} , W_{T′}: the number of potential walk classes or legal walks on a form, type, or new type with various additional restrictions (such as irreducibility), 52, 59

whole-loop: two self-loops (about the same vertex) paired with each other (in a graph), 20

References

[AFKM86] R. Adler, J. Friedman, B. Kitchens, and B. Marcus. State splitting for variable length graphs. IEEE Transactions on Information Theory, 32(1):108–115, January 1986.

[Alo86] N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. Theory of computing (Singer Island, Fla., 1984).

[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.

[Buc86] Marshall W. Buck. Expanders and diffusers. SIAM J. Algebraic Discrete Methods, 7(2):282–304, 1986.

[DD89] Warren Dicks and M. J. Dunwoody. Groups acting on graphs. Cambridge University Press, Cambridge, 1989.

[Dod84] Jozef Dodziuk. Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc., 284(2):787–794, 1984.

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

[FKS89] J. Friedman, J. Kahn, and E. Szemerédi. On the second eigenvalue of random regular graphs. In 21st Annual ACM Symposium on Theory of Computing, pages 587–598, 1989.

[Fri] Joel Friedman. SVD misalignment and eigenvalue separation. In preparation.

[Fri91] Joel Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, 11(4):331–362, 1991.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke Math. J., 69(3):487–525, 1993.

[Fri03] Joel Friedman. Relative expanders or weakly relatively Ramanujan graphs. Duke Math. J., 118(1):19–35, 2003.

[FT02] Joel Friedman and Jean-Pierre Tillich. Generalized Alon-Boppana theorems and error-correcting codes. May 2002. preprint.

[FTP83] Alessandro Figà-Talamanca and Massimo A. Picardello. Harmonic analysis on free groups. Marcel Dekker Inc., New York, 1983.

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

[GJKW02] Catherine Greenhill, Svante Janson, Jeong Han Kim, and Nicholas C. Wormald. Permutation pseudographs and contiguity. Combin. Probab. Comput., 11(3):273–298, 2002.

[God93] C. D. Godsil. Algebraic combinatorics. Chapman & Hall, New York, 1993.

[HMS91] Chris D. Heegard, Brian H. Marcus, and Paul H. Siegel. Variablelength state splitting with applications to average runlengthconstrained (ARC) codes. IEEE Trans. Inform. Theory, 37(3, part 2):759–777, 1991.

[Joh90] D. L. Johnson. Presentations of groups. Cambridge University Press, Cambridge, 1990.

[JS89] Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149–1178, 1989.

[Kit98] Bruce P. Kitchens. Symbolic dynamics. Springer-Verlag, Berlin, 1998.

[KW01] Jeong Han Kim and Nicholas C. Wormald. Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs. J. Combin. Theory Ser. B, 81(1):20– 44, 2001.

[LM95] Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995.

[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.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[Mar88] G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

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

[Mor94] Moshe Morgenstern. Existence and explicit constructions of q +1 regular Ramanujan graphs for every prime power q. J. Combin. Theory Ser. B, 62(1):44–62, 1994.

[Nil91] A. Nilli. On the second eigenvalue of a graph. Discrete Math., 91(2):207–210, 1991.

[Sen81] E. Seneta. Nonnegative matrices and Markov chains. Springer Series in Statistics. Springer-Verlag, New York, second edition, 1981.

[SJ89] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput., 82(1):93–133, 1989.

[SW49] Claude E. Shannon and Warren Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1971/1949.

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

[Woe00] Wolfgang Woess. Random walks on infinite graphs and groups. Cambridge University Press, Cambridge, 2000.

[Wor99] N. C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), pages 239–298. Cambridge Univ. Press, Cambridge, 1999.