2026-08-07T16:42:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20446 2024-07-18T12:12:42Z ddc:004 open_access

Tree Walks and the Spectrum of Random Graphs Hainzl, Eva-Maria de Panafieu, Élie Spectrum of random matrices generating functions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eva-Maria Hainzl and Élie de Panafieu 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.11 urn:nbn:de:0030-drops-204466 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode