On the Relativized Alon Second Eigenvalue Conjecture III: Asymptotic Expansions for Tangle-Free Hashimoto Traces
Preprint
Abstract
This is the third in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we consider random graphs that are random covering graphs of large degree $n$ of a fixed base graph. We prove the existence of asympototic expansion in $1/n$ for the expected value of the number of strictly non-backtracking closed walks of length $k$ times the indicator function that the graph is free of certain {\em tangles}; moreover, we prove that the coefficients of these expansions are "nice functions" of $k$, namely approximately equal to a sum of polynomials in $k$ times exponential functions of $k$. Our results use the methods of Friedman used to resolve Alon's original conjecture, combined with the results of Article~II in this series of articles. One simplification in this article over the previous methods of Friedman is that the "regularlized traces" used in this article, which we call {\em certified traces}, are far easier to define and work with than the previously utilized {\em selective traces}.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Ramanujan coverings of graphsAdvances in Mathematics, 2018
- Expansion of random graphs: new proofs, new resultsInventiones Mathematicae, 2014
- Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees2013
- Spectra of lifted Ramanujan graphsAdvances in Mathematics, 2011
- Word maps and spectra of random graph liftsRandom Structures & Algorithms, 2010
- Lifts, Discrepancy and Nearly Optimal Spectral Gap*Combinatorica, 2006
- Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power qJournal of Combinatorial Theory, Series B, 1994
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984