The k-cut model in deterministic and random trees
From MaRDI portal
Publication:2223481
DOI10.37236/9486zbMATH Open1462.60010arXiv1907.02770OpenAlexW3129467249MaRDI QIDQ2223481FDOQ2223481
Authors: Gabriel Berzunza, Xing Shi Cai, Cecilia Holmgren 
Publication date: 29 January 2021
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Abstract: The -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.
Full work available at URL: https://arxiv.org/abs/1907.02770
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Recommendations
Cites Work
- Title not available (Why is that?)
- Emergence of Scaling in Random Networks
- Random Trees
- Title not available (Why is that?)
- Probability: a graduate course
- The depth first processes of Galton-Watson trees converge to the same Brownian excursion
- The continuum random tree. III
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- Cutting down recursive trees
- Title not available (Why is that?)
- Random cutting and records in deterministic and random trees
- Cutting down very simple trees
- The cut-tree of large Galton-Watson trees and the Brownian CRT
- Cutting down trees with a Markov chainsaw
- Cutting down random trees
- Note on the heights of random recursive trees and random m‐ary search trees
- Title not available (Why is that?)
- Almost giant clusters for percolation on large trees with logarithmic heights
- Novel characteristics of split trees by use of renewal theory
- Profiles of random trees: Plane-oriented recursive trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- On random trees
- Title not available (Why is that?)
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Random records and cuttings in binary search trees
- Universal Limit Laws for Depths in Random Trees
- The total path length of split trees
- On the distribution of distances in recursive trees
- On the asymptotic behaviour of random recursive trees in random environments
- Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
- Cutting resilient networks -- complete binary trees
- \(k\)-cut on paths and some trees
Cited In (9)
- Title not available (Why is that?)
- Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
- A model in which every Kurepa tree is thick
- A note on the probability of cutting a Galton-Watson tree
- On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- Cut-Set Sums and Tree Processes
- \(k\)-cut model for the Brownian continuum random tree
- The cut metric, random graphs, and branching processes
This page was built for publication: The \(k\)-cut model in deterministic and random trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223481)
