The uncover process for random labeled trees

DOI10.1007/S44007-023-00060-3MaRDI QIDQ6140883zbMATH OpenFDO

Authors

Publication date 2 January 2024

Published in La Matematica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

phase transitionfunctional central limit theoremlimiting distributionlabeled treeuncover process

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Functional limit theorems; invariance principles (60F17) Combinatorial probability (60C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with $n$ vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this work: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.

Recommendations

• The continuum random tree. I
• The shape of unlabeled rooted random trees
• The profile of unlabeled trees
• On the maximum size of a tree in a random unlabelled unrooted forest
• The continuum random tree is the scaling limit of unlabeled unrooted trees

Cites work

• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• A geometric representation of fragmentation processes on stable trees
• Analytic combinatorics
• Coalescents with multiple collisions
• Cutting down random trees
• Cutting down trees with a Markov chainsaw
• Destruction of very simple trees
• Factorizations of some weighted spanning tree enumerators
• Higher dimensional quasi-power theorem and Berry-Esseen inequality
• Isolating a leaf in rooted trees via random cuttings
• On Ramanujan's Q-function
• Phase transition for Parking blocks, Brownian excursion and coalescence
• Probability theory. A comprehensive course
• Random Fragmentation and Coagulation Processes
• Random cutting and records in deterministic and random trees
• Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Spanning trees and function classes
• The coalescent
• The standard additive coalescent

Cited in

(2)

• An asymptotic analysis of labeled and unlabeled k-trees
• Pareto quantiles of unlabeled tree objects

This page was built for publication: The uncover process for random labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140883)