**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 (29p), 2015. [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.

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