#### Submitted preprints

Recursive functions on conditional Galton--Watson trees. N. Broutin, L. Devroye, and N. Fraiman. Submitted (14 p.), 2018. [±]

A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element $U$. The value of the root is the key quantity of interest in general. In this first study, all node values and function values are in a finite set $S$. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on $S$, and the tree $T_n$ is a random Galton--Watson tree of size $n$.

Limits of multiplicative inhomogeneous random graphs and Lévy trees. N. Broutin, T. Duquesne and M. Wang. Submitted (101 p.), 2018. [±]

We consider a natural model of inhomogeneous random graphs that extends the classical Erdös--Rényi graphs and shares a close connection with the multiplicative coalescence, as pointed out by Aldous [Ann. Probab., vol. 25, pp. 812--854, 1997]. In this model, the vertices are assigned weights that govern their tendency to form edges. It is by looking at the asymptotic distributions of the masses (sum of the weights) of the connected components of these graphs that Aldous and Limic [Electron. J. Probab., vol. 3, pp. 1--59, 1998] have identified the entrance boundary of the multiplicative coalescence, which is intimately related to the excursion lengths of certain Lévy-type processes. We, instead, look at the metric structure of these components and prove their Gromov--Hausdorff--Prokhorov convergence to a class of (random) compact measured metric spaces. Our asymptotic regimes relate directly to the general convergence condition appearing in the work of Aldous and Limic. Our techniques provide a unified approach for this general critical'' regime, and relies upon two key ingredients: an encoding of the graph by some Lévy process as well as an embedding of its connected components into Galton--Watson forests. This embedding transfers asymptotically into an embedding of the limit objects into a forest of Lévy trees, which allows us to give an explicit construction of the limit objects from the excursions of the Lévy-type process. As a consequence of our construction, we give a transparent and explicit condition for the compactness of the limit objects and determine their fractal dimensions. These results extend and complement several previous results that had obtained via model- or regime-specific proofs, for instance: the case of Erdos-Renyi random graphs obtained by Addario-Berry, Goldschmidt and B. [Probab. Theory Rel. Fields, vol. 153, pp. 367--406, 2012], the asymptotic homogeneous case as studied by Bhamidi, Sen and Wang [Probab Theory Rel. Fields, vol. 169, pp. 565--641, 2017], or the power-law case as considered by Bhamidi, Sen and van der Hofstad [Probab. Theory Rel. Fields, vol. 170, pp. 387--474, 2018].

A limit field for orthogonal range searches in two-dimensional random point search trees. N. Broutin and H. Sulzbach. Submitted (22 p.), 2017. [±]

We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an old question of Chanzy, Devroye and Zamora-Cura [\emph{Acta Inf.}, 37:355--383, 2000].

The combinatorics of the colliding bullets problem. N. Broutin and J.-F. Marckert. Submitted (27 p.), 2017. [±]

The finite colliding bullets problem is the following simple problem: consider a gun, whose barrel remains in a fixed direction; let $(V_i)_{1\le i\le n}$ be an i.i.d. family of random variables with uniform distribution on $[0,1]$; shoot $n$ bullets one after another at times $1,2,\dots, n$, where the $i$th bullet has speed $V_i$. When two bullets collide, they both annihilate. We give the distribution of the number of surviving bullets, and in some generalisation of this model. While the distribution is relatively simple (and we found a number of bold claims online), our proof is surprisingly intricate; we argue that any rigorous argument must very likely be rather elaborate.

Self-similar real trees defined as fixed-points and their geometric properties. N. Broutin and H. Sulzbach. Submitted (47 p.), 2016. [±]

We consider fixed-point equations for probability measures charging measured compact metric spaces that naturally yield continuum random trees. On the one hand, we study the existence, the uniqueness of the fixed-points and the convergence of the corresponding iterative schemes. On the other hand, we study the geometric properties of the random measured real trees that are fixed-points, in particular their fractal properties. We obtain bounds on the Minkowski and Hausdorff dimension, that are proved tight in a number of applications, including the very classical continuum random tree, but also for the dual trees of random recursive triangulations of the disk introduced by Curien and Le Gall [Ann Probab, vol. 39, 2011]. The method happens to be especially powerful to treat cases where the natural mass measure on the real tree only provides weak estimates on the Hausdorff dimension.

Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph. S. Bhamidi, N. Broutin, S. Sen, and X. Wang. Submitted (99 p.), 2014. [±]

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter $t$ (usually related to edge density) and a (model dependent) critical time tc which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős--Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like $n^{2/3}$) and (b) the structure of components (rescaled by $n^{−1/3}$) converge to random fractals related to the continuum random tree. Till date, (a) has been proven for a number of models using different techniques while (b) has been proven for only two models, the classical Erdős-Rényi random graph and the rank-1 inhomogeneous random graph. The aim of this paper is to develop a general program for proving such results. The program requires three main ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent (ii) scaling exponents of susceptibility functions are the same as the Erdős-Rényi random graph and (iii) macroscopic averaging of expected distances between random points in the same component in the barely subcritical regime. We show that these apply to a number of fundamental ran- dom graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules. Thus these models all belong to the domain of attraction of the classical Erdős-Rényi random graph. As a by product we also get results for component sizes at criticality for a general class of inhomogeneous random graphs.

#### Edited volumes

Special Issue Honouring the Memory of Philippe Flajolet - Part 3. N. Broutin, J.A. Fill, M. Nebel and M.D. Ward (Eds). Combinatorics, Probability and Computing., vol. 24, Issue 01, January 2015.
Special Issue Honouring the Memory of Philippe Flajolet - Part 2. N. Broutin, J.A. Fill, M. Nebel and M.D. Ward (Eds). Combinatorics, Probability and Computing., vol. 23, Issue 06, November 2014.
Special Issue Honouring the Memory of Philippe Flajolet - Part 1. N. Broutin, J.A. Fill, M. Nebel and M.D. Ward (Eds). Combinatorics, Probability and Computing., vol. 23, Issue 05, September 2014.

#### Papers in journals

Reversing the cut tree of the Brownian continuum random tree. N. Broutin and M. Wang. Electronic Journal of Probability, vol. 22, paper 80, pp. 1--23, 2017. [±]

Consider the logging process of the Brownian continuum random tree (CRT) $\cal T$ using a Poisson point process of cuts on its skeleton [Aldous and Pitman, Ann. Probab., vol. 26, pp. 1703--1726, 1998]. Then, the cut tree introduced by Bertoin and Miermont describes the genealogy of the fragmentation of $\cal T$ into connected components [Ann. Appl. Probab., vol. 23, pp. 1469--1493, 2013]. This cut-tree $\operatorname{cut}(\cal T)$ is distributed as another Brownian CRT, and is a function of the original tree $\cal T$ and of the randomness in the logging process. We are interested in reversing the transformation of $\cal T$ into $\operatorname{cut}(\cal T)$: we define a shuffling operation, which given a Brownian CRT $\cal H$, yields another one $\operatorname{shuff}(\cal H)$ distributed in such a way that $(\cal T, \operatorname{cut}(\cal T))$ and $(\operatorname{shuff}(\cal H), \cal H)$ have the same distribution.

Bounded monochromatic components for random graphs. N. Broutin and R.J. Kang. Journal of Combinatorics, to appear (37 p), 2017. [±]

We consider vertex partitions of the binomial random graph $G_{n,p}$. For $np\to\infty$, we observe the following phenomenon: for any partition into asymptotically fewer than $\chi(G_{n,p})$ parts, i.e. $o(np/\log np)$ parts, there must be one part whose induced subgraph has a connected component of order at least roughly the average part size. Stated another way, we consider the $t$-component chromatic number, the smallest number of colours needed in a colouring of the vertices such that each colour class induces a subgraph of maximum component order at most $t$. As long as $np \to \infty$, there is a threshold around $t = \Theta(\log_b np)$ (where $b = 1/(1-p)$), such that if $t$ is smaller then the $t$-component chromatic number is about as large as the chromatic number, whereas if $t$ is greater then it is close to the trivial upper bound $n/t$. For $p\in (0,1)$ fixed, we obtain more precise information. In particular, we find something more subtle happens at the threshold $t = \Theta(\log n)$, and we determine the asymptotic first-order behaviour. Moreover, we consider the $t$-component stability number, the maximum order of a vertex subset that induces a subgraph with maximum component order at most $t$, and show that it is concentrated in a constant length interval about an explicitly given formula, so long as $t = O(\log \log n)$.

And/or trees: a local limit point of view. N. Broutin and C. Mailler. Random Structures and Algorithms, to appear (37 pages), 2017. [±]

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel models, not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shape. Fix an integer $k$, take a sequence of random (rooted) trees of increasing sizes, say $(t_n)_{n\ge 1}$, and label each of these random trees uniformly at random in order to get a random Boolean expression on $k$ variables.
We prove that, under rather weak local conditions on the sequence of random trees $(t_n)_{n\ge 1}$, the distribution induced on Boolean functions by this procedure converges as $n\to\infty$. In particular, we characterise two different behaviours of this limit distribution depending on the shape of the local limit of $(t_n)_{n\ge 1}$: a degenerate case when the local limit has no leaves; and a non degenerate case, which we are able to describe in more details under stronger but reasonable conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples we cover include, in a unified way, trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton--Watson trees).

The scaling limit of the minimum spanning tree of a complete graph. L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. The Annals of Probability, vol. 45, pp. 3075--3144, 2017. [±]

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.

Cutting down $\mathbf p$-trees and inhomogeneous continuum random trees. N. Broutin and M. Wang. Bernoulli, vol. 23, pp. 2380--2433, 2016. [±]

We study a fragmentation of the $\mathbf p$-trees of Camarri and Pitman [Electr. J. Probab., vol. 5, pp. 1--18, 2000]. We give exact correspondences between the $\mathbf p$-trees and trees which encode the fragmentation. We then use these results to study the fragmentation of the ICRTs (scaling limits of $\mathbf p$-trees) and give distributional correspondences between the ICRT and the tree encoding the fragmentation. The results for the ICRT extend the results of Bertoin and Miermont [Ann. Appl. Probab., vol. 23(4), pp. 1469--1493, 2013] about the cut tree of the Brownian continuum random tree.

Almost optimal sparsification of random geometric graphs. N. Broutin, L. Devroye, and G. Lugosi. The Annals of Applied Probability, vol. 26, pp. 3078-3109, 2016. [±]

A random geometric irrigation graph $\Gamma_n(r_n,\xi)$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_1,\ldots,X_n$ in the unit square $[0,1]^2$. Each point $X_i$ selects $\xi_i$ neighbors at random, without replacement, among those points $X_j$ ($j\neq i$) for which $\|X_i-X_j\| \le r_n$, and the selected vertices are connected to $X_i$ by an edge. The number $\xi_i$ of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each $X_i$ such that $\xi_i$ satisfies $1\le \xi_i \le \kappa$ for a constant $\kappa>1$. We prove that when $r_n = \gamma_n \sqrt{\log n/n}$ for $\gamma_n \to \infty$ with $\gamma_n =o(n^{1/6}/\log^{5/6}n)$, then the random geometric irrigation graph experiences \emph{explosive percolation} in the sense that when $\mathbf E \xi_i=1$, then the largest connected component has size $o(n)$ but if $\mathbf E \xi_i >1$, then the size of the largest connected component is with high probability $n-o(n)$. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.

A new encoding of combinatorial coalescent processes. Applications to the additive and multiplicative cases. N. Broutin and J.-F. Marckert. Probability Theory and Related Fields, vol. 166, pp. 515--552, 2016. [±]

We revisit the discrete additive and multiplicative coalescents, starting with $n$ particles with unit mass. These cases are known to be related to some combinatorial coalescent processes'': a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $(G(n,p), p\in [0,1])$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $n\to +\infty$. We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous [Ann. Probab., vol. 25, pp. 812--854, 1997]: we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $\lambda$, converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $(B_t+\lambda t - t^2/2, t\geq 0)$, but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi, Budhiraja and Wang [Probab. Theory Rel., to appear] using an additional Poisson point process.

Efficiently navigating a random Delaunay triangulation. N. Broutin, O. Devillers, and R. Hemsley. Random Structures and Algorithms, vol. 49, pp. 95--136, 2016. [hal-00940743] [±]

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given $n$ uniform points in a smooth convex domain of unit area, and for any start point $z$ and query point $q$; cone walk applied to $z$ and $q$ will access at most $O(|zq|\sqrt{n} +\log^7 n)$ sites with complexity $O(|zq|\sqrt{n} \log \log n + \log^7 n)$ with probability tending to 1 as $n$ goes to infinity. We additionally show that in this model, cone walk is $(\log ^{3+\xi} n)$-memoryless with high probability for any pair of start and query point in the domain, for any positive $\xi$. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border.

Connectivity of sparse Bluetooth networks. N. Broutin, L. Devroye, and G. Lugosi. Electronic Communications in Probability, vol. 20, no 48, pp. 1--10, 2015. [±]

Consider a random geometric graph defined on $n$ vertices uniformly distributed in the $d$-dimensional unit torus. Two vertices are connected if their distance is less than a visibility radius'' $r_n$. We consider Bluetooth networks that are locally sparsified random geometric graphs. Each vertex selects $c$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of $n^{-(1-\delta)/d}$ for some $\delta > 0$, then a constant value of $c$ is sufficient for the graph to be connected, with high probability. It suffices to take $c \ge \sqrt{(1+\epsilon)/\delta} + K$ for any positive $\epsilon$ where $K$ is a constant depending on $d$ only. On the other hand, with $c\le \sqrt{(1-\epsilon)/\delta}$, the graph is disconnected with high probability.

The dual tree of a recursive triangulation of the disk. N. Broutin and H. Sulzbach. The Annals of Probability, vol. 43, pp. 738--781, 2015. [±]

In the recursive lamination of the disk, one tries to add chords one after another 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 confirms a conjecture of Curien and Le Gall.

Cutting down trees with a Markov chainsaw. L. Addario-Berry, N. Broutin and C. Holmgren. The Annals of Applied Probability, vol. 24, pp. 2297–2339, 2014. [±]

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.

Connectivity threshold for Bluetooth graphs. N. Broutin, L. Devroye, N. Fraiman, and G. Lugosi. Random Structures and Algorithms, vol. 44, pp. 45--66, 2014. [±]

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.

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, vol. 23, pp. 2560--2603, 2013. [±]

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.

Asymptotics of trees with a prescribed degree sequence. N. Broutin and J.-F. Marckert. Random Structures and Algorithms, vol. 44, pp. 290--316, 2014. [±]

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. [±]

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. [±]

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. [±]

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. [±]

We consider the Erdős-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. [±]

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. [±]

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. [±]

We consider the Erdős-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. [±]

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.

#### Articles in refereed conference proceedings

Efficiently navigating a random Delaunay triangulation. N. Broutin, O. Devillers, and R. Hemsley. Proceedings of the 25th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA), 2014. [±]

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given $n$ uniform points in a smooth convex domain of unit area, and for any start point $z$ and query point $q$; cone walk applied to $z$ and $q$ will access at most $O(|zq|\sqrt{n} +\log^7 n)$ sites with complexity $O(|zq|\sqrt{n} \log \log n + \log^7 n)$ with probability tending to 1 as $n$ goes to infinity. We additionally show that in this model, cone walk is $(\log ^{3+\xi} n)$-memoryless with high probability for any pair of start and query point in the domain, for any positive $\xi$. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border.

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).

#### Slides of some talks

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.

#### Theses

Trees, graphs and recursive partitions. Habilitation, Université Paris 6, 2013.
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.