LIPIcs.AofA.2022.10.pdf
- Filesize: 0.89 MB
- 17 pages
Document
Uncovering a Random Tree
Authors
Benjamin Hackl 
,
Alois Panholzer ,
Stephan Wagner
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
File
Document Identifiers
Author Details
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.AofA.2022.10
https://doi.org/10.4230/LIPIcs.AofA.2022.10
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Random graphs
- Mathematics of computing → Generating functions
Keywords
- Labeled tree
- uncover process
- functional central limit theorem
- limiting distribution
- phase transition
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- David Aldous and Jim Pitman. The standard additive coalescent. Ann. Probab., 26(4):1703-1726, 1998. URL: https://doi.org/10.1214/aop/1022855879.
- Jean Bertoin. Random fragmentation and coagulation processes, volume 102 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. URL: https://doi.org/10.1017/CBO9780511617768.
- Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, Inc., New York, second edition, 1999. URL: https://doi.org/10.1002/9780470316962.
- P. Chassaing and G. Louchard. Phase transition for parking blocks, Brownian excursion and coalescence. Random Structures Algorithms, 21(1):76-119, 2002. URL: https://doi.org/10.1002/rsa.10039.
- Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511801655.
- Svante Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithms, 29(2):139-179, 2006. URL: https://doi.org/10.1002/rsa.20086.
- J. F. C. Kingman. The coalescent. Stochastic Process. Appl., 13(3):235-248, 1982. URL: https://doi.org/10.1016/0304-4149(82)90011-4.
- Achim Klenke. Probability theory - a comprehensive course. Universitext. Springer, Cham, 2020. Third edition. URL: https://doi.org/10.1007/978-3-030-56402-5.
- Jeremy L. Martin and Victor Reiner. Factorization of some weighted spanning tree enumerators. J. Combin. Theory Ser. A, 104(2):287-300, 2003. URL: https://doi.org/10.1016/j.jcta.2003.08.003.
- Jim Pitman. Coalescent random forests. J. Combin. Theory Ser. A, 85(2):165-193, 1999. URL: https://doi.org/10.1006/jcta.1998.2919.
- Jim Pitman. Coalescents with multiple collisions. Ann. Probab., 27(4):1870-1902, 1999. URL: https://doi.org/10.1214/aop/1022677552.
- Jeffery B. Remmel and S. Gill Williamson. Spanning trees and function classes. Electron. J. Combin., 9(1):Research Paper 34, 24, 2002. URL: http://www.combinatorics.org/Volume_9/Abstracts/v9i1r34.html.
- Daniel Revuz and Marc Yor. Continuous martingales and Brownian motion, volume 293 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, third edition, 1999. URL: https://doi.org/10.1007/978-3-662-06400-9.
-
John Riordan. Combinatorial identities. John Wiley & Sons, Inc., New York, 1968.
- Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. URL: https://doi.org/10.1017/CBO9780511609589.