On the Relativized Alon Eigenvalue Conjecture II: Asymptotic Expansion Theorems for Walks

Understand

This is the second 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.

• The first main result in this article concerns the function $f(k,n)$ defined as the number of SNBC (strictly non-backtracking closed) walks of length $k$ of a given homotopy type in a random covering graph of degree $n$ of a fixed graph.
• We prove the existence of asymptotic expansions in powers of $1/n$ for $f(k,n)$, where the coefficients---functions of $k$---are proven to have some desirable properties; namely, these coefficients are approximately a sum of polynomials times exponential functions.
• The second main result is a generalization of the first, where the number of SNBC walks of length $k$ is multiplied by an indicator function that the covering graph contains a certain type of {\em tangle}; the second result requires more terminology, although its proof uses the same basic tools used to prove the first result.