## Research

**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. [arXiv:1411.3417] [±]

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.

**A new encoding of combinatorial coalescent processes. Applications to the additive and multiplicative cases**N. Broutin and J.-F. Marckert. Submitted (29 p.), 2014. [arXiv:1409.4266] [±]

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.

**Reversing the cut tree of the Brownian continuum random tree.**N. Broutin and M. Wang. Submitted (24 p.), 2014. [arXiv:1408.2924] [±]

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.

**Cutting down $\mathbf p$-trees and inhomogeneous continuum random trees.**N. Broutin and M. Wang. Submitted (44 pages), 2014. [arXiv:1408.0144] [±]

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.

**Bounded monochromatic components for random graphs.**N. Broutin and R.J. Kang. Submitted (20 pages), 2014. [arXiv:1407.3555] [±]

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

**Almost optimal sparsification of random geometric graphs.**N. Broutin, L. Devroye, and G. Lugosi. Submitted (26 pages), 2014. [arXiv:1403.1274] [±]

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.

**Efficiently navigating a random Delaunay triangulation.**N. Broutin, O. Devillers, and R. Hemsley. Submitted (46 p), 2014. [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.

**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), 2013. [aXv:1301.1664] [±]

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.

**Special Issue 06 (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, Special Issue 06, November 2014. ISSN:1469-2163.

**Special Issue 05 (Honouring the Memory of Philippe Flajolet).**N. Broutin, J.A. Fill, M. Nebel and M.D. Ward (Eds).

*Combinatorics, Probability and Computing.*, vol. 23, Special Issue 05, September 2014. ISSN:0963-5483.

**Proceedings of the 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12).**N. Broutin and L. Devroye (Eds)

*DMTCS Proc.*, vol. AQ, 2012.

**Connectivity of sparse Bluetooth networks.**N. Broutin, L. Devroye, and G. Lugosi.

*Electronic Communications in Probability*, to appear (13 pages), 2015. [arXiv:1402.3696] [±]

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

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

**Connectivity threshold for Bluetooth graphs.**N. Broutin, L. Devroye, N. Fraiman, and G. Lugosi.

*Random Structures and Algorithms*, vol. 44, pp. 45--66, 2014. [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.

**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. [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.

**Asymptotics of trees with a prescribed degree sequence.**N. Broutin and J.-F. Marckert.

*Random Structures and Algorithms*, vol. 44, pp. 290--316, 2014. [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 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. [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 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. [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.

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

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