Uncovering a Random Tree

Authors Benjamin Hackl , Alois Panholzer , Stephan Wagner



PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.10.pdf
  • Filesize: 0.89 MB
  • 17 pages

Document Identifiers

Author Details

Benjamin Hackl
  • Uppsala University, Sweden
  • University of Klagenfurt, Austria
Alois Panholzer
  • TU Wien, Austria
Stephan Wagner
  • Uppsala University, Sweden

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

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)
    0
    PDF Downloads

References

  1. David Aldous and Jim Pitman. The standard additive coalescent. Ann. Probab., 26(4):1703-1726, 1998. URL: https://doi.org/10.1214/aop/1022855879.
  2. 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.
  3. Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, Inc., New York, second edition, 1999. URL: https://doi.org/10.1002/9780470316962.
  4. 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.
  5. Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511801655.
  6. 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.
  7. 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.
  8. Achim Klenke. Probability theory - a comprehensive course. Universitext. Springer, Cham, 2020. Third edition. URL: https://doi.org/10.1007/978-3-030-56402-5.
  9. 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.
  10. Jim Pitman. Coalescent random forests. J. Combin. Theory Ser. A, 85(2):165-193, 1999. URL: https://doi.org/10.1006/jcta.1998.2919.
  11. Jim Pitman. Coalescents with multiple collisions. Ann. Probab., 27(4):1870-1902, 1999. URL: https://doi.org/10.1214/aop/1022677552.
  12. 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.
  13. 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.
  14. John Riordan. Combinatorial identities. John Wiley & Sons, Inc., New York, 1968. Google Scholar
  15. 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.
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