The $k$-cut model in deterministic and random trees

Berzunza, Gabriel, Cai, Xing Shi and Holmgren, Cecilia (2019) The $k$-cut model in deterministic and random trees. The Electronic Journal of Combinatorics, 28 (1). pp. 1-30.

Access the full-text of this item by clicking on the Open Access link.

Text
1907.02770v2.pdf - Submitted version
Download (743kB) | Preview

Official URL: http://dx.doi.org/10.37236/9486

Abstract

The $k$-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converges 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. Using the same method, we also show that the k-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.

Item Type:	Article
Additional Information:	30 pages, 1 figure
Uncontrolled Keywords:	math.PR, math.PR, 60C05
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	08 Jul 2021 07:58
Last Modified:	05 Mar 2023 07:42
DOI:	10.37236/9486
Open Access URL:	https://www.combinatorics.org/ojs/index.php/eljc/a...
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3129191