The k-cut model in deterministic and random trees

DOI10.37236/9486zbMATH Open1462.60010OpenAlexW3129467249MaRDI 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 $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.

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

• \(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

zbMATH Keywords

random treeGalton-Watson tree\(k\)-cut number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

• Title not available (Why is that?)
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree
• Record process on the continuum random tree
• 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
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• 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
• Cutting resilient networks -- complete binary trees
• The cut metric, random graphs, and branching processes
• \(k\)-cut on paths and some trees
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson 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)