DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.11

Tree Walks and the Spectrum of Random Graphs

Authors: Eva-Maria Hainzl and Élie de Panafieu

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

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.

Cite as

Eva-Maria Hainzl and Élie de Panafieu. Tree Walks and the Spectrum of Random Graphs. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hainzl_et_al:LIPIcs.AofA.2024.11,
  author =	{Hainzl, Eva-Maria and de Panafieu, \'{E}lie},
  title =	{{Tree Walks and the Spectrum of Random Graphs}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.11},
  URN =		{urn:nbn:de:0030-drops-204466},
  doi =		{10.4230/LIPIcs.AofA.2024.11},
  annote =	{Keywords: Spectrum of random matrices, generating functions}
}

Document

DOI: 10.4230/LIPIcs.AofA.2022.7

Universal Properties of Catalytic Variable Equations

Authors: Michael Drmota and Eva-Maria Hainzl

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract

Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that under certain positivity assumptions the dominant singularity of the solution function has a universal behavior. We have to distinguish between linear catalytic equations, where a dominating square-root singularity appears, and non-linear catalytic equations, where we - usually - have a singularity of type 3/2.

Cite as

Michael Drmota and Eva-Maria Hainzl. Universal Properties of Catalytic Variable Equations. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2022.7,
  author =	{Drmota, Michael and Hainzl, Eva-Maria},
  title =	{{Universal Properties of Catalytic Variable Equations}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.7},
  URN =		{urn:nbn:de:0030-drops-160930},
  doi =		{10.4230/LIPIcs.AofA.2022.7},
  annote =	{Keywords: catalytic equation, singular expansion, univeral asymptotics}
}

Search Results

Documents authored by Hainzl, Eva-Maria

Tree Walks and the Spectrum of Random Graphs

Abstract

Cite as

Universal Properties of Catalytic Variable Equations

Abstract

Cite as

Thanks for your feedback!

Could not send message