The scaling limit of the minimum spanning tree of a complete graph. L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. Submitted (60 p), 2012. [±]

Consider the minimum spanning tree of the complete graph with $n$ vertices, when edges are assigned independent random weights. We show that, when this tree is endowed with the graph distance renormalized by $n^{1/3}$ and with the uniform measure on its vertices, the resulting space converges in distribution as $n\to\infty$ to a random limiting metric space in the Gromov--Hausdorff--Prokhorov topology. We show that this space is a random binary $\mathbb R$-tree and has Minkowski dimension $3$ almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the minimum spanning tree problem and the Erdös--Rényi random graph, and the explicit description of its scaling limit in the so-called critical window.

The dual tree of a recursive triangulation of the disk. N. Broutin and H. Sulzbach. Submitted (29 p), 2012. [arXiv:1211.1343] [±]

In the recursive lamination of the disk, one tries to add chords one after an other at random; a chord is kept and inserted if it does not intersect any of the previously inserted ones. Curien and Le Gall [Ann. Probab., vol. 39, pp. 2224--2270, 2011] have proved that the set of chords converges to a limit triangulation of the disk encoded by a continuous process $\mathscr M$. Based on a new approach resembling ideas from the so-called contraction method in function spaces, we prove that, when properly rescaled, the planar dual of the discrete lamination converges almost surely in the Gromov--Hausdorff sense to a limit real tree $\mathscr T$, which is encoded by $\mathscr M$. This is one of the first natural limit real trees which is identified and does not come from the excursion of a Lévy process.

Cutting down trees with a Markov chainsaw. L. Addario-Berry, N. Broutin and C. Holmgren. Submitted (23 pages), 2011. [arXiv:1110.6455] [±]

We provide simplified proofs for the asymptotic distribution of the number of cuts required to cut down a Galton--Watson tree with critical, finite-variance offspring distribution, conditioned to have total progeny $n$. Our proof is based on a coupling which yields a precise, non-asymptotic distributional result for the case of uniformly random rooted labeled trees (or, equivalently, Poisson Galton--Watson trees conditioned on their size). Our approach also provides a new, random reversible transformation between Brownian excursion and Brownian bridge.

A limit process for partial match queries in random quadtrees and 2-d trees. N. Broutin, R. Neininger, and H. Sulzbach. The Annals of Applied Probability, to appear (30 pages), 2012. [arXiv:1202.1342] [±]

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the classical model where the data consist of independent and uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the complexity, measured as the number of nodes $C_n(\xi)$ to visit in order to report the items matching a random query $\xi$, independent and uniformly distributed on $[0,1]$, satisfies $\mathbf E[C_n(\xi)]\sim \kappa n^{\beta}$, where $\kappa$ and $\beta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(s)$ of any fixed query $s\in [0,1]$, and give precise estimates for the variance and limit distribution. Moreover, a functional limit law for a rescaled version of the process $(C_n(s))_{0\le s\le 1}$ is derived in the space of cadlag functions with the Skorokhod topology. For the worst case complexity $\max_{s\in [0,1]} C_n(s)$ the order of the expectation as well as a limit law are given.

Connectivity threshold for Bluetooth graphs. N. Broutin, L. Devroye, N. Fraiman and G. Lugosi. Random Structures and Algorithms, to appear (21 pages), 2011. [arXiv:1103.0351] [±]

We study the connectivity properties of random Bluetooth graphs that model certain ``ad hoc'' wireless networks. The graphs are obtained as ``irrigation subgraphs'' of the well-known random geometric graph model. There are two parameters that control the model: the radius $r$ that determines the ``visible neighbors'' of each node and the number of edges $c$ that each node is allowed to send to these. The randomness comes from the underlying distribution of data points in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters $r, c$ and completely characterize the connectivity threshold (in $c$) for values of $r$ close the critical value for connectivity in the underlying random geometric graph.

Asymptotics of trees with a prescribed degree sequence. N. Broutin and J.-F. Marckert. Random Structures and Algorithms, to appear (26 pages), 2012. [arxiv:1110.5203] [±]

Let $t$ be a rooted tree and $n_i(t)$ the number of nodes in $t$ having $i$ children. The degree sequence $(n_i(t),i\geq 0)$ of $t$ satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0} in_i(t)=|t| $, where $|t|$ denotes the number of nodes in $t$. In this paper, we consider trees sampled uniformly among all trees having the same degree sequence $\mathbf s$; we write $\mathbb P_{\bf s}$ for the corresponding distribution. Let $\mathbf s(\kappa)=(n_i(\kappa),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size ${\sf n}_\kappa\to+\infty$. We show that under some simple and natural hypotheses on $(\mathbf s(\kappa),\kappa>0)$ the trees sampled under $\mathbb P_{\mathbf s(\kappa)}$ converge to the Brownian continuum random tree after normalisation by $\sqrt{{\sf n}_\kappa}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.

Longest path distance in random circuits. N. Broutin and O. Fawzi. Combinatorics, Probability and Computing, vol. 21, pp. 856--881, 2012. [arXiv:1101.5547] [±]

We study distance properties of a general class of random directed acyclic graphs (DAGs). In a DAG, many natural notions of distance are possible, for there exists multiple paths between pairs of nodes. The distance of interest for circuits is the maximum length of a path between two nodes. We give laws of large numbers for the typical depth (distance to the root) and the minimum depth in a random DAG. This completes the study of natural distances in random DAGs initiated (in the uniform case) by Devroye and Janson (2009+). We also obtain large deviation bounds for the minimum of a branching random walk with constant branching, which can be seen as a simplified version of our main result.

The distribution of height and diameter in random non-plane binary trees. N. Broutin and P. Flajolet. Random Structures and Algorithms, vol. 41, pp. 215--252, 2012. [arXiv:1009.1515] [±]

This study is dedicated to precise distributional analyses of the height of non-plane unlabelled binary trees (``Otter trees''), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size $n$ is proved to admit a limiting theta distribution, both in a central and local sense, as well as obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height.

The total path length of split trees. N. Broutin and C. Holmgren. The Annals of Applied Probability, vol. 22, pp. 1745--1777, 2012. [arXiv:1102.2541] [±]

We consider the model of random trees introduced by Devroye [SIAM J Comput 28, 409--432, 1998]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length towards a distribution characterized uniquely by a fixed point equation. Our result covers using a unified approach many data structures such as binary search trees, $m$-ary search trees, quad trees, median-of-$(2k+1)$ trees, and simplex trees.

The continuum limit of critical random graphs. L. Addario-Berry, N. Broutin and C. Goldschmidt. Probability Theory and Related Fields, vol. 152, pp.367--406, 2012. [arXiv:0903.4730] [±]

We consider the Erdos--Rényi random graph $G(n,p)$ inside the critical window, that is when $p=1/n+\lambda n^{-4/3}$, for some fixed $\lambda\in \mathbb R$. We prove that the sequence of connected components of $G(n,p)$, considered as metric spaces using the graph distance rescaled by $n^{-1/3}$, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of $G(n,p)$ rescaled by $n^{-1/3}$ converges in distribution to an absolutely continuous random variable with finite mean.

Total progeny in killed branching random walk. L. Addario-Berry and N. Broutin. Probability Theory and Related Fields, vol. 151, pp. 265--295, 2011. [arXiv:0908.1083] [±]

We consider a branching random walk for which the maximum position of a particle in the $n$'th generation, $M_n$, has zero speed on the linear scale: $M_n/n \to 0$ as $n\to\infty$. We further remove (``kill'') any particle whose displacement is negative, together with its entire descendence. The size $Z$ of the set of un-killed particles is almost surely finite. In this paper, we confirm a conjecture of Aldous that $\mathbf E[Z]<\infty$ while $\mathbf E [Z\log Z]=\infty$. The proofs rely on precise large deviations estimates and ballot theorem-style results for the sample paths of random walks.

On combinatorial testing problems. L. Addario-Berry, N. Broutin, L. Devroye and G. Lugosi, The Annals of Statistics, vol. 38, pp. 3063--3092, 2010. [arXiv:0908.3437] [±]

We study a class of hypothesis testing problems in which, upon observing the realization of an $n$-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been ``contaminated,'' that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.

Critical random graphs: limiting constructions and distributional properties. L. Addario-Berry, N. Broutin and C. Goldschmidt. Electronic Journal of Probability, vol. 15, pp. 741--775, 2010. [arXiv:0903.4730] [±]

We consider the Erdos--Rényi random graph $G(n,p)$ inside the critical window, where $p=1/n+\lambda n^{-4/3}$ for some $\lambda\in \mathbb R$. We proved that considering the connected components of $G(n,p)$ as a sequence of metric spaces with the graph distance rescaled by $n^{-1/3}$ and letting $n \to \infty$ yields a non-trivial sequence of limit metric spaces $\mathcal C=(\mathcal C_1, \mathcal C_2, \dots)$. These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous' Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on $\mathbb R_+$. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Luczak, Pittel and Wierman (1995) by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component.

Note on the structure of Kruskal's algorithm. N. Broutin, L. Devroye, and E. McLeish. Algorithmica, vol. 56, pp 141--159, 2010. [±]

We study the merging process when Kruskal's algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on $n$ vertices lying in $[0,1]^d$, and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be $\Theta(n)$ on average. On the way to the proof, we obtain similar results for the complete graph and the $d$-dimensional square lattice with i.i.d. edge weights.

The longest minimum weight path in a complete graph. L. Addario-Berry, N. Broutin and G. Lugosi. Combinatorics, Probability and Computing, vol. 19, pp. 1--19, 2010. [arXiv:0809.0275] [±]

We consider the minimum-weight path between any pair of nodes of the $n$-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about $\alpha^\star \log n$ edges where $\alpha^\star\approx 3.5911$ is the unique solution of the equation $\alpha \log \alpha - \alpha =1$. This answers a question left open by Janson.

Effective resistance of random trees. L. Addario-Berry, N. Broutin and G. Lugosi. The Annals of Applied Probability, vol. 19, p. 1092--1107, 2009. [arXiv:0801.1909] [±]

We investigate the effective resistance $R_n$ and conductance $C_n$ between the root and leaves a binary tree of height $n$. In this electrical network, the resistance of each edge $e$ at distance $d$ from the root is defined by $r_e=2^d X_e$ where the $X_e$ are i.i.d. positive random variables bounded away from zero and infinity. It is shown that $\mathbf E[R_n] = n\mathbf E [X_e] - (\mathbf{Var}(X_e)/\mathbf E [X_e])\ln n + O(1)$ and $\mathbf{Var}(R_n)=O(1)$. Moreover, we %prove that all higher moments of $R_n$ are bounded and establish sub-Gaussian tail bounds for $R_n$. We also discuss some possibles extensions to supercritical Galton--Watson trees.

Critical random graphs and the structure of a minimum spanning tree. L. Addario-Berry, N. Broutin and B. Reed. Random Structures and Algorithms, vol. 35, p. 323-347, 2009. [±]

We consider the complete graph on $n$ vertices whose edges are weighted by independent and identically distributed edge weights and build the associated minimum weight spanning tree. We show that if the random weights are all distinct, then the expected diameter of such a tree is $\Theta(n^{1/3})$. This settles a question of Frieze and McDiarmid (1997). The proofs are based on a precise analysis of the behaviour of random graphs around the critical point.

The height of increasing trees. N. Broutin, L. Devroye, E. McLeish, and M. de la Salle. Random Structures and Algorithms, vol. 32, p.494--518, 2008. [±]

We extend results about heights of random trees by Devroye. In this paper, a general split tree model is considered in which the normalized subtree sizes of nodes converge in distribution. The height of these trees is shown to be in probability asymptotic to $c\log n$ for some constant $c$. We apply our results to obtain a law of large numbers for the height of all polynomial varieties of increasing trees.

Weighted height of random trees. N. Broutin, L. Devroye and E. McLeish. Acta Informatica, vol. 45, pp. 237--277, 2008. [±]

We consider a model of random trees similar to the split trees of Devroye (1997) in which a set of items is recursively partitioned. Our model allows for more flexibility in the choice of the partitioning procedure, and has weighted edges. We prove that for this model, the height $H_n$ of a random tree is asymptotic to $c\log n$ in probability for a constant $c$ that is uniquely characterized in terms of multivariate large deviations rate functions. This extension permits us to obtain the height of pebbled tries, pebbled ternary search tries, $d$-ary pyramids, and to study geometric properties of partitions generated by $k$-d trees. The model also includes all polynomial families of increasing trees recently studied by Broutin, Devroye, McLeish and de la Salle.

An analysis of the height of tries with random weights on the edges. N. Broutin and L. Devroye. Combinatorics, Probability and Computing, vol. 17, pp. 161--202, 2007. [±]

We analyze the weighted height of random tries built from independent strings of i.i.d. symbols on the finite alphabet $\{ 1,\ldots,d\}$. The edges receive random weights whose distribution depends upon the number of strings that visit that edge. Such a model covers the hybrid tries of de la Briandais (1959) and the TST of Bentley and Sedgewick (1997), where the search time for a string can be decomposed as a sum of processing times for each symbol in the string. Our weighted trie model also permits one to study maximal path imbalance. In all cases, the weighted height is shown be asymptotic to $c \log n$ in probability, where $c$ is determined by the behavior of the core of the trie (the part where all nodes have a full set of children) and the fringe of the trie (the part of the trie where nodes have only one child and form spaghetti-like trees). It can be found by maximizing a function that is related to the Cramér exponent of the distribution of the edge weights.

Large deviations for the weighted height of an extended class of trees. N. Broutin, and L. Devroye. Algorithmica, vol. 46, p. 271--297, 2006. [±]

We use large deviations to prove a general theorem on the asymptotic edge-weighted height $H_n^\star$ of a large class of random trees for which $H_n^\star\sim c\log n$ for some positive constant $c$. A graphical interpretation is also given for the limit constant $c$. This unifies what was already known for binary search trees [Devroye, 1986, 1988], random recursive trees [Devroye, 1987] and plane oriented trees [Pittel, 1994] for instance. New applications include the heights of some random lopsided trees [Kappoor and Reingold, 1989] and of the intersection of random trees.

Partial match queries in random quadtrees. N. Broutin, R. Neininger, and H. Sulzbach. Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1056--1065, 2012. [arXiv:1107.2231] [±]

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the data consist of uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the number of nodes $C_n(\xi)$ to visit in order to report the items matching an independent and uniformly on $[0,1]$ random query $\xi$ satisfies $E[C_n(\xi)]\sim \kappa n^{\beta}$, where $\kappa$ and $\beta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(x)$ of any fixed query $x\in [0,1]$, and give precise estimates for the variance and limit distribution of the cost $C_n(x)$. Our results permit to describe a limit process for the costs $C_n(x)$ as $x$ varies in $[0,1]$; one of the consequences is that ${\bf E}{\max_{x\in [0,1]} C_n(x)} \sim \gamma n^\beta$ ; this settles a question of Devroye.

The height of random binary unlabelled trees. N. Broutin and P. Flajolet. Fifth Colloquium on Mathematics and Computer Science, Discrete Mathematics and Computer Science Proc., vol. AI, pp. 121--134, 2008. [arXiv:0807.2365] [±]

This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.

The height of list-tries and TST. N. Broutin and L. Devroye. International Conference on Analysis of Algorithms, Discrete Mathematics and Computer Science Proc, vol. AH, pp. 271--282, 2007. [±]

We characterize the asymptotics of heights of the trees of de la Briandais [1959] and the ternary search trees (TST) of Bentley and Sedgewick [1997]. Our proof is based on a new analysis of the structure of tries that distinguishes the bulk of the tree, called the core, and the long trees hanging down the core, called the spaghetti.

The diameter of the minimum spanning tree of a complete graph. L. Addario-Berry, N. Broutin, and B. Reed. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees Combinatorics and Probability, Discrete Mathematics and Computer Science Proc., vol. AG, pp. 237--240, 2006. [±]

Let $\{X_1,\ldots,X_m\}$, $m={n\choose 2}$, be independent identically distributed weights for the edges of $K_n$. If $X_i \neq X_j$ for $i \neq j$, then there exists a unique minimum weight spanning tree $T$ of $K_n$ with these edge weights. We show that the expected diameter of $T$ is $\Theta(n^{1/3})$. This settles a question of Frieze and McDiarmid (1997).

Cutting down random trees with a Markov chainsaw YEP VII, Eurandom, Mar. 2010.

La limite d'échelle des graphes aléatoires critiques. Journées ALEA, Luminy, Mar. 2009

The structure of digital trees. Combinatorics Seminar, Oxford, Sept. 2008.

Faire la lumiere sur les arbres digitaux. Journées ALEA, Luminy, Mar. 2007.

The diameter of the minimum spanning tree of a complete graph. Fourth Colloquium on Trees, Combinatorics and Probability, Nancy, Sept. 2006.

Trees, graphs and recursive partitions. HDR Submitted, Paris 6, 2012.

Shedding New Light on Random Trees. PhD Thesis, McGill University, 2007.

Sélection optimale d'oligonucléotides et graphes Mémoire de DEA, ENST Bretagne et Université de Bretagne Sud, 2003.

Étude probabiliste du problème du voyageur de commerce euclidien en dimension 2. Mémoire de fin d'étude, École Polytechnique, 2001.