The k-Cut Model in Conditioned Galton-Watson Trees

Authors Gabriel Berzunza , Xing Shi Cai , Cecilia Holmgren



PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.5.pdf
  • Filesize: 0.49 MB
  • 10 pages

Document Identifiers

Author Details

Gabriel Berzunza
  • Department of Mathematics, Uppsala University, Sweden
Xing Shi Cai
  • Department of Mathematics, Uppsala University, Sweden
Cecilia Holmgren
  • Department of Mathematics, Uppsala University, Sweden

Cite AsGet BibTex

Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-Cut Model in Conditioned Galton-Watson Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.AofA.2020.5

Abstract

The k-cut number of rooted graphs was introduced by Cai et al. [Cai and Holmgren, 2019] as a generalization of the classical cutting model by Meir and Moon [Meir and Moon, 1970]. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson [Janson, 2006].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • k-cut
  • cutting
  • conditioned Galton-Watson trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Louigi Addario-Berry, Nicolas Broutin, and Cecilia Holmgren. Cutting down trees with a Markov chainsaw. Ann. Appl. Probab., 24(6):2297-2339, 2014. URL: https://doi.org/10/f22cjg.
  2. David Aldous. The continuum random tree. II. An overview. In Stochastic Analysis (Durham, 1990), volume 167 of London Math. Soc. Lecture Note Ser., pages 23-70. Cambridge Univ. Press, Cambridge, 1991. Google Scholar
  3. David Aldous. The continuum random tree. III. Ann. Probab., 21(1):248-289, 1993. URL: https://doi.org/10/ckg9qj.
  4. Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-cut model in deterministic and random trees. arXiv e-prints, July 2019. URL: http://arxiv.org/abs/1907.02770.
  5. Robert M. Blumenthal. Excursions of Markov Processes. Probability and Its Applications. Birkhäuser Boston, Inc., Boston, MA, 1992. Google Scholar
  6. Xing Shi Cai and Cecilia Holmgren. Cutting resilient networks - complete binary trees. The Electronic Journal of Combinatorics, 26(4):P4.43, December 2019. URL: https://doi.org/10/ggmnn3.
  7. Xing Shi Cai, Cecilia Holmgren, Luc Devroye, and Fiona Skerman. k-cut on paths and some trees. Electron. J. Probab., 24:22 pp., 2019. URL: https://doi.org/10/ggcq7j.
  8. Michael Drmota, Alex Iksanov, Martin Moehle, and Uwe Roesler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms, 34(3):319-336, 2009. URL: https://doi.org/10/ftj6gh.
  9. Cecilia Holmgren. Random records and cuttings in binary search trees. Combin. Probab. Comput., 19(3):391-424, 2010. URL: https://doi.org/10/b56679.
  10. Cecilia Holmgren. A weakly 1-stable distribution for the number of random records and cuttings in split trees. Adv. in Appl. Probab., 43(1):151-177, 2011. Google Scholar
  11. Alex Iksanov and Martin Möhle. A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Comm. Probab., 12:28-35, 2007. URL: https://doi.org/10/fz3c45.
  12. Svante Janson. Random records and cuttings in complete binary trees. In Mathematics and Computer Science. III, Trends Math., pages 241-253. Birkhäuser, Basel, 2004. Google Scholar
  13. Svante Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithms, 29(2):139-179, 2006. URL: https://doi.org/10/dk76cq.
  14. Olav Kallenberg. Foundations of Modern Probability. Probability and Its Applications (New York). Springer-Verlag, New York, second edition, 2002. Google Scholar
  15. Jean-François Marckert and Abdelkader Mokkadem. The depth first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab., 31(3):1655-1678, 2003. URL: https://doi.org/10/dwgcwz.
  16. A. Meir and J. W. Moon. Cutting down random trees. J. Austral. Math. Soc., 11:313-324, 1970. URL: https://doi.org/10/b8bdzq.
  17. A. Meir and J.W. Moon. Cutting down recursive trees. Mathematical Biosciences, 21(3):173-181, 1974. URL: https://doi.org/10/dkdjtv.
  18. Alois Panholzer. Destruction of recursive trees. In Mathematics and Computer Science. III, Trends Math., pages 267-280. Birkhäuser, Basel, 2004. Google Scholar
  19. Alois Panholzer. Cutting down very simple trees. Quaest. Math., 29(2):211-227, 2006. URL: https://doi.org/10/chw83w.
  20. Daniel Revuz and Marc Yor. Continuous Martingales and Brownian Motion, volume 293 of Grundlehren Der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, third edition, 1999. Google Scholar
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