Uniform Temporal Trees

• Authors: Caelan Atamanchuk, Luc P Devroye and Gábor Lugosi
• Random Structures & Algorithms, Vol. 67, No. 4, December 2025

Motivated by the study of random temporal networks, we introduce a class of random trees that we coin uniform temporal trees. A uniform temporal tree is obtained by assigning independent uniform (Formula presented.) labels to the edges of a rooted complete infinite (Formula presented.) -ary tree and keeping only those vertices for which the path from the root to the vertex has decreasing edge labels. The (Formula presented.) -percolated uniform temporal tree, denoted by (Formula presented.), is obtained similarly, with the additional constraint that the edge labels on each path are all below (Formula presented.). We study several properties of these trees, including their size, height, the typical depth of a vertex, and degree distribution. In particular, we establish a limit law for the size of (Formula presented.) which states that (Formula presented.) converges in distribution to an (Formula presented.) random variable as (Formula presented.). For the height (Formula presented.), we prove that (Formula presented.) converges to (Formula presented.) in probability. Uniform temporal trees show some remarkable similarities to uniform random recursive trees.