We study the connected components in critical percolation on the Hamming hypercube $\{0, 1\}^m$ . We show that their sizes rescaled by $2^{−2m/3}$ converge in distribution, and that, considered as metric measure spaces with the graph distance rescaled by $2^{−m/3}$ and the uniform measure, they converge in distribution with respect to the Gromov–-Hausdorff–-Prokhorov topology. The two corresponding limits are as in critical Erdős–-Rényi graphs.

We give an explicit construction of the scaling limit of the minimum spanning tree of the complete graph. The limit object is described using a recursive construction involving the convex minorants of a Brownian motion with parabolic drift (and countably many i.i.d. uniform random variables); we call it the Brownian parabolic tree.

Aside from the new representation, this point of view has multiple consequences. For instance, it permits us to prove that its Hausdorff dimension is almost surely 3. It also intrisically contains information related to some underlying dynamics: one notable by-product is the construction of a standard metric multiplicative coalescent which couples the scaling limits of random graphs at different points of the critical window in terms of the same simple building blocks.

The above results actually fit in a more general framework. They result from the introduction of a new family of continuum random trees associated with functions via their convex minorants, that we call convex minorant trees. We initiate the study of these structures in the case of Brownian-like paths. In passing, we prove that the convex minorant tree of a Brownian excursion is a Brownian continuum ranndom tree, and that it provides a coupling between the Aldous--Pitman fragmentation of the Brownian continuum random tree and its representation by Bertoin.

We consider random temporal graphs, a version of the classical Erdős-Rényi random graphs $G(n,p)$ where each edge has additionally a distinct random time stamp, and connectivity is reduced to sequences of edges with increasing time stamps. We study the asymptotics for the distances in such graphs, mostly in the regime of interest where $np$ is of order $\log n$. We establish the first order asymptotics for the lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, the maxima of these lengths from a given vertex, as well as the maxima between any two vertices; this covers the (temporal) diameter.

We develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdős-Rényi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime. As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an $L^3$ graphon. In particular, we define a notion of the critical window in this setting. The $L^3$ assumption ensures that the model is in the Erdős-Rényi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel’s RGIV model inside the critical window. Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs. In a companion paper, we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Ruciński and Wormald’s random graph process with degree restrictions provided an additional technical condition about the barely subcritical behavior of this model can be proved.

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.

Motivated by online recommendation systems, we study a family of random forests. The vertices of the forest are labeled by integers. Each non-positive integer $i\le 0$ is the root of a tree. Vertices labeled by positive integers $n \ge 1$ are attached sequentially such that the parent of vertex $n$ is $n-Z_n$, where the $Z_n$ are i.i.d.\ random variables taking values in $\mathbb N$. We study several characteristics of the resulting random forest. In particular, we establish bounds for the expected tree sizes, the number of trees in the forest, the number of leaves, the maximum degree, and the height of the forest. We show that for all distributions of the $Z_n$, the forest contains at most one infinite tree, almost surely. If $\mathbf E Z_n < \infty$, then there is a unique infinite tree and the total size of the remaining trees is finite, with finite expected value if ${\mathbf E }Z_n^2 < \infty$. If $\mathbf E Z_n = \infty$ then almost surely all trees are finite.

We consider a pruning of the inhomogeneous continuum random trees, as well as the cut trees that encode the genealogies of the fragmentations that come with the pruning. We propose a new approach to the reconstruction problem, which has been treated for the Brownian CRT in [Electron. J. Probab. vol. 5, 2000] and for the stable trees in [Ann. IHP B, vol 55, 2019]. Our approach does not rely upon self-similarity and can potentially apply to general Lévy trees as well.

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 that have been introduced in a companion paper. 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. The mains results combined with the ones in the other paper allow us to extend and complement several previous results that had been obtained via model- or regime-specific proofs, for instance: the case of Erdős--Rényi 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].

Motivated by limits of critical inhomogeneous random graphs, we construct a family of sequences of measured metric spaces that we call continuous multiplicative graphs, that are expected to be the universal limit of graphs related to the multiplicative coalescent (the Erdős--Rényi random graph, more generally the so-called rank-one inhomogeneous random graphs of various types, and the configuration model). At the discrete level, the construction relies on a new point of view on (discrete) inhomogeneous random graphs that involves an embedding into a Galton--Watson forest. The new representation allows us to demonstrate that a processus that was already present in the pionnering work of Aldous [Ann. Probab., vol.~25, pp.~812--854, 1997] and Aldous and Limic [Electron. J. Probab., vol.~3, pp.~1--59, 1998] about the multiplicative coalescent actually also (essentially) encodes the limiting metric: The discrete embedding of random graphs into a Galton--Watson forest is paralleled by an embedding of the encoding process into a Lévy process which is crucial in proving the very existence of the local time functionals on which the metric is based; it also yields a transparent approach to compactness and fractal dimensions of the continuous objects. In a companion paper, we show that the continuous Lévy graphs are indeed the scaling limit of inhomogeneous random graphs.

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.

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

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.

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

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.

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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