2 Search Results for "Hackl, Benjamin"

Document
DOI: 10.4230/LIPIcs.AofA.2022.10
Uncovering a Random Tree

Authors: Benjamin Hackl, Alois Panholzer, and Stephan Wagner

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

Abstract
We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with n vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this extended abstract: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.
Cite as

Benjamin Hackl, Alois Panholzer, and Stephan Wagner. Uncovering a Random Tree. 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. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hackl_et_al:LIPIcs.AofA.2022.10,
  author =	{Hackl, Benjamin and Panholzer, Alois and Wagner, Stephan},
  title =	{{Uncovering a Random Tree}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{10:1--10:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.10},
  URN =		{urn:nbn:de:0030-drops-160962},
  doi =		{10.4230/LIPIcs.AofA.2022.10},
  annote =	{Keywords: Labeled tree, uncover process, functional central limit theorem, limiting distribution, phase transition}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.26
Counting Ascents in Generalized Dyck Paths

Authors: Benjamin Hackl, Clemens Heuberger, and Helmut Prodinger

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

Abstract
Non-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees. We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance.
Cite as

Benjamin Hackl, Clemens Heuberger, and Helmut Prodinger. Counting Ascents in Generalized Dyck Paths. 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. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hackl_et_al:LIPIcs.AofA.2018.26,
  author =	{Hackl, Benjamin and Heuberger, Clemens and Prodinger, Helmut},
  title =	{{Counting Ascents in Generalized Dyck Paths}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-89191},
  doi =		{10.4230/LIPIcs.AofA.2018.26},
  annote =	{Keywords: Lattice path, Lukasiewicz path, ascent, asymptotic analysis, implicit function, singular inversion}
}
  • Refine by Author
  • 2 Hackl, Benjamin
  • 1 Heuberger, Clemens
  • 1 Panholzer, Alois
  • 1 Prodinger, Helmut
  • 1 Wagner, Stephan

  • Refine by Classification
  • 2 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Mathematical software
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Labeled tree
  • 1 Lattice path
  • 1 Lukasiewicz path
  • 1 ascent
  • 1 asymptotic analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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