The k-Cut Model in Conditioned Galton-Watson Trees
k-cut
cutting
conditioned Galton-Watson trees
- Mathematics of computing → Probabilistic algorithms
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].
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.