Search Results

Documents authored by Hackl, Benjamin

Document
DOI: 10.4230/LIPIcs.AofA.2024.19
Binomial Sums and Mellin Asymptotics with Explicit Error Bounds: A Case Study

Authors: Benjamin Hackl and Stephan Wagner

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

Abstract
Making use of a newly developed package in the computer algebra system SageMath, we show how to perform a full asymptotic analysis by means of the Mellin transform with explicit error bounds. As an application of the method, we answer a question of Bóna and DeJonge on 132-avoiding permutations with a unique longest increasing subsequence that can be translated into an inequality for a certain binomial sum.
Cite as

Benjamin Hackl and Stephan Wagner. Binomial Sums and Mellin Asymptotics with Explicit Error Bounds: A Case Study. 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. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hackl_et_al:LIPIcs.AofA.2024.19,
  author =	{Hackl, Benjamin and Wagner, Stephan},
  title =	{{Binomial Sums and Mellin Asymptotics with Explicit Error Bounds: A Case Study}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-204549},
  doi =		{10.4230/LIPIcs.AofA.2024.19},
  annote =	{Keywords: binomial sum, Mellin transform, asymptotics, explicit error bounds, B-terms}
}
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.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}
}
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