Relative Expanders or Weakly Relatively Ramanujan Graphs

Joel Friedman^{∗}

April 8, 2002

Abstract

Let G be a fixed graph with largest (adjacency matrix) eigenvalue λ_{0} and with its universal cover having spectral radius ρ. We show that a random cover of large degree over G has its “new” eigenvalues bounded in absolute value by roughly \sqrt{λ_{0}ρ}.

This gives a positive result about finite quotients of certain trees having “small” eigenvalues, provided we ignore the “old” eigenvalues. This positive result contrasts with the negative result of Lubotzky-Nagnibeda that showed that there is a tree all of whose finite quotients are not “Ramanujan” in the sense of Lubotzky-Philips-Sarnak and Greenberg.

Our main result is a “relative version” of the Broder-Shamir bound on eigenvalues of random regular graphs. Some of their combinatorial techniques are replaced by spectral techniques on the universal cover of G. For the choice of G that specializes our theorem to the Broder-Shamir setting, our result slightly improves theirs.

MSC 2000 numbers: Primary: 05C50; Secondary: 05C80, 68R10.

∗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.

1 Introduction

The term Ramanujan has arisen in connection with the eigenvalues or spectrum of a graph, or more precisely the graph’s adjacency matrix^{1}. In [Gre95], a finite graph, X, is called Ramanujan if Spec(X) ⊂ [−ρ, ρ]∪{−λ_{0}, λ_{0}} where ρ is the spectral radius of X’s universal cover (i.e. of the adjacency matrix thereof), and λ_{0} is the Perron-Frobenius (or largest) eigenvalue of X. If X is k-regular then this means that λ = ±k or |λ| ≤ 2\sqrt{k − 1} for each eigenvalue, λ, of X; this agrees with the definition in [LPS88].

Lubotzky and Nagnibeda (see [LN98]) have shown that there are trees, T, with finite quotients where none of these quotients are Ramanujan in the above sense. We shall soon explain why this negative result may be considered surprising. The main goal of this paper is to show that there is a positive result for “most” finite quotients of a tree, provided that one weakens the notion of being Ramanujan and provided that one considers a “relative” notion of being weakly Ramanujan (we also conjecture that “weakly Ramanujan” can be replaced by “Ramanujan”). To do so we “relativize” the Broder-Shamir method for bounding the second eigenvalue (in [BS87]), generalizing their result and slightly improving it in the original setting (and, to us, the special setting) of regular graphs.

It is known that for certain k there are infinitely many k-regular graphs that are Ramanujan (see [LPS88, Mar88, Mor94]). Furthermore, it is known that “most” k-regular graphs^{2} with k even are “weakly Ramanujan” in the following sense. Say that X is ν-weakly Ramanujan if Spec(X) ⊂ [−ν, ν] ∪ {−λ_{0}, λ_{0}} (also we usually insist that ν < λ_{0} to prevent a trivial situation). Then building a k-regular graph from k/2 permutations (assuming that k is even), a number of papers have shown that most graphs are ν-weakly Ramanujan (see [BS87, FKS89, Fri91]) for certain values of ν; for example, in [Fri91] it is shown that there is a constant C such that most k-regular graphs on a sufficiently large number of vertices are ν-weakly Ramanujan with ν = 2\sqrt{k} + 2 log k + C. Furthermore, numerical experiments (like those in [Fri93]) suggest that most random regular graphs on a large number of vertices are Ramanujan.

1It arose because the proof that certain graphs’ eigenvalues (in [LPS88]) were small relied upon known parts of the Ramanujan conjectures.

2Here “most” means in the sense of the random k-regular graph used by Broder and Shamir, to be described later in this paper. This is not the same as the “uniform regular graph” model, but the two models are contiguous (see [GJKW]).

It therefore seems plausible to conjecture that most k-regular graphs are Ramanujan, i.e. most finite quotients of the k-regular tree, T, are Ramanujan (where the word “most” is given any “reasonable” interpretation). This makes the negative result of Lubotzky and Nagnibeda surprising: the notion of Ramanujan seems highly dependent on the tree.

For what follows, we recall the notion of a covering map. If G, H are undirected graphs without multiple edges or self-loops, a morphism (i.e., graph homomorphism) π: H → G is called a covering map if for every vertex, h, of H, π gives a bijection from the edges incident upon h with those incident upon π(h). Also, G is called the base graph and H the covering graph. If G is connected then the size of π^{−1} of a vertex or edge is constant, and is called the degree of the covering map. We can also define “covering maps” for graphs that are directed and/or have multiple edges and/or self-loops (see section 5).

If A_{H}, A_{G} are the adjacency matrices of finite graphs H, G with a covering map π: H → G, then any A_{G} eigenfunction, f, pulls back to an eigenfunction π^{∗}f = f ∘ π of A_{H}. Such an eigenfunction is called an old eigenfunction (for π), and the resulting eigenvalue of A_{H} from A_{G} is an old eigenvalue. Since A_{G} is symmetric, the linear span of the old eigenfunctions is the space of functions which are pullbacks, π^{∗}f = f ∘ π, of an arbitrary f on G; this space is called the space of old functions. Its orthogonal complement is called the space of new functions, which are just those functions that sum to zero on each “vertex fiber,” π^{−1}(v), for all vertices, v, of G. A new eigenfunction/value is an eigenfunction/value coming from a new function. Since A_{H} is symmetric, the new and old eigenpairs give a complete set of eigenpairs of A_{H}.

The result of Lubotzky and Nagnibeda uses the fact that there are many graphs, G, such that any finite quotient of G’s universal cover admits a covering map to G. If such a G’s eigenvalues are outside [−ρ, ρ] ∪ {−λ_{0}, λ_{0}} as above, none of T ’s finite quotients will be Ramanujan. In this paper we show that in this situation the new eigenvalues, i.e., those not coming from G, are weakly Ramanujan.

More generally, in this paper we study the following notion.

Definition 1.1 A covering map of graphs, π: H → G, is called ν-weakly Ramanujan if the new spectrum of the cover lies in [−ν, ν], and is called Ramanujan if we may take ν to be the spectral radius of the universal cover of G.

We shall prove a generalization of the Broder-Shamir result (the expected eigenvalue result in [BS87]). For any graph, G = (V, E), we form a probability space of degree n covers of G, denoted C_{n}(G), as follows: our random graph has vertex set V_{n} = V ×{1, …, n}, and for each e ∈ E we choose an arbitrary orientation of e, (u, v), and choose uniformly a random permutation, σ_{e}, on {1, …, n} (permutations of different edges are chosen independently); we form edges from (u, i) to (v, σ_{e}(i)) for all i. This model of random cover (sometimes “random lift”) has also been studied in [AL02, AL, ALM02, LR].

Theorem 1.2 Let G be a fixed graph, let λ_{0} denote the largest eigenvalue of G, and let ρ denote the spectral radius of the universal cover of ρ. There is a function α(n) such that α(n) → 0 as n → ∞ and positive constants C_{1}, C_{2} such that the expected value,

E_{C_{n}(G)} ( ∑_{λ new} λ^{t}) ≤ C_{2}ν^{t},

where

ν = \sqrt{λ_{0}ρ} + α(n),

and 0 < t ≤ 2⌊C_{1} log n⌋. This theorem holds for G containing multiple edges and self-loops, with C_{n}(G) replaced by any Broder-Shamir family of models of a random cover of degree n (as in section 5).

In particular, the probability of a graph in C_{n}(G) being ν-weakly Ramanujan with ν = \sqrt{λ_{0}ρ} + α(n) goes to one as n → ∞ for some function, α(n), with α(n) → 0 as n → ∞.

A more precise form of Theorem 1.2 and some of its implications (including a precise description of the α(n) above) are given in sections 2 and 5.

We claim that the above theorem gives a positive result as mentioned earlier. Indeed, it is not hard to see that there are many trees, T (including those occurring in [LN98]), such that for some graph, G, any finite quotient of T occurs in C_{n}(G) for the appropriate n; for example, from [LN98] there are graphs, G (without half-loops), such that every finite quotient of G’s universal cover admits a covering map to G. It is easy to see that all covers of G (without half-loops) occur in C_{n}(G), and that the probability of a cover, H, of G = (V, E) of occurring is

(n!)^{|V |−|E|}/|Aut(H/G)|,

where Aut(H/G) is the group of automorphisms of H over G (see [Fri93]). C_{n}(G) becomes a seemingly reasonable model of a probabilistic space of finite quotients of T of a given number of vertices. Our generalization of the Broder-Shamir result says that most of the resulting covering maps are weakly Ramanujan.

We remark that there are trees, T, that admit a finite quotient (and therefore infinitely many finite quotients) such that there is no “minimal” finite quotient, G, covered by all finite quotients. However, according to [Fri93], there is a minimal pregraph (in the sense of [Fri93]) that is covered by all finite quotients. It is therefore important to generalize the results of this paper to pregraphs, e.g., to generalize Theorem 1.2 to allow G to be a pregraph. This is the subject of a work of the author in progress.

If in Theorem 1.2 we take G to have one vertex with d/2 whole-loops (see section 5), then we are in the setting of d-regular graphs generated by d/2 permutations as in [BS87]; however our result slightly improves upon that in [BS87]. One key point in the Broder-Shamir trace method is to estimate the number of closed walks from a given vertex on a tree of a given length; their estimate (their Lemma 5) involves a weaker estimate of this number than the estimate we use; we shall use the beautiful (and simple) estimate based on the spectral radius of the tree, as done in [Buc86].

We mention that our strengthening of the Broder-Shamir result is interesting for the following reason. The eignevalue estimates for random graphs proven by the author and by Kahn-Szemerédi (in [FKS89, Fri91]) involve undetermined constants; hence there is no known fixed value of the degree, k, for which their estimates are non-trivial; it is only known that as k → ∞ their results become interesting (and ultimately improve upon those of Broder and Shamir). However, the original Broder-Shamir result yields (α(n)+2^{1/2}k^{3/4})- weakly Ramanujan (for “most” graphs) where α(n) → 0 as n → ∞ (for k even); this result is interesting for every even k > 4. So our strengthening of the Broder-Shamir result gives new interesting bounds for random k-regular graphs for small k and any particular fixed even value of k > 2. In our result the 2^{1/2}k^{3/4} is improved to \sqrt{2k}(k − 1)^{1/4}.

Another interesting note is that our version of Broder-Shamir gives the first direct^{3}results for the k-regular random graph model based on k perfect matchings (when the degree of the cover is even). Thus we obtain the first direct results for odd degree random graphs (by taking G to be one vertex with half-loops; see section 5).

3One can get “indirect” results on odd degree random graphs by starting with an even degree random graph (with the Broder-Shamir model) and adding a perfect matching (assuming an even number of vertices).

The rest of this paper is organized as follows. In sections 2 and 3 we prove Theorem 1.2 in the case where the base graph, G, has no self-loops or multiple edges; this gives us the essential ideas to prove Theorem 1.2 in any case. In section 2 we also give a more precise form of Theorem 1.2 (Theorem 2.7) and a number of interesting consequences. In section 4 we give a relative version of the Alon-Boppana bound, which is a new eigenvalue lower bound (for any graph cover) to complement the Broder-Shamir theorems of section 2; namely, we show that any cover of G of degree n has a new eigenvalue as large as ρ − α(n) with α(n) → 0 as n → ∞. In section 5 we describe some generalizations of the Broder-Shamir and Alon-Boppana theorems for a general base graph, and give some directions for future work.

2 A Simple Case

Our main theorems are less awkward to prove when the base is a graph with no self-loops or multiple edges. We shall first deal with this case, assuming the model C_{n}(G) in the previous section; this case illustrates all the main ideas. The more general situation follows the same ideas, and will be described in section 5.

We wish to use the trace method to bound the eigenvalues of H, a random element in C_{n}(G). This means we bound the expected value of the trace of the adjacency matrix of H; i.e., we bound the probability that a walk of a given length from a given vertex results in a cycle.

Throughout this section, if e is oriented as (u, v) (for the purpose of forming our random graph cover, H, in C_{n}(G) from the σ_{e}’s as in section 1), we may write σ_{u,v} for σ_{e} and σ_{v,u} for σ_{e}^{−1}.

So given a vertex in H, u_{0} = (v_{0}, i_{0}), a walk in H starting from u_{0} is determined by its projection in G. The walk in H will be a cycle precisely when the following two conditions hold: (1) the corresponding walk in G is a cycle, v_{0}, v_{1}, …, v_{k} = v_{0}, and (2) we return to the original vertex over v_{0} in H, i.e.,

i_{0} = σ_{v_{k−1},v_{k}} ∘ σ_{v_{k−2},v_{k−1}} ∘ ⋯ ∘ σ_{v_{0},v_{1}}(i_{0}).  (1)

With the cycle v_{0}, v_{1}, …, v_{k} = v_{0} we associate the cyclic word

w = σ_{v_{k−1},v_{k}}σ_{v_{k−2},v_{k−1}} ⋯ σ_{v_{0},v_{1}},

and write P (w) for the probability that equation (1) holds for a fixed i_{0} (clearly this probability is independent of i_{0}).

More generally, by a word we mean a string

σ_{v_{k−1},v_{k}}σ_{v_{k−2},v_{k−1}} ⋯ σ_{v_{0},v_{1}},

where {v_{i}, v_{i+1}} is an edge in G for all i, and where v_{k} need not equal v_{0}. If A_{H} is the adjacency matrix of H, then clearly

E(Tr(A_{H}^{k})) = ∑_{w∈W_{k}} P (w)n,

where W_{k} is the collection of all cyclic words of length k in G. The problem is reduced to estimating this sum involving the P (w)’s.

First we notice that σ_{v,v′}σ_{v′,v} is always the identity. Thus to evaluate P (w) we may cancel all consecutive pairs of inverses in w, potentially reducing the size of w. We call the new word obtained the reduction of w (which is easily seen to be independent of the order in which the reductions are made). If Irred_{m} denotes the irreducible cyclical words of length m we have

∑_{w∈W_{k}} P (w) = ∑_{m=0}^{k} ∑_{w∈Irred_{m}} P (w)n_{k}(w),

where n_{k}(w) denotes the number of cyclical words of length k that reduce to w. Of course, n_{k}(w) = 0 if k and |w|, the length of w, have different parity.

Lemma 2.1 (Buck) Let e be the empty word. Then n_{k}(e) ≤ |V_{G}|ρ^{k}, where ρ is the spectral radius of the adjacency matrix of the universal cover of G, and V_{G} is the set of vertices of G.

Proof We repeat the proof from [Buc86] (part of Proposition 3.1 there), since we will use the same idea for bounding the number of other types of walks. Let x be a vertex of the universal cover, T, of G, and let A_{T} be the adacency matrix of T. By spectral theory we know that the bounded operator A_{T} is self-adjoint, and hence ∥A_{T} ∥ = ρ. Then if δ_{x} is the function that is 1 on x and 0 on other vertices,

(δ_{x}, A_{T}^{k} δ_{x}) ≤ ∥A_{T} ∥^{k}∥δ_{x}∥^{2} = ρ^{k}.

But the left-hand-side of the above equation corresponds to those walks on x’s image in G whose corresponding cyclical word reduces to e. So applying this to one x for each vertex in G yields the lemma.

□

Clearly P (e) = 1 when e is the empty word. Hence

∑_{w∈W_{k}} P (w) ≤ n|V_{G}|ρ^{k} + ∑_{m=1}^{k} ∑_{w∈Irred_{m}} P (w)n_{k}(w).

Next we relativize two of the key lemmas in the Broder-Shamir analysis.

Lemma 2.2 Let w be an irreducible cyclic word of length k > 0 that is not of the form w = w_{a}^{−1}w_{b}^{j}w_{a} for any words w_{a}, w_{b} with w_{b} ≠ e and j ≥ 2. Then

P (w) ≤ \frac{1}{n − k} + \binom{k}{2}\frac{k^{2}}{(n − k)^{2}} .

Proof The proof is essentailly the same as in [BS87]. We explain this approach in our context in section 3; the lemma is an immediate consequence of Lemmas 3.1, 3.2, and 3.5.

□

Similarly, this next lemma is an immediate consequence of Lemmas 3.1, 3.2, and 3.6, and is essentailly the same as in [BS87].

Lemma 2.3 Let w be any irreducible cyclic word of length k. Then

P (w) ≤ \frac{k}{n − k} + \binom{k}{2}\frac{k^{2}}{(n − k)^{2}} .

We now need another counting lemma, using spectral techniques as in [Buc86].

Lemma 2.4 The number of cyclic words of length k that reduce to a word of the form w_{a}^{−1}w_{b}^{j}w_{a} with w_{b} ≠ e and j ≥ 2 is at most

|V_{G}|k(k − 1)\binom{k}{2}ρ^{k}.

Proof If w = w_{a}^{−1}w_{b}^{j}w_{a} with w_{b} ≠ e and j ≥ 2, then there is a “cyclic shift,” w̃, of w,

w̃ = σ_{v_{t},v_{t+1}}σ_{v_{t−1},v_{t}} ⋯ σ_{v_{0},v_{1}}σ_{v_{k−1},v_{k}} ⋯ σ_{v_{t+1},v_{t+2}},

such that w̃ reduces to w_{b}^{j}. Since there are k cyclic shifts of w, it suffices to show that the number of words of length k reducing to one of the form w_{b}^{j} with w_{b} ≠ e and j ≥ 2 is at most |V_{G}|(k − 1)\binom{k}{2}ρ^{k}.

For any vertex v_{0} ∈ V, fix a vertex x of the universal cover, T, of G, lying over v_{0}. Each irreducible word w_{b} begining with σ_{v_{0},v_{1}} for some vertex v_{1} corresponds uniquely to a vertex, y, of T. A word reduces to w_{b}^{j} with j ≥ 2 precisely when its corresponding walk starting at x (in T) does the following:

(1) for some ℓ_{1} > 0 its first ℓ_{1}’s σ’s reach y, thereby “tracing out” w_{b}, (2) for some ℓ_{2} > 0 its next ℓ_{2}’s σ’s again trace w_{b}, and (3) the rest of its σ’s trace w_{b}^{i} for some i ≥ 0. It follows that the number of such words is bounded by

∑_{i=0}^{k−2} ∑_{ℓ_{1}+ℓ_{2}≤k}(A_{G}^{ℓ_{1}}δ_{x})(y)(A_{G}^{ℓ_{2}}δ_{x})(y)(A_{G}^{k−ℓ_{1}−ℓ_{2}}δ_{x})(y^{i}),

where y^{i} is the vertex corresponding to w_{b}^{i}, and where A_{G} is the adjacency matrix of G. Summing over all y ≠ x yields a bound for the words with reduction to w_{b}^{j}, j ≥ 2 and any w_{b} ≠ e. We now estimate as follows:

(A_{G}^{k−ℓ_{1}−ℓ_{2}}δ_{x})(y^{i}) ≤ ∥A_{G}^{k−ℓ_{1}−ℓ_{2}}δ_{x}∥_{2} ≤ ρ^{k−ℓ_{1}−ℓ_{2}}∥δ_{x}∥_{2} = ρ^{k−ℓ_{1}−ℓ_{2}}.

Hence

∑_{y≠x}(A_{G}^{ℓ_{1}}δ_{x})(y)(A_{G}^{ℓ_{2}}δ_{x})(y)(A_{G}^{k−ℓ_{1}−ℓ_{2}}δ_{x})(y^{i}) ≤ ρ^{k−ℓ_{1}−ℓ_{2}} ∑_{y≠x}(A_{G}^{ℓ_{1}}δ_{x})(y)(A_{G}^{ℓ_{2}}δ_{x})(y)

≤ ρ^{k−ℓ_{1}−ℓ_{2}}(A_{G}^{ℓ_{1}}δ_{x}, A_{G}^{ℓ_{2}}δ_{x}) ≤ ρ^{k−ℓ_{1}−ℓ_{2}}ρ^{ℓ_{1}}ρ^{ℓ_{2}} = ρ^{k}.

It follows that the total number of words of length k that reduce to one of the form w_{b}^{j} with j ≥ 2 and w_{b} beginning at a fixed vertex, v_{0}, is at most

∑_{i=0}^{k−2} ∑_{ℓ_{1}+ℓ_{2}≤k} ρ^{k} = (k − 1) ∑_{ℓ_{1}+ℓ_{2}≤k} ρ^{k} = (k − 1)\binom{k}{2}ρ^{k},

recalling that the ℓ_{i} are positive integers.

Hence the total number of words of length k that reduce to one of the form w_{b}^{j} with j ≥ 2 with w_{b} ≠ e is at most

|V_{G}|(k − 1)\binom{k}{2}ρ^{k}.

□

Combining all the above lemmas yields:

Lemma 2.5

E(Tr(A_{H}^{k})) ≤ |V_{G}|ρ^{k}n + |V_{G}|k(k − 1)\binom{k}{2}ρ^{k} (\frac{kn}{n − k} + \binom{k}{2}\frac{k^{2}n}{(n − k)^{2}} )

+Tr(A_{G}^{k}) (\frac{n}{n − k} + \binom{k}{2}\frac{k^{2}n}{(n − k)^{2}} ) .

In particular, if k ≤ n/2 we have

E(Tr(A_{H}^{k})) ≤ |V_{G}|ρ^{k}(n + 2k^{8}) + Tr(A_{G}^{k}) + |V_{G}|λ_{0}^{k}4k^{4}/n.

Proof There are Tr(A_{G}^{k}) cyclic walks of length k in G. Each walk either (1) reduces to e, (2) reduces of w_{a}^{−1}w_{b}^{j}w_{a} with w_{b} ≠ e and j ≥ 2, or (3) does neither (1) nor (2). In case (1) we have P (w) = 1, and in the other cases we use one of the previous lemmas to bound P (w). The first statement follows, and the second statement follows from the first, using the bound Tr(A_{G}^{k}) ≤ |V_{G}|λ_{0}^{k}.

□

Finally we arrive at the essential eigenvalue estimate:

Theorem 2.6 If k ≤ n/2 then we have

E ( ∑_{λ new} λ^{k}) ≤ |V_{G}|ρ^{k}(n + 2k^{8}) + |V_{G}|λ_{0}^{k}4k^{4}/n.  (2)

Proof We have

Tr(A_{H}^{k}) = (∑_{λ old} λ^{k}) + ( ∑_{λ new} λ^{k}) = Tr(A_{G}^{k}) + ( ∑_{λ new} λ^{k}) ,

so the theorem follows from the preceding lemma.

□

We apply this theorem with k = 2⌊log n/ log(λ_{0}/ρ)⌋, assuming λ_{0} > ρ. For this value of k there are positive constants c_{1}, c_{2} for which

c_{1}(λ_{0}/ρ)^{k/2} ≤ n ≤ c_{2}(λ_{0}/ρ)^{k/2}

(actually, one can take c_{2} = 1/c_{1} = λ_{0}/ρ). The following theorem follows almost at once.

Theorem 2.7 Let G be fixed. There is a C such that for any n, setting k_{0} = 2⌊log n/ log(λ_{0}/ρ)⌋, we have that for any k ≤ k_{0}

E_{C_{n}(G)}(ρ_{new}^{k}) ≤ (Ck_{0})^{4k/k_{0}}(λ_{0}ρ)^{k/2}.  (3)

Proof The k = k_{0} case follows easily from the last theorem. That k can be taken smaller follows from Jensen’s inequality.

□

We now state a number of consequences.

Corollary 2.8 For fixed G we have

E_{C_{n}(G)}(ρ_{new}) ≤ \sqrt{λ_{0}ρ} + O(log log n/ log n).

Proof We take k = 1 in Theorem 2.7, whereupon there

(Ck_{0})^{4k/k_{0}} ≤ e^{C′ log(k_{0})/k_{0}} ≤ 1 + \frac{C′′ log(k_{0})}{k_{0}} ≤ 1 + \frac{C′′′ log log n}{log n}.

Applying this to equation 3 yields the corollary.

□

Corollary 2.9 For any fixed G and B > 0 there are positive constants C_{1}, C_{2} such that

ρ_{new} ≥ \sqrt{λ_{0}ρ} (1 + α(n))

in C_{n}(G) with probability at most

C_{1}(log n)^{4}n^{−C_{2}α(n)}

whenever α(n) ≤ B.

Proof If P is the aforementioned probability, then

E_{C_{n}(G)}(ρ_{new}^{k}) ≥ P (\sqrt{λ_{0}ρ} (1 + α(n)))^{k}

for any k. Now take k = k_{0} as in Theorem 2.7; equation 3 implies that

P (1 + α(n))^{k_{0}} ≤ (Ck_{0})^{4}.

Since k_{0} is proportional to log n, the corollary follows.

□

This corollary, in turn, has various corollaries depending on which function α(n) we choose. If we take α(n) to be constant, we conclude:

Theorem 2.10 For any fixed G and ϵ > 0 there are C, δ > 0 such that the largest new eigenvalue is ≥ (1 + ϵ)\sqrt{λ_{0}ρ} with probability ≤ Cn^{−δ}.

We also conclude another theorem by taking α(n) = C log log n/ log n with C sufficiently large:

Theorem 2.11 For a fixed G there is a C such that the probability that ρ_{new} is ≤ \sqrt{λ_{0}ρ} + C log log n/ log n goes to 1 as n → ∞.

3 The Broder-Shamir Approach

In this section we describe the remarkable and beautiful approach of Broder and Shamir in [BS87] to analyze the P (w)’s of the previous section and to prove Lemmas 2.2 and 2.3.

Fix a word, w, of length k (we may later insist that w be irreducible). To study P (w), let

w = σ_{v_{k−1},v_{k}}σ_{v_{k−2},v_{k−1}} ⋯ σ_{v_{0},v_{1}},

and fix an i_{0} ∈ {1, …, n}. We shall determine where w takes (v_{0}, i_{0}) by determining the steps of the walk in order, i.e., first determining i_{1} = σ_{v_{0},v_{1}}(i_{0}), then i_{2} = σ_{v_{1},v_{2}}(i_{1}), etc. Initially we view all σ_{u,v}’s as “completely random” or “completely undetermined,” each taking on any one of the n! permutations on {1, …, n} with the same probability. Then we determine i_{1} = σ_{v_{0},v_{1}}(i_{0}) as being chosen from {1, …, n}, each with probability 1/n. This determining of i_{1} conditions the σ_{u,v}’s in that σ_{v_{0},v_{1}}(i_{0}) is fixed (as is σ_{v_{1},v_{0}}(i_{1})) and σ_{v_{0},v_{1}} now can only take on (n − 1)! possibly permutations. Assume that for some s we have determined i_{j} = σ_{v_{j−1},v_{j}}(i_{j−1}) for j = 1, …, s − 1, and now we wish to determine i_{s} = σ_{v_{s−1},v_{s}}(i_{s−1}). There are two possibilities: (1) a forced choice, where σ_{v_{s−1},v_{s}}(i_{s−1}) has already been determined (previously in the walk), and (2) a free choice, where σ_{v_{s−1},v_{s}}(i_{s−1}) has not been determined. For a free choice, i_{s} takes on one of possibly n − t values from 1 to n with equal probability, where t is the number of values of σ_{v_{s−1},v_{s}} that have been determined up to that point; clearly t ≤ s − 1.

For a free choice, we say that a coincidence has occurred if (v_{s}, i_{s}) has been previously visited in the walk; i.e., (v_{s}, i_{s}) = (v_{j}, i_{j}) for some j < s (with j = 0 possible). A coincidence occurs with probability at most (s − 1)/(n − s + 1).

We record the following two simple but important observation:

Lemma 3.1 Fix a word, w = σ_{v_{k−1},v_{k}} ⋯ σ_{v_{0},v_{1}}, of length k, and a fixed i_{0}. The probability that the walk determined by w and i_{0} has two or more coincidences is at most:

\binom{k}{2}\frac{k − 1}{n − k + 1} \frac{k − 2}{n − k + 2}.

Proof There are \binom{k}{2} ways of choosing two of the choices of i_{1}, …, i_{k} to be both coincidences; the first coincidence occurs with probability ≤ (k − 1)/(n − k + 1), and the second ≤ (k − 2)/(n − k + 2).

□

Lemma 3.2 If w is irreducible, k > 0, and there are no coincidences, then i_{k} ≠ i_{0}. Moreover, (v_{s}, i_{s}) ≠ (v_{t}, i_{t}) for any s ≠ t.

Proof Assume, to the contrary, that there are s, t with 0 ≤ s < t ≤ k with (v_{s}, i_{s}) = (v_{t}, i_{t}). Let s, t be as such, with t as small as possible. The minimality of t implies that (v_{s}, i_{s}) ≠ (v_{r}, i_{r}) for any 0 ≤ s < r ≤ t − 1.

Since (v_{s}, i_{s}) = (v_{t}, i_{t}) and since i_{t} was not a coincidence, σ_{v_{t−1},v_{t}}(i_{t−1}) was already determined. But this can only happen in case for some j < t we have either (1) (v_{t}, i_{t}) = (v_{j}, i_{j}) and (v_{t−1}, i_{t−1}) = (v_{j−1}, i_{j−1}), or (2) (v_{t}, i_{t}) = (v_{j−1}, i_{j−1}) and (v_{t−1}, i_{t−1}) = (v_{j}, i_{j}). Case (1) is impossible, since (v_{t−1}, i_{t−1}) = (v_{j−1}, i_{j−1}) contradicts the minimality of t. Case (2) requires j = t − 1 to avoid having (v_{t−1}, i_{t−1}) = (v_{j}, i_{j}) contradict the minimality of t; but then v_{t} = v_{j−1} = v_{t−2}, and w is reducible (since it contains the subword σ_{v_{t−1},v_{t}}σ_{v_{t−2},v_{t−1}} = σ_{v_{t−1},v_{t}}σ_{v_{t},v_{t−1}}. Hence both cases (1) and (2) lead to contradictions, and so we derive a contradiction by our assumption that (v_{s}, i_{s}) = (v_{t}, i_{t}) for some s ≠ t.

□

Essentially the same proof yields the following stronger lemma:

Lemma 3.3 Let w be an irreducible cyclic word of length k, and assume that i_{p} (as above) is a free choice for some p between 1 and k. Let none of i_{p}, i_{p+1}, … i_{k} be a coincidence (i.e., each is either a forced choice or a free choice that is not a coincidence). Then the vertices (v_{t}, i_{t}) for t ≥ p will all be distinct and will not coincide with any vertex (v_{r}, i_{r}) for r < p.

Proof We are claiming that (v_{s}, i_{s}) ≠ (v_{t}, i_{t}) for any s < t and t ≥ p. If not, again fix an s and t and with t minimal; clearly t > p since i_{p} is a free choice and not a coincidence. The same two case analysis as in the previous proof yields a contradiction.

□

Lemma 3.4 Let w be an irreducible cylcic word such that i_{k} = i_{0} in which only one coincidence occurs. Then for some j ≥ 1 we may write w = w_{a}^{−1}w_{b}^{j}w_{a} where (1) w_{b}w_{a} is irreducible, and (2) if |w_{a}| = s and |w_{b}| = t then the coincidence occurs at i_{t+s}, the coincidence being (v_{t+s}, i_{t+s}) = (v_{s}, i_{s}).

Proof Clearly there is are unique s, t such that the coincidence is (v_{t+s}, i_{t+s}) = (v_{s}, i_{s}). Let w_{a} be the word from i_{0} to i_{s} and w_{b} that from i_{s+1} to i_{s+t}. After i_{t+s}, all other choices must be forced, in view of Lemma 3.3 and the facts that i_{k} = i_{0} and there is exactly one coincidence occurring. At i_{s+t+1} we must either (1) begin to follow w_{b}, or (2) begin to follow w_{a}^{−1}. Since w is irreducible, if we begin to follow w_{b} we must traverse it in its entirety, returning to (v_{s}, i_{s}) again. Eventually we will follow w_{a}^{−1}, whereupon the irreducibility of w implies that we will end and reach (v_{k}, i_{k}) when we finish traversing w_{a}^{−1}. This implies the lemma.

□

Lemma 3.5 Let w be irreducible of length k > 0. Assume that w ≠ w_{a}^{−1}w_{b}^{j}w_{a} for any irreducible words w_{a}, w_{b} with j ≥ 2. Then the probability that i_{k} = i_{0} and exactly one coincidence occurs is at most

\frac{1}{n − k + 1}.

Proof Let w_{a} be the longest irreducible subword of w such that w = w_{a}^{−1}w_{b}w_{a} (with w_{b}w_{a} irreducible). If |w_{a}| = s then i_{k} = i_{0} iff i_{k−s} = i_{s}. By Lemma 3.4, i_{1}, …, i_{k−s−1} are free choices, and i_{k−s} is a coincidence and must take on the value i_{s}. This coincidence occurs with probability at most

\frac{1}{n − k + s + 1} ≤ \frac{1}{n − k + 1}.

Similarly we have the following useful lemma:

Lemma 3.6 Let w be any irreducible word of length k > 0. Then the probability that i_{k} = i_{0} and exactly one coincidence occurs is at most

\frac{k}{n − k + 1}.

Proof w_{a} be the longest irreducible subword of w such that w = w_{a}^{−1}w_{c}w_{a} (with w_{c}w_{a} irreducible). There are at most k positive integers, j, such that w_{c} = w_{b}^{j}. Lemma 3.4 shows that i_{k} = i_{0} requires there to be such a j, and for each j there is one specific coincidence (of the form i_{s+t} = i_{s} for a given s and t) that must occur. For each j value the associated event occurs with probability ≤ 1/(n − k + 1).

□

4 Alon-Boppana Bounds

Fix a graph, G, whose universal cover has spectral radius ρ. In this section we explain that the largest new eigenvalue of a cover, H, of G of degree n must be at least ρ − α(n), where α(n) is a function of n tending to 0 as n → ∞. The case of d-regular graphs, where G is a boquet of loops of total degree d, was first claimed in [Alo86] (as due to Alon and Boppana), and appears in [Nil91].

Theorem 4.1 Let G be a fixed graph. There exists a function α = α(n) defined for n a positive integer such that (1) α(n) → 0 as n → ∞, and (2) for any covering map π: H → G of degree n, there is a new eigenvalue of absolute value at least ρ − α(n).

In [Nil91], where G is a boquet of loops of total degree d, α(n) was shown to be at most proportional to 1/ log n. In the independent works of Friedman and Kahale (see [Fri93]), α(n) was shown to be at most proportional to 1/ log^{2} n. We will use a weaker technique to prove the above theorem, which does not estimate α(n). Proof We will make use of the following lemma that is a special case of part of Proposition 3.1 of Buck in [Buc86].

Lemma 4.2 (Buck) Let G be a connected graph, and fix a vertex v ∈ V_{G}. Then for any ϵ > 0, there is an r_{0} such that the number of walks of length 2r from v to itself is at least (ρ − ϵ)^{2r}, provided that r ≥ r_{0}.

By Lemma 2.1, this number of walks is bounded above by ρ^{2r} for all r > 0.

Now fix an ϵ > 0 and let r_{0} be as in the above lemma. Let G’s maximum degree be D. Let

n_{0} = 1 + D + D(D − 1) + D(D − 1)^{2} + ⋯ + D(D − 1)^{2r_{0}}.

Then in any subset of > n_{0} vertices of a graph of maximum degree ≤ D, there are two vertices of distance > 2r_{0}.

Now consider a covering map π: H → G of degree n > n_{0}; we can fix u, v ∈ V_{H} of distance > 2r_{0} such that π(u) = π(v). Let f = χ_{u} − χ_{v} be the function that is 1 on u, −1 on v, and 0 elsewhere. Then (A_{H}^{2r_{0}}f, f) is the sum of the number of walks of length 2r_{0} from, respectively u and v, that return to their starting vertex. So

(A_{H}^{2r_{0}}f, f) ≥ 2(ρ − ϵ)^{2r_{0}}.

But f is a new function of L^{2} norm \sqrt{2}, and so the norm of A_{H}^{2r_{0}} restricted to the new functions is ≥ (ρ − ϵ)^{2r_{0}}. Hence the largest eigenvalue of A_{H}^{2r_{0}} restricted to L_{new}^{2} is at least (ρ − ϵ)^{2r_{0}}, and so that of A_{H} is at least ρ − ϵ. This proves the theorem.

□

5 Generalizations and Concluding Remarks

Up to now we have developed Broder-Shamir theorems (i.e. Theorem 2.7 and its consequences) and Alon-Boppana theorems (Theorem 4.1) for only one model, C_{n}(G), of a random cover of G, and we have assumed that G has no multiple edges or self-loops. It is easy to generalize the following theorems to (1) graphs with multiple edges, (2) graphs with self-loops (either half-loops or whole-loops in the terminology of [Fri93]), and (3) graphs with weighted edges (where the adjacency matrix entries are sums of the appropriate edge weights). Furthermore, define a C-Broder-Shamir permutation model to be a probability space of permutation on n-elements for each n (or some collection of n) such that for any n, k with k ≤ n/4 we have that if k values of the permutation, σ, are fixed, any undetermined value, σ(i), of the permutation has σ(i) = j with probability at most (1/n) + (Ck/n^{2}) (for all j). Then the Broder-Shamir theorems generalize to a random cover of G model given by any independent permutations, {σ_{e}}_{e∈E}, that are C-Broder-Shamir for some C (independent of n). The details and examples can be found in [Fri].

We now give some directions for further work.

It would be nice to generalize the theorems here to allow the base graph to be a “pregraph” (in the sense of [Fri93]). Then there would be a relative Broder-Shamir theorem for quotients of every fixed tree, T.

Given a graph (or pregraph), G, with a “reasonable” (we remain vague here) model of a random degree n cover of G, one can conjecture that ρ_{new} ≤ ρ with probability tending to 1 (or even, less ambitiously, nonzero probability). One could weaken this “Ramanujan” condition to having ρ_{new} ≤ ρ + ω(n) where ω is some suitable function of n. One could also ask similar question about Galois covers (see [Fri93]). [LPS88] give examples of Galois covers where the base graph has one or two vertices.

Another interesting direction would be to fix a cover π: G_{0} → G with G_{0} infinite. Then one could ask about the above conjectures, as well as the theorems in this paper, where we take a “random” finite quotient of G_{0} that covers G and take ρ to be the spectral radius of G_{0} (the Alon-Boppana theorem easily generalizes to this situation).

We remark that there are some very interesting of covers with small new spectral radius in certain cases. For example, it is not hard to see that the Boolean n-cube^{4}, B^{n}, has one degree two cover all of whose eigenvalues are ±\sqrt{n} (see [Fri94]).

4This is the graph with vertices {0, 1}^{n} and edge between two vertices of Hamming distance one, i.e. two vertices that differ in exactly one coordinate.

References

[AL] A. Amit and N. Linial. Random graph coverings II: Edge expansion. Combinatorics, Probability and Computing. To appear.

[AL02] A. Amit and N. Linial. Random graph coverings I: General theory and connectivity. Combinatorica, 22:1–18, 2002.

[ALM02] A. Amit, N. Linial, and J. Matousek. Random graph coverings III: Independence and chromatic number. Random Structures and Algorithms, 20:1–22, 2002.

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

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

[Buc86] Marshall W. Buck. Expanders and diffusers. SIAM J. Algebraic Discrete Methods, 7(2):282–304, 1986.

[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] J. Friedman. Further remarks on relative expanders. Preprint.

[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.

[Fri94] J. Friedman. Relative expansion and an extremal degree two cover of the boolean cube. 1994. Preprint.

[GJKW] C.S. Greenhill, S. Janson, J. H. Kim, and N.C. Wormald. Permutation graphs and contiguity. See http://www.ms.unimelb.edu.au/˜ nick/abstracts.html.

[Gre95] Y. Greenberg. PhD thesis, Hebrew University, Jerusalem, 1995. In Hebrew.

[LN98] Alexander Lubotzky and Tatiana Nagnibeda. Not every uniform tree covers Ramanujan graphs. J. Combin. Theory Ser. B, 74(2):202–212, 1998.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[LR] N. Linial and E. Rozenman. Random graph coverings IV: Perfect matchings. Combinatorica. To appear.

[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.

[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.