License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.10
URN: urn:nbn:de:0030-drops-160962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16096/
Go to the corresponding LIPIcs Volume Portal

Hackl, Benjamin ; Panholzer, Alois ; Wagner, Stephan

Uncovering a Random Tree

pdf-format:
LIPIcs-AofA-2022-10.pdf (0.9 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/16096},
  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}
}

Keywords: Labeled tree, uncover process, functional central limit theorem, limiting distribution, phase transition
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI