The k-cut model in deterministic and random trees

DOI10.37236/9486MaRDI QIDQ2223481zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1907.02770

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-cut numberGalton-Watson treerandom tree

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

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.

Review text

This paper studies a \(k\)-cut cutting down process over conditioned Galton-Watson trees. The process generally starts with a tree \(T_n\) over \(n\) nodes by choosing uniformly at random a node from the component containing the root and cutting the chosen node once. If the vertex has been cut \(k\) times, it will be removed from the graph. The process continues until the root has been removed. The total number of cuts needed to end the procedure is called the \(k\)-cut number denoted by \(K_k(T_n)\). If \(T_n\) is a Galton-Watson tree conditioned on its number of vertices being \(n\) with offspring distribution defined with unit expectation and finite variance \(\sigma^2\), then it is shown that \(\sigma^{-1/k}n^{-1+1/2k}K(T_n)\) converges in distribution to \(Z_{CRT}\) as \(n\) goes to infinity, where \(Z_{CRT}\) is a non-degenerate variable with the distribution determined by all its moments, which have been worked out.

Recommendations

• \(k\)-cut model for the Brownian continuum random tree
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• \(k\)-cut on paths and some trees
• A note on the probability of cutting a Galton-Watson tree
• Cutting resilient networks -- complete binary trees

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)