4 Search Results for "Stufler, Benedikt"

Document
DOI: 10.4230/LIPIcs.AofA.2024.6
Phase Transition for Tree-Rooted Maps

Authors: Marie Albenque, Éric Fusy, and Zéphyr Salvy

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

Abstract
We introduce a model of tree-rooted planar maps weighted by their number of 2-connected blocks. We study its enumerative properties and prove that it undergoes a phase transition. We give the distribution of the size of the largest 2-connected blocks in the three regimes (subcritical, critical and supercritical) and further establish that the scaling limit is the Brownian Continuum Random Tree in the critical and supercritical regimes, with respective rescalings √{n/log(n)} and √n.
Cite as

Marie Albenque, Éric Fusy, and Zéphyr Salvy. Phase Transition for Tree-Rooted Maps. 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. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albenque_et_al:LIPIcs.AofA.2024.6,
  author =	{Albenque, Marie and Fusy, \'{E}ric and Salvy, Z\'{e}phyr},
  title =	{{Phase Transition for Tree-Rooted Maps}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{6:1--6:14},
  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.6},
  URN =		{urn:nbn:de:0030-drops-204413},
  doi =		{10.4230/LIPIcs.AofA.2024.6},
  annote =	{Keywords: Asymptotic Enumeration, Planar maps, Random trees, Phase transition}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.7
Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models

Authors: Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner

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

Abstract
Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of q-enumeration (this is a model where objects with a parameter of value k have a Gibbs measure/Boltzmann weight q^k). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value q = q_c, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime (q > q_c), and it is a Boltzmann distribution in the subcritical regime (0 < q < q_c). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
Cite as

Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner. Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models. 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. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2024.7,
  author =	{Banderier, Cyril and Kuba, Markus and Wagner, Stephan and Wallner, Michael},
  title =	{{Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-204427},
  doi =		{10.4230/LIPIcs.AofA.2024.7},
  annote =	{Keywords: Composition schemes, q-enumeration, generating functions, Gibbs distribution, phase transitions, limit laws, Mittag-Leffler distribution, chi distribution, Boltzmann distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.10
Cut Vertices in Random Planar Maps

Authors: Michael Drmota, Marc Noy, and Benedikt Stufler

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.
Cite as

Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2020.10,
  author =	{Drmota, Michael and Noy, Marc and Stufler, Benedikt},
  title =	{{Cut Vertices in Random Planar Maps}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.10},
  URN =		{urn:nbn:de:0030-drops-120403},
  doi =		{10.4230/LIPIcs.AofA.2020.10},
  annote =	{Keywords: random planar maps, cut vertices, generating functions, local graph limits}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.34
Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex

Authors: Benedikt Stufler

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We prove limit theorems describing the asymptotic behaviour of a typical vertex in random simply generated trees as their sizes tends to infinity. In the standard case of a critical Galton-Watson tree conditioned to be large, the limit is the invariant random sin-tree constructed by Aldous (1991). Our main contribution lies in the condensation regime where vertices of macroscopic degree appear. Here we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with "large" degree. Beyond this distinguished ancestor, different behaviours may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the important case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.
Cite as

Benedikt Stufler. Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{stufler:LIPIcs.AofA.2018.34,
  author =	{Stufler, Benedikt},
  title =	{{Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and 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.2018.34},
  URN =		{urn:nbn:de:0030-drops-89276},
  doi =		{10.4230/LIPIcs.AofA.2018.34},
  annote =	{Keywords: Galton-Watson trees, local weak limits}
}
  • Refine by Author
  • 2 Stufler, Benedikt
  • 1 Albenque, Marie
  • 1 Banderier, Cyril
  • 1 Drmota, Michael
  • 1 Fusy, Éric
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Enumeration
  • 2 Mathematics of computing → Generating functions
  • 2 Mathematics of computing → Stochastic processes
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 2 generating functions
  • 1 Asymptotic Enumeration
  • 1 Boltzmann distribution
  • 1 Composition schemes
  • 1 Galton-Watson trees
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2024
  • 1 2018
  • 1 2020

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact