Uniform attachment with freezing: Scaling limits

2023/08/01 by Étienne Bellin, Bellin, Étienne, Arthur Blanc-Renaudie +5 · 2 citations
Mathematics · Physics and Astronomy · #60D05 60F05 #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2308.00484

openalex publication_date 2023/08/01 · openalex created_date 2023/08/19 · openalex updated_date 2026/07/28

Abstract

We investigate scaling limits of trees built by uniform attachment with freezing, which is a variant of the classical model of random recursive trees introduced in a companion paper. Here vertices are allowed to freeze, and arriving vertices cannot be attached to already frozen ones. We identify a phase transition when the number of non-frozen vertices roughly evolves as the total number of vertices to a given power. In particular, we observe a critical regime where the scaling limit is a random compact real tree, closely related to a time non-homogenous Kingman coalescent process identified by Aldous. Interestingly, in this critical regime, a condensation phenomenon can occur.

Cited by

• Does freezing impede the growth of random recursive trees?
• Preferential Attachment Trees with Vertex Death: Persistence of the Maximum Degree

Related

• Uniform attachment with freezing
• Does freezing impede the growth of random recursive trees?
• Scaling limit of trees with vertices of fixed degrees and heights
• Frozen percolation on the binary tree is nonendogenous
• Two-dimensional volume-frozen percolation: deconcentration and prevalence of mesoscopic clusters