2019/11/13 by Joel Friedman, Friedman, Joel, David Kohler +1
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Markov Chains and Monte Carlo Methods #Primary 68R10
paper · pdf · doi:10.48550/arxiv.1911.05775
openalex publication_date 2019/11/13 · openalex created_date 2019/11/22 · openalex updated_date 2026/07/28
This is the sixth 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 article we show that if the fixed graph is regular Ramanujan, then the \em algebraic power of the model of random covering graphs is +∞. This implies a number of interesting results, such as (1) one obtains the upper and lower bounds---matching to within a multiplicative constant---for the probability that a random covering map has some new adjacency eigenvalue outside the Alon bound, and (2) with probability smaller than any negative power of the degree of the covering map, some new eigenvalue fails to be within the Alon bound without the covering map containing one of finitely many "tangles" as a subgraph (and this tangle containment event has low probability).