A note on the trace method for random regular graphs

DOI10.1007/S11856-023-2497-5MaRDI QIDQ6076192zbMATH OpenOpenAlexFDO

Authors

Publication date 23 October 2023

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.13605

zbMATH Keywords

non-backtracking spectrum of a regular graphrandom \(d\)-regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The main goal of this note is to illustrate the advantage of analyzing the non-backtracking spectrum of a regular graph rather than the ordinary spectrum. We show that by switching to non-backtracking spectrum, the method of proof used in [Puder 2015, arXiv::1212.5216] yields a bound of $2sqrtd-1+frac2sqrtd-1$ instead of the original $2sqrtd-1+1$ on the second largest eigenvalue of a random $d$-regular graph.

Recommendations

• The spectral gap of random regular graphs
• A proof of alon's second eigenvalue conjecture
• On the second eigenvalue and random walks in random d-regular graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• The spectral gap of dense random regular graphs

Cites work

• A combinatorial proof of Ihara-Bass's formula for the zeta function of regular graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A proof of Alon’s second eigenvalue conjecture and related problems
• Cutoff on all Ramanujan graphs
• Eigenvalues and expanders
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Expander graphs and their applications
• Expansion of random graphs: new proofs, new results
• Growth of primitive elements in free groups.
• How groups grow.
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• Measure preserving words are primitive
• On the second eigenvalue and random walks in random d-regular graphs
• On the second eigenvalue of a graph
• Primitive words, free factors and measure preservation.
• Random lifts of graphs
• Relative expanders or weakly relatively Ramanujan graphs.

Cited in

(4)

• Spectral gap in random bipartite biregular graphs and applications
• Word measures on \(\mathrm{GL}_N(q)\) and free group algebras
• Black holes, complex curves, and graph theory: revising a conjecture by Kasner
• An extension of the cogrowth formula to arbitrary subsets of the tree

This page was built for publication: A note on the trace method for random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076192)