The k-cut model in deterministic and random trees
From MaRDI portal
Publication:2223481
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.
Recommendations
Cites work
- \(k\)-cut on paths and some trees
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Almost giant clusters for percolation on large trees with logarithmic heights
- Cutting down random trees
- Cutting down recursive trees
- Cutting down trees with a Markov chainsaw
- Cutting down very simple trees
- Cutting resilient networks -- complete binary trees
- Emergence of Scaling in Random Networks
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 2127735 (Why is no real title available?)
- scientific article; zbMATH DE number 2127740 (Why is no real title available?)
- scientific article; zbMATH DE number 19286 (Why is no real title available?)
- scientific article; zbMATH DE number 1099195 (Why is no real title available?)
- Note on the heights of random recursive trees and random m‐ary search trees
- Novel characteristics of split trees by use of renewal theory
- On random trees
- On the asymptotic behaviour of random recursive trees in random environments
- On the distribution of distances in recursive trees
- Probability: a graduate course
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Profiles of random trees: Plane-oriented recursive trees
- Random cutting and records in deterministic and random trees
- Random records and cuttings in binary search trees
- Random recursive trees and preferential attachment trees are random split trees
- Random Trees
- The continuum random tree. III
- The cut-tree of large Galton-Watson trees and the Brownian CRT
- The depth first processes of Galton-Watson trees converge to the same Brownian excursion
- The total path length of split trees
- Universal Limit Laws for Depths in Random Trees
Cited in
(16)- A model in which every Kurepa tree is thick
- 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
- \(k\)-cut model for the Brownian continuum random tree
- Cutting resilient networks -- complete binary trees
- k-cuts on a path
- The vertex-cut-tree of Galton-Watson trees converging to a stable tree
- Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
- \(k\)-cut on paths and some trees
- Record process on the continuum random tree
- The cut-tree of large Galton-Watson trees and the Brownian CRT
- Cut-Set Sums and Tree Processes
- Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
- A note on the probability of cutting a Galton-Watson tree
- The cut metric, random graphs, and branching processes
- scientific article; zbMATH DE number 7703232 (Why is no real title available?)
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)
