Tight universal bounds on the height times the width of random trees
We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size n, this product is O( n log(n) ) in probability, answering a question by Addario-Berry (2019). The order of this bound is tight in this generality.
Optimal root recovery for uniform attachment trees and d-regular growing trees.
We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy ε > 0, such an algorithm outputs a set of nodes that contains the root with probability at least 1 - ε. We prove that, for the optimal algorithm, an output set of size exp(O( log¹⸍²(1/ε) )) suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017).
Refined Horton-Strahler numbers I: a discrete bijection
The Horton-Strahler number of a rooted tree T is the height of the tallest complete binary tree that can be homeomorphically embedded in T. The number of full binary trees with n internal vertices and Horton-Strahler number s is known to be the same as the number of Dyck paths of length 2n whose height h satisfies ⌊log₂(1 + h)⌋ = s.
In this paper, we present a new bijective proof of the above result, that in fact strengthens and refines it as follows. We introduce a sequence of trees (τⱼ , j ≥ 0) which "interpolates" the complete binary trees, in the sense that τ₂ʰ₋₁ is the complete binary tree of height h for all h ≥ 0, and τⱼ₊₁ strictly contains τⱼ for all j ≥ 0. Defining 𝒮 (T) to be the largest j for which τⱼ can be homeomorphically embedded in T, we then show that the number of full binary trees T with n internal vertices and with 𝒮 (T) = h is the same as the number of Dyck paths of length 2n with height h. (We call 𝒮 (T) the refined Horton-Strahler number of T.)
Our proof is bijective and relies on a recursive decomposition of binary trees (resp. Dyck paths) into subtrees with strictly smaller refined Horton-Strahler number (resp. subpaths with strictly smaller height). In a subsequent paper, we will show that the bijection has a continuum analogue, which transforms a Brownian continuum random tree into a Brownian excursion and under which (a continuous analogue of) the refined Horton-Strahler number of the tree becomes the height of the excursion.
Fluctuations of the Horton-Strahler number of stable Galton-Watson trees
The Horton-Strahler number, also called the register function, is a combinatorial tool that quantifies the branching complexity of a rooted tree. We study the law of the Horton-Strahler number of stable Galton-Watson trees conditioned to have size n, including the Catalan trees. While these random variables are known to grow as a multiple of log(n) in probability, their fluctuations are not well understood because they are coupled with deterministic oscillations. To rule out the latter, we introduce a real-valued variant of the Horton-Strahler number. We show that a rescaled exponential of this quantity jointly converges in distribution to a measurable function of the scaling limit of the trees, i.e. the stable Lévy tree. We call this limit the Strahler dilation and we discuss its similarities with the Horton-Strahler number.
The Horton-Strahler number of Galton-Watson trees with possibly infinite variance
The Horton-Strahler number, also known as the register function, provides a tool for quantifying the branching complexity of a rooted tree. We consider the Horton-Strahler number of critical Galton-Watson trees conditioned to have size n and whose offspring distribution is in the domain of attraction of an α-stable law with α ∈ [1,2]. We give tail estimates and when α > 1, we prove that it grows as a multiple of log(n) in probability. This extends the result in Brandenberger, Devroye & Reddad dealing with the finite variance case for which α = 2. We also characterize the cases where α = 1, namely the spectrally positive Cauchy regime, which exhibits more complex behaviors.
Convergences of looptrees coded by excursions
In order to study convergences of looptrees, we construct continuum trees and looptrees from real-valued càdlàg functions without negative jumps called excursions. We then provide a toolbox to manipulate the two resulting codings of metric spaces by excursions and we formalize the principle that jumps correspond to loops and that continuous growths correspond to branches. Combining these codings creates new metric spaces from excursions that we call vernation trees. They consist of a collection of loops and trees glued along a tree structure so that they unify trees and looptrees. We also propose a topological definition for vernation trees, which yields what we argue to be the right space to study convergences of looptrees. However, those first codings lack some functional continuity, so we adjust them. We thus obtain several limit theorems. Finally, we present some probabilistic applications, such as proving an invariance principle for random discrete looptrees.
Study of a division-like property
We introduce a weak division-like property for noncommutative rings: a nontrivial ring is fadelian if for all nonzero a, x there exist b, c such that x = ab + ca. We prove properties of fadelian rings, and construct examples of such rings which are not division rings, as well as non-Noetherian and non-Ore examples. Some of these results are formalized using the Lean proof assistant.
Scaling limits of tree-valued branching random walks
We consider a branching random walk (BRW) taking its values in the k-ary rooted tree 𝕎ₖ (i.e. the set of finite words written in the alphabet {1, …, k}, with k ≥ 2). The BRW is indexed by a critical Galton-Watson tree conditioned to have n vertices; its offspring distribution is aperiodic and is in the domain of attraction of a γ-stable law, γ ∈ (1,2]. The jumps of the BRW are those of a nearest-neighbour null-recurrent random walk on 𝕎ₖ (reflection at the root of 𝕎ₖ and otherwise: probability 1/2 to move closer to the root of 𝕎ₖ and probability 1/(2k) to move away from it to one of the k sites above). We denote by ℛₖ(n) the range of the BRW in 𝕎ₖ which is the set of all sites in 𝕎ₖ visited by the BRW. We first prove a law of large numbers for #ℛₖ(n) and we also prove that if we equip ℛₖ(n) (which is a random subtree of 𝕎ₖ) with its graph-distance d, then there exists a scaling sequence (aₙ , n ∈ ℕ) satisfying aₙ → ∞ such that the metric space (ℛₖ(n) , aₙ⁻¹d), equipped with its normalised empirical measure, converges to the reflected Brownian cactus with γ-stable branching mechanism: namely, a random compact real tree that is a variant of the Brownian cactus introduced by N. Curien, J-F. Le Gall and G. Miermont.
Time and place of the maximum for one-dimensional diffusion bridges and meanders
For three constrained Brownian motions, the excursion, the meander, and the reflected bridge, the densities of the maximum and of the time to reach it were expressed as double series by Majumdar, Randon-Furling, Kearney, and Yor (2008). Some of these series were regularized by Abel summation. Similar results for Bessel processes were obtained by Schehr and Le Doussal (2010) using the real space renormalization group method. Here this work is reviewed, and extended from the point of view of one-dimensional diffusion theory to some other diffusion processes including skew Brownian bridges and generalized Bessel meanders. We discuss the limits of the application of this method for other diffusion processes.
In this thesis, we study discrete random branching phenomena and seek to relate them to continuum fractal metric structures. Galton-Watson trees, which describe the genealogical history of an asexual population whose individuals reproduce under the same law and independently of each other, are our main model. In the first part, we focus on the study of a random walk (said critical biased) on an infinite tree (called the environment) and indexed by a critical Galton-Watson tree conditioned to be large (called the genealogy). The offspring distribution of the genealogy is assumed to be in the domain of attraction of a stable law of index α ∈ (1, 2]. We both consider the case where the environment is a regular rooted tree and the case where it is a supercritical Galton-Watson tree modified to have an infinite depth. Under some hypothesis of moments for the environment, we show that the number of points visited by the random walk grows linearly, and at a deterministic speed, with respect to the size of the genealogy when the latter tends to infinity. Furthermore, we prove that the subtree of points visited by the branching random walk admits a scaling limit. Previously introduced in the context of the study of random planar maps, this limit metric space is the (reflected) Brownian cactus with α-stable branching mechanism. Comparison of this new study with earlier work about random walks indexed by a linear time or taking values in a Euclidean lattice illustrates the influence of the branching nature of the genealogy and the environment. In the second part, we study the branching complexity of Galton-Watson trees by considering their Horton-Strahler numbers. This combinatorial tool, also known as the register function, was originally introduced in hydrogeology but was subsequently rediscovered and applied by many other scientific disciplines. Here, we give a deterministic asymptotic equivalent of the Horton- Strahler number of a size-conditioned critical Galton-Watson tree whose offspring distribution is in the domain of attraction of a stable law of index α ∈ [1, 2]. This estimate depends only on α when α > 1, but the α = 1 cases are model-dependent and subject to more complex behaviors. We then examine the fluctuations of the Horton-Strahler number for the specific family of stable Galton-Watson trees, which contains the binary critical Galton-Watson tree. To do so, we introduce a continuous variant of the Horton-Strahler number that converges after recentering towards a metric characteristic of the scaling limit of the trees. We study the properties of this new quantity, which acts as a continuum analog of the Horton-Strahler number.