Search Results

Documents authored by Stufler, Benedikt

Document
DOI: 10.4230/LIPIcs.AofA.2026.4
Scaling Limits of Multitype Bienaymé Trees

Authors: Louigi Addario-Berry, Philipp Beltran, Benedikt Stufler, and Paul Thévenin

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We first consider irreducible critical multitype Bienaymé trees and extend the results to the case, when they possess a critical irreducible component with attached subcritical components. We study these trees under two distinct conditioning frameworks: first, conditioning on the value of a linear combination of the numbers of vertices of given types; and second, conditioning on the precise number of vertices belonging to a selected subset of types. We prove that, under a finite exponential moment condition, the scaling limit as the tree size tends to infinity is given by the Brownian Continuum Random Tree. Additionally, we establish strong non-asymptotic tail bounds for the height of such trees. Our main tools include a flattening operation applied to multitype trees and sharp estimates regarding the structure of monotype trees with a given sequence of degrees.
Cite as

Louigi Addario-Berry, Philipp Beltran, Benedikt Stufler, and Paul Thévenin. Scaling Limits of Multitype Bienaymé Trees. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{addarioberry_et_al:LIPIcs.AofA.2026.4,
  author =	{Addario-Berry, Louigi and Beltran, Philipp and Stufler, Benedikt and Th\'{e}venin, Paul},
  title =	{{Scaling Limits of Multitype Bienaym\'{e} Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.4},
  URN =		{urn:nbn:de:0030-drops-262750},
  doi =		{10.4230/LIPIcs.AofA.2026.4},
  annote =	{Keywords: branching processes, multitype trees, scaling limit}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.10
Gibbs Partitions and Lattice Paths

Authors: Niccolò Bosio, Markus Kuba, and Benedikt Stufler

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We study a Gibbs partition model (composition scheme) under a new condition on the component weights, leading to a previously unobserved regime for the number of components. We establish a condensation phenomenon producing a unique giant component, and prove a Cox process limit describing a sublinear power-law growth of sizes of non-maximal components. Our results are motivated by applications to lattice paths and random walks, including simple random walks in the cube, Delannoy paths, pairs of Dyck bridges, urn models and card guessing games.
Cite as

Niccolò Bosio, Markus Kuba, and Benedikt Stufler. Gibbs Partitions and Lattice Paths. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bosio_et_al:LIPIcs.AofA.2026.10,
  author =	{Bosio, Niccol\`{o} and Kuba, Markus and Stufler, Benedikt},
  title =	{{Gibbs Partitions and Lattice Paths}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.10},
  URN =		{urn:nbn:de:0030-drops-262814},
  doi =		{10.4230/LIPIcs.AofA.2026.10},
  annote =	{Keywords: Gibbs partitions, composition schemes, lattice paths, random walks, condensation}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.11
Poisson-Dirichlet Graphons and Permutons

Authors: Benedikt Stufler

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We introduce classes of supergraphs and superpermutations with novel universal graphon and permuton limiting objects whose construction involves the two-parameter Poisson-Dirichlet process introduced by Pitman and Yor (1997). We demonstrate the universality of these limiting objects through general invariance principles in a heavy-tailed regime and establish a comprehensive phase diagram for the asymptotic shape of superstructures.
Cite as

Benedikt Stufler. Poisson-Dirichlet Graphons and Permutons. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{stufler:LIPIcs.AofA.2026.11,
  author =	{Stufler, Benedikt},
  title =	{{Poisson-Dirichlet Graphons and Permutons}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.11},
  URN =		{urn:nbn:de:0030-drops-262821},
  doi =		{10.4230/LIPIcs.AofA.2026.11},
  annote =	{Keywords: Graphons, Permutons, Poisson-Dirichlet point processes}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact