**And/or trees: a local limit point of view.**N. Broutin and C. Mailler. Submitted (37 pages), 2015. [arXiv:1510.06691] [±]

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

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

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