The uncover process for random labeled trees

DOI10.1007/S44007-023-00060-3zbMATH Open1529.05140arXiv2301.00664MaRDI QIDQ6140883FDOQ6140883

Authors:

Publication date: 2 January 2024

Published in: La Matematica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)