Does freezing impede the growth of random recursive trees

Anna Brandenberger, Simon Briend, Hannah Cairns, Igor Kortchemski · 2025

Read Does freezing impede the growth of random recursive trees by Anna Brandenberger, Simon Briend, Hannah Cairns, Igor Kortchemski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16571.txt.

Introduction

Anna Brandenberger and co-authors study random growing trees that can freeze in a 2025 paper. A random recursive tree grows by attaching each new node to a random older one. In the freezing version, nodes can lock, after which nothing new may attach to them. The question is how such rules affect the tree's height, a key measure of its shape.

Results run against first intuition. Removing an attachment step can, on average, make the tree taller. Freezing, meanwhile, cannot drag the height down by much. The proofs rest on coupling arguments, which compare two growth processes side by side and track how they diverge. The work sits in probability theory, but its processes echo network growth models where members go inactive over time.

Catalog record

CREATORAnna Brandenberger, Simon Briend, Hannah Cairns, Igor Kortchemski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16571

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Does freezing impede the growth of random recursive trees? Thanks: Department of Mathematics and Statistics, McGill University, [email protected] Anna Brandenberger, Simon Briend, Hannah Cairns, Igor Kortchemski Abstract Uniform attachment with freezing is an extension of the classical model of random recursive trees, in which trees are recursively built by attaching new vertices to old ones. In the model of uniform attachment with freezing, vertices are allowed to freeze, in the sense that new vertices cannot be attached to already frozen ones. We study the impact of removing attachment and/or freezing steps on the height of the trees. We show in particular that removing an attachment step can increase the expected height, and that freezing cannot substantially decrease the height of random recursive trees. Our methods are based on coupling arguments. \useosf 1 Introduction We are interested in the height of random recursive trees built using uniform attachment with freezing, which is a model recently introduced by Bellin et al. [2] . The motivation of the model stems from contact tracing in SIR epidemic models. More generally, the impact of freezing on dynamically-built random graph models is a natural mathematical question. The work of Bellin et al. [3] studies scaling limits in the specific regime where the number of non-frozen vertices roughly evolves as the total number of vertices to a given power. Based on results of Bellin et al. [2] , Kammerer et al. [7] completes the study of the height of the infection tree of a SIR epidemic on the complete graph using uniform attachment with freezing. This model is defined as follows. Given a choice sequence \mathrm{\mathbf{x}}=(\mathrm{x}_{i})_{1\leq i\leq m}\in\{-1,+1\}^{m} , we set S_{0}(\mathrm{\mathbf{x}})\coloneqq 1 and for every j\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m\mathclose{\rrbracket} , let S_{j}(\mathrm{\mathbf{x}})\coloneqq 1+\sum_{i=1}^{j}\mathrm{x}_{i}\,;\quad\text{ and }\quad\tau(\mathrm{\mathbf{x}})\coloneqq\min\{j\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m\mathclose{\rrbracket}:S_{j}(\mathrm{\mathbf{x}})=0\} (1.1) with the convention \min\varnothing=\infty . Starting from a unique active vertex, defined to be the root, we recursively build random rooted trees by reading the elements of the sequence one after the other, by applying a “uniform freezing” step when reading -1 (which amounts to freezing an active vertex chosen uniformly at random) and a “uniform attachment” step when reading +1 (which amounts to attaching a new vertex to an active vertex chosen uniformly at random). Note that \tau(\mathrm{\mathbf{x}}) , if finite, represents the first time at which all vertices in the tree are frozen. For every j\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m\mathclose{\rrbracket} we denote by \mathcal{T}_{j}(\mathrm{\mathbf{x}}) the random rooted tree built in this fashion after reading the first j elements of \mathrm{\mathbf{x}} (see Section 2.1 for a precise definition) and let \mathcal{T}(\mathrm{\mathbf{x}})=\mathcal{T}_{m}(\mathrm{\mathbf{x}}) be the last tree. We denote by \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) the height of \mathcal{T}(\mathrm{\mathbf{x}}) and \mathsf{h}(v) the height of a vertex v\in\mathcal{T}(\mathrm{\mathbf{x}}) . Finally, we define \mathbb{X}_{n}=\bigcup_{m\geq n}\{\mathrm{\mathbf{x}}=(\mathrm{x}_{i})_{1\leq i\leq m}\in\{-1,+1\}^{m}:\#\{i\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m\mathclose{\rrbracket}:\mathrm{x}_{i}=+1\}=n\textrm{ and }\tau(\mathrm{\mathbf{x}})\geq m\}, so that trees of the form \mathcal{T}(\mathrm{\mathbf{x}}) with \mathrm{\mathbf{x}}\in\mathbb{X}_{n} are all possible n -edge trees built by uniform attachment with freezing. To simplify notation, we write (+1)^{m}=(+1,+1,\ldots,+1) where +1 appears m times and similarly define (-1)^{m} . Also, we write \mathrm{\mathbf{x}}\mathrm{\mathbf{y}} for the concatenation of \mathrm{\mathbf{x}} and \mathrm{\mathbf{y}} . In this note, we address a question of Bellin et al. [2] on whether \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) always stochastically dominates the height of the uniform attachment tree, also known as the random recursive tree. Our main result ( Theorem 1.2 below) states that, roughly speaking, the asymptotic order of magnitude of \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) for any \mathrm{\mathbf{x}}\in\mathbb{X}_{n} is at least e\log(n) with high probability, which is the order of magnitude of the height of a random recursive tree \mathcal{R}_{n} with n edges. This can informally be rephrased by saying that freezing random trees doesn’t asymptotically shrink them. At first glance this may seem quite obvious in light of the results of Bellin et al. [3] : there it is shown (under some technical assumptions) that if the number of active vertices evolves as n^{\alpha} , where n is the total number of vertices and \alpha\in(0,1) , then the height of the tree is of order n^{1-\alpha} , thus indicating that adding more freezing tends to increase the height. However this is specific to this regime, and not true in general. Indeed, it is not true that the height of random recursive tree with n edges is stochastically dominated by \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) for any \mathrm{\mathbf{x}}\in\mathbb{X}_{n} (see Section 2.2 ). More generally, there is no obvious coupling that would exhibit a stochastic ordering when modifying the choice sequence. Indeed, the expected height of the tree can increase under both removal of a freezing step or removal of an attachment step, as emphasized in the following result. Proposition 1.1 . The following assertions hold. (i) Removing a freezing step immediately followed by an attachment step can increase the expected height of the tree. More precisely, for every A>0 , there exist n,m\in\mathbb{N} such that for \mathrm{\mathbf{x}}=(+1)^{m}(-1)^{m-1}(-1,+1)(+1)^{n}\qquad\textrm{and}\qquad\hat{\mathrm{\mathbf{x}}}=(+1)^{m}(-1)^{m-1}(+1)^{n}, (1.2) we have \mathbb{E}\left[\mathsf{H}(\mathcal{T}(\hat{\mathrm{\mathbf{x}}}))\right]\geq\mathbb{E}\left[\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\right]+A . In particular, if \bar{\mathrm{\mathbf{x}}}=(+1)^{m}(-1)^{m-1}(+1)^{n+1} then we have \mathbb{E}\left[\mathsf{H}(\mathcal{T}(\bar{\mathrm{\mathbf{x}}}))\right]\geq\mathbb{E}\left[\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\right]+A , so removing a freezing step can increase the expected height of the tree. (ii) Removing an attachment step immediately followed by a freezing step can increase the expected height of the tree. More precisely, for every A>0 , there exist n,m\in\mathbb{N} such that for \mathrm{\mathbf{x}}=(+1)^{m}(-1)^{m-1}(+1,-1)(+1)^{n}\qquad\textrm{and}\qquad\hat{\mathrm{\mathbf{x}}}=(+1)^{m}(-1)^{m-1}(+1)^{n}, (1.3) we have \mathbb{E}\left[\mathsf{H}(\mathcal{T}(\hat{\mathrm{\mathbf{x}}}))\right]\geq\mathbb{E}\left[\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\right]+A . (iii) Removing an attachment step can increase the expected height of the tree. More precisely, there exists n\in\mathbb{N} such that for \mathrm{\mathbf{x}}=(+1,+1,-1)(+1)^{n}\qquad\textrm{and}\qquad\hat{\mathrm{\mathbf{x}}}=(+1,-1)(+1)^{n}, (1.4) we have \mathbb{E}\left[\mathsf{H}(\mathcal{T}(\hat{\mathrm{\mathbf{x}}}))\right]>\mathbb{E}\left[\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\right] . Despite the lack of stochastic domination under the above two natural operations on the choice sequence, we are able to show that for any \mathrm{\mathbf{x}}\in\mathbb{X}^{n} , \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) is asymptotically at least of the same order as \mathsf{H}(\mathcal{R}_{n}) , so that adding freezing cannot substantially decrease the height of random recursive trees. For random recursive trees, it is well known (see Addario-Berry and Ford [1, Corollary 1.3] and Pain and Sénizergues [9, Eq. (1.3)] ) that as n\rightarrow\infty , \mathsf{H}(\mathcal{R}_{n})=e\log n-\frac{3}{2}\log\log n+O_{\mathbb{P}}(1),\qquad\mathbb{E}\left[\mathsf{H}(\mathcal{R}_{n})\right]=e\log n-\frac{3}{2}\log\log n+O(1). (1.5) The following statement formalizes our claim that the asymptotic lower bound for \mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})) matches \mathsf{H}(\mathcal{R}_{n}) to leading order. Theorem 1.2 . We have \min_{\mathrm{\mathbf{x}}\in\mathbb{X}_{n}}\mathbb{P}\left(\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\geq e\log(n)-5\log\log n\right)\rightarrow 1. as n\to\infty . Also, for every n sufficiently large, \min_{\mathrm{\mathbf{x}}\in\mathbb{X}_{n}}\mathbb{E}\left[\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}}))\right]\geq e\log n-5\log\log n. The key to proving the result is the following. Recall that the random recursive tree with n edges corresponds to the sequence \mathrm{\mathbf{x}}=(+1)^{n} without any freezing steps, so we can write \mathcal{R}_{n}=\mathcal{T}((+1)^{n}) . We make use of the following coupling which does stochastically decrease the height of the tree. Theorem 1.3 . Let \mathrm{\mathbf{x}}=(\mathrm{x}_{i})_{1\leq i\leq m}\in\{-1,+1\}^{m} such that S_{j}(\mathrm{\mathbf{x}})>0 for every j\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m-1\mathclose{\rrbracket} . Suppose there exists k\in\mathopen{\llbracket}1\mathclose{}\mathpunct{},m-1\mathclose{\rrbracket} such that \mathrm{x}_{1}=\mathrm{x}_{2}=\cdots=\mathrm{x}_{k}=+1 and \mathrm{x}_{k+1}=-1 . Let \hat{\mathrm{\mathbf{x}}}=(\mathrm{x}_{1},\dots,\mathrm{x}_{k-1},\mathrm{x}_{k+2},\dots,\mathrm{x}_{m}) be the sequence obtained from \mathrm{\mathbf{x}} by removing \mathrm{x}_{k} and \mathrm{x}_{k+1} . Then \mathsf{H}(\mathcal{T}(\hat{\mathrm{\mathbf{x}}}))\preceq_{\mathrm{st}}\mathsf{H}(\mathcal{T}(\mathrm{\mathbf{x}})). We establish this stochastic domination via a coupling between the construction of the two random trees, which is relatively general and may be of independent interest. Using it recursively allows us to compare the heights of a tree with freezing and of a random recursive tree. The proof of Theorem 1.3 is based on an alternative construction of uniform attachment trees with freezing of Bellin et al. [2] , based on time-reversal, through a growth-coalescent process of rooted forests. Outline. Section 2 studies the influence of local modifications of certain choice sequences on the height, and proves Proposition 1.1 . In Section 3 , we first show that removing the first attachment step

Read the complete text