Tree walks and the spectrum of random graphs

2024/05/14 by Hainzl, Eva-Maria, de Panafieu, Élie · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.2405.08347

Abstract

It is a classic result in spectral theory that the limit distribution of the spectral measure of random graphs G(n, p) converges to the semicircle law in case np tends to infinity with n. The spectral measure for random graphs G(n, c/n) however is less understood. In this work, we combine and extend two combinatorial approaches by Bauer and Golinelli (2001) and Enriquez and Menard (2016) and approximate the moments of the spectral measure by counting walks that span trees.

Cited by

• Formulas and asymptotics of hypergraph Catalan numbers
• Bridging Classical and Quantum Information Scrambling with the Operator Entanglement Spectrum

Related

• Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
• Resolvent of Large Random Graphs
• On the spectral distribution of large weighted random regular graphs
• New bounds on the spectral radius of graphs based on the moment problem
• Walks and the spectral radius of graphs