Alon's Second Eigenvalue Conjecture: Simplified and Generalized by David-Emmanuel Kohler M.Sc., Ecole Polytechnique Federale de Lausanne, 2006 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) July 2013 c David-Emmanuel Kohler 2013 Abstract For a fixed graph,B, we study a probability model, Cn(B), of random cover- ing maps : G! B of degree n. Specifically, we study spectral properties ofG's new eigenvalues of the adjacency matrix of G, and of the Hashimoto matrix of G (i.e., the adjacency matrix of the directed line graph of G). Our main theorem says that if B is d-regular, then for every " > 0, the probability that G 2 Cn(B) has a new adjacency eigenvalue greater than 2 p d 1+" tends to zero as n tends to infinity. Thismatches the generalized Alon-Boppana lower bound, in the sense that any degree n cover, G, of a fixed graph, B, must have a new eigenvalue of at least (A bB) on (1), where (A bB) is the spectral radius of the universal cover, bB, of B, and where on (1) is a function that tends to zero as n tends to infinity. When the base graph, B, is d-regular, it is well known that (A bB) = 2pd 1 and hence explains the context of our result. For general base graphs, B, Friedman conjectured in that the new eigenvalue bound holds with 2 p d 1 replaced with (A bB). We refer to this conjecture as the generalized Alon conjecture; Alon stated this con- jecture in the case where B has one vertex, i.e., the case of random d- regular graphs on n vertices. However, for some non-regular base graphs B, we cannot yet prove any non-trivial new eigenvalue upper bound with high probability. We use trace methods, as pioneered by Broder and Shamir for random, d-regular graphs; these methods were eventually refined by Friedman to prove the original Alon conjecture, i.e., in the case whereB has one vertex. Our methods involve several significant simplifications of the methods of Friedman. ii Preface This dissertation is original and constitutes independent work by the author, D. Kohler and his supervisor J. Friedman. The author and his supervisor intend to submit these results in a future article. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation and Historical Context . . . . . . . . . . . . . . . 1 1.2 The Generalized Alon Conjecture . . . . . . . . . . . . . . . 4 1.3 Outline of Our Trace Method . . . . . . . . . . . . . . . . . . 7 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Essential Graph Terminology . . . . . . . . . . . . . . . . . . 14 2.2 Adjacency Eigenvalues . . . . . . . . . . . . . . . . . . . . . 16 2.3 Hashimoto Eigenvalues . . . . . . . . . . . . . . . . . . . . . 18 2.4 Graph Coverings . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5 Variable-Length Graphs . . . . . . . . . . . . . . . . . . . . . 25 2.6 The Broder-Shamir Model . . . . . . . . . . . . . . . . . . . . 25 2.7 Polyexponential Functions . . . . . . . . . . . . . . . . . . . 27 2.8 Functions of Bounded Growth . . . . . . . . . . . . . . . . . 29 2.9 B-Ramanujan Functions . . . . . . . . . . . . . . . . . . . . 33 iv 3 Walk Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1 Potential Walks . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Walk Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Asymptotic Expansion . . . . . . . . . . . . . . . . . . . . . 44 3.4 Types and Forms . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Tangles and the Certified Trace . . . . . . . . . . . . . . . . . . . 56 4.1 Tangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Finitely Certifiable Partial Orders . . . . . . . . . . . . . . . . 64 4.3 The Certified Trace . . . . . . . . . . . . . . . . . . . . . . . 71 4.4 Asymptotic Expansion . . . . . . . . . . . . . . . . . . . . . 74 5 The Side-Stepping Lemma . . . . . . . . . . . . . . . . . . . . . . 80 5.1 The Shift Operator . . . . . . . . . . . . . . . . . . . . . . . . 80 5.2 Statement of the Side-Stepping Lemma . . . . . . . . . . . . 82 5.3 Proof of the First Exception Bound . . . . . . . . . . . . . . . 87 5.4 The Proof of the Limit Formula . . . . . . . . . . . . . . . . . 92 5.5 The End of The Proof of Lemma 5.2.5 . . . . . . . . . . . . . 100 6 Proof of the Main Result . . . . . . . . . . . . . . . . . . . . . . . 102 6.1 Certified Traces In Graphs With Tangles . . . . . . . . . . . 103 6.2 End of the Proof . . . . . . . . . . . . . . . . . . . . . . . . . 109 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 v List of Symbols Symbols and notations are ordered alphabetically. In the case of Greek symbols, they are ordered in their English names e.g. the Greek letter chi, , is understood as starting with the letter c. AG adjacency matrix of the graph G . . . . . . . . . . . . . . . . . . 16bB the universal cover of the base graph B . . . . . . . . . . . 4 newB (HG) new Hashimoto spectral radius . . . . . . . . . . . . . . . . . . . 24 Cn(B) the Broder-Shamir model . . . . . . . . . . . . . . . . . . . . . . . . . 25 (G) Euler characteristic of G . . . . . . . . . . . . . . . . . . . . . . . . . . 21 CertSNBC certified SNBC walk collection . . . . . . . . . . . . . . . . . . . . 71 CertTr certified trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 CertTr<r truncated certified trace . . . . . . . . . . . . . . . . . . . . . . . . . . 71 dmax maximum degree of a graph . . . . . . . . . . . . . . . . . . . . . 21 En[X] expectation in Cn(B) of the r.v. X . . . . . . . . . . . . . . . . . 26 F a form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 F(w;~t ) form of the potential walk (w;~t ) . . . . . . . . . . . . . . . . . . .49 G a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Graph(w;~t ) the graph traced out by a potential walk . . . . . . . . . . 39 HG Hashimoto matrix of the graph G . . . . . . . . . . . . . . . . . 18 ITF(r;B)[n] indicator function of Cn(B)nTangler;B[n] . . . . . . . . . . 62 Line(G) directed line graph of G) . . . . . . . . . . . . . . . . . . . . . . . . . 18 NB(e1; e2; k) # of non-backtracking k-walks from e1 to e2 . . . . . . 50 OccursB connected graphs that can occur in Cn(B) . . . . . . . . .7 ord(w;~t ) the order of a potential walk . . . . . . . . . . . . . . . . . . . . . . 40 Probn[E ] probability in Cn(B) of the event E . . . . . . . . . . . . . . . . 26 (AG) = A(G) spectral radius of AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 vi (HG) = H(G) spectral radius of HG . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 newB (AG) new adjacency spectral radius . . . . . . . . . . . . . . . . . . . 23 SNBC strictly non-backtracking closed walks collection . 42 Spec(AG) spectrum of adjacency eigenvalues . . . . . . . . . . . . . . 16 Spec(HG) spectrum of Hashimoto eigenvalues . . . . . . . . . . . . . . 18 SpecnewB (AG) new adjacency spectrum of the covering G . . . . . . 23 SpecnewB (HG) new Hashimoto spectrum . . . . . . . . . . . . . . . . . . . . . . . . 24 T a type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 T (w;~t ) type of the potential walk (w;~t ) . . . . . . . . . . . . . . . . . . . 49 [~t ]n;w the (n;w)-equivalence symmetry class of ~t . . . . . . . 40 TangleB set of tangles that can occur in Cn(B) . . . . . . . . . . . . 61 Tangler;B set of tangles in TangleB of order less than r . . . . . 61 HasTangleminr;B set of minimal tangles in HasTangler;B . . . . . . . . . . . 61 Tr(M) trace of the matrix M . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Treed( ) universal d-regular cover with a -inclusion . . . . . . 57 Types[r] types of order less than r . . . . . . . . . . . . . . . . . . . . . . . . . 49 W a walk collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 W(k; n) (k; n)-walks inW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Wn(G; k) (k; n)-modified trace ofW . . . . . . . . . . . . . . . . . . . . . . . . 42 WF (W; k; ~m ) consistent walks in F of multiplicity ~m . . . . . . . . . . . . 51 WT (~m;~k(F)) consistent (~m;~k )-walks in T . . . . . . . . . . . . . . . . . . . . . .51 (w;~t ) a potential walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 [w;~t ]n equivalence class of potential walks . . . . . . . . . . . . . . 41 WalkSum(W; k; n) (k; n) walk sum ofW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 vii Acknowledgements The writing of this thesis is also the product of the help and support of several people, some of whom I would like to acknowledge here. First, I would like to thank my parents, Adia-Pia and Kurt, for their un- conditional love and support. Thanks to my siblings, Jeremy, Evan and Megan, my aunt, Alexandra and my grandfather Henri for their invaluable presence in my life and all their love. I thank my supervisor, Dr. Joel Friedman, for his patience, mathematical expertise and unwavering support. It has been a privilege to work with him and discover the beauty of his work, that combines so many different fields of mathematics. I thank as well my supervision committee members as well as Dr. Brian Marcus and Dr. Patrick Brosnan for their support at the earlier stages of my degree. I would like to acknowledge my mathematical colleagues: Dr. David Steinberg and Dr. Warren Code for their friendship in the past several years. I am grateful to Dr. Fok-Shuen Leung, Dr. Mark Mac Lean and Dr. Djun Kim for their support and many discussions on the teaching of mathematics. And many thanks to my many friends, who happen to be mathematicians as well: Dr. Anthony Arnold, Dr. Olivier Isely, Dr. Peter Jossen, Varvara Karpova and Dr. Simon Rose. There are too many friends in Switzerland, in Canada and elsewhere that I would like to acknowledge. Special thoughts for the extraordinary Nina Vogt who has seen me doing mathematics for over a decade now. I cannot express enough gratitude to Laura Tremblay-Boyer for her sup- port and friendship. For their friendship, cooking skills, coaching, love and overall awesomeness, thanks to Cesar Oboni, Nick Hermes, Kate Moore, Patrick Thompson and Bruce Yoder; Xavier Alexandre and Oliver Prosperi; viii Carley Kennedy and Kristen Mcllhenney; Sévrine Knuchel; Lou Legros Lefeuvre; Nicole Huk; Roselynn Verwoord; Helena Palmqvist; Christopher Ryan and Cacilda Jethá. A huge thank you to Marlène Oberson, Beth At- wood, and Jessica Mill for being in my life. I love you all. Finally, I'd like to acknowledge Aaron Kafka and his wonderful coffee shop, Kafka's Coffee and Tea, where most of this thesis was written in the company of many an espresso macchiato. ix Dedication To Dr. Henri Woog, who has given me my love for mathematics and all sciences. It is a privilege for me to be his grandson. x Chapter 1 Introduction Themain goal of this thesis is to study spectral properties of random covers of a fixed graph, B. We develop tools to prove what we call a generalized Alon conjecture for arbitrary base graph, B, formulated in [Fri03]. In this thesis, we succeed in proving the generalized Alon conjecture for the case where the base graph, B, is any d-regular graph. Our approach follows the Broder-Shamir trace method of [BS87], with its refinements developed by Friedman in [Fri91, Fri08], which we adapt to the more general situation of random, degree n covering maps of a fixed graph, B. However, our proofs significantly simplify the arguments of [Fri08]; in particular, we replace the cumbersome selective trace by a much simpler modified trace that we call a certified trace; there are several other new ideas that simplify the methods of [Fri08]. We review these con- jectures and their historical context. We shall assume some terminology of algebraic graph theory to be given in chapter 2. 1.1 Motivation and Historical Context This thesis is inscribed in a large body of research that can be attached to the study of expanders. Expansion requires that a graph is simultane- ously sparse and highly connected. The recent survey by Hoory, Linial and Wigderson [HLW06] gives a brief overview of the more than four decades of work that has been done around the concept of expansion. The uni- versality of this notion is becoming more evident as more connections are made, primarily in combinatorics, geometry, probability and algebra. We will touch briefly upon some points of interest to describe the moti- 1 vation of our work. Let us begin by a definition of expansion. Definition 1.1.1. Let G be a d-regular graph on n vertices, its edge expan- sion ratio, denote h(G) is defined as: h(G) = min jSjn 2 j@Sj jSj where @S is the number of edges connecting vertices in the set S to its complement. Definition 1.1.2. A sequence of d-regular graphs fGigi1 of size increasing with i is a family of expander graphs if there exists " > 0 such that h(Gi) > " for all i 1. The construction of explicit families of expander graphs presents nu- merous difficulties and is itself an interesting problem. Let us approach this from an algebraic point of view. If G is a graph on n vertices, its adja- cency matrix is real and symmetric and thus has n real eigenvalues which we denote by 1 2 : : : n and that is called the spectrum of the graph G. If G is d-regular, then 1 = d (it is the Perron-Frobenius eigen- value of the graph) and the graph's second eigenvalue is closely related to its edge expansion ratio. The following theorem is well known. Theorem 1.1.3. Let G be a d-regular graph on n vertices, then d 2 2 h(G) p 2d(d 2) Let (G) = maxfjij j i 6= dg, the quantity d (G) is called the spectral gap of the graph and provides an estimate on its expansion. In particular, a d-regular graph has an edge expansion ratio bounded away from zero if and only if its spectral gap is bounded away from zero. Also of interest is the expander mixing lemma which shows that a small second eigenvalue implies that the graph is nearly random in the sense that its edges are spread out. 2 Theorem 1.1.4 (Expander Mixing Lemma). Let G be a d-regular graph on n vertices, then for all sets of vertices S; T VG we have:EG(S; T ) djSjjT jn (G)pjSjjT j At this point, we are interested in how big can the spectral gap be and as such, estimates of (G). The Alon-Boppana bound [Nil91] gives the following tight bound Theorem 1.1.5 (Alon-Boppana). Let G be a d-regular graph on n vertices, then (G) 2pd 1 on(1) Since bipartite or disconnected regular graphs have (G) = d, there are no interesting deterministic upper bounds on (G). Of interest are graphs such that (G) 2pd 1 which are called Ramanujan graphs. Explicit constructions of families of Ramanujan graphs are hard to come by and offers many interesting problems. An open question is to prove the exis- tence of infinitely many d-regular Ramanujan graphs for all d 3. A major result, due to Lubotzky-Phillips-Sarnak [LPS88] and independently by Mar- gulis [Mar88] that arbitrarily large d-regular Ramanujan graphs exist when d 1 is prime, and moreover they can be explicitly constructed. Morgen- stern [Mor94] extended this to the case when d 1 is a prime power. During the writing of this thesis, we learned of a preprint by Marcus, Spielman and Srivastava [MSS13] which establishes the existence of infi- nite families of d-Ramanujan bipartite graphs for all d 3. Theorem 1.1.6 (Lubotzky-Phillips-Sarnak, Margulis, Morgenstern). Let p be a prime and k a positive integer, then there exist infinitely many (pk + 1)- regular Ramanujan graphs. Despite the difficulty to explicitly construct Ramanujan graphs, it is con- jectured that they are not rare. Experimental evidence by Miller-Novikoff- Sabelli [MNS08] indicates that the probability that a random d-regular graph on n vertices is Ramanujan tends to 27% as n tends to infinity. Relaxing this condition to nearly Ramanujan graphs, Alon [Alo86] conjectured: 3 Conjecture 1.1.7 (Alon). Let G be a random d-regular graph on n vertices, then (G) 2pd 1 + on(1) a.a.s.1 In [Fri08], Friedman proved this conjecture. Theorem 1.1.8 (Friedman). Let G be a d-regular graph on n vertices, then, for any " > 0, (G) 2pd 1 + " a.a.s. The Alon-Boppana bound shows that the constant 2 p d 1 cannot be improved. 1.2 The Generalized Alon Conjecture A significant generalization of this conjecture makes sense of the 2 p d 1 constant. Consider the universal cover, bB, of any d-regular graph. bB is the infinite d-regular tree and its spectral radius, (A bB) satisfies (A bB) = 2pd 1 When considering d-regular graphs for d even, one can make the following simple observation: any d-regular graph,G, is a covering map of the graph consisting of one vertex and d/2 whole-loops. From this, one can extend the probabilistic model developed in [BS87] to formulate a natural model, Cn(B), for any choice of base graph B. This model constructs a random graph, G, admitting a covering map : G ! B of degree n constructed via the choice of jEBj independent and uniformly chosen elements of the symmetric group, Sn, of permutations of n elements. B may have multiple edges and self-loops (if B has half-loops, then we insist that n be even and that we choose from those elements of Sn that are perfect matchings). For any covering : G ! B, the multiset of its adjacency eigenvalues can be partitioned into two sets: old eigenvalues arising from the base graph B 1Asymptotically almost surely i.e. with probability converging to 1 as n tends to infinity. 4 and the remaining new eigenvalues depending on G. We let SpecnewB (AG) denote the multiset of new eigenvalues of G and let newB (AG) denote the largest new eigenvalue in absolute value of the covering graph G. We remark that for any positive integer k, we haveX 2SpecnewB (AG) k = Tr(AkG) Tr(AkB) and so it follows that the new eigenvalues of covering graphG depend only on the graphs B and G and not on the particular covering map : G! B. In [Fri03], the following conjecture is studied. Conjecture 1.2.1 (The generalized Alon conjecture). For any fixed base graph, B, let (A bB) be the spectral radius of the adjacency operator on the universal cover, bB, of the base graph. Consider the probability space, Cn(B), of random covering graphs of degree n of the graph B. Then the probability that a random covering graph, G, of degree n satisfies newB (AG) (A bB) + " tends to zero as n tends to infinity, for any " > 0. A weakened form of this conjecture was proven by Friedman [Fri03] with (A bB) replaced by q d(A bB). Linial and Puder [LP10], improved this to 3d1/32/3 where = (A bB). Lubetzky, Sudakov and Vu in [LSV11] im- proved this to order of maxf;pdg log(d) where is the absolute value of the largest non-trivial adjacency eigenvalue of B. Addario-Berry and Griffiths in [ABG10] improved this to c p d where c is 430656. Recently, Puder [Pud12] has improved this to + 0:84, for B regular and to 3 for arbitrary B. The main result of this thesis is to prove conjecture 1.2.1 for any d- regular graph B. Specifically, we prove the following theorem. Theorem 1.2.2. Let B be a d-regular graph with d 3 and consider the Broder-Shamir probability model, Cn(B) of random covering graphs of B 5 of degree n. Then for any " > 0, we have ProbG2Cn(B)[newB (AG) (A bB) + "] C/n (1.1) for some constant C = C(B; "). As mentioned above, Friedman's famous proof of the Alon Conjecture in [Fri08] can be here see as the specific case where the base graph, B, is the graph with one vertex and d/2 self-loops. We shall prove theorem 1.2.2 by using the fundamental ideas of Broder- Shamir [BS87], later refined by Friedman [Fri91, Fri08]. These methods en- able to use estimates for the expected number of closed, non-backtracking walks of a given length in a random graph. This leads us to theorems re- garding the eigenvalues of the Hashimoto matrix, HG, of a graph G. For d-regular graphs, there is a direct translation between Hashimoto eigenval- ues and adjacency eigenvalues, which allows us to prove theorem 1.2.2. The Hashimoto eigenvalues of a covering graph have properties similar to those of the adjacency eigenvalues. Our trace method allows to prove the following theorem on the Hashimoto eigenvalues of random covering graphs. Theorem 1.2.3. Let B be a d-regular graph with d 3 and consider the Broder-Shamir probability model, Cn(B) of random covering graphs of B of degree n. Then for any " > 0, we have ProbG2Cn(B)[newB (HG) (H bB) + "] C/n (1.2) for some constant C = C(B; "). Kotani and Sunada, in [KS00], show that if G is any graph of maximum degree, dmax , then any Hashimoto eigenvalue, , that is not real satisfies jj p dmax 1 and each adjacency eigenvalue, , of absolute value grater than 2 p dmax 1 gives rise to a real Hashimoto eigenvalue greater than p dmax 1. When 6 B is d-regular, it is known that (H bB) = pd 1 and hence, Kotani and Sunada's result shows that theorem 1.2.3 implies theorem 1.2.2. We be- lieve it is possible to use their result to prove a weakened generalized Alon conjecture, where (A bB) is replaced by 2pdmax 1. 1.3 Outline of Our Trace Method A lot of the techniques and theorems in this thesis hold for arbitrary base graph B. The case when B is regular is an important special case, one of the limited cases of B for which we establish Conjecture 1.2.1. However, many of the results in the following chapters are valid for arbitrary B. The techniques and theorems in this thesis apply to a number of mod- els of covering graphs of a base graph B of degree n. However, in this thesis, we assume the Broder-Shamir model mentioned above and to be described in more details in the next chapter. This means that for certain choices of a base graph B, the model insists that n be an even integer (in the case where B has half-loops). Definition 1.3.1. Consider the Broder-Shamir model, Cn(B), and let: (1) OccursB denote the connected graphs,H, such that for n sufficiently large, H is isomorphic to a subgraph of Cn(B) with positive probabil- ity; (2) Tangler;B = 2 OccursB j connected, (H ) p d 1 and ( ) < rg where ( ) is the Euler characteristic of the graph ; (3) r;B = Minimal elements of Tangler;B ; (4) HasTangler;B[n] = fG 2 Cn(B) j G has a subgraph isomorphic to an element of Tangler;Bg; (5) IHasTangle(r;B)[n](G) the indicator function of the event HasTangler;B[n]. (6) ITF(r;B)[n](G) = 1 IHasTangle(r;B)[n] the characteristic function of the complement of the event HasTangler;B[n]; 7 Most of the work in this thesis is devoted to an asymptotic series for the expected value of ITF(r;B)[n](G)Tr(HkG); i.e., the expected value of Tr(HkG), where we replace the trace by zero when G contains an element of Tangler;B as a subgraph. The series is in powers of 1/n, and the coefficients are polyexponentials in k, defined as follows. Definition 1.3.2. We say that a function, P = P (~k), defined on a tuple of non-negative integers, ~k, is polyexponential if P (~k) = X i igi;1(k1) : : : gi;t(kt) with i 2 C and where the functions gi;j are powerexponentials, that is function of the type g(k) = kks for some non-negative integer s and complex number . We call the set of all complex numbers in these functions the base of P and denote it by L = L(P ). Given a graph, B, set 1 = (HB) , the Perron-Frobenius eigenvalue of the Hashimoto matrix of B, and set L = LB to be those eigenvalues of HB that are greater than (1)1/2 in absolute value. We say that a function, P = P (k), defined on non-negative integers, is B-Ramanujan if there is a polyexponential function, Q(k), with bases L, such that for any ~" > 0 there is a C > 0 for which jP (k)Q(k)j CkC(1)1/2 + ~"k for all k ; we callQ the principal part or polyexponential part of P . (The prin- ciple part is therefore defined only modulo a term smaller than kC (1) 1/2+ ~" k for each ~" > 0 .) For example, if B = Wd/2 , then Cn(B) is the Broder-Shamir model of a random d-regular graph on n vertices, for d 4 even. Then the eigenvalues 8 ofHB are precisely d1; 1;1 (which feature prominently in [Fri91, Fri08]), andL = fd1g. Notice that the definition ofB-Ramanujan is less restrictive than the definition of d-Ramanujan in [Fri08], since our definition allows a ~" > 0, whereas in [Fri08] we essentially take ~" = 0. The ~" > 0 turns out to greatly simplify our estimates, and does not weaken any conclusions regarding the generalized Alon conjecture. Theorem 1.3.3. Let r be any positive integers. Then we have EG2Cn(B)[ITF(r;B)(G)Tr(HkG)] = P0(k)+P1(k)n1+ +Pr1(k)n1r+errr(n; k) (1.3) where the Pi(k) are B-Ramanujan functions in k, and there is a C for which jerrr(n; k)j CkC(d 1)knr In the above theorem, if we knew that the principle part of each Pi(k) was zero, then we could apply the methods detailed in [Fri08] to conclude the generalized Alon conjecture, i.e., Conjecture 1.2.1, for all d-regular graphs, B, by applying (1.3) to a single value of k which is proportional to logn. However, it turns out that the fact this (1.3) holds for many val- ues of k can be exploited to show that the fact that P0(k) = Tr(HkB) (which has essentially been known since [Fri03]) already implies the generalized Alon Conjecture, for B d-regular. The idea is that the principle part of each Pi(k) is annihilated by an appropriate polynomial of the shift in k operator, and we apply a polynomial of the shift operator to both sides of (1.3); we thereby show that the coefficients Pi(k) are accounted precisely by HG eigenvalues very near the eigenvalues of HB. This idea was called the Side-Stepping Lemma in [Fri08] -- side-stepping the fact that the principle parts of the Pi(k) are not known to vanish; in this article we give a somewhat stronger version of this lemma which allows us to prove the generalized Alon conjecture. We emphasize that the above results on the generalized Alon Conjec- ture would not follow by an application of (1.3) of one value of k for each n; rather we apply a polynomial of the shift k operator, meaning that we 9 simultaneously apply (1.3) to some values k; k + 1; : : : ; k + , where is a constant depending on "; r;B, and then take k an appropriate value, roughly proportional to logn. Furthermore, we mention that if we do not remove graphs, G, that con- tain tangles as above, but rather we directly apply the inequality ProbG2Cn(B)[ SpecnewB (AG)]k EG2Cn(B)[Tr(AkG) Tr(AkB)] to one value of k for each n, then we cannot get an interesting bound with = 2(d 1)1/2 + " for arbitrary " > 0; i.e., we cannot use the trace method as is to conclude the generalized Alon conjecture. 1.3.1 Series Expansions We now try to give a rough idea of how to prove (1.3), with Pi(k) being B- Ramanujan. We will have to be rather vague until we define precise notions of potential walks, and the form and type of a potential walk, in Chapter 3. The fact that (1.3) holds for some functions, Pi(k), is a consequence of the methods of [Fri91], and one main idea is already evident in [BS87]. The point is that a walk, w, in G, traces out a subgraph, Graph(w), in G, and one can study Tr(HkG) on the basis of the rough geometry of Graph(w). Specifically, Tr(HkG) counts the number of strictly non-backtracking walks in G, and by disregarding the walks, w, for which (Graph(w)) r (where is the Euler characteristic), we lose a factor of at most roughly nr k 2r Tr(HkB): The point is that if(Graph(w)) r, then the event that w occurs involves at least r coincidences, each coincidence contributing roughly a multiple of 1/n to its expected value (see Chapter 3). Furthermore, we can express the Pi(k) in terms of the type of a (length k, closed, strictly non-backtracking) walk, w, in G. Each walk, w, in G, traces out a subgraph, Graph(w) of G; given a covering map, : G ! B, 10 restricts to a map from Graph(w) to B. The basic idea of Broder and Shamir is to organize the walks, w, by the graph T associated to w by setting VT to be the initial vertex of w and all vertices of Graph(w) of degree at least 3; assuming w is non-backtracking, all vertices of Graph(w) have degree at least 2, and the vertices not in VT can be contracted to get a graph T whose vertices are VT and whose edges represent beaded paths (whose interior vertices are all of degree 2) in Graph(w). By comparison, ifw backtracks, then Graph(w) can have ver- tices of degree 1 and the geometry of Graph(w) can be more complicated. This idea is used in [Fri91], but is essentially the same as the case treated in Broder-Shamir; they consider non-backtracking closed walks that are not necessarily strictly non-backtracking, and there are two types---a cy- cle and a cycle with a tail---of Euler characteristic zero, that they address for their case of r = 1. For a walk, w, in G, we remember some additional data beyond the graph, T , obtained by collapsing the degree two paths inGraph(w); namely we remember (1) the vertices of B lying below (i.e., via the projection : G ! B re- stricted to Graph(w) G) the vertices of Graph(w) that we remember in T (i.e., the vertices of T , which are the initial vertex and all vertices of degree at least three), (2) a lettering, meaning, for each edge incident to a vertex of T in Graph(w), we remember to which edge in B it is mapped, and (3) the order in which all type edges and vertices are first encountered in w (so the edges and vertices of T are ordered sets), and the direction in which each edge is first traversed. We call this data the type of w, denoting it T , which consists of an un- derlying graph, T , along with the B structure of the 1-neighbourhood of all T vertices in w, and the ordering of the vertices and edges of T , and orientation of edges. 11 It turns out that, as a fairly straightforward extension of the ideas of [Fri91], we have that the Pi(k) are linear combinations of sums of the form:X ~m~k=k WT (~m;~k)P (~k); (1.4) where (1) ~m;~k 2 ZET1 ; i.e., ~m;~k are vectors indexed over ET of positive integers; (2) P (~k) is a polyexponential in bases Spec(HB), where ~k is a vector indexed over ET ; and (3) WT (~m;~k) counts the number of walks in T that correspond to walks contributing to closed, strictly non-backtracking walks of length k, where edge f 2 ET corresponds to a path of length kf in Graph(w) andmf is the number of times f 2 ET is traversed (in either direction). For now, WT (~m;~k) is independent of ~k. The problem with (1.4) is that the functionWT (~m;~k) is often too large to prove that the sum in (1.4) is B-Ramanujan. In fact, it is known that if you don't remove the tangles, then Pi(k) will not be Ramanujan for B = Wd/2 and i of size roughly d1/2 log d (see [Fri03]). To remedy this, we note that (1.3) can be generalized to EG2Cn(B)[Wn(G; k)] = PW0 (k) + PW1 (k)n1 + + PWr1(k)n1r + errr(n; k) (1.5) where W(G; k) counts strictly non-backtracking closed walks subject to certain types of restrictions (we will leave this vague for now, but see these are formalized as walk sums in [Fri08] and in chapter 3 in this article), and where PWi (k) are functions given by linear combinations of sums similar to (1.4), namely X ~m~k=k WWT (~m;~k)P (~k); (1.6) 12 with P (~k) are before, but nowWWT (~m;~k) counts walks in T , the underlying graph of T , corresponding to strictly non-backtracking closed walks with the restrictions ofW. The idea is that if W counts only the strictly closed, non-backtracking walks, w, such that don't trace out a tangle, thenWWT (~m;~k) should be small enough so that (1.6) converges to a B-Ramanujan function. In [Fri08] this was achieved with W being a selective trace, which is a fairly technical concept; in this paper we instead use a certified trace, which simply counts the w of with (T ) < r for which (HGraph(w)) < (d 1)1/2. (Note that Graph(w) and its associated type, T , with underlying graph T , have the same Euler characteristic, (Graph(w)) = (T ) ). The point is that in this case WWT (~m;~k) is simply the original WT (~m) if VLG(T;~k ), i.e., the graph formed from T by replacing each edge, f with a path of length kf , has (HVLG(T;~k )) < (d 1)1/2. What this means is that now we sum in (1.6) with the additional constraint in ~k that (HVLG(T;~k )) < (d 1)1/2. We call this W a certified trace. One crucial aspect of the certified trace, like other simplifications such as types, is that it leads to dealing with finite sums. This sum can be seen to be a good approximation to Tr(HkG), for graphs, G, that do not contain tangles from Tangle";r;B as subgraphs. Unfortu- nately, this sum seems unpredictable if G does contain such a tangle. As a remedy, one can see that if we form the same sum, but this time insist that G contains a tangle, we also get terms analogous to (1.6) that converge to B-Ramanujan functions. Subtracting the two walk sums, we get EG2Cn(B)[ ITF(G)Tr(HkG) ] = P0(k)+P1(k)n1+ +Pr1(k)n1r+errr(n; k); for B-Ramanujan functions Pi(k), and at this point we can apply a side- stepping lemma, as described in the previous section, and standard cal- culations to show that P0(k) = Tr(HkB), and conclude the generalized Alon Conjecture in the case of regular B. 13 Chapter 2 Preliminaries Since we do not always use standard terminology and since some con- cepts have not yet crystallized in the community; we define in this chapter the essential objects that we will be working with. We layout definitions for directed graphs, graphs, their adjacency and Hashimoto eigenvalues. We define graph coverings, variable-length graphs and the Broder-Shamir probability model for random graph coverings of a fixed based graph. We finish this chapter with a description of polyexponential and Ramanujan functions. 2.1 Essential Graph Terminology In this paper, we are working with a broader definition of what is usually called a graph. Mainly, we allow self-loops and multiple edges. We for- malize this below. Definition 2.1.1. A directed graph (or digraph) is a tuple G = (V;Edir; t; h) where V andEdir are disjoint sets -- the vertex and directed edge sets - and t : Edir ! V is the tail map and h : Edir ! V is the head map. A directed edge e is called a self-loop if t(e) = h(e), that is, if its tail is its head. Note that our definition also allows for multiple edges, that is distinct directed edges with identical tails and heads. Unless specifically mentioned, we will only consider directed graphs which have finitely many vertices and directed edges. The notation G = (VG; EG; tG; hG) is convenient when discussing more than one graph at a time, or if we want to emphasize the graph G. 14 A graph arises from a directed graph by adding an involution that pairs up edges. Definition 2.1.2. An undirected graph (or simply a graph) is a tuple G = (V;Edir; t; h; ) where (V;Edir; t; h) is a directed graph and where : Edir ! Edir, called the opposite map, is an involution on the set of directed edges (that is, 2 = idEdir is the identity) satisfying t = h. The directed graph G = (V;Edir; t; h) is called the underlying directed graph of the graph G. If e is an edge, we denote by e1 = (e) and call it the opposite edge. A self-loop e is called a half-loop if (e) = e and a whole loop otherwise. The oppositemap induces an equivalence relation on the directed edges of the graph and we call the quotient set, E, the undirected edges of the graph G (or simply its edges). Given an edge of a graph, an orientation of that edge is the choice of a representative directed edge in the equivalence relation (given by the opposite map). Next, we define morphisms of undirected and directed graphs. Definition 2.1.3. A morphism of directed graphs, ' : G ! H is a pair ' = ('V ; 'E) for which 'V : VG ! VH is a map of vertices and 'E : EdirG ! EdirH is a map of directed edges satisfying hH('E(e)) = 'V (hG(e)) and tH('E(e)) = 'V (tG(e)) for all e 2 EdirG . When confusion is unlikely to arise, we simply write ' instead of 'V or 'E . This forms the category of directed graphs (with the obvious identities and composition of morphisms). This category has products and coprod- ucts (disjoint unions). We can extend this to undirected graphs by requiring that H('(e)) = '(G(e)) for all e 2 EdirG . Note that in this case, the terminal object is the ver- tex with a half-loop (half-loops can only be mapped to half-loops, whereas whole-loops can be mapped to either whole or half loops). Definition 2.1.4. An oriented graph is an undirected graph, G, endowed with an orientation of each of its edges. In this context, when referring to an edge e 2 EG we always assume it represents its underlying directed edge and hence extend the language of directed edges to this edge (so 15 it has a tail and a head map) and we denote by e1 its opposite directed edge. Walks on graphs offer interesting questions on their own, see [Lov93] for a survey on the topic. We recall their definition and our terminology here. Definition 2.1.5. Let G = (V;Edir; t; h) be a directed graph and k 0 an integer. A walk of length k in G is an alternating sequence of vertices and directed edges, v0; e1; v1; e2; v2; : : : ; ek; vk for which t(ei) = vi1 and h(ei) = vi. We say that a walk is: closed if v0 = vk, Furthermore, if G is an undirected graph, say that a walk is: non-backtracking (or irreducible) if (ei+1) 6= ei for all i = 1; : : : ; k1, strictly non-backtracking (or strongly irreducible) if it is not closed and non-backtracking; or if it is closed, non-backtracking and (ek) 6= e1. When k > 0 it is easier to identify a walk with its sequence of edges only. Our main interest lies in the algebraic properties of graphs. We review some elementary definitions of algebraic graph theory in the next sections. 2.2 Adjacency Eigenvalues In this section, we describe our terminology and review fundamental prop- erties of the adjacency matrix and its eigenvalues. Definition 2.2.1. Given a directed graph G and an ordering of its vertices V = fv1; v2; : : : ; vng, its adjacency matrix, AG, is the nn square matrix in- dexed on the vertices whose (vi; vj) entry is the number of directed edges 16 whose tail is the vertex vi and head is the vertex vj . The adjacency matrix of an undirected graph is simply the adjacency matrix of its underlying di- rected graph. The ordering of the vertices is usually understood and since the algebraic properties considered are invariant under matrix similarity, it is customary to simply talk about the adjacency matrix of the graph itself. The adjacency eigenvalues (or simply the eigenvalues) of a directed graph G are the eigenvalues of its adjacency matrix. When the graph is undirected, its adjacency matrix is symmetric and hence the spectral the- orem guarantees that all its eigenvalues are real. In that case, we denote them by 1 2 : : : n, ordered in decreasing order and duplicat- ing eigenvalues by their multiplicity. We denote by Spec(AG) the multiset of these eigenvalues that we call the adjacency spectrum and define its adjacency spectral radius, (AG) or A(G) to be the largest adjacency eigenvalue in absolute value. We reserve the notation i(G) to denote the eigenvalues of the adjacency matrix of a graph G. Of interest to us, are d-regular graphs. We recall their definition and then some important and well-known properties of their adjacency eigenvalues. Definition 2.2.2. Let G = (V;Edir; t; h) be a directed graph and v 2 V be one of its vertices. We define the in-degree (respectively out-degree), denoted by degh(v) (respectively degt(v)), to be the number of directed edges whose head (respectively tail) is the vertex v. In the case of an undirected graph, the involution guarantees that the in-degree always equals the out-degree and hence we simply call it the degree of the vertex v and denote it by deg(v). Let d be a positive integer, we say that a graph is d-regular if the degree of each of its vertices is d. Using Perron-Frobenius theory, one obtains the following well-known properties of the adjacency eigenvalues. Proposition 2.2.3. Let G be a graph with adjacency eigenvalues 1 2 : : : n. Then 17 (1) Its first eigenvalue, 1, is the largest in absolute value and has a posi- tive eigenvector. This eigenvalue is often called the Perron-Frobenius eigenvalue. (2) The Perron-Frobenius eigenvalue satisfies 1 (G) where (G) is the maximal degree of the graph. Furthermore, if the graph is d-regular, then (3) The Perron-Frobenius eigenvalue satisfies 1 = d, and the vector (1; : : : ; 1) is an eigenvector. (4) Themultiplicity of the Perron-Frobenius eigenvalue is exactly the num- ber of connected components of the graph. (5) Any eigenvector for an eigenvalue that is not the Perron-Frobenius eigenvalue has its vector components sum to zero. One of the main combinatorial interest of the adjacency matrix is its connection to walks in a graph. We summarize these well-known properties in the following proposition. Proposition 2.2.4. Let G be a graph, AG its adjacency matrix, and k a positive integer, then (1) AkG i;j is the number of walks of length k starting at the vertex vi and ending at the vertex vj . (2) Tr(AkG) is the number of closed walks of length k in the graph G. 2.3 Hashimoto Eigenvalues Definition 2.3.1. Let G = (VG; EdirG ; tG; hG; G) be a graph, we define its associated directed line graph, denoted Line(G), to be the directed graph Line(G) = (VL; EdirL ; tL; hL) given as follow. Its vertex set, VL, is the set 18 EdirG of directed edges in the directed graph G. Its set of directed edges is defined by EdirL = n (e1; e2) 2 EdirG EdirG j hG(e1) = tG(e2) and G(e1) 6= e2 o that is, non-backtracking walks of length 2. The tail and headmaps are sim- ply defined to be the projections in each component, that is by tL(e1; e2) = e1 and hL(e1; e2) = e2. The adjacency matrix of the directed line graph of a graph G is called the Hashimoto matrix of G and we denote it by HG. The eigenvalues of the Hashimoto matrix are called the Hashimoto eigenvalues of G and we denote them by i(G), for i = 1; : : : ; jEdirG j, reserving 1(G) to denote the Perron-Frobenius eigenvalue of the directed line graph. Since the oriented line graph is not an undirected graph, those eigenvalues are not always real. We denote by Spec(HG) the multiset of these eigenvalues and call it the Hashimoto spectrum of the graph G. We define its Hashimoto spectral radius, (HG) or H(G) to be the largest Hashimoto eigenvalue in absolute value. Remark 2.3.2. In the case where the starting graph G is undirected, there is another construction, often referred to as the line graph, which takes for vertices the undirected edges of G. This yields a different construction than the one presented above and we do not use it in our work. Our main interest in the Hashimoto matrix is that it encodes strictly non- backtracking walks. We review here the main properties that we will be using in our work. Proposition 2.3.3. Let G be a directed graph and Line(G) its associated directed line graph. Then (1) A walk of length k in Line(G) corresponds to a non-backtracking walk of length k + 1 in G, (2) a closedwalk in Line(G) corresponds to a closed strictly non-backtra- cking walk in G 19 and hence, for any positive integer k we have (3) HkG i;j is the number of strictly non-backtracking walks of length k+1 starting at the vertex tG(ei) and ending at the vertex hG(ej). (4) Tr(HkG) is the number of closed strictly non-backtracking walks of length k in the graph G. Using the Ihara zeta-function, Bass proved show a relationship between the adjacency and Hashimoto eigenvalues. The Ihara zeta-function is a zeta function associated with a finite graph. It closely resembles the Sel- berg zeta-function, and is used to relate closed paths to the spectrum of the adjacency matrix. The Ihara zeta-function was first defined in [Iha66] by Yasutaka Ihara in 1966 in the context of discrete subgroups and then in [Sun86] by Toshikazu Sunada in the context of graphs in 1986. Definition 2.3.4. The Ihara-Zeta function of a graph G is the function G defined on the complex numbers and given by G(t) = 1 det [I tHG] If is a Hashimoto eigenvalue of G, then t = 1/ is a pole of G. In [Bas92], Bass proves that the Ihara-Zeta function can be expressed in terms of the adjacency matrix. Theorem 2.3.5 (Bass). Let G be a graph without half-loops, HG its Hashi- moto matrix, AG its adjacency matrix and DG the degree matrix, then G(t) = (1 t2)(G) det [I tAG + t2(DG I)] Using this theorem, we can link the adjacency eigenvalues to the Hashi- moto eigenvalues when the graph G is d-regular. Proposition 2.3.6. Let G be a d-regular graph with no half-loops and de- note by 1 : : : n its adjacency eigenvalues. Then its Hashimoto 20 eigenvalues are given as follow: For each adjacency eigenvalue , there are 2 corresponding Hashimoto eigenvalues (up to multiplicity), 1;2(), given as solutions of the equation 2 + d 1 = 0 Furthermore, there are Hashimoto eigenvalues 1 and 1 which each come with additional multiplicity n(d 2)/2. Proof. Using Bass formula, we obtain that det[I tHG] = (1 t2)(G) det I tAG + t2(DG I) Since G is d-regular, we have that DG I = (d 1)I and hence if is an adjacency eigenvalue, that is a solution of the equation det [I AG] = 0 then any solution, = 1/t of the equation 2 + (d 1) = 0 will be a solution of the equation det [I HG] = 0 and so yield a Hashimoto eigenvalue. For the second part of our assertion, just observe that if G is d-regular and doesn't have half-loops, then (G) = (jVGj jEGj) = n+ nd 2 = n(d 2) 2 which justifies the additional multiplicities of the Hashimoto eigenvalues 1 and 1. More generally, Kotani and Sunada, in [KS00], show the following result which is valid in the general case when the graph is not d-regular. Our bound on adjacency eigenvalues relies on this result and allows us to work with Hashimoto eigenvalues, which show to be easier to handle. Theorem 2.3.7 (Kotani and Sunada). IfG is any graph of maximum degree dmax , then any Hashimoto eigenvalue, that is not real satisfies jj p dmax 1 and if is an adjacency eigenvalue satisfying jj > 2 p dmax 1 gives rise 21 to a real Hashimoto eigenvalue greater than p dmax 1. 2.4 Graph Coverings Definition 2.4.1. A morphism of directed graphs : H ! G is a covering map if is an epimorphism (it is surjective on both the vertex and edge sets of G) and a local isomorphism, that is for any vertex w 2 VH , the edge morphism E induces a bijection between t1H (w) and t 1 G ((w)) and a bijection between h1H (w) and h 1 G ((w)); that is, a bijection between incident edges at this vertex. We call G the base graph and H a graph covering of G. If : H ! G is a covering map and G is connected, then the degree of , denoted [H : G], is the number of preimages of a vertex or edge in G under (which does not depend on the vertex or edge). If G is not con- nected, we insist that the the number of preimages of of a vertex or edge is the same, i.e., the degree is independent of the connected component, and we will write this number as [H : G]. A morphism of graphs is a covering map if the morphism on underlying directed graphs is a covering map. We are particularly interested in the behaviour of the eigenvalues of graph coverings. The following proposition shows that adjacency eigen- values of the base graph lift to their coverings. Proposition 2.4.2. Let B be a connected base graph and : G ! B a covering map of degree n. Then if : VB ! C is an eigenvector of the adjacency matrix, AB, of the base graph with associated eigenvalue , then = : VG ! C is an eigenvector of the adjacency matrix, AG, of the covering graph G with the same associated eigenvalue. Proof. Since is an eigenvector of the base graph, we have that for each vertex v 2 VB X e2t1B (v) (hB(e)) = (v) 22 Let us just check that is an eigenvector of the covering graph. Let w 2 VG, we haveX f2t1G (w) ()(hG(f)) = X f2t1G (w) ((hG(f))) Since is a covering map, it induces a bijection between t1G (w) and t1B ((w)) hence = X e2t1B ((w)) (f)=e ((hG(f))) Since is a morphism of graphs, it commutes with the tail map and so = X e2t1B ((w)) (f)=e (hB((f))) = X e2t1B ((w)) (hB(e)) = ((w)) = ()(w) This fact yields a notion of "new" and "old" eigenvalues among adja- cency eigenvalues of the graph covering. Definition 2.4.3. If : G! B is a covering map, we partition the multiset of its adjacency eigenvalues in two: Spec(AG) = SpecnewB (AG) t SpecoldB (AG) Wecall these respectively the new adjacency eigenvalues and old adjacen- cy eigenvalues of G, where SpecoldB (AG) = Spec(AB) is the set of eigen- values that are lifted from the base graph B. We denote by newB (AG) the largest new adjacency eigenvalue in absolute value of the graph G. 23 We want to establish the same type of relationship for Hashimoto eigen- values. First, we observe that covering maps induce covering maps on directed line graphs. Proposition 2.4.4. Let : G ! B be a covering map. Then induces a covering map Line : Line(G)! Line(B). Proof. The induced map Line : Line(G)! Line(B) is simply given by Line(f) = (f) and Line(f1; f2) = ((f1); (f2)) for any vertex in the directed line graph of G, f 2 VLine(G) = EdirG , (which are directed edges in G); and for any edge, (f1; f2) 2 ELine(G). This is clearly an epimorphism of directed graphs. To show that it is a local isomor- phism, consider a vertex f , in Line(G), which is simply a directed edge inG. The one-to-one correspondence between t1Line(G)(f) and t 1 Line(B)(Line(f)) is given by the one-to-one correspondence between h1G (w) and h 1 B ((w)) given by the covering at the vertex w = tG(f) and reciprocally for the head when looking at the correspondence on tails at the vertex hG(f). This implies "new" and "old" Hashimoto eigenvalues for graph cover- ings. Definition 2.4.5. If : G! B is a covering map, then the Hashimoto eigen- values of the base graph B lift to the covering graph G. We can hence partition the multiset of Hashimoto eigenvalues of G in two: Spec(HG) = SpecnewB (HG) t SpecoldB (HG) called respectively the new Hashimoto eigenvalues and old Hashimoto eigenvalues of G and where SpecoldB (HG) = Spec(HB) is the set of Hashi- moto eigenvalues that are lifted from the base graph B. We denote by newB (HG) the largest new Hashimoto eigenvalue in absolute value of the graph G. 24 2.5 Variable-Length Graphs We are interested in the various subgraphs that are traced out by random walks. If for example, a walk visits new vertices at each step and finally comes back to its starting point, we call this a simple loop. The length of that loop is not as important as its fundamental shape and thismotivates our usage of variable-length graphs which are graphs with weighted edges. This concept allows to handle graphs which have large or infinite parts of them being paths or regular trees. Definition 2.5.1. A variable-length graph is a tuple G = (V;Edir; t; h; ; `) where (V;Edir; t; h; ) is a graph and where each edge, e 2 E, is assigned a weight, `(e), called the length of the edge, that can be any positive integer. The length of a walk in a variable-length graph is the sum of all the lengths of the edges in the walk. If ~k 2 ZjEj0 is a vector of positive integers for each edge of G, we denote by VLG(G;~k ) the variable-length graph based on G with edge lengths given by ~k. All that we will be using in this thesis about variable-length graphs can be found in [Fri08], section 3.2. 2.6 The Broder-Shamir Model For a graph, B, and integer n, we give a model of random cover of B of degree n which slightly generalizes the model used in [Fri03]. Definition 2.6.1. Let B = (VB; EdirB ; hB; tB; B) be a graph that we refer to as the base graph of the model. A permutation assignment of B is a map : EdirB ! Sn satisfying e = (e) 1 where Sn denotes the set of permutations of n elements and where we denote by e the permutation associated to a directed edge e 2 EdirB . We associate a graph covering of degree n, denotedB[], to each permutation 25 assignment. This covering is constructed as follow. The vertex set and edge set respectively are V = VB f1; : : : ; ng and Edir = EdirB f1; : : : ; ng with the head and tail maps t(e; i) = (tB(e); i) and h(e; i) = (hB(e); e(i)) And the covering map, [] : B[] ! B is simply the projection on the first component. The Broder-Shamir model of degree n of B, we mean the uniform distribution over all permutation assignments, : EdirB ! Sn and we use Cn(B) to denote the induced probability space of covering graphs of degree n of the base graph B. If d is a positive even integer and B is the graph with one vertex and d/2 whole loops, the corresponding Broder-Shamir model is the one originally described by Broder and Shamir in [BS87] and then used by Friedman in [Fri03] and [Fri08]. Unless explicitly mentioned, all probabilities and expectations are com- puted on the Broder-Shamir model. If X is a random variable and E an event in the probability space Cn(B), we will denote their respective ex- pectation and probabilities by En[X] = EG2Cn(B)[X] and Probn[E ] (we might drop the mention of nwhen obvious in the context). In Chapter 4, we will need to describe the collection of all graphs that occur as a subgraph of a random covering, G 2 Cn(B), for some n large enough. We denote that set by Occurs(B). 26 2.7 Polyexponential Functions Definition 2.7.1. A powerexponential function is a function of the form g : Z0 ! C k 7! kks for some non-negative integer s and complex number . We call the base of the function and s its power. If ~k = (k1; : : : ; kt) is a t-dimensional variable, a t-variate powerexponential function is a product g(~k ) = g1(k1) : : : gt(kt) of powerexponential functions. We define a polyexponential function to be a C-linear combination of powerexponential functions, and similarly, we define t-variate polyexponential functions. The fundamental example of polyexponential function is the function that is the i; j-th entry of a k-th power of a fixed matrix. By the Jordan normal form, we know that this function is a polyexponential function, with bases being the eigenvalues of the matrix. In our work, we will only be interested in the case where the matrix is the Hashimoto matrix of a fixed base graph B. For example, in [Fri08], Friedman considered the Hashimoto matrix of the graph Wd/2 consisting of one vertex and d/2 whole-loops. In this case, the number of strictly non- backtracking walks of length k in Wd/2 is g(k) = (d 1)k + (d 1) + (d 2)(1)k which is a polyexponential function of bases d 1; 1;1, which are the eigenvalues of the Hashimoto matrix of the graph Wd/2. Definition 2.7.2. Let g1 and g2 be two functions defined on the non-negative integers. We define their convolution, g1 g2, to be the function on non- 27 negative integers given by (g1 g2)(k) = kX j=0 g1(j)g2(k j) for any k 0. First, we make the following observation. Theorem 2.7.3. The convolution of two polyexponential functions is poly- exponential. Proof. It suffices to do this for powerexponential functions. Let g1(k) = kks and g2(k) = kkt be two powerexponential functions, for ; 2 C and non-negative integers s; t. In the case = , we have (g1 g2)(k) = kX j=0 g1(j)g2(k j) = k kX j=0 (k j)sjt We now examine this sum kX j=0 (k j)sjt = kX j=0 sX i=0 s i ki(1)sijs+ti = sX i=0 (1)si s i ki kX j=0 js+ti Sums of the type Pk j=0 j p are known to be polynomials in k of degree p+1 and so we can conclude that (g1 g2)(k) = kp(k) for some polynomial 28 p(k) of degree at most s+ t+ 1. For the case where 6= , we remark that the polynomial g(x; y) = kX j=0 xkjyj satisfies g(x; y) = xk+1 yk+1 x y Differentiating s times in x and t times in y yields kX j=0 k j s j t xkjsyjt = xkhs;t(x; y) + ykht;s(x; y) for rational functions, hs;t, whose denominator contains only powers of xy. Expressing zs (with z an indeterminate) as a linear combination of binomial coefficients z 0 ; : : : ; z s and setting z to k j, and doing similarly for zt with z = j, yields the theorem. 2.8 Functions of Bounded Growth We are interested in results about the convolutions of two (or more) func- tions, when one or both functions are arbitrary functions satisfying some growth restrictions. Definition 2.8.1. We say that a function g = g(k) defined on non-negative integers has growth bounded by for some real > 0, provided that there exists a positive constant c for which jg(k)j CkCk 29 Theorem 2.8.2. The convolution of any finite number of functions of growth is again of growth . Proof. It is sufficient to consider the convolution of two functions, g1; g2; the general claim follows by repeated applications of the result for two func- tions. So consider g(k) = X k1+k2=k k1;k20 g1(k1)g2(k2) with g1; g2 having growth bounded by ; for some constants C1; C2 we have jg1(k)j C1kC1k and jg2(k)j C2kC2k There are k + 1 ways of writing k as the sum of two non-negative integers, k1; k1. For each such pair, (k1; k2), we have jg1(k1)g2(k2)j C1C2kC11 kC22 k1+k2 C1C2kC1+C2k Since there are at most k + 1 pairs, (k1; k2), we have jg(k)j C1C2(k + 1)kC1+C2k and so it follows that g has growth bounded by . For reasons that go back to [Fri91], we will need to convolve polyno- mials and polyexponentials with functions for which we only have a growth rate bound. Definition 2.8.3. For any polynomial, P = P (x), with real or complex coef- ficients, we define its coefficient norm, kPk as the largest absolute value among its coefficients in its expansion by powers of x; i.e., ks0 + xs1 + + xtstk = max i jsij Theorem 2.8.4. For every non-negative integerD there is a constant, C2 = C2(D), for which the following holds. Let Q = Q(x) be any polynomial of 30 degree at most D, and h(r) a function defined on non-negative integers, r, for which jh(r)j C1rDr for some positive constants, C1 and with < 1. Then the infinite sum, q(x) = 1X s=0 Q(x s)h(s) converges in coefficient norm, and has degree at most that of Q, and sat- isfies kqk C1C2(1 )2DkQk The same is true of qk(x) = 1X s=k+1 Q(x s)h(s) except the norm coefficient bound of qk is given by kqkk C1C2k2D(1 )2DkkQk Hence j(Q h)(k) q(k)j = jqk(k)j C1C2kQkk3Dk(1 )2D Proof. The statement on the convergence and norms of q and qh follow from Lemma 8.8 of [Fri08]; the fact that the sum begins with r = 0 just affects the constants slightly. For ease of reading, we review the proof, which goes back to [Fri91] (as the last step of the proof of Sublemma 2.16). The idea is that we can restrict ourselves to the cases where Q(x) = xi for some i between 0 and D. Then we write 1X r=0 Q(x r)h(r) = 1X r=0 (x r)ih(r) (2.1) and we expand the (x r)i via the binomial theorem, and use an identity 31 such as 1X r=0 r r = (1 )+1 to show the convergence to q for qk, and obtain the coefficient norm esti- mate. For the last statement, we see that 1X r=0 Q(k r)h(r) is absolutely convergent, and hence (Q h)(k) = kX r=0 Q(x r)h(r) = 1X r=0 Q(k r)h(r) 1X r=k+1 Q(k r)h(r) = q(k) qk(k) But for k 1, we have qk(x) is bounded in absolute value by D + 1 times its largest monomial, and hence jqk(k)j kqkk(D + 1)kD C1C2k2D(1 )2DkkQk(D + 1)kD C1kQkk(1 )2DC2k3D Corollary 2.8.5. Fix a d > 2, a D > 0, and an " > 0. Then for each 2 C with jj > pd 1 + " there exists a constant, C2, for which the following is true. If P (k) = kik with integer i with 0 i D, and h(r) satisfies jh(r)j C1rD( p d 1 + ")r, for some constant C1 > 0, then we have that p(x) = 1X i=0 P (x i)h(i) 32 converges to a polyexponential function p(k), and j(P h)(k) p(k)j C2( p d 1 + ")k Proof. We have (P h)(k) = k( eP eh) where eP (k) = ki; eh(k) = kh(k) Hence jeh(k)j C1rDk where p d 1 + " jj Hence 1, for a given d and ", is bounded away from zero. Now we apply theorem 2.8.4. 2.9 B-Ramanujan Functions Definition 2.9.1. LetB be a graph and g a function defined on non-negative integers, k. We say that g is B-Ramanujan if there is a polyexponential function P , with bases in the Hashimoto eigenvalues of B such that for every " > 0 there exists a constant C for which jg(k) P (k)j C((H bB) + ")k For example in our work, when the base graph,B, is d-regular, then (H bB) =p d 1. And when the base graph consists of d/2 whole-loops (for d even) on one vertex, then its Hashimoto eigenvalues are d 1; 1;1 and so a B-Ramanujan function is a d-Ramanujan function in the sense of [Fri08]. Definition 2.9.2. Let g1; : : : ; gs be functions on non-negative integers. Let ~m = (m1; : : : ;ms) be a s-tuple of positive integers. The weighted convolu- tion of the gi of weights ~m is denoted by (g1 : : : gs)~m and is defined to 33 be (g1 : : : gs)~m(k) = X ~m~k=k ~k~0 g(k1) : : : g(ks) And if ~k0 = (k01; : : : ; k0s) is a s-tuple of non-negative integers, we define the truncated weighted convolution, denoted by (g1 : : : gs)~k0~m , to be (g1 : : : gs)~k0~m (k) = X ~m~k=k ~k~k0 g(k1) : : : g(ks) This changes very little for the analysis, but is what we will be using for our certified trace. Example 2.9.3. Consider the case where g1(k) = g2(k) = (d 1)k and ~m = (1; 2), then the identity on partial sums of geometric series 1 + x+ : : :+ xt = xt+1 1 x 1 with x = d 1 easily gives (g1 g2)~m(k) = 8<: 1d2 (d 1)k+1 (d 1)k/2 if k is even, 1 d2 (d 1)k (d 1)(k+1)/2 if k is odd. This is not an exact polyexponential function, but it is a B-Ramanujan func- tion. Theorem 2.9.4. Let ~m ~1 and ~k0 ~1. Let g1; : : : ; gs be B-Ramanujan functions, then the (truncated) weighted convolution (g1 : : : gs)~k0~m is B-Ramanujan as well. Proof. First, observe that a change of variable 1 = k1 k01 + 1 2 = k2 k01 + 1 34 allows us, without loss of generality, to remove the truncated condition. So, we assume that ~k0 = ~1. If the function gi is B-Ramanujan, then we can write gi(k) = X `2L p`;i(k)` k + errori(k) where p`;i is a polynomial and where the error bound is such that for any " > 0, we have jerrori(k)j C( p d 1 + ")k for some constant C = C(i; "). The set L is always finite, since it is the set of Hashimoto eigenvalues that are larger than p d 1 in absolute value. Hence, without any loss of generality, we can assume that gi(k) = p`;i(k)` k or gi(k) = errori(k) with jerrori(k)j C( p d 1 + ")k and treat each of the three corresponding cases for i = 1; 2. Note that in either case, we have that jgi(k)j eCk eC(d 1)k for some constant eC, since d 1 is the largest possible Hashimoto eigen- value. Let us consider now, the case where both gi are error terms. In this case, we have j(gi g2)(k)j X m1k1+m2k2=k jerror1(k1)error2(k2)j X m1k1+m2k2=k C1( p d 1 + ")k1+k2 C2 #f(k1; k2) 2 Z21 j m1k1 +m2k2 = kg ( p d 1 + e")k for some e" sufficiently small and since k1 + k2 m1k1 +m2k2 = k and we 35 roughly bound #f(k1; k2) 2 Z21 j m1k1 +m2k2 = kg k + 1 2 k2 C2kC2 to obtain that j(gi g2)(k)j C( p d 1 + ")k for any " > 0 (for an appropriate choice of C and e") making it an error term of a B-Ramanujan function and thus B-Ramanujan itself. For each of the two remaining cases, we need to look at three sub cases: (1) when m1 = m2 = 1, (2) when m1;m2 2 and (3) when m1 = 1;m2 2. Consider (1), when m1 = m2 = 1. Then if g1 and g2 are both polyexpo- nential functions, theorem 2.7.3 shows that their convolution is polyexpo- nential as well and hence a B-Ramanujan function. In the case where g1 is polyexponential while g2 is an error term, corollary 2.8.5 shows that their convolution is a B-Ramanujan function. We can treat both cases when m1;m2 2 simply using the fact that gi(k) eCk eC(d 1)k. Indeed, we have j(gi g2)(k)j X m1k1+m2k2=k jg1(k1)g2(k2)j X m1k1+m2k2=k C1k C1 1 k C1 2 (d 1)k1+k2 (d 1)k/2 X m1k1+m2k2=k C1k C1 1 k C1 2 since if m1;m2 2 we have that k1 + k2 k/2 and so for some constant C2 we have j(gi g2)(k)j (d 1)k/2C2kC2 C3( p d 1 + ")k for some other constant C3 and any " > 0; which shows that it is an error term and hence a B-Ramanujan function as well. Finally, let us consider (3), when m1 = 1, m = m2 2, g1(k) = p(k)`k 36 is a polyexponential function and we will treat both cases for g2 by simply assuming that jg2(k)j CkC(d 1)k for some constant C. Then we have that (g1 g2)(k) = X k1+mk2=k p(k1)` k1g2(k2) = k/mrX i=1 g2(i)p(k mi)`kmi for some r = r(k) such that k/m r is the largest possible value of k2. We now rewrite this sum as `k 24X i1 p(k mi)g2(i) `mi X ik/mr+1 p(k mi)g2(i) `mi 35 since jg2(k)j CkC(d 1)k, m 2 and ` > p d 1, we have thatg2(i)`mi C1kC1 d 1`2 k C1kC1k for < 1. We can now apply theorem 2.8.4 to show that the convolution is a B-Ramanujan function. 37 Chapter 3 Walk Sums In this chapter, we show that the expected value of the kth-Hashimoto trace has an expansion in 1/n which satisfies, for any integer r, En[Tr(HkG)] = f0(k) + f1(k) n + : : :+ fr1(k) nr1 + error(r; k) nr where the fi are functions of k and with an upper bound on the error term of jerror(r; k)j ck4r(d 1)k Furthermore, such an expansion is obtained for a broader notion of trace that we call a walk sum. To obtain this result, we observe that the trace of the kth power of the Hashimotomatrix is the number of strictly non-backtracking closedwalks of length k. We generalize this notion with the definition of a walk sum, which counts the number of walks satisfying certain properties, and in this con- text, show that the expected number of walks has the desired asymptotic expansion. This follows and expands on the theory that was developed by Friedman in [Fri91] and then in [Fri08]. 3.1 Potential Walks We consider a probabilistic theory describing walks on a random cover of the base graph B. Consider the probability space Cn(B). For the purpose of this chapter, the base graph does not need to be d-regular. Definition 3.1.1. A potential (k; n)-walk is a pair (w;~t ) consisting of a walk, 38 called the base walk w = (v0; e1; v1; e2; : : : ; ek; vk) in the base graph B of length k; and a vector, called the trajectory ~t = (t0; : : : ; tk) with each ti 2 f1; : : : ; ng. We refer to k as the length and n as the size of the potential walk. Given G 2 Cn(B), we say that a potential (k; n)-walk (w;~t ) is feasible in G if the vector ~t represents the actual sheets that are visited when the walk w is lifted to G, that is, with the above notations, if ei(ti1) = ti 8i = 1; : : : ; k where G = B[] and = fege2EB . We denote by E(w;~t ) the event in Cn(B) that the potential walk is feasible in G and denote by P (w;~t ) the probability of this event. A potential (k; n)-walk is feasible if P (w;~t ) 6=> 0. Lemma 3.1.2. A potential (k; n)-walk (w;~t ) is feasible if and only if the fol- lowing two feasibility conditions hold: (1) for any i; j such that ei = ej , we have ti1 = tji () ti = tj (2) and for any i; j such that ei = 1ej , we have ti1 = tj () ti = tj1 Definition 3.1.3. The associated graph of a potential (k; n)-walk (w;~t ), de- noted by Graph(w;~t ), is the subgraph that is traced out in any random covering G 2 Cn(B) in which the potential walk is feasible. If e 2 EB is an edge in the base graph, we define ae = ae(w;~t ) to be the number of edges in the associated graph of the potential walk in the fibre of the edge e. And 39 if v 2 VB is a vertex in the base graph, we define bv = bv(w;~t ) to be the number of vertices in the associated graph of the potential walk which is in the fibre of the vertex v. Hence we have thatX e2EB ae = jEGraph(w;~t )j and X v2VB bv = jVGraph(w;~t )j and we denote by (w;~t ) = jVGraph(w;~t )j jEGraph(w;~t )j the Euler char- acteristic of the associated graph. Following the work of Friedman, we define the order of a potential walk (w;~t ) to be the non-negative integer ord(w;~t ) = (w;~t ). We will eventually regroup potential walks with similar graphs under our notion of forms and types. First we describe an obvious equivalence class among potential walks and their associated graph. Definition 3.1.4. Fix a base walk w = (v0; e1; v1; : : : ; ek; vk). We say that two trajectories of length k and size at most n, ~t and ~s, differ by a symmetry and denote this by ~t w ~s if they only differ by a permutation of the vertices in each fibre; that is if there exists a collection of permutations of n elements = fvgv2VB such that ~s = (~t ) that is if si = vi(ti) i = 0; : : : k This is a modification of the original definition in [Fri08] that accounts for the multiple vertices of the base graph. Indeed, consider the following two examples. First, if the base walk is a loop, then the trajectories (1; 1) and (1; 2) are not equivalent since the fist one yields a loop and the second an edge; but if the base walk is not a loop, then these trajectories are equivalent since they both yield an edge (they refer to vertices in different fibres of the base graph). With this definition we guarantee that if ~t w ~s then P (w;~t ) = P (w;~s ). Define the (n;w)-equivalence symmetry class of ~t to be [~t ]n;w = f~s j ~s w ~t and si n; i = 1; : : : ; kg We may omit the n subscript of n is understood. We denote by [w;~t ]n the 40 equivalence class of all potential walk with base walk w whose trajectories are in the equivalence class [~t ]n;w, that is [w;~t ]n = f(w;~s ) j ~s 2 [~t ]n;wg and we also say that these potential walk differ by a symmetry. Clearly, if two potential (k; n)-walks differ by a symmetry, then their associated graphs are canonically isomorphic (the isomorphism being given by the collection of permutation) and hence the quantities ae and bv are identical in the equivalence class for all e and v. 3.2 Walk Sums We make the following observation. If HG is the Hashimoto matrix of a random covering graph G, then En h Tr(HkG) i = X (w;~t )2W P (w;~t ) where W is the set of all potential (k; n)-walks (w;~t ) whose walk w is a closed strictly non-backtracking walk of length k in the base graph B. We want to generalize this to allow the use of some other "traces", that is sums of P (w;~t ) over appropriate w's and ~t's. Definition 3.2.1. A walk collection, W = fW(k; n)gk;n1 is a collection where for any two positive integers k and n the elements of the setW(k; n) are potential (k; n)-walks satisfying the following conditions. (1) Symmetry: The walk collection contains all trajectories that differ by a symmetry; that is, if (w;~t ) 2 W(k; n) then [w;~t ]n W(k; n). (2) Size invariance: The walk collection reflects the fact that the size of a walk isn't uniquely determined; that is, if (w;~t ) 2 W(k; n) then (w;~t ) 2 W(k;m) for all m maxfti j ~t = (t0; t1; : : : ; tk)g 41 (3) Strictly non-backtracking walks: All the potential walks in the walk col- lection are strictly non-backtracking; that is, the base walk w of any potential (k; n)-walk (w;~t ) in the collection is strictly non-backtracking (see definition 2.1.5). (4) Closed walks: All the potential walks in the walk collection are closed; that is, the base walk w of any potential (k; n)-walk (w;~t ) in the col- lection is closed and its trajectory must satisfy t0 = tk. Given a walk collection,W, its associated (k; n)-modified trace is the ran- dom variable,Wn, defined on Cn(B), where Wn(G; k) = #f(w;~t ) 2 W(k; n) j (w;~t ) is feasible in Gg if G 2 Cn(B). Given a walk collection,W, its associated (k; n)-walk sum is WalkSum(W; k; n) = X (w;~t )2W(k;n) P (w;~t ) Note that this sum is always a finite sum (unless the base graph B has infinitely many edges). Example 3.2.2. We denote by SNBC = fSNBC(k; n)gk;n1 the walk collec- tion of all strictly non-backtracking closed walks of length k and size n. Its associated (k; n)-modified trace is simply the kth Hashimoto trace: SNBCn(G; k) = Tr(HkG) (thought of as a random variable on Cn(B)) and its associated (k; n)-walk sum is simply the expected value of the kth Hashimoto trace: WalkSum(SNBC; k; n) = En[Tr(HkG)] This walk collection is the largest possible, that is, any other walk collection consists of subsets of this one. 42 Since walk collections are symmetric, we can regroup the terms of the above sum by grouping trajectories that differ by a symmetry. Definition 3.2.3. Let Esymm(w;~t )n = X ~s2[~t ]n;w P (w;~s ) then we have WalkSum(W; k; n) = X (w;[~t ]n;w)2W(k;n) Esymm(w;~t )n (3.1) Now we comment on Esymm(w;~t )n and will later use this to work out an asymptotic expansion of a walk sum. Proposition 3.2.4. Let (w;~t ) be a potential (k; n)-walk then we have Esymm(w;~t )n = Y v2VB n! (n bv)! Y e2EB (n ae)! n! (3.2) with ae and bv as in definition 3.1.3, provided that B has no half-loops; for each e 2 EB that is a half-loop, we replace (n ae)! n! by (n 2ae)!! (n 1)!! Proof. Since all potential walks considered differ by a symmetry, the prob- ability that they occur in a random cover is the same. Without loss of gen- erality, we can assume that ~t 2 [~t ]n;w and hence we have Esymm(w;~t )n = X ~s2[~t ]n;w P (w;~s ) = [~t ]n;w P (w;~t ) and we evaluate each term separately. First to compute the size of the equivalence class [~t ]n;w, we only need to consider how we can shuffle the vertices in the fibre of a vertex of the 43 base graph. If there are bv elements of the trajectory ~t in the fibre of the vertex v then there are n(n1) : : : (nbv+1)ways to choose those vertices among n possible and this is true for the fibre of each vertex v 2 VB of the base graph. A random coveringB[] is given by the choice of a collection of permu- tations = fege2EB . Assume B has no half-loops; if there are ae edges of the associated graph to the potential walk that are in the fibre of the base edge e, then it means that there are ae values of the permutation e that are determined by the walk. The other nae values can thus be chosen at random. This implies that there are (n ae)! permutations out of the pos- sible n! which satisfy the conditions imposed by the potential walk on the choice of the permutation e. Doing this for each edge of the base graph concludes the proof. If B has half-loops, then we replace the factorials by double factorials, where n!! = n(n 2)(n 4) : : : since e is a random perfect matching. 3.3 Asymptotic Expansion Again, begin with the assumption that B has no half-loops. We can rewrite equation 3.2 as n(w; ~t ) Y v2VB n(n 1) : : : (n bv + 1) Y e2EB 1 n(n 1) : : : (n ae + 1) Consider the power series expansions about x = 0 of (1 x)(1 2x) : : : (1mx) and 1 (1 x)(1 2x) : : : (1mx) The xi coefficient is a polynomial of degree at most 2i in m. Using this for x = 1/n, we can deduce that there must exist polynomials p0; p1; : : : in the variables ae and bv for e 2 EB and v 2 VB such that Esymm(w;~t )n = n(w; ~t ) X i0 pi(~a;~b ) 1 ni (3.3) 44 Definition 3.3.1. We call the polynomials p0; p1; : : : the expansion polyno- mials of the potential walk. We now comment on this expansion and in particular, its truncated form. Theorem 3.3.2. For any potential (k; n)-walk (w;~t ) with k n/2 and any integer r 1 we have Esymm(w;~t )n = n(w; ~t ) p0 + p1 n + : : :+ pr1 nr1 + error(k; n) nr (3.4) where the pi are the expansion polynomials of the potential walk (w;~t ) in the variables faege2EV ; fbvgv2VB and with jerror(k; n)j ck2r+2 where c is a constant that depends only on r. Proof. Consider a function of the form g(x) = (1 1x) : : : (1 sx)(1 1x)1 : : : (1 tx)1 where i and j are positive constants. The ith-derivative of this function satisfies the boundg(i)(x)i! (1 xmax)i Xj +Xji where max is the maximum of the k (by equation (6) in [Fri91] on page 339). Using Taylor's theorem about x = 0 we obtain that there must exist some 2 [0; 1/n] such that jerror(k; n)j (1 max)r X j + X j r On the interval [0; 1[ we have that (1 x)1 ex/(1x) and since max k we have (1 max)r erk/(nk). If k n/2 we have that erk/(nk) er, hence a constant that only depends on r. The P j represents the sum for 45 all v 2 VB of all sums of 0; 1; : : : ; bv 1, and the P j represents the sum of all e 2 EB of 0; 1; : : : ; ae1, both of which are at most 0+1+: : :+k1 = k 2 . Since 2 k 2 k2 we get the second part of the claimed error term. We now study the error term of the truncated expansion. Definition 3.3.3. Let W be a walk collection and r 1 a positive integer. We define its r-truncated (k; n)-modified trace to be the random variable, Wn;<r, defined on Cn(B) with Wn;<r(G; k) = #f(w;~t ) 2 W(k; n) j (w;~t ) is feasible in G and ord(w;~t ) < rg and we define its associated r-truncated (k; n)-walk sum to be WalkSum<r(W; k; n) = X (w;~t )2W(k;n) ord(w;~t )<r P (w;~t ) The following lemma is essentially the observation, dating to Broder and Shamir, of looking at walks and noticing that if a walk is of order i, it has i+ 1 coincidences. Lemma 3.3.4. For any walk collection,W, and any positive integer, r 1, we have that WalkSum(W; k; n) = WalkSum<r(W; k; n)+On jVBj k r + 1 (d 1)knr for any k n/3. Proof. We can use here the same method as in [Fri93]. Each walk w such that ord(w) r has at least r + 1 coincidences. Consider the first r + 1 coincidences that occur in w. There are k r+1 places among the steps of the walk and each coincidence represents an event of probability at most 1/(n k) in a random permutation (and 1/(n 2k) in a random perfect matching). Each such w begins at one of the njVBj vertices of the random graph. 46 We can use this now to prove an expansion theorem for any walk sum. Theorem 3.3.5. Let B be a base graph, letW be a walk collection, and fix an integer r 1. Then for all k n/2 we have WalkSum(W; k; n) = f0(k) + f1(k) n + : : :+ fr1(k) nr1 + error(r; n; k) where fi(k) = r1X j=0 X (w;[~t ])2Wj(k) pij(w;~t ) and whereWj(k) is the set of all equivalence classes of potential walks of length k and of order j; with the error term satisfying jerror(r; n; k)j ck4r(d 1)knr where c is a constant that depends on r only. Proof. The proof of this theorem mostly follows the proof of theorem 5.9 in [Fri08]. We review it briefly and indicate the one minor variation that accommodates it for a general base graph. Friedman first shows that for a given base walk w of length k n/2, we haveX [~t ]n;w ord(w;~t )r P (w;~t ) ck2r+2nr for some constant c depending only on r. Then he shows that if w is a non- backtracking base walk of length k, then there are at most ck2r+2 equiva- lence classes [~t ]n;w whose order with w is at most r 1. Combining equa- tions 3.1 and 3.4, and reordering by powers of n and then by the order of the potential walks considered, truncating for potential walks of order at least r. We introduce an error of at most ck2r+2nr per word by ignoring potential walks of order at least r. Each word has at most ck2r+2 associ- ated potential walk classes of order at most r 1 and truncating results in an error of at most ck2r+2 (given in theorem 3.3.2). The number of strongly 47 non-backtracking base walks is at most (d 1)k which yields the desired error bound. Such an expansion would give us the Alon conjecture if we could show that the coefficients, fi(k) are B-Ramanujan functions for all values of r. In chapter 4, we show why this doesn't hold and how the notion of tangle is responsible for this obstruction. 3.4 Types and Forms We finish this chapter with a section that describes how to rearrange the walk sum by examining more closely the shapes that the walks can take. Friedman first introduced the notions of types and forms in [Fri91] and then refined them in [Fri08]. We maintain the language and simplify the defini- tions here. The main difference is that we first define types as essentially variable-length graphs satisfying some technical conditions such that if we fix any positive integer, r, there are only finitely many types of order at most r. From there, we define forms and rewrite the walk sums accordingly. This will play a crucial role in chapter 4 where we will use this to obtain the de- sired B-Ramanujan asymptotic expansions. Definition 3.4.1. A type is a tuple T = (T; V ; E ;L), where T is an oriented graph, V an ordering of the vertices of T , E an ordering of the edges of T and L = (Lt;Lh), called the lettering of the type, where Lt;Lh : ET ! EB are maps of oriented graphs called the lettering at the tail and the lettering at the head respectively. Additionally, we require the following two condi- tions to hold: (1) All the vertices, except possible for the first one (in the ordering given by the type) are of degree at least 3, and (2) the lettering is consistent, that is, for any vertex v 2 VT and any edges f1; f2 2 ET such that tT (f1) = tT (f2) (respectively hT (f1) = hT (f2)) we have that Lt(f1) 6= Lt(f2) (respectively Lh(f1) 6= Lh(f2)). In other 48 words, the lettering at the tail for two edges sharing their tail vertex is distinct, and similarly at the head. Definition 3.4.2. A form of type T is a tupleF = (F; E)where F is a variable- length graph based on the underlying graph of the type T and where E is a labelling of the edges: if f 2 EF is an edge of F , then E(f) = (e1; : : : ; e`(f)) is a walk in the base graph B, where `(f) is the length of the edge f and we request that the labelling be consistent with the lettering of the type T , that is, we demand that e1 = Lt(f) and e`(f) = Lh(f) We write F 2 T to mean that the form F is of type T . Given a potential walk, (w;~t ), there is a unique type, T (w;~t ) and form, F(w;~t ), associated to it. The type is obtained by considering the as- sociated graph to the walk, removing all beaded paths, preserving only the initial vertex and other vertices of degree at least three. The vertices and edges are ordered as they occur in the walk. The edges of the form take their length from their corresponding beaded paths in the associated graphs and inherit their labelling from the corresponding walk in the base graph, which then becomes the lettering of the type. Recall that we defined the order of a potential walk, (w;~t ) to be the opposite of its Euler characteristic. Since, this only depends on the num- ber of edges and vertices and is stables when removing beaded paths, we can define the order of a form or a type to be the order of any of its associated potential walk and we denote it by ord(w;~t ) = ord(F(w;~t )) = ord(T (w;~t )). Proposition 3.4.3. For any positive integer r, there are only finitely many types T of order less than r. We denote that finite set, Types[r]. Proof. Besides the initial vertex which might be of degree 1, all other ver- tices in a type are of degree at least 3. Applying this to the handshaking 49 lemma, we obtain 2jET j = X v2VT deg(v) 1 + 3(jVT j 1) and since we require that jET j jVT j r we have jET j 3r + 2 and jVT j 2r + 2 which implies that there are finitely many graphs on which to base a type of order at most r. There are clearly only finitely many ways to order the vertices and the edges as well as adding a lettering (since the alphabet is finite and fixed by the based graph B). We are going to reorganize walk sums by types and forms. Definition 3.4.4. Let F = F(w;~t ) be a form associated to some potential walk (w;~t ) with underlying oriented graph F . We say that a walk in F is consistent inF if it is strictly non-backtracking, if it reaches every vertex and edge of F , and if it reaches them in the order specified by the orderings on F . Proposition 3.4.5. Let (w;~t ) be a potential walk and let F = F(w;~t ) be its associated form. There is a natural one-to-one correspondence between (1) the set of potential walk classes [w;~t ]n whose form is F , and (2) the set of consistent walks in F . Proof. This is immediate: A consistent walk uniquely defines a base walk and an equivalence class of trajectories and reciprocally. Lemma 3.4.6. Let T be a type, with underlying graph T and let e1 and e2 be two directed edges in T . Define NB(e1; e2; k) to denote all walks of length k from e1 to e2 in T . For each such walk, w and each edge, e 2 EB, of the graph B, let ae(w) be the number of times e appears in the walk w. Then 50 for any polynomial Q = Q(faege2ET ) in the variables ae, then we have thatX w2NB(e1;e2;k) Q(ae(w)) is a B-polyexponential function in k. Proof. This is proven just as in [Fri93]. Definition 3.4.7. Fix a walk collection, W, a type, T with underlying graph T . For every form, F , of type T , and every ~m 2 ZET1 , let WF (W; k; ~m ) be the number of consistent potential walk classes, [w;~t ]n 2 W(k; n), of form F , that traverse each edge, f 2 ET ,mf times. We say thatW ismultiplicity and length determined if WF (W; k; ~m ) is just a function of T ; ~m;~k where ~k = ~k(F) is the lengths of the ET -edges in the form F , i.e. WF (W; k; ~m ) = WT (~m;~k(F)) (3.5) Example 3.4.8. If W is the walk collection SNBC of all strictly non - back- tracking closed walks, then it is multiplicity and length determined. Fur- thermore, it is a function of ~m alone. Furthermore if the sub-collection,W0, of SNBC of all walks, w, for which the number of edges in Graph(w) is a prime number, then it is multiplicity and length determined; in fact, more generally, for every type, T , with underlying graph T , say one is a given a subset K(T ) 2 ZET1 ; let W0 be the walk sub-collection of SNBC of walks w for which the form of the walk has vector of length, ~k = ~k(F), on the ET edges that lie in K(T ), then the walk sub-collection,W0, is multiplicity and length determined. Definition 3.4.9. We say that a walk collection, W, decouples, if for every type, T with underlying graph T , the walk collectionW satisfies the follow- ing property: if two forms of type T induce the same edge lengths on ET , then the first form belongs toW if and only if the second one does too. In other words, to each type, T , there corresponds a subset of ZET1 such that a form of type T belongs to W if and only if the induced vector of edge lengths on T is in that subset. 51 This allows us to state the main theorem of this section, namely an ex- pansion of the walk sum in terms of types. Theorem 3.4.10. Given a walk collection W that is multiplicity and length determined, and a positive integer r, we have an expansion, called the type-form expansion ofW: WalkSum<r(W; k; n) = X T 2Types[r] n ord(T ) rord(T )X i=0 QT ;i(k)ni+error(r; n; k) where the QT ;i are functions satisfying QT ;i(k) = X ~m;~k2ZET1 ~m~k= k WT (~m;~k )Pi(~k ) where the Pi(~k ) are B-polyexponential functions, and WT (~m;~k ) is the function given in equation 3.5. Finally, the error term satisfies a similar bound to theorem 3.3.5, that is jerror(r; n; k)j ck4r(d 1)knr Proof. Given a form F , we denote by WF (W; k; n) the number of poten- tial walk classes, [w;~t ]n of length k in the walk collection whose form is F . The previous proposition shows that this is the same as the number of consistent walks of length k in the from. Given a potential walk, (w;~t ), its associated form, F , contains infor- mation that is equivalent to the ae and bv and hence, Esymm(w;~t )n only depends on the form. So we define E[F ]n = Esymm(w;~t )n. This allows to rewrite our walk sums as WalkSum(W; k; n) = X T X F2T WF (W; k; n)E[F ]n Further on, we will only sum over types of at most some order, so the sum will effectively be finite. 52 For a fixed type, T , define E[T ]n;k to mean E[T ]n;k = X F2T WF (W; k; n)E[F ]n Since we usually do not work with more than one walk collection at a time, we drop its mention from the notation. For a ~k = fkege2ET , let T (~k ) denote the set of all forms, F , of type T , such that the length of the edges of the forms is given by ~k. For each edge e 2 ET of the type, fix an integer me 1, and denote ~m = fmege2ET . This allows us to write E[T ]n;k = X ~m~k= k WT (~m;~k ) X F2T (~k ) E[F ]n Since each of the E[F ]n have a 1/n expansion, by adding expansions, we get an asymptotic expansion X F2T (~k ) E[F ]n = n ord(T ) X F2T (~k ) P0(F) + P1(F) n + : : : where Pi(F) = pi(~a(F);~b(F)) where the pi are the expansion polynomials in equation 3.3. Note that the vector ~b(F) is an affine linear function of the variables ~a(F) for all forms F of a given type T , so we write Pi(F) = Pi;T (~a(F)) Rearranging the sum yields En[T ]n;k = n ord(T ) Q0(k) +Q1(k)n 1 + : : : 53 where Qi(k) = X ~m;~k ~m~k= k WT (~m;~k ) X F2T (~k) Pi;T (~a(F)) For each form, F , of type T , let Ae;f (F) be the number of occurrences of a label e 2 EB on an edge f 2 ET . We have that ~a(F) = fAe;f (F)ge2EB ;f2ET for all e 2 EB, ae(F) = X f2ET Ae;f (F) and for a form F 2 T (~k ), we have that kf = X e2EB Ae;f (F) We claim that X F2T (~k) Pi;T (~a(F)) is polyexponential in k; indeed, it suffices to show that for any non-negative integers, se;f , with e 2 EB, f 2 ET , we haveX F2T (~k) Y f2ET Y e2EB Ae;f se;f is polyexponential in ~k. But sinceW decouples, the above equals Y f2ET 0@ X wf2NB(e1(f);e2(f);kf ) 0@ Y e2EB Ae;f se;f1A1A where e1 and e2 are determined by the lettering, which by Lemma 3.4.6 is just Y f2ET Pf (kf ) 54 for some polyexponential functions, Pf , with bases in the spectrum of HB. Hence X F2T (~k) Pi;T (~a(F)) is polyexponential in k. 55 Chapter 4 Tangles and the Certified Trace Tangles are low-probability events that prevent our asymptotic expansion of the expected trace to have B-Ramanujan coefficients. This was first observed by Friedman in [Fri08] and lead him to define a selective trace, which despite being quite cumbersome, showed to be effective to settle the Alon Conjecture. In our work, we simplify his selective trace and develop a certified trace in this chapter. Before doing this, we review his arguments and revisit the language, which we have simplified as well. In [Fri08], Theorem 2.12, Friedman shows that there exists an absolute constant (independent of d), C, such that the expansion functions, fi, of Theorem 3.3.5, cannot be B-Ramanujan for all i Cpd log(d). This is due to the presence of rare events, called tangles, which we describe again in the next section. This observation lead Friedman to develop a modified trace (the selective trace of [Fri08]) that essentially avoids those tangles. We here introduce another modified trace, the certified trace, which shows to be simpler to use than the selective trace. The main result of this chapter is Theorem 4.4.1, which shows that we can obtain a B-Ramanujan expan- sion of the certified trace of arbitrary length. 4.1 Tangles Wemainly use the theory developed by Friedman. We are modifying some of the language and notation, so we revisit the whole theory here for sim- plicity and clarity. In [Fri08], Friedman shows that when d-regular graphs contain some specific subgraphs, their second largest eigenvalue cannot be bounded 56 by the desired bound of 2 p d 1. We review here his arguments and gen- eralize them to the context of random covers of a d-regular base graph. Theorem 4.1.1. Fix d 3, a d-regular base graph B and a connected graph whose maximum degree is at most d. Then any covering graph G of degree n of the base graph B which contains as a subgraph satisfies newB (AG) (ATreed( )) on (1) where Treed( ) is the universal cover of d-regular graphs with a -inclusion (for more details on how to construct this universal cover, see [Fri08] defi- nition 3.12). Proof. This is Theorem 4.2 in [Fri08]. We repeat here the main points of his proof for completeness. Fix an " > 0, we will show that for n large enough, any graph G on n vertices that contains has newB (AG) (ATreed( )) ". First, there is a finitely supported function on the vertices of Treed( ) such that kAfk kfk( ") where A is the adjacency operator of Treed( ) and without loss of gener- ality, we can assume that f is non-negative, non zero and that Af(v) ( ")f(v) 8v 2 VTreed( ) If we let : Treed( ) ! G denote the covering map, we can define f to be the function on G defined by (f)(v) = X (w)=v f(w) And show that AG(f) ( ")(f) So the Rayleigh quotient, RAG of f satisfies RAG(f) " 57 On the other hand, the support, N , of f is of size no greater than that of f and this size is bounded independently of G and n. Hence, we can conclude that if g is the characteristic function of the set of vertices of G at distance at least 2 to the support, N , of f , then its Rayleigh quotient satisfies RAG(g) d on (1) and since f is orthogonal to both g and AGg, then we can use the Min- Max theorem and conclude the proof. In most cases, the infinite tree Treed( ) has spectral radius 2 p d 1 but in some rare cases the radius is larger than that. In what is dubbed a curious theorem, Friedman shows that this can be characterized in terms of Hashimoto eigenvalues. For completeness, we restate his result here. Theorem 4.1.2. Let d 3 and let be a connected graph whose maximum degree is at most d, then A(Treed( )) = 2 p d 1 () H( ) p d 1 A(Treed( )) > 2 p d 1 () H( ) > p d 1 Proof. This is Theorem 3.13 in [Fri08]. We repeat here themain points of his proof for completeness. Consider G, the variable-length graph based on the graph that realizes Treed( ). Then 1(Treed( )), the spectral radius of the d-regular tree completion of the the graph , is the inverse of the infimum of all the positive roots, z, of the equation det [I ZG(z)] = 0 In other words, we have 1 1(Treed( )) = inf fz j det [I ZG(z)] = 0g Where ZG(z) is the adjacency matrix of G. Lemma 4.1.3. For any connected graph and the variable length graph 58 G = Treed( ) we have ZG(z) = zA+ dI D d 1 Sd(z) whereA = A is the adjacency matrix of the graph ,D = D is its degree matrix and Sd(z) = 1p1 4(d 1)z2 2 Lemma 4.1.4. The largest irreducible eigenvalue of the graph , Irred( ) is the inverse of the smallest root, y of the equation det[I yA+ y2(D I)] = 0 Proof. This is a straight consequence of Bass' formula: det[H I] = (2 1)( ) det[(2 + d 1)I A] where Irred( ) is the largest solution of the equation det[H I ] = 0 by substituting y = 1/ we get the equivalence of the solutions. Now consider the change of variables y = y(z) = z 1 Sd(z) () z = z(y) = y (d 1)y2 + 1 which is valid if jzj < 1 2 p d 1 and jyj < 1p d 1 Notice that this change of variable is increasing as long as it converges. Then we have I ZG(z) = (1 Sd(z))(I yA+ y2(D I)) which holds for jzj < 1 2 p d 1 59 We can now finish the proof. First, take the case where 1(Treed( )) > 2 p d 1 then there is a z0 such that z0 < 1 2 p d 1 which is a root of the equation det[I ZG(z)] = 0. Let y0 = y(z0) = z0 1 Sd(z0) which is clearly a root of the equation det[IyA+y2(DI)] = 0 and since y0 < (d 1)1/2 we can conclude that Irred( ) > p d 1 Finally, for the case where 1(Treed( )) = 2 p d 1 then this means that if z0 is a root of det[I ZG(z)] = 0 then we have that 1 z0 2pd 1 Assume by contradiction that Irred( ) > p d 1 then there exists a y0 such that y0 < (d 1)1/2 and that is a root of the equation det[I yA+ y2(D I)] = 0 But then, our correspondence of eigenvalues gives an associated eigen- value z0 such that z0 < 1 2 p d 1 which contradicts our hypothesis. Hence we can claim that Irred( ) p d 1 which concludes the proof of this property. We formalize this with the following definition. Despite the appear- 60 ances, the case of graphs whose largest irreducible eigenvalue is preciselyp d 1 is critical as well for reasons we will expose later on. Definition 4.1.5. A connected graph whose maximum degree is at most d 3 is called a d-tangle (or simply a tangle) if (H ) p d 1 We say that is d-critical if (H ) = p d 1. We denote the set of all tangles that occur in some element of the Broder-Shamir model by TangleB. Using the notation developed in section 2.6, we can write TangleB = f 2 Occurs(B) j (H ) p d 1g The order of a tangle is the opposite of its Euler characteristic, that is, we define the order to be the non-negative integer: ord( ) = jE j jV j and we let Tangler;B be the subset of all tangles of order less than r, that is Tangler;B = f 2 TangleB j ord( ) < rg And finally, we consider the event, HasTangler;B[n], where a random cov- ering graph, G, contains a subgraph that is isomorphic to a tangle of order less than r, that is HasTangler(B)[n] = fG 2 Cn(B) j 9H < G;H 2 Tangler;Bg For the trace method to yield the Alon conjecture, one must then avoid these tangles. First, we show that if we restrict ourselves to tangles up to some fixed order, then there are only finitely many of them to consider. Theorem 4.1.6. Consider the set Tangler;B of all tangles of order less than r, and let HasTangleminr;B be the minimal set of Tangler;B, that is the set of all tangles of order less than r that are minimal with respect to inclusion. Then the set HasTangleminr;B is finite. Proof. This is lemma 9.2 of [Fri08]. We repeat here the main points of his 61 proof for completeness. Assume by contradiction that the set is not finite. Then there must exist a type T , with underlying graph T and an infinite sequence of tangles of type T , which each correspond to a choice ~k 2 ZET1 of lengths of the edges of T . Let us refer to that infinite sequence by f~kigi1, without loss of generality, for each edge f 2 ET , we can assume that the corresponding sequence of lengths for this edge is either constant or tends to infinity. Furthermore, there must exist at least one edge whose length sequence tends to infinity. Denote by 1 this limiting graph, where we discard the edges with length tending to infinity. Since tangles have their Hashimoto spectral radius at least p d 1, the same must hold for the limiting graph and hence 1 is a tangle as well. Furthermore, the order of 1 is at most that of the tangle in the sequence and clearly is included in all of them, which contradicts their assumed minimality. Definition 4.1.7. We will denote by ITF(r;B)[n] the indicator function of the complement of the event Tangler;B[n], that is ITF(r;B)[n](G) = 1 () G /2 Tangler;B[n] A lot of work in this thesis consists of obtaining a B-Ramanujan expansion of En[ITF(r;B)[n] Tr(HkG)] for any choice of r, then our side-stepping lemma, described in chapter 5, will allow us to conclude the Alon conjecture. Tangles are rare events in the sense of the following theorem. Theorem 4.1.8. Let be a tangle of order r. Then the expected number of occurrences of in an element G of Cn(B) is nr + On nr1 and the probability that al least one occurrence occurs is a at most nr/c + On nr1 where c is a constant depending on the tangle. Proof. This is Theorem 4.7 in [Fri08]. We repeat here the main points of his proof for completeness. Let V = f u1; : : : ; usg and for a tuple ~t of distinct integers between 1 and n, let ~t denote the event that the map mapping ui to the vertex at height ti above the matching vertex of the base graph B, is an occurrence of in G 2 Cn(B). If ae is the number of edges of 62 labelled with the edge e 2 EB, then the event ~t involves setting ae values of the corresponding permutations which will occur with probability at most Y e2EB (n ae)! n! = njE j +On njE j1 Since the sum of the ae is jE j. For any vertex v 2 VB, denote by vb the number of vertices of in the fibre of v, then the number of choices for ~t is Y v2VB n! (n bv)! = n jV j +On njV j1 and so we can conclude that the expected number of occurrences of is n ord( ) +On n ord( )1 The remaining part of the proof is obtained by an inclusion-exclusion ar- gument, observing that the order of subgraph is always at least that of the graph containing it (and the order is strictly less if the graph is properly con- tained); that if a graph has two connected components, then both must be of non-negative order; and that the if a tangle is made of two distinct copies of a smaller tangle, than its order is strictly larger than that of the smaller tangle. We now comment on the probability that a random covering contains a tangle. Proposition 4.1.9. Consider the event HasTangleminr;B [n] of all the random graphsGwhich contain an element ofHasTangleminr;B . Then, for r sufficiently large enough we have Probn h HasTangleminr;B [n] i = Cn for some = fund(B). Proof. We can use Theorem 4.1.8 and obtain that this is true for fund(B) being the smallest order of a tangle in HasTangleminr;B . 63 Corollary 4.1.10. We have an expansion Probn[ITF(r;B)[n](G) = 1] = 1 q1n1 q2n2 : : : where qi are some constants. Proof. We simply apply the inclusion-exclusion principle to proposition 4.1.9. 4.2 Finitely Certifiable Partial Orders In this section, we revisit cones in partially ordered sets. The main theorem of this section is Theorem 4.2.14, which shows that under some assump- tions (that we call being finitely certifiable), some infinite sums can be dealt with using only finitely many cone sums. This result will be used in the fol- lowing section to define a certifiable trace. Definition 4.2.1. Let (P;) be a partially ordered set. For p 2 P we define the cone at p to be Cone(p) = ft 2 P j t pg and we define the open cone at p to be Cone(p) = ft 2 P j t > pg Definition 4.2.2. Let (P;) be a partially ordered set and let p; q 2 P be two distinct elements of the set. We say that p and q have a maximum (or least upper bound) if there exists an element, denoted max(p; q), such that Cone(p) \ Cone(q) = Cone(max(p; q)) We say that (P;) has maximums if every pair of distinct elements p; q 2 P have a maximum. Definition 4.2.3. A subset Q P of a partially ordered set (P;) is an upper set if q 2 Q implies that Cone(q) Q. We say that (P;) has finitely 64 generated upper sets if every upper set, Q P , has a finite number of minimal elements, which we denote Minimal(Q); that is, if every upper set is the union of finitely many cones. Definition 4.2.4. We say that a partially ordered set (P;) is Noetherian if every infinite sequence of upper sets in P Q1 Q2 : : : stabilizes, that is there exists a positive integer N such that Qi = Qj for all i; j N . We make this simple observation. Theorem 4.2.5. A partially ordered set is Noetherian if and only if it has finitely generated upper sets. Proof. Assume that (P;) is Noetherian. Let Q P be an upper set and assume by contradiction that Minimal(Q) is infinite. Then, there exists a countable sequence of distinct minimal elements q1; q2; : : :. Consider the sets Qi = i[ j=0 Cone(qj) Each Qi is an upper set since it is a union of cones and clearly Qi Qi+1 for all i 1 but this sequence cannot stabilize since it is constituted of minimal elements, which contradicts (P;) being Noetherian. Assume now that (P;) has finitely generated upper sets and consider an infinite sequence of upper sets Q1 Q2 : : : Consider the set Q = [ i0 Qi Being the union of upper sets makes it an upper set as well, and hence it has a finite set of minimal elements, Minimal(Q) = fq1; : : : ; qng. Since there are finitely many of them, they must all belong to some Qj for j large enough and thus have the sequence stabilize which shows that (P;) is Noetherian. 65 Definition 4.2.6. A partially ordered set (P;) is finitely certifiable if it has maximums and is Noetherian. Proposition 4.2.7. Let (P;) be a finitely certifiable partially ordered set, and let Q P be an upper set of P . Then (Q;) is finitely certifiable. Proof. Since Q is an upper set, we are guaranteed that the maximum of any two elements in Q is in Q as well. And similarly, if Q1 Q2 : : : is a sequence of upper sets in Q, then since it stabilizes in P it does in Q as well. Definition 4.2.8. Let (P1;1) and (P2;2) be two partially ordered set. De- fine their product to be the partially ordered set (P1 P2;) where (p1; p2) (q1; q2) () p1 1 q1 and p2 2 q2 Wewant to show now that the finite product of finitely certifiable partially order sets is finitely certifiable as well. For this, we first show the following lemma. Lemma 4.2.9. Let (P;) be a Noetherian partially ordered set, and let P 0 P be any infinite subset of P . Then there is an infinite sequence p1; p2; : : : of elements of P for which p1 < p2 < : : : that is, for all i we have pi 6= pi+1 and pi pi+1. In particular, there is no infinite subset of incomparable elements. Proof. Let Q be the union of the cones of the elements of the set P 0. Since Q is an upper set, it has a finite set of minimal elements, Minimal(Q), which has to be a subset of P 0. So there must exist at least one element of Minimal(Q), say p1, whose cone meets infinitely many elements of P 0. Let P 00 be those elements of P 0 in the cone of p1 that are not equal to p1. Ap- plying the same argument to the set P 00 yields an element, p2, in P 00 whose cone meets an infinite number of elements of P 00 and clearly we have that p1 < p2. Iterating this argument yields the desired infinite sequence. 66 Theorem 4.2.10. Using the notation of definition 4.2.8, the product of two finitely certifiable partially ordered sets is finitely certifiable. Proof. Let Q be an upper set of (P;) and assume by contradiction that the set Minimal(Q) is infinite. This implies that there is an infinite sequence (p11; p 1 2); (p 2 1; p 2 2); (p 3 1; p 3 2); : : : of distinct elements of Minimal(Q). Then we can find an infinite sequence of distinct elements in either P1 or P2. Without loss of generality, let us assume that the set P 0 = fp11; p21; : : :g P1 is infinite and that its element are all distinct, that is, for all i 6= j we have pi1 6= pj1. Passing to a subsequence and using lemma 4.2.9, we can assume without loss of generality that we have p11 < p 2 1 < p 3 1 < : : : But then we can conclude that for each i 6= j we have pi2 6= pj2 or else one of (pi1; p i 2) and (pi1; p j 2) would not be minimal. Hence the set fp12; p22; : : :g P2 is an infinite set. Using lemma 4.2.9 again and passing to a subsequence, we can assume without loss of generality that we have p (1) 2 < p (2) 2 < p (3) 2 < : : : for some permutation, , of the integers. But this is impossible: consider j0 such that (j0) = 1 then for any j > j0 we have p12 = p (j0) 2 < p (j) 2 and hence (p11; p 1 2) < (p (j) 1 ; p (j) 2 ) which contradicts the minimality of (p(j)1 ; p (j) 2 ). 67 Our main interest in this paper consists of the following example. Example 4.2.11. Let Zt0 be the set of non-negatives t-tuples and equip it with the partial order (a1; : : : ; at) (b1; : : : ; bt) () ai bi 8i then this partially ordered set is finitely certifiable. Proof. Using Theorem 4.2.10, we simply need to show that the partially ordered set (Z0;) is finitely certifiable. The existence of maximums is obvious. Since this set is actually well-ordered, an upper set is always of the form [a;+1[ for some element a which its unique minimal element; which implies that it is a Noetherian partially ordered set. We now study functions on partially ordered sets and aim to conclude that when they are finitely certifiable, functions can be expressed as finite linear combinations. Definition 4.2.12. Let (P;) be a partially ordered set and let L1(P ) denote the set of functions f : P ! C for which kfk1 = X p2P jf(p)j is finite. For each function f 2 L1(P ) and element p 2 P define the cone sum of f at p to be bf(p) = X q2Cone(p) f(q) We now state an inclusion-exclusion theorem, giving Möbius-type co- efficients. Theorem 4.2.13. Let (P;) be a finitely certifiable partially ordered set and let f 2 L1(P ). Then for all p 2 P , there are integers (p) for which (1) (p) = 0 for all but finitely many elements, p 2 P , and 68 (2) for any function f 2 L1(P ) we haveX p2P f(p) = X p2P (p) bf(p) Specifically, (p) is the sum of the number of times p appears as the maxi- mum of an odd number of minimal points of P , minus the number of times it appears as the maximum of an even (non-zero) number of minimal points. Proof. Let " > 0, we will show that X p2P f(p) X p2P (p) bf(p) < " for some coefficients, (p), that we will describe below. We begin by replacing f by a function which is very close but has the advantage of having a finite support, which we need in order to rearrange what would otherwise be infinite sums. SinceX p2P jf(p)j is finite, there exists a function f" of finite support such that kf f"k1 < ". Now, we observe that j bf(q) bf"(q)j < ", since j bf(q) bf"(q)j X p2Cone(q) jf(p) f"(p)j kf f"k1 < " Now since f" has a finite support, we can use the finite inclusion-exclusion principle on the cones of the minimal elements of P to obtain X p2P f"(p) = X 1i1n bf"(pi1) X 1i1<i2n bf"(max(pi1 ; pi2)) + : : : + (1)n+1 X 1i1<:::<inn bf"(max(pi1 ; : : : ; pin)) 69 This sum being finite, we can rearrange it and write asX p2P (p) bf"(p) where is a function on P whose support is included in the set of all pos- sible combinations of maximums of minimal elements of P , that is support() fmax(pi1 ; : : : ; pik) j k = 1; : : : ; n ij 2 f1; : : : ; ngg As claimed in the theorem's statement, one can see that (p) is the sum of the number of times p appears as the maximum of an odd number of minimal points of P , minus the number of times it appears as the maximum of an even (non-zero) number of minimal points. We now have X p2P f(p) X p2P (p) bf(p) X p2P f(p) f"(p) + X p2P f"(p) (p) bf"(p) + X p2P (p) bf"(p) (p) bf(p) kf f"k1 + 0 + " X p2P j(p)j < C" For some fixed constant C which only depends on P and thus concludes the proof. This allows to state the main theorem of this section. It follows immedi- ately from the above theorems and its application suggests a very simple modified trace that we will describe in the next section. Theorem 4.2.14. Let (P;) be a finitely certified partially ordered set, let Q be an upper set of P and let f 2 L1(P ). Then there exists Möbius coefficients, Q : Q! Z, such thatX q2Q f(q) = X q2Q (q) bf(q) 70 where Q(q) = 0 for all but finitely many elements of Q. Proof. This is immediate, applying Theorem 4.2.13 toQ itself since proposi- tion 4.2.7 guarantees it is a finitely certifiable partially ordered set itself. 4.3 The Certified Trace Definition 4.3.1. Consider the collection of sets CertSNBC = fCertSNBC(k; n)gk;n1 defined by CertSNBC(k; n) = f(w;~t ) 2 SNBC(k; n) j H(Graph(w;~t )) < p d 1g that is, all the potential walks that are closed, strictly non-backtracking, of order less than r and which are not tangles. Proposition 4.3.2. The collection of sets CertSNBC is a walk collection. Proof. This is immediate since both the Hashimoto spectral radius is pre- served up to symmetry and size increase. Definition 4.3.3. We define the kth certified trace of size n, CertTr(G; k), of a graph G 2 Cn(B) to be the (k; n)-modified trace associated to CertSNBC and we write its associated walk sum as En[CertTr(G; k)] = WalkSum(CertSNBC(k; n)) and for any positive integer, r 1, we define the truncated certified trace to be the associated truncated walk sum En[CertTr<r(G; k)] = WalkSum<r(CertSNBC(k; n)) which only sums certified potential walks of order less than r. 71 The whole idea of this definition is that for graphs which do not contain tangles, the truncated certified trace is a convenient approximation of the Hashimoto trace. We state this more precisely in the next proposition. Proposition 4.3.4. For any positive integer r 1 and k n/2 we have En[ITF(r;B)[n](G)Tr(HkH)] = En[CertTr<r(G; k)] +On kcr(d 1)kn(r+1) for some constant c. Proof. Modifying Theorem 3.3.5 slightly, we have that any walk sum can be written as WalkSum(W; k; n) = f0(k) + f1(k) n + : : :+ fr(k) nr + error(r; k) for any choice of an integer r 1 and any k n/2, where fi(k) = r1X j=0 X (w;[~t ])2Wj(k) pij(w;~t ) and whereWj(k) is the set of all equivalence classes of potential walks of length k and of order j; with the error term satisfying jerror(r; k)j ck4(r+1)(d 1)kn(r+1) Our truncated certified trace only considers potential walks of order less than r and since we are only considering the case for random graphs, G, that are free of any tangles, we can conclude that the expansions of En[ITF(r;B)[n](G)Tr(HkH)] and En[ITF(r;B)[n](G)CertTr<r(G; k)] have to agree up to the term of order r and so we are simply left with the error term as claimed. We now observe that if a graph is a tangle, thenmaking its edges longer (assume it is a variable-length graph) will eventually disappear the 72 Proposition 4.3.5. Let T be the graph of a type T . Then the set of vectors f~k 2 ZjET j1 j VLG(T;~k ) /2 TangleBg is an upper set of ZjET j1 . In other words, if a choice of edge lengths, ~k, for a type do not make the resulting graph a tangle, then any larger choice of edge lengths, ~k0 ~k will guarantee that it isn't a tangle either. Proof. This is fairly straightforward and is but only a slight modification of the argument of Theorem 4.1.6. Given a variable-length graph, making its edges longer will either leave its Hashimoto spectral radius unchanged or lower it. In both cases, if it wasn't a tangle in the first place, it will remain that way. Corollary 4.3.6. For each type, T , there is a finite number of tangle certifi- cates, that is, a finite family of vectors, ~k0;1; : : : ;~k0;s such that VLG(T;~k) /2 TangleB () ~k ~k0;i for some i = 1; : : : ; s where T is the underlying graph of the type T We now have all the elements required to state the main theorem of this section. Theorem 4.3.7. Consider the type-form expansion described in Theorem 3.4.10. The walk sum of the certified trace can be written as a finite linear combination of functions of the form Term[T ;~k0; r](k) = X ~k~k0 X ~m~k= k WT (~m;~k )Pi(~k ) where WT (~m;~k ) counts the number of strictly non-backtracking walks in the type T with edge lengths defined by ~k and that traverses each edge f 2 ET of the type mf times; and Pi(~k ) is a polyexponential function. Proof. Since CertSNBC is clearly multiplicity and length determined, we 73 can apply Theorem 3.4.10 to obtain an expansion CertTr<r(W; k; n) = X T 2Types[r] n ord(T ) rord(T )X i=0 QT ;i(k)ni + error(r; n; k) where the QT ;i are functions satisfying QT ;i(k) = X ~m;~k2ZET1 ~m~k= k WT (~m;~k )Pi(~k ) where the Pi(~k ) are B-polyexponential functions, and with error term jerror(r; n; k)j ck4r(d 1)knr Now, we simply apply Theorem 4.2.14 to the upper set f~k 2 ZjET j1 j VLG(T;~k ) /2 TangleBg and obtain that there are finitely many certificates, ~k0, such that we can rewrite the QT ;i(k) as a finite linear combination of cone sums of the form Term[T ;~k0; r](k) = X ~k~k0 X ~m~k= k WT (~m;~k )Pi(~k ) 4.4 Asymptotic Expansion Our goal here is to prove that we have a B-Ramanujan expansion for the certified trace and prove the following theorem. Theorem 4.4.1. The terms of the form Term[T ;~k0; r](k) = X ~k~k0 X ~m~k= k WT (~m;~k )Pi(~k ) (4.1) 74 given in Theorem 4.3.7 are B-Ramanujan functions. In other words, the truncated certified trace admits a B-Ramanujan. These types of sums are similar to those in Theorem 8.2 of [Fri08] and Theorem 2.18 of [Fri91]. In both those theorems, a key idea is to divide the vector ~m by those components equal to 1 and those components that are at least 2. Here we notice that by a similar division, into components at mostM and components at leastM +1, for a fixed value ofM , we greatly simplify the computations. The role of tangles on the asymptotic expansion becomes clear as well. Fix an integer M such that M 1/" and fix a partition of the edges of the type ET = ET;1 q ET;2 We call the edges in ET;1 the short and the edges in ET;2 long. We write ~m 2ML(k;M) = ML(k;M;ET;1; ET;2) if (1) ~m 2 f~m j ~k ~k = k; ~k ~k0; for ~k0 a certificateg, (2) mf M if f 2 ET;1, (3) mf M + 1 if f 2 ET;2. and so we can rewrite equation (4.1) as Term[T ;~k0; r](k) = X ET;1qET;2=ET X (~m;~k )2ML(k;M;ET;1;ET;2) WT (~m )qi(~k ) For each (~m;~k ) 2ML(k;M) define K1(~m;~k ) = X f2ET;1 mfkf and K2(~m;~k ) = X f2ET;2 mfkf (4.2) and so it follows that K1(~m;~k ) +K2(~m;~k ) = k for all (~m;~k ) 2 ML(k;M). Since there are finitely many partitions of the edges of the type, we only 75 need to consider expressions of the form Term(k;ET;1; ET;2) = X (~m;~k )2ML(k;M) WT (~m )qi(~k ) (4.3) and show that they are B-Ramanujan functions, which would prove our Theorem 4.4.1 Theorem 4.4.2. Let T 2 Types[r] be a type of order less than r and let (ET;1; ET;2) be a partition of the edges of the type. Then for any " > 0 and integer M 1/" we have that the function Term(k;ET;1; ET;2), as de- scribed above, is B-Ramanujan. Proof. We distinguish two cases for this proof: (1) When ET;1 = (2) When ET;1 6= So, let us start with the first case: we consider the term in (4.3), in the case where ET;1 = and ET;2 = ET . For every (~m;~k) 2ML(k;M) we have WT (~m) CkC(d 1)k/2; since each walk in WT (~m) gives a walk of length k in Path(T;~k), which corresponds to walk of length at most k in Path(T;~k0), and the number of such walks is bounded by CkC(d 1)k/2 since the largest Hashimoto eigenvalue of Path(T;~k0) is at most (d 1)1/2. Now we note the following crude bound. Lemma 4.4.3. The number of pairs (~m;~k) for which ~m;~k ~1 and ~m ~k = k is at most k + jET j 1 jET j 1 kjET j: Proof. For each (~m;~k), set sf = mfkk for each f 2 ET . Then the sum of the sf is k, and there are k+jET j1 jET j1 ways of representing k as the sum of integers fsfgf2ET with sf 0. Furthermore, each sf can be represented as at most k products mfkf , with mf ; kf 1. 76 Finally, we notice that if mf M + 1 for all f 2 ET , and ~m ~k = k, then we have S = X f2ET kf k/(M + 1); and so P (~k) Y f2ET (d 1)kfCkCf C 0kC 0 (d 1) P f2ET kf C 0kC0(d 1)k/(M+1): It follows that, in the notation of (4.3), we have jTerm(; ET )j jML(k;M;; ET )j max ~m2ML(k;M;ET ) jWT (~m)j max ~k2ML(k;M;;ET ) P (~k) CkC (d 1)k/2CkC C 0kC0(d 1)(k/2)+(k/(M+1)): C 00kC00(d 1)k((1/2)+"): It follows that for any e" > 0 and some (new) constant, C, and sufficiently large M we have jTerm(; ET )j CkC(d 1 + e")k/2: It suffices to give a similar bound for Term(ET;1; ET;2) for the other par- titions of ET as ET;1qET;2. But this case alone shows how the certification seems essential, in that ifWT (~m) could be as large as (d1+)k/2 for some fixed > 0, we could not give a good enough bound just on Term(; ET ). A Specialized Bound For WT (~m) To bound Term(ET;1; ET;2)whenET;1 is not empty, wewill use Theorem 2.8.4. To do so we would like to bound WT (~m) for each (~m;~k) 2 ML(k;M), in terms of K1;K2 given by (4.2). Specifically, we which for mf fixed for f 2 ET;1, gives a bound for WT (~m) in terms of the exponent K2, rather than k. Here is what we will need. Lemma 4.4.4. Fix T ;~k0;M , and a partition ET;1 q ET2 of ET . Then there 77 exists a constant, C, for which WT (~m) CKC2 (d 1)K2/2 provided that (~m;~k) 2ML(k;M;ET;1; ET;2) Proof. Consider a walk, w, in T . Such a walk traverses a bounded number of edges in ET;1, namely at most B =M jET;1j edges. Let w0 be the walk in ET;2 edges taken before the first ET;1 edge is taken in w, and for 1 i B, let wi be the walk taken between the i-th and (i + 1)-th occurrence of an ET;1 edge in w. (Some of the wi will be empty when w traverses two or more ET;1 edges in a row; and some of the wi will be empty if w traverses fewer thanB edges ofET;1.) LetKi2 denote the number of edges traversed in wi when transferred to the graph Path(T;~k). First, we have K02 +K 1 2 + +KB2 = K2: Second, for fixed Ki2, the number of walks in Path(T;~k) of length at most Ki2 is bounded by C(Ki2) C(d 1)Ki2/2 (4.4) Finally, between wi and wi+1, we traverse one edge of ET;1, which can happen in at most a constant number of ways (namely one less than the maximum degree of T ). It follows that WT (~m) X Ki20 K02++KB2 =k CB BY i=0 [C(Ki2) C(d 1)Ki2/2]; (4.5) where the CB term reflects the B choices of ET;1 element, and the prod- uct over i comes from the (4.4). We bound the right-hand-side of (4.5) as follows: BY i=0 [C(Ki2) C(d1)Ki2/2] CKC2 B+1(d1)(K02++KB2 )/2 C 0KC02 (d1)K2/2: 78 Finally the number of ways of writing K2 as a sum of the Ki2, i.e., B + 1 non-negative integers is exactly K2+B B+1 , a polynomial in K2. Hence (4.5) yields WT (~m) K2 +B B + 1 C 0KC 0 2 (d 1)K2/2: It remains to show an asymptotic expansion forWT (~m)P (~k) forB-Rama- nujan P . Let us partition ~m and ~k by the ET;1 q ET;2 partition; namely, let ~ki = fkfgf2ET;i ; so we may write ~k = (~k1;~k2), and similarly ~m = (~m1; ~m2). It suffices to show that for P1(~k1) and P2(~k2) polyexponentials, we have that g(ET;1; ET;2; k) = X (~m;~k)2ML(k;M;ET;1;ET;2) WT (~m)P1(~k1)P2(~k2) is B-Ramanujan. So for any integer, K1, and any ~m1 2 f1; : : : ;MgET;1 , let Q1(K1; ~m 1) = X ~m1~k1=K1 ~m1~1; ~k1~k1;0 P1(~k 1); and Q2(K2) = X ~m2~k2=K2 ~m2~1; ~k2~k2;0 WT ((~m1; ~m2))P2(~k2): We have Q1 is a B-Ramanujan, and Q2 is of growth at most (d 1 + ")1/2. Hence, for each ~m1 2 f1; : : : ;MgET;1 we have Q1 Q2 is B-Ramanujan. Hence the sum over all ~m1 is B-Ramanujan. This completes the proof of Theorem 4.4.2 and with it, the proof of The- orem 4.4.1 79 Chapter 5 The Side-Stepping Lemma In this chapter, we prove a new version of the side-stepping lemma in [Fri08]. We improve this lemma to the more general case where we con- sider polyexponential functions with bases on all the Hashimoto eigen- values strictly greater than (d 1)1/2 which will allow us to use the B- Ramanujan expansions that we have to conclude theorem 1.2.3. The key idea is to use the fact that we can have an expansion for several consecutive values of k and apply the shift operator, described in the next section, several times. This side-stepping lemma is stated for an abstract collection of finite probability spaces. 5.1 The Shift Operator Let S denote the shift operator in k, meaning the operator on functions, f(k), defined on non-negative integers, k, taking f to (Sf)(n; k) = f(n; k + 1) For any integer i 0 we let Si denote the i-fold application of S, so that (Sif)(n; k) = f(n; k + i) For any polynomial (with real or complex coefficients), Q(z) = q0 + q1z + + qtzt 80 we define Q(S) in the natural way, i.e., Q(S) = q0S 0 + q1S 1 + + qtSt The utility of polynomials in S is due to the following simple observa- tions. Proposition 5.1.1. Let Q(z) be a polynomial, then for k 0 we have (1) (Q(S))(k) = Q()k for any 2 C, (2) (S 1)(kD) = O(kD1), (3) (S 1)D(f) 0 for any function f(k) = kp(k) where 2 C and p is a polynomial of degree at most D 1. Proof. (1) and (2) are straightforward and (3) is a consequence of the fol- lowing identity, NX k=0 N k (1)kkp = 0 for any N 0 and any p < N . When h(k) is a function for which we do not have a simple expression, but is rather bounded by a polyexponential function (such as in our "error terms"), we employ the following crude bound. Lemma 5.1.2. Let h(k) be a function for which jh(k)j CkkC ; for some positive real numbers C and with 1. Let Q(x) be any com- plex polynomial of degree at most D 1. Then, for k 0, we have jQ(S)h(k)j CDkQkk+D(k +D)C Where kQk denotes the largest absolute value of Q's coefficients. In par- 81 ticular, for fixed Q and we have for all k 0 jQ(S)h(k)j C 0kkC0 (5.1) for some constant C 0. Proof. Denote Q(x) = q0 + q1x+ + qD1xD1 and for any non-negative integer i we clearly have jSih(k)j Ck+i(k + i)C Ck+D(k +D)C Hence jQ(S)h(k)j D1X i=0 jqij jSih(K)j DkQkCk+D(k +D)C Clearly the last equation of the lemma, (5.1), follows. 5.2 Statement of the Side-Stepping Lemma The main lemma of this section, Lemma 5.2.5, generalizes the Side-Step- ping Lemma of [Fri08], both of which can be viewed as abstract lemmas in probability theory. Of course, these abstract lemmas are motived by our trace methods, and we will need Lemma 5.2.5 to prove the Hashimoto version of the generalized Alon conjecture for all base graphs, B, which are d-regular. Also, Lemma 5.2.5, especially (5.4), is, arguably, more direct and simpler than the Side-Stepping Lemma in [Fri08]. This chapter involves a number of positive, real constants, depending on various parameters, that need to be chosen sufficiently large; we will generally use the letters C;C 0; C 00, for various of these constants, when no confusion is likely to arise. 82 Definition 5.2.1. By a finite probability space we mean a pair, ( ; ), where is a finite set, and a probability measure, , which we view as a function : ! R, such that (!) 0 for each ! 2 , andX !2 (!) = 1: We will view as giving a measure to each subset E in the usual way, i.e., (E) = X !2E (!): By a complex random variable on ( ; ) we mean a function : ! C; similarly we define a real random variable. We often write Prob [E] for (E) and, for a random variable, = (!), E!2 [(!)] for X !2 (!)(!) As such, the measure will often be omitted in notation, being implicit in the notation Prob [E] and E!2 [(!)]. Definition 5.2.2. Let 0; 1; be positive real numbers for which 0 < 1; let L be a finite collection of real numbers, each of whose absolute value is strictly larger than 0 and at most 1. By an abstract partial trace with pa- rameters (0; 1; ; L) we mean the following data for each positive integer, n: 1. a finite probability space, ( n; n); 2. complex random variables i = i(!) on ( n; n) such that for all i = 1; : : : ; n and ! 2 n we have i(!) 2 R1 [R2; 83 where R1 = fz 2 C j jzj 0g; R2 = fz 2 R j 0 < jzj 1g; 3. there are polyexponentials P0(k); P1(k); : : : with bases in L, for which for any integer r > 0 we have X !2En n(!) nX i=1 ki (!) = P0(k)+P1(k)n 1+ +Pr1(k)n1r+errr(n; k) (5.2) for all positive integers k; n with k n/2, where errr(n; k) is a function such that for any " > 0 there is a constant, C (depending on " and r) for which jerrr(n; k)j CkC k1 n r + (0 + ")k : Example 5.2.3. We will apply the above setting to n = Cn(B) with the following parameters when B is d-regular: 0 = (d 1)1/2, 1 = d 1, = jEdirB j; the choice of i(!) is a bit intricate: we will fix an "0 > 0 and take the i(!) be either (1) all zero, if G contains a (d; "0)-tangle, or (2) the Hashimoto eigenvalues of G, except that the old Hashimoto eigenvalues will be set to zero. Note that the "0 in this paragraph is different from the " in Lemma 5.2.5. We remark that above setting essentially permits the random variables i(!), to range over i = 1; : : : ; f(n) for any function, f(n), bounded by n for some fixed ; this can be done simply by introducing new ``dummy'' random variables, i(!) = 0 for i = f(n) + 1; : : : ; n. We shall prove a lemma which will apply (5.2) for numerous values of k to show that it is ``unlikely'' for ! 2 n that some i(!) is larger than 0 + " in absolute value but not near any ` 2 L. We shall also obtain important information on the ``dominant'' part of the Pi(k) corresponding to the `k term for each ` 2 L. To describe this, we need some further terminology. Definition 5.2.4. Consider an abstract partial trace as defined above with parameters (0; 1; C; L) and with n; n; i as above. For any "; > 0 and 84 integer n, set Out(; ") = fz 2 R j 0 + " < jzj 1 and jz `j > for all ` 2 Lg and Exceptionn(; ") = f! 2 n j i(!) 2 Outn(; ") for some ig and AbsoluteExceptionn(") = f! 2 n j ji(!)j > 0 + " for some ig: Also set Nearn(`; ) = E!2 n h i ji(G) `j i ; i.e., the expected number of i(!) which lie within of `. Lemma 5.2.5 (Improved Side-Stepping Lemma). Consider an abstract par- tial tracewith parameters (0; 1; C; L) as above, with n; n; i; Pi as above. For any ; " > 0 there exists a > 0 for which Probn[Exceptionn(n; ")] n (5.3) for n sufficiently large. Furthermore, write Pi(k) = X `2L p`;i(k)` k; i.e., let p`;i(k) be the polynomial coefficient of `k in Pi(k). Assume that for some j and ` 2 L we have that p`;0(k) = = p`;j1(k) = 0: Then p`;j(k) is a constant (i.e., independent of k), and this constant is the limit p`;j = lim n!1n j Nearn `; n (5.4) 85 for any > 0 sufficiently small (i.e., there is a 0 > 0 such that (5.4) holds for any with 0 < < 0). Finally, if j is any positive integer for which P0(k) = = Pj1(k) = 0; then for each " > 0 there is a C = C" for which Probn[AbsoluteExceptionn(")] C"nj : (5.5) Lemma 5.2.5 will be proven in the sections that follow. The proofs are based on the simple idea of applying certain polynomials of the ``shift op- erator in k'' to (5.2). The basic idea behind these proofs is very simple: we let S denote the ``shift operator in k,'' taking a function, f(n; k), to the shifted function (Sf)(n; k) = f(n; k+1); we begin our proof by establishing (5.3), by applying Q(S) = Y `2L (S `)D to both sides of (5.2), whereD is an even integer that is sufficiently large to annihilate the Pi(k) for i = 0; : : : ; r1 (this is explained in the next section); we then prove the second part, regarding the p`;i(k), by applying, for each ` 2 L, Q`;D(S) = Y `02L; `0 6=` (S `0)D to both sides of (5.2), to isolate the effect of the i near `. A very similar set of ideas appears in [Fri08], Chapter 11, where the side-stepping lemma there is proven only in the case L = f1g, which suf- fices for random d-regular graphs, i.e., base graph B = Wd/2 or B being one vertex and d half-loops. The proof of Lemma 5.2.5 is primarily compli- cated by the fact that L can have two or more elements, unlike the case in [Fri08]. 86 5.3 Proof of the First Exception Bound In this section we will prove (5.3). In other words, fix an " > 0; we will show that for any > 0, there exists a = () > 0 for which (5.3) holds. First, let us describe = () explicitly, in rather unmotivated terms. Let be any real number with > 2. Let 0; 00 be any real numbers satisfying 0 > + 1 log 0+"0+("/2) (5.6) and 00 > + 2 log 0+"0 : (5.7) Let > 0 be any real number for which < (1/2) log(1/0): (5.8) Let r be any positive integer for which r/2 > max(; 0/; 00/): (5.9) let P0; : : : ; Pr1 be as in Definition 5.2.2, and D be an even integer bound- ing the polynomial degree of the p`;i ranging over all ` 2 L and i = 0; : : : ; r 1; we take to be any positive real number for which < /(jLjD); (5.10) hence , and D; r; ; ; 0; 00, depend only on ; "; 0; 1; L. So can be viewed as a function depending only on ; "; 0; 1; L. For the rest of this section we will prove that this value of satisfies (5.3). even integer. Our general approach is to note that Q(S) = Y `2L (S `)D; satisfies Q(S)Pi(k) = 0 for all i; we shall apply Q(S) to both sides of (5.2). 87 For the rest of this section, the letters C;C 0; C 00 will refer to various constants that are independent of k and n, but may depend on any of ; "; 0; 1; L, and the above ; 0; 00; ; r;D;Q; , which are functions of ; "; 0; 1; L. Let us begin with a few immediate remarks about Q(S): 1. for 2 R, Q() is real and non-negative; 2. we have jQ()j, for any with jj 1 is bounded by a constant depending on Q and 1; 3. for /2 B(L) we have jQ()j jLjD; 4. for any real > 0, if h(k) = k with jj , then jQ(S)h(k)j Ck for some C depending only on Q; 5. furthermore, if h(k) is any function bounded by CkCk for some C, then we have jQ(S)h(k)j C 0kC0k for a constant, C 0, depending only on C and Q. We are now ready to apply Q(S) to both sides of (5.2). Beginning the with left-hand-side, we write: Q(S)E!2 n " nX i=1 ki (!) # = E!2 n " nX i=1 Q(S)ki (!) # ; note that for each i and ! for which i(!) /2 R we have ji(!)j 0, and hence jQ(S)(ki (!))j C 0k0 ; 88 where C 0 is independent of n; k. Since there are n values of i in the above, we have nX i=1 Q(S)ki (!) X i; i2R Q(S)ki (!) X i; i /2R jQ(S)ki (!)j X i; i2R Q(S)ki (!) C 00nk0 for some constant C 00 independent of n; k. Furthermore, since Q() 0 for real, we have for any j = 1; : : : ; n and ! 2 n for which j = j(!) is real Q(j) k j X i; i2R Q(S)ki (!) C 00nk0 +Q(S) nX i=1 Q(S)ki (!): But for each ! 2 Exceptionn(; ") we have j(!) 2 Out(; ") for some j, and hence Q(j(!)) k j (!) is non-negative, and bounded from below by jLjD(0 + ")k: It follows that for ! 2 Exceptionn(; ") we have Probn[Exceptionn(; ")]jLjD(0 + ")k E!2 n 24 X i; i(!)2R Q(S)ki (!) 35 C 00nk0 +Q(S)LHS; where LHS is the left-hand-side of (5.2), i.e., LHS = E!2 n " nX i=1 ki (!) # : But the left-hand-side of (5.2) equals its right-hand-side, RHS, and Q(S) 89 applied to any Pi(k) vanishes; hence Probn[Exceptionn(; ")]jLjD(0 + ")k C 00nk0 +Q(S)RHS (5.11) C 00nk0 + Q(S)h1(k) + h2(n; k); (5.12) for any k; n with k +D n/2, where jh1(k)j CkC 0 + ("/2) k ; jh2(n; k)j CkCk1 nr for some constant, C, independent of n; k. Lemma 5.1.2 implies that jQ(S)h1(k)j CkC 0 + ("/2) k (5.13) and jQ(S)h2(n; k)j CkCk1 nr (5.14) for a new constant, C, independent of n; k. Combining these estimates with (5.11) and (5.12) we have Probn[Exceptionn(; ")] jLjDC nk0 + k C 0 + ("/2) k + kCk1 n r (0 + ")k ! ; (5.15) with C independent of n; k. We claim that setting k to be k = f(n) = the smallest even integer greater than max(0; 00) logn; (5.16) for sufficiently large n we have that (5.15) implies Probn[Exceptionn(; ")] 3jLjDn (5.17) If so, then (5.3) follows by taking = n, for then, in view of (5.10) Probn[Exceptionn(n; ")] 3njLjDn n+ 90 which, since > 2, is at most n for sufficiently large in. So we will finish this section, i.e., the proof of (5.3), by establishing (5.17). To show (5.17), from (5.15) is suffices to show that each of the three expressions Cnk0 (0 + ")k ; CkC 0 + ("/2) k (0 + ")k ; and Ck Ck1 n r (0 + ")k is bounded by n for n sufficiently large. For the first expression, we note that Cnk0 (0 + ")k Cn0/(0+")k Cn0/(0+")00 logn Cnn2 = Cn1; using (5.16) and (5.7), which is therefore bounded by n for sufficiently large n. For the second expression, we note that CkC 0 + ("/2) k (0 + ")k CkC 0 + ("/2) 0 + " 0 logn CkCn1; using (5.16) and (5.6), which is therefore bounded by n for sufficiently large n. For the third expression, we note that k max(0; 00) logn+ 2 by virtue of (5.16), and hence k (r/2) logn for sufficiently large n, by virtue of (5.9), and hence CkCk1 n r (0 + ")k CkCnr(1/0)k CkCnrnr/2 = CkCnr/2; using (5.8), and by virtue of (5.9), CkCnr/2 is bounded by n for suffi- ciently large n. 91 Hence we conclude (5.17), which, as mentioned just below this equa- tion, implies (5.3). 5.4 The Proof of the Limit Formula In this section we will prove the limit formula in (5.4). Since we have estab- lished (5.3), we will use (5.3) and perform a slight variant of the technique in the previous section. However, there is an added subtlety which we now explain. Given r, let D0 be a positive integer for which bounds the degrees of the polynomials which are the coefficients of the Pi(k) over all i = 0; : : : ; r 1. For each ` 2 L, and each even, positive integer D with D D0, consider Q`;D(z) = Y `02Lnf`g (z `)D: (5.18) We shall apply Q`;D(S) to both sides of (5.2), the rough new ideas being: 1. Q`;D(S)Pi(k) annihilates the part of Pi(k) involving a polynomial in k times (`0)k, for any `0 2 L with `0 6= `; 2. Q`;D(S)Pi(k) does not annihilate the part of Pi(k) involving a polyno- mial in k times `k; and 3. for within n of any `0 2 Lwith `0 6= `, we have thatQ() is bounded by roughly nD. The new ideas (1) and (2) indicate that our choice of Q`;D can isolate the `k terms in the Pi(k); the new idea (3) is subtle, in that we will fix j; r; > 0 first, deducing a value > 0 for which (5.3) holds, and then will we choose D sufficiently large so that D is large enough, compared to j. Let us, as in the previous section, now fix a number of variables in a somewhat unmotivated fashion. First, we fix an " > 0 sufficiently small so that 0 + " is strictly less than the absolute value of any element of L. It follows that for sufficiently small > 0, we have that the closed balls of radius about each element of L are disjoint, and also disjoint from the set 92 of complex numbers of absolute value at most 0 + ". Fix an ` 2 L and an integer j 1 for which p`;0(k) = = p`;j1(k) = 0: Let = (j + 2) log(1/j`j) log j`j/(0 + ") which is non-negative, and equals zero iff j`j = 1. (The illustrates the fact that the case j`j = 1 is, in a sense, easier than j`j < 1.) Choose so that 1 j 2 > (5.19) and choose r so that r j 1 > ; (5.20) let > 0 be chosen so that (5.3) holds for sufficiently large n. Choose an even integer D so that 1. D is greater than the degree of all polynomials p`0;i with i = 0; : : : ; j1 and `0 2 L n f`g, and 2. D j 2 > : (5.21) Given the above, we can find a real number > 0 for which log j`j/(0 + ") > (j + 2) > (j + 2) log(1/j`j)min(X): (5.22) Where X = f 1 j 2; r j 1; D j 2g. Let Q`;D(z) be as in (5.18). Our strategy will be so apply Q`;D(S) to both sides of (5.2), and then choose k = f(n) = the smallest even integer greater than logn: (5.23) 93 We claim that (5.4) will follow. Before going through this calculation, let us note for future use that the choice of as above, (5.22), shows that max(D; n+1; nr1) k1 ; (0 + ")k are both O(nj2)`k (5.24) where = n, for a constant in the O(n) notation that is independent of n; k. Again, we use C;C 0 to denote various constants that are independent of n; k, but may depend upon L; ; `; 0; 1; "; j, and therefore depending on ; r; ;D; ; as above. We shall make some simple observations about Q`;D(z), analogous to the ones make of Q(z) in the last section. There is only one set of new estimates, which we state as a lemma. Lemma 5.4.1. The following bounds hold for, say, all 1: 1. if for some `0 2 L with `0 6= ` we have jz `0j , then jQ`;D(z)j (21 + )(jLj2)DD CD; where C is a constant independent of n; k. 2. for any 0, we have that jzj 0 implies that jQ`;D(z)j (0 + 1)(jLj1)D C; where C is a constant independent of n; k. Proof. For (1), we see that if `00 2 L with `00 6= `0; `, then jz `00j jzj+ j`00j (1 + ) + 1 = 21 + ; hence jQ`;D(z)j jz `0jD Y `002Lnf`;`0g jz `00jD D (21 + )(jLj2)D: 94 For (2) we note that `0 2 L implies that jz `0j jzj+ j`0j 0 + 1; and (2) follows. We compile a list of simple observations about Q`;D(z), analogous to the ones make of Q(z) in the last section: 1. for 2 R, Q`;D() is real and non-negative; 2. for any with jj 1 we have jQ`;D()j (21)(jLj1)D C (5.25) where C is a constant independent of n; k (by (2) of Lemma 5.4.1); 3. Q`;D(`) 6= 0; 4. for real z with jz `j and 1, we have Q`;D(z) = Q`;D(`) +O(); (5.26) where the constant in the O() is independent of n; k (and, in fact, depends only on L and D), which follows using the mean-value- theorem, with the O() constant being any bound on the derivative Q0`;D(z) over all z within 1 of `; 5. for any real > 0, if h(k) = k with jj , then jQ`;D(S)h(k)j Ck for some C depending only on L and D; and 6. furthermore, if h(k) is any function bounded by CkCk for some C, then we have jQ`;D(S)h(k)j C 0kC0k for a constant, C 0, depending only on C, L, and D. 95 In addition to these simple estimates, we will use Lemma 5.4.1. Returning to Lemma 5.2.5, the goal of the rest of this section is to es- tablish (5.4). As in the previous section, we let LHS and RHS, respectively, be the left-hand-side and right-hand-side of (5.2). Again, the basic idea is to apply Q`;D(S) to LHS = RHS. As before, we see that Q`;D(S)LHS = E!2 n "X i Q`;D i(!) ki (!) # ; (5.27) and we wish to estimate this expectation (for various values of n; k). For > 0 sufficiently small (ultimately we will take = n) for each i and ! 2 n we have that exactly one of the following holds: 1. for some `0 2 L n f`g we have ji(!) `0j ; 2. we have ji(!) `j ; 3. we have ji(!)j 0 + "; 4. we have i(!) 2 Out(; "): Assume that is sufficiently small for this to hold. In view of (5.27), let us estimate the contribution to the expected value of Q`;D()k for = i(!) in each of the above four cases. For case (1), i.e., ji(!) `0j with `0 2 L n f`g, use the estimate E!2 n 24 X i s:t: ji(!)`0j Q`;D ki (!) ki (!) 35 Nearn(`0; )DC(`0)k; using Lemma 5.4.1, where C is independent of n; k. Summing over all `0 2 L n f`g, and using the crude boundX `02L Nearn(`0; ) n; 96 we conclude that E!2 n 24 X i s:t: ji(!)`0j for some`02Lnf`g Q`;D ki (!) ki (!) 35 (5.28) nD(21 + )(jLj2)Dmax `0 (`0)k CnDk1 ; where C is independent of n; k. For case (2), i.e., ji(!) `j , with > 0 sufficiently small, we note that jki (!) `kj ji(!) `j jk1i (!) + k2i (!)`+ + `k1j ji(!) `j k(1 + )k k(`+ )k = k`k 1 + (/`) k : Hence we have ki (!) = ` k 1 + k O(1) ; with the O(1) being at most e, provided that (1/k) `/; given k as in (5.23), this holds for all n sufficiently large. Then (5.26) implies that E!2 n 24 X i s:t: ji(!)`j Q`;D ki (!) ki (!) 35 = Nearn(`; )Q`;D(`) 1 +O() `k 1 + k O(1) ; and so E!2 n 24 X i s:t: ji(!)`j Q`;D ki (!) ki (!) 35 = Nearn(`; )Q`;D(`)`k1+kO(1): (5.29) where the constant in the O(1) is independent of n; k for = n and k as in (5.23). 97 For case (3), (5.25) implies that E!2 n 24 X i s:t: ji(!)j0+" Q`;D ki (!) ki (!) 35 n (21)(jLj1)D(0 + ")k (5.30) nC(0 + ")k (5.31) with C independent of n; k. Finally, for case (4), we use the estimate E!2 n 24 X i s:t: i(!)2Out(;") Q`;D ki (!) ki (!) 35 n Ck1 Probn[Exceptionn(; ")]; since i(!) 2 Out(; ") implies that ! 2 Exceptionn(; "), and in this case there are at most n values of i for which i(!) lies in Out(; "), and for each such i we have Q`;D ki (!) is at most a constant, C, by (5.25). Hence, using (5.3), we have E!2 n 24 X i s:t: i(!)2Out(;") Q`;D ki (!) ki (!) 35 (5.32) Cnk1 n: for n sufficiently large, and C independent of n; k. Combining (5.28)--(5.32), and (5.27), we get that for = n, for all k with k `/ and n sufficiently large we have and Q`;D(S)LHS Nearn(`; )Q`;D(`)`k 1 + kO(1) = O(n) Dk1 + (0 + ") k + n1k1 ; (5.33) 98 where the constant in the O(n) is independent of n; k. But (5.24) implies that (5.33) isO(`knj1) for k as in (5.23), and hence for k as such we have Q`;D(S)LHS Nearn(`; )Q`;D(`)`k 1 + kO(1) = O(`knj1): (5.34) As in the previous section, we apply Q`;D(S) to RHS, and find Q`;D(S)RHS = r1X i=0 Q`;D(S)Pi(k) +O(n j1)`k (5.35) provided that for any C independent of n; k we have kC 0 + ("/2) k + kCk1 n r = O(nj1)`k (for the same reasoning as (5.13), (5.14), (5.12)); but this is implied by (5.24). Hence, dividing (5.35) by `k, we have Q`;D(`) r1X i=0 p`;i(k)n i = `kQ`;D(S)RHS+O(nj1) = `kQ`;D(S)LHS+O(nj1) = Nearn(`; )Q`;D(`) 1 + kO(1) +O(nj1) for k as in (5.23). Given that p`;0(k); : : : ; p`;j1 all vanish, we have, upon dividing by njQ`;D(`), that p`;j(k) +O(n 1) = njNearn(`; n) +O(n1): But njNearn(`; n) is independent of k, and k is proportional to logn. Hence taking n!1 we conclude (5.4). We note that the only requirement on our choice of > 0 is that satis- fies (5.3) for our chosen value of (in (5.19)). Hence if 0 is such a value of , then for any such that 0 < < 0, then Probn[Exceptionn(n; ")] Probn[Exceptionn(n0 ; ") ] n; 99 for n sufficiently large. Hence any with 0 < < 0 also satisfies (5.3) for (in (5.19)), and hence satisfies (5.4). 5.5 The End of The Proof of Lemma 5.2.5 It remains to prove (5.5), having established (5.3) and (5.4). First we note that (5.4) implies that for any ` 2 L and " > 0 (and given L; ; 0; 1; j) there is a C > 0 for which Nearn(`; n) C(nj) (5.36) for any fixed > 0 for which (5.3) holds with given in (5.19). Hence this also holds with replaced by any smaller, positive value of . Proof. Given an " > 0, we can therefore choose a > 0 for which 1. for this ", and with = j, we have (5.3) holds; and 2. we have that (5.36) holds for all ` 2 L. We have Probn[f! j ji(!) `j n for some ig] Nearn(`; n) C nj for a constant, C, independent of n; k. Hence, summing over all `, we have Probn[En C nj ] where En = f! j ji(!) `j n for some i and some ` 2 Lg: Since also satisfies (5.3) with = j, we have Probn[Exceptionn(n; ")] nj ; 100 for n sufficiently large. But clearly Probn[AbsoluteExceptionn(")] Probn[Exceptionn(n; ")] + Probn[En]; since if ! 2 n has ji(!)j > 0 + " for some i, then either i(!) lies in Out(n; ") or i(!) is within n of some ` 2 L. Hence Probn[AbsoluteExceptionn(")] Probn[Exceptionn(n; ")] + Probn[En] Cnj : 101 Chapter 6 Proof of the Main Result We can now finish our proof of the regular case of the proof of the Alon conjecture in the Broder-Shamir model, Cn(B), where B is any connected d-regular graph. In section 4.1, we define the event Tangler;B[n] = fG 2 Cn(B) j 9H < G;H 2 Tangler;Bg where a random covering contains a tangle of order less than r as a sub- graph; and denoted by ITF(r;B)[n] the indicator function of the complement of this event, that is ITF(r;B)[n](G) = 1 () G /2 Tangler;B[n] In order to be able to use our side-stepping lemma, we need to prove that we have a B-Ramanujan expansion for En[ITF(r;B)[n](G)Tr(HkG)]. To do this, we will show that this is the case for our truncated certified trace since we have that En[ITF(r;B)[n](G)Tr(HkG)] = En[ITF(r;B)[n](G)CertTr<r(G; k)] +On k2rnr (6.1) Given theB-Ramanujan expansion for the certified trace (Theorem 4.4.1), it is enough to show that En [(1 ITF(r;B)[n](G))CertTr(G; k)] admits a B- Ramanujan expansion. Theorem 6.0.1. We have a B-Ramanujan expansion, En[ITF(r;B)[n](G)Tr(HkG)] = P0(k) + P1(k) n + : : :+ Pr1(k) nr1 + error(r; n; k) 102 where jerror(r; n; k)j CkC(d 1)knr Proof. Since ITF(r;B)[n](G) + (1 ITF(r;B)[n](G)) = 1, we have that En[ITF(r;B)[n](G)CertTr<r(G; k)] = En[CertTr<r(G; k) ] En[(1 ITF(r;B)[n](G))CertTr<r(G; k) ] The first term of the right-hand side has a B-Ramanujan expansion by Theorem 4.4.1 and the second one by Theorem 6.0.2. The sum of B- Ramanujan expansions is B-Ramanujan. Using equation (6.1) concludes the proof. Theorem 6.0.2. We have a B-Ramanujan expansion, En[(1 ITF(r;B)[n](G))CertTr<r(G; k)] = P0(k) + P1(k) n + : : : + Pr1(k) nr1 + error(r; n; k) where jerror(r; n; k)j CkC(d 1)knr Proof. The proof of this theorem is in the next section. Take Theorem 6.1.2 with = HasTangleminr;B . So let us state and prove the last missing expansion theorem in the next section. 6.1 Certified Traces In Graphs With Tangles In this section we widen the notion of a type to prove the following theorem, based on the ideas of Chapter 9 of [Fri08]. The main difference here is that we will view a tangle as a finite graph with a given morphism to B. Definition 6.1.1. By a B-graph, , we mean a finite graph, along with a morphism ! B. We view OccursB as a set of B-graphs. 103 Theorem 6.1.2. Let be any finite collection of B-graphs, such that each in satisfies ( ) 1. Let I (G) be the function that is one or zero according to whether or not G has a subgraph isomorphic to an element of . Then for any positive integer r and base graph, B, we have En[I (G)CertTr<r(G; k)] = P0(k)+P1(k)n1+ +Pr1(k)n1r+errr(n; k); where the Pi(k) are B-Ramanujan, and there is a C independent of n; k for which jerr(n; k)j Ck2r+2(d 1)knr Our proof is a straightforward adaptation of Chapter 9 of [Fri08] to this slightly more general situation. Let us give the rough idea, before giving a rigorous proof. We have established this for being the empty set, where the above expectation has Pi(k) that are given by a finite number of termsX ~m~k=k ~k~k0 WWT (~m)P (~k) for types, T , of order (i.e., minus Euler characteristic) at most r. To multiply the certified trace by I (G) can be seen as taking the information in a type, T , and augmenting it by futher information that describes how G is supposed to contain one or more elements of as a subgraph. This is handled by inclusion/exclusion, and since ( ) 1 for 2 , it follows that the inclusion/exclusion can be stopped after a finite number of levels. Our interest in the above theorem is the following corollary, obtained by setting to be r, the set of minimal elements of tangles of order less than r; each such element, , has all vertices of degree at least two, and must have some vertex of degree three, or else is a cycle, which has (H ) = 1 which is impossible, since a tangle, , has (H ) (d 1)1/2 > 1. Hence each element of r has all vertices of degree at least two, and at least one vertex of degree three, and hence each such element has order at least one. We therefore conclude. 104 Theorem 6.1.3. For any positive integer r and base graph, B, we have EG2Cn(B) ITF(r;B)[n](G)CertSNBCr(G; k) and EG2Cn(B) (1 ITF(r;B)[n](G))CertSNBCr(G; k) both have asymptotic expansions of the form P0(k) + P1(k)n 1 + + Pr1(k)n1r + errr(n; k); where the Pi(k) are B-Ramanujan, and there is a C independent of n; k for which jerr(n; k)j Ck2r+2(d 1)knr Another consequence of this technique is the following theorem. Theorem 6.1.4. Let be any finite collection of graphs, such that each in satisfies ( ) 1. Let I (G) be the function that is one or zero according to whether or not G has a subgraph isomorphic to an element of . Then for any positive integer r and base graph, B, we have that Probn[G contains a B-subgraph isomorphic to some element of ] = En[I (G)] = p1n1 + p2n2 + + pr1n1r +O(nr) for some constants pi. At this point we simply adapt the proof of Theorem 9.3 of [Fri08] to this situation. Define a potential graph specialization as a pair, ( ; ), where is a B-graph, and : V ! f1; : : : ; ng is a map. Given a potential walk, (w;~t), we define Probn[(w;~t); ( ; )] as the probability that (w;~t) and ( ; ) occur as subgraphs in G, and we let En[(w;~t); ( ; )] 105 be the expected number of times that (w;~t0) and ( ; 0) occurs inG, where ~t0; 0 are just ~t; , respectively, with the numbers f1; : : : ; ng permuted. We also write En[( ; )] just for the expected number of times that a ( ; 0) as above occurs in G. We have that both En[(w;~t); ( ; )]; En[( ; )] are given by asymptotic expansions in 1/n with coefficients pi(~a), where ~a = ~a((w;~t); ( ; )) or ~a = ~a(( ; )) is a vector indexed on the edges e 2 EB that counts the number of occurrences of e in the union of the data that (w;~t) and ( ; ) occur in G. Let the derived graphs of , denoted +, be the B-graphs in OccursB which can be expressed as the union of graphs isomorphic to a finte union of elements of , and let +<r be those elements of + of order less than r. For any two finite graphs, ; 0, letN( ; 0) denote the number of inclusions of in 0 asB-graphs, i.e., the number ofB-subgraphs of 0 isomorphic to . ClearlyN( ; 0) is finite (andN( ; ) is the number ofB-automorphisms of ). We view + as a partially ordered set via 0 if N( ; 0) > 0, i.e., is a B-subgraph of 0 (if 0 and 0 then the inclusion of into 0 must be surjective, and hence 0 and are the same B-graph). Möbius inversion yields the following lemma (see Proposition 9.5 in [Fri08]). Lemma 6.1.5. There exist real numbers f g 2+ such that for any 0 2 + we have X 0 N( ; 0) = 1: It follows that En[I(G)CertSNBCr(G; k)] = X (w;~t)2W X ( ;); 2 + En[(w;~t); ( ; )] ; (6.2) 106 and similarly En[I(G)] = X ( ;); 2 + En[( ; )] (6.3) (compare (37) and (38) of [Fri08]). Lemma 6.1.6. Let be a set of B-graphs each of order at least one. For each r, +< r, is a finite set. Furthermore, in (6.2), we may replace + with +<r, with a difference of at most C(d 1)knrk2r+2; similarly, we may do the same in (6.3), with a difference of O(nr). Proof. See the proof of Lemma 9.6 of [Fri08] Hence, to prove Theorems 6.1.2 and 6.1.4, it suffices to prove an asymp- totic expansion, for any fixed 2 +<r forX (w;~t)2CertSNBCr X En[(w;~t); ( ; )] and the same without the (w;~t). Theorem 6.1.4 follows immediately from the fact that each En[( ; )] is simply a power series in 1/n, and each 2 + is of order at least one. It remains to show Theorem 6.1.2, we requires us to encorporate the original notion of a type with the new data from . So we fix 2 +<r, and we define an -specialization of a form, , as in Definition 9.7 of [Fri08], and an -type as in Definition 9.8 of [Fri08]: namely, 1. an -specialization of a form, , is an inclusion, V[V ! f1; : : : ; ng, where the notation V [ V means that we allow V and V to share vertices (i.e., viewing V and V as different sets, we impose on a subset of V , an identification for each element of this subset with 107 an element of V); we see that En[(w;~t); ( ; )] depends only on the -specialized form of (w;~t); ( ; ), and so we may write En[(w;~t); ( ; )] = En[; ]n; which has an asymptotic expansion with coefficients pi(~a) with ~a = ~a(); 2. an -type is a type, T , as before, except that we have the additional information that is a subgraph of T , the underlying graph of T , and that now VT contains not only the initial vertex of the walk and vertices of degree at least three, but also contains all vertices and edges of ; hence T may be disconnected (if (w;~t) and ( ; ) represent a disconnected graph), and the beaded paths of Graph(w) can contain edges and vertices of , which are retained in the -type. It should be noted that -types, T , have two types of edges, namely (1) edges belonging to , which are fixed, with a fixed association of each fixed edge to an edge of B, and (2) "variable" edges, which represent beaded paths in the walk or form (that are free of edges). To each -type, T , wemay associate its type, T 0, obtained by forgetting the edges of , i.e., derived from the walk (w;~t) from which it arises; each edge of the underlying graph of T 0 corresponds to a path in the edges of T , some fixed and some variable. The certification of a walk, (w;~t), now means that each edge in the type, T 0, which corresponds to some path in T , has a lower bound on its length. But the set of variable edge lengths in T satisfying these lower bounds on each T 0 edge is an upset in functions ZE 0 T 1 , where E0T are the variable edges in T . Hence we get an expansion for the Pi(k) in terms of a sumsX ~m;~k WWT (~m)P (~k); (6.4) where T is an -type, and the ~m;~k vary over the variable edges of T , with ~k ~k0, andWWT (~m) satisfies the same bounds, via certification, that does 108 WWT (~m). Furthermore, any original type, T 0, can be associated to at most finitely many -types, T , since we obtain T from T 0 by including into the edges and vertices of T 0, adding only a finite additional number of edges and vertices (i.e., those of ( ; ) which do not lie on the graph of (w;~t). Hence the total number of -types with original type of order less than r is finite, and hence only a finite number of sums as in (6.4) are involved in the Pi(k) for Theorem 6.1.2. Hence we conclude Theorem 6.1.2. 6.2 End of the Proof We now proceed to complete our proof of the Alon conjecture for d-regular base graphs. Let us review our strategy here briefly. Due to the presence of tangles, we cannot expect a B-Ramanujan expansion of En[Tr(HkG)]. This lead us to show Theorem 6.0.1 that we have a B-Ramanujan expansion of En[ITF(r;B)[n](G)Tr(HkG)] To do this, we defined our certified trace, which essentially agrees up to any given order, r with the Hashimoto trace for random graphs that are tangle- free. Most of this thesis was devoted to show that this certified trace admits a B-Ramanujan expansion. Finally, our side-stepping lemma, allows us to make some conclusion out of this expansion if we can show that some of the coefficients of the expansion vanish. It has been known since [Fri03] that the principal part of the coefficient of order 0 vanishes: Lemma 6.2.1. Consider the B-Ramanujan expansion of Theorem 6.0.1. En[ITF(r;B)[n](G)Tr(HkG)] = P0(k) + P1(k) n + : : :+ Pr1(k) nr1 + error(r; n; k) with jerror(r; n; k)j CkC(d 1)knr 109 then there exists a constant C0, independent of n; k such that jP0(k) Tr(HkB)j C0kC0(d 1)k/2 Proof. This is essentially calculated in [Fri03]. The point is that the Pk(0) is the sum of the number of walks of length k in a type, T , whose underlying graph, T , has order 0. Since T is a connected graph with all vertices of degree at least two, we see that T must consist of a single vertex and a single self-loop (hence there is only one order that can be imposed on it). The additional type information (beyond T and its ordering of vertices and edges) is the lettering. Since Pk(0) is the leading term of the series for T , it follows that Pk(0) equals the expected number of strictly non-backtracking closed walks of length k0 in B, summed over all k0 divisible by k. Hence Pk(0) = X k0 divides k Tr(Hk0B ): But if k0 is a positive integer dividing k, then either k0 = k, or else k0 is between 1 and k/2. Hence jPk(0) Tr(HkB)j (k/2) max 1k0k/2 Tr(Hk0B ) (k/2)jEdirB j(d 1)k/2: This, along with our side-stepping lemma allows us to prove our Theo- rem 1.2.3: Proof. We want to apply the side-stepping lemma here. For this, we need a polyexponential expansion of the "new" Hashimoto trace, when the graph doesn't contain any tangles. Recall that the "new trace", that is, the sum of all new eigenvalues is given by TrnewB (HkG) = X 2SpecnewB (HG) k = Tr(HkG) Tr(HkB) 110 In other words, we are interested in the expansion of En[ITF(r;B)[n](G)TrnewB (HkG) ] So En[ITF(r;B)[n](G)TrnewB (HkG) ] = En[ITF(r;B)[n](G)Tr(HkG) ] En[ITF(r;B)[n](G)Tr(HkB)] = r1X i=0 Pi(k) ni + error(r; n; k) ! Tr(HkB)Probn[ITF(r;B)[n](G) = 1] Corollary 4.1.10 gives us that Probn[ITF(r;B)[n](G) = 1] = 1 q1n1 q2n2 : : : hence we can rewrite this as En[ITF(r;B)[n](G)TrnewB (HkG) ] = r1X i=0 bPi(k)ni + error(r; n; k) for bPi(k) = Pi(k) qi Tr(HkB), and where the error bound satisfies jerror(r; n; k)j CkC(d 1)knr We want to rewrite this as an expansion of polyexponential functions in order to apply our side-stepping lemma. If ePi denotes the principal part ofbPi, then we can rewrite this as En[ITF(r;B)[n](G)TrnewB (HkG) ] = r1X i=0 ePi(k)ni + error(r; n; k) with a new error term satisfying jerror(r; n; k)j CkC(d 1)knr + CkC(pd 1 + ")k 111 Notice that bP0(k) = P0(k) Tr(HkB) and by lemma 6.2.1 we have jP0(k) Tr(HkB)j CkC(d 1)k/2 hence eP0(k) = 0 and we can apply the side-stepping lemma to conclude that for any " > 0 there is a constant C for which Probn[newB (HG) p d 1 + "] C/n which completes our proof. As mentioned in the introduction on page 6, for regular graphs, Theo- rem 1.2.3 implies the Alon Conjecture for regular graphs, that is our Theo- rem 1.2.2. 112 Chapter 7 Conclusion We have successfully proved the generalized Alon conjecture for all regu- lar graphs. This generalizes the result of Friedman [Fri08] and improves on the work of [Fri03, LP10, LSV11, ABG10, Pud12]. In an article in prepara- tion, the author and Joel Friedman, will give a weakened generalized Alon conjecture for some non-regular base graphs based on the ideas of this thesis. To solve the generalized Alon conjecture for arbitrary base graph, one could try to develop analogous results for walks that allow backtracking. The Broder-Shamir [BS87] approach is necessarily more complicatedwhen backtracking is allowed, but we believe that a coincidence theory can still be adapted to this situation; however, there seem to be some serious diffi- culties in extending some of our methods to walks that can backtrack. There are many generalizations of the Alon conjecture to other classes of random graphs [FJR+96] or to other matrices associated to a graph [Pud12]. The recent result of [MSS13] shows that new eigenvalues of random coverings lead to d-regular Ramanujan graphs for all values of d. This gives stronger motivation to consider spectral aspects of random covering graphs. 113 Bibliography [ABG10] Louigi Addario-Berry and Simon Griffiths, The spectrum of ran- dom lifts, ArXiv e-prints 1012.4097 (2010). [Alo86] Noga Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83--96. [Bas92] Hyman Bass, The Ihara-Selberg zeta function of a tree lattice, International Journal of Mathematics 3 (1992), no. 6, 717--797. [BS87] Andrei Broder and Eli Shamir, On the second eigenvalue of ran- dom regular graphs, 28th Annual Symposium on Foundations of Computer Science (1987), 286--294. [FJR+96] Joel Friedman, Antoine Joux, Yuval Roichman, Jacques Stern, and Jean-Pierre Tillich, The action of a few random permutations on r-tuples and an application to cryptography, STACS, 1996, pp. 357--386. [Fri91] Joel Friedman, On the second eigenvalue and random walks in random d-regular graphs, Combinatorica 6 (1991), no. 2, 331-- 362. [Fri93] , Some geometric aspects of graphs and their eigenfunc- tions, Duke Mathematics Journal 69 (1993), no. 3, 487--525. [Fri03] , Relative expanders or weakly relative ramanujan graphs, Duke Mathematical Journal 118 (2003), no. 1, 19--35. 114 [Fri08] , A proof of Alon's second eigenvalue conjecture and re- lated problems, Memoirs of the American Mathematical Society 195 (2008), no. 910. [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applicationns, Bulletin of the American Mathe- matical Society 43 (2006), no. 4, 439--561. [Iha66] Yasutaka Ihara, On discrete subgroups of the two by two projec- tive linear group over p-adic fields, Journal of the Mathematical Society of Japan 18 (1966), 219--235. [KS00] Motoko Kotani and Toshikazu Sunada, Zeta functions of finite graphs, Journal of Mathematical Sciences, The University of Tokyo 7 (2000), no. 1, 7--25. [Lov93] László Lovász, Random walks on graphs: A survey, Paul Erdös is Eighty 2 (1993), 1--46. [LP10] Nati Linial and Doron Puder, Word maps and spectra of random graph lifts, Random Structures and Algorithms 37 (2010), no. 1, 100--135. [LPS88] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak, Ramanu- jan graphs, Combinatorica 8 (1988), no. 3, 261--277. [LSV11] Eyal Lubetzky, Benny Sudakov, and Van Vu, Spectra of lifted Ra- manujan graphs, Advances in Mathematics 227 (2011), no. 4, 1612--1645. [Mar88] Gregory Margulis, Explicit group-theoretic constructions of com- binatorial schemes and their applications in the construction of expanders and concentrators, Problems of Information Trans- mission 24 (1988), no. 1, 39--46. [MNS08] Steven Miller, Tim Novikoff, and Anthony Sabelli, The distribution of the largest nontrivial eigenvalues in families of random regular graphs, Experimental Mathematics 17 (2008), no. 2, 231--244. 115 [Mor94] Moshe Morgenstern, Existence and explicit construction of q+1 regular ramanujan graphs for every prime power q, Journal of Combinatorial Theory, Series B 62 (1994), no. 1, 44--62. [MSS13] Adam Marcus, Daniel Speilman, and Nikhil Srivastava, Interlac- ing families I: Bipartite Ramanujan graphs of all degrees, ArXiv e-prints 1304.4132 (2013). [Nil91] Alon Nilli, On the second eigenvalue of a graph, Discrete Math- ematics 91 (1991), no. 2, 207--210. [Pud12] Doron Puder, Expansion of random graphs: New proofs, new results, ArXiv e-prints 1212.5216 (2012). [Sun86] Toshikazu Sunada, L-functions in geometry and some applica- tions, Lecture Notes in Mathematics 1201 (1986), 266--284. 116
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Alon's second eigenvalue conjecture : simplified and...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Alon's second eigenvalue conjecture : simplified and generalized Kohler, David-Emmanuel 2013
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Alon's second eigenvalue conjecture : simplified and generalized |
Creator |
Kohler, David-Emmanuel |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | For a fixed graph, B, we study a probability model of random covering maps of degree n. Specifically, we study spectral properties of new eigenvalues of the adjacency matrix of a random covering, and its Hashimoto matrix (i.e., the adjacency matrix of the associated directed line graph). Our main theorem says that if B is d-regular, then for every positive epsilon, the probability that a random covering has a new adjacency eigenvalue greater than 2(d-1)^(1/2) + epsilon tends to zero as n tends to infinity. This matches the generalized Alon-Boppana lower bound. For general base graphs, B, Friedman conjectured in that the new eigenvalue bound holds with 2(d-1)^(1/2) replaced with the spectral radius of the universal cover of B. We refer to this conjecture as the generalized Alon conjecture; Alon stated this conjecture in the case where B has one vertex, i.e., the case of random d-regular graphs on n vertices. However, for some non-regular base graphs B, we cannot yet prove any non-trivial new eigenvalue upper bound with high probability. We use trace methods, as pioneered by Broder and Shamir for random, d-regular graphs; these methods were eventually refined by Friedman to prove the original Alon conjecture, i.e., in the case where B has one vertex. Our methods involve several significant simplifications of the methods of Friedman. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-07-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-ShareAlike 3.0 Unported |
DOI | 10.14288/1.0073984 |
URI | http://hdl.handle.net/2429/44686 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-sa/3.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_fall_kohler_david.pdf [ 429.14kB ]
- Metadata
- JSON: 24-1.0073984.json
- JSON-LD: 24-1.0073984-ld.json
- RDF/XML (Pretty): 24-1.0073984-rdf.xml
- RDF/JSON: 24-1.0073984-rdf.json
- Turtle: 24-1.0073984-turtle.txt
- N-Triples: 24-1.0073984-rdf-ntriples.txt
- Original Record: 24-1.0073984-source.json
- Full Text
- 24-1.0073984-fulltext.txt
- Citation
- 24-1.0073984.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0073984/manifest