2 Search Results for "Panholzer, Alois"

Document
DOI: 10.4230/LIPIcs.AofA.2024.29
Statistics of Parking Functions and Labeled Forests

Authors: Stephan Wagner and Mei Yin

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

Abstract
In this paper we obtain some new results on the enumeration of parking functions and labeled forests. We introduce new statistics both for parking functions and for labeled forests that are connected to each other by means of a bijection. We determine the joint distribution of two statistics on parking functions and their counterparts on labeled forests. Our results on labeled forests also serve to explain the mysterious equidistribution between two seemingly unrelated statistics in parking functions recently identified by Stanley and Yin and give an explicit bijection between the two statistics.
Cite as

Stephan Wagner and Mei Yin. Statistics of Parking Functions and Labeled Forests. 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. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.AofA.2024.29,
  author =	{Wagner, Stephan and Yin, Mei},
  title =	{{Statistics of Parking Functions and Labeled Forests}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-204648},
  doi =		{10.4230/LIPIcs.AofA.2024.29},
  annote =	{Keywords: parking function, labeled forest, generating function, Pollak’s circle argument, bijection}
}
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}
}
  • Refine by Author
  • 2 Wagner, Stephan
  • 1 Hackl, Benjamin
  • 1 Panholzer, Alois
  • 1 Yin, Mei

  • Refine by Classification
  • 2 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Random graphs

  • Refine by Keyword
  • 1 Labeled tree
  • 1 Pollak’s circle argument
  • 1 bijection
  • 1 functional central limit theorem
  • 1 generating function
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2024

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