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
- 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?)
- 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
- 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 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
- 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
- \(k\)-cut on paths and some trees
Cited in
(15)- The cut-tree of large Galton-Watson trees and the Brownian CRT
- The cut metric, random graphs, and branching processes
- \(k\)-cut on paths and some trees
- A note on the probability of cutting a Galton-Watson tree
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
- On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
- scientific article; zbMATH DE number 7703232 (Why is no real title available?)
- Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
- The vertex-cut-tree of Galton-Watson trees converging to a stable tree
- Record process on the continuum random tree
- Cut-Set Sums and Tree Processes
- \(k\)-cut model for the Brownian continuum random tree
- A model in which every Kurepa tree is thick
- Cutting resilient networks -- complete binary trees
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)
