Document Open Access Logo

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

Funding

This work is supported by the Knut and Alice Wallenberg Foundation, the Swedish Research Council and The Swedish Foundations' starting grant from Ragnar Söderbergs Foundation.

Cite As Get 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
    0
    Metadata Views

Related Versions

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact