Search

We identify the scaling limit of random intersection graphs inside their critical windows. The limit graphs vary according to the clustering regimes, and coincide with the continuum Erdos--Renyi graph in two out of the three regimes. Our approach to the scaling limit relies upon the close connection of random intersection graphs with binomial bipartite graphs, as well as a graph exploration algorithm on the latter. This further allows us to prove limit theorems for the number of triangles in the large connected components of the graphs.

It has been claimed in Aldous, Miermont and Pitman [PTRF, 2004] that all L\'evy trees are mixings of inhomogeneous continuum random trees. We give a rigorous proof of this claim in the case of a stable branching mechanism, relying on a new procedure for recovering the tree distance from the graphical spanning trees that works simultaneously for stable trees and inhomogeneous continuum random trees.

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. 22, 2017] 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\'evy trees as well.

We consider the classical Yaglom limit theorem for a branching Markov process $X = (X_t, t \ge 0)$, with non-local branching mechanism in the setting that the mean semigroup is critical, i.e. its leading eigenvalue is zero. In particular, we show that there exists a constant $c(f)$ such that \[ {\rm Law}\left(\frac{\langle f, X_t\rangle}{t} \bigg| \langle 1, X_t\rangle > 0 \right) \to {\mathbf e}_{c(f)}, \qquad t \to \infty, \] where ${\mathbf e}_{c(f)}$ is an exponential random variable with rate $c(f)$ and the convergence is in distribution. As part of the proof, we also show that the probability of survival decays inversely proportionally to time. Although Yaglom limit theorems have recently been handled in the setting of branching Brownian motion in a bounded domain and superprocesses, \cite{Ellen, Yanxia}, these results do not allow for non-local branching, which complicates the analysis. Our approach and the main novelty of this work is based around a precise result for the scaled asymptotics for the $k$-th martingale moments of $X$ (rather than the Yaglom limit itself). We then illustrate our results in the setting of neutron transport, for which the non-locality is essential, complementing recent developments in this domain \cite{SNTE, SNTEII, SNTEIII, MCNTE, MultiNTE}., Comment: 2 figures

This paper continues our treatment of the Neutron Transport Equation (NTE) building on the work in [arXiv:1809.00827v2], [arXiv:1810.01779v4] and [arXiv:1901.00220v3], which describes the flux of neutrons through inhomogeneous fissile medium. Our aim is to analyse existing and novel Monte Carlo (MC) algorithms, aimed at simulating the lead eigenvalue associated with the underlying model. This quantity is of principal importance in the nuclear regulatory industry for which the NTE must be solved on complicated inhomogenous domains corresponding to nuclear reactor cores, irradiative hospital equipment, food irradiation equipment and so on. We include a complexity analysis of such MC algorithms, noting that no such undertaking has previously appeared in the literature. The new MC algorithms offer a variety of advantages and disadvantages of accuracy vs cost, as well as the possibility of more convenient computational parallelisation.

To model the destruction of a resilient network, Cai, Holmgren, Devroye and Skerman introduced the $k$-cut model on a random tree, as an extension to the classic problem of cutting down random trees. Berzunza, Cai and Holmgren later proved that the total number of cuts in the $k$-cut model to isolate the root of a Galton--Watson tree with a finite-variance offspring law and conditioned to have $n$ nodes, when divided by $n^{1-1/2k}$, converges in distribution to some random variable defined on the Brownian CRT. We provide here a direct construction of the limit random variable, relying upon the Aldous-Pitman fragmentation process and a deterministic time change., Comment: 10 pages, 1 figure

We consider a natural model of inhomogeneous random graphs that extends the classical Erd\H os-R\'enyi graphs and shares a close connection with the multiplicative coalescence, as pointed out by Aldous [AOP 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 [EJP 1998] have identified the entrance boundary of the multiplicative coalescence, which is intimately related to the excursion lengths of certain L\'evy-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\'evy 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\'evy trees, which allows us to give an explicit construction of the limit objects from the excursions of the L\'evy-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 regime-specific proofs, for instance: the case of Erd\H os-R\'enyi random graphs obtained by Addario-Berry, Goldschmidt and B. [PTRF 2012], the asymptotic homogeneous case as studied by Bhamidi, Sen and Wang [PTRF 2017], or the power-law case as considered by Bhamidi, Sen and van der Hofstad [PTRF 2018]., Comment: 81 pages. arXiv admin note: substantial text overlap with arXiv:1804.05871

The Box-Ball System, shortly BBS, was introduced by Takahashi and Satsuma as a discrete counterpart of the KdV equation. Both systems exhibit solitons whose shape and speed are conserved after collision with other solitons. We introduce a slot decomposition of ball configurations, each component being an infinite vector describing the number of size $k$ solitons in each $k$-slot. The dynamics of the components is linear: the $k$-th component moves rigidly at speed $k$. Let $\zeta$ be a translation invariant family of independent random vectors under a summability condition and $\eta$ the ball configuration with components $\zeta$. We show that the law of $\eta$ is translation invariant and invariant for the BBS. This recipe allows us to construct a big family of invariant measures, including product measures and stationary Markov chains with ball density less than $\frac12$. We also show that starting BBS with an ergodic measure, the position of a tagged $k$-soliton at time $t$, divided by $t$ converges as $t\to\infty$ to an effective speed $v_k$. The vector of speeds satisfies a system of linear equations related with the Generalized Gibbs Ensemble of conservative laws.

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\H{o}s--R\'enyi 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\'evy 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\'evy graphs are indeed the scaling limit of inhomogeneous random graphs., Comment: 48 pages; paper has been split into two

We introduce weights on the unrooted unlabelled plane trees as follows: let $\mu$ be a probability measure on the set of nonnegative integers whose mean is no larger than $1$; then the $\mu$-weight of a plane tree $t$ is defined as $\Pi \, \mu (degree (v) -1)$, where the product is over the set of vertices $v$ of $t$. We study the random plane tree with a fixed diameter $p$ sampled according to probabilities proportional to these $\mu$-weights and we prove that, under the assumption that the sequence of laws $\mu_p$, $p\! \geq \! 1$, belongs to the domain of attraction of an infinitely divisible law, the scaling limits of such random plane trees are random compact real trees called the unrooted Levy trees, which have been introduced in Duquense & Wang., Comment: 25 pages, 4 figures

We study the diameter of L{\'e}vy trees that are random compact metric spaces obtained as the scaling limits of Galton-Watson trees. L{\'e}vy trees have been introduced by Le Gall and Le Jan (1998) and they generalise Aldous' Continuum Random Tree (1991) that corresponds to the Brownian case. We first characterize the law of the diameter of L{\'e}vy trees and we prove that it is realized by a unique pair of points. We prove that the law of L{\'e}vy trees conditioned to have a fixed diameter r $\in$ (0, $\infty$) is obtained by glueing at their respective roots two independent size-biased L{\'e}vy trees conditioned to have height r/2 and then by uniformly re-rooting the resulting tree; we also describe by a Poisson point measure the law of the subtrees that are grafted on the diameter. As an application of this decomposition of L{\'e}vy trees according to their diameter, we characterize the joint law of the height and the diameter of stable L{\'e}vy trees conditioned by their total mass; we also provide asymptotic expansions of the law of the height and of the diameter of such normalised stable trees, which generalises the identity due to Szekeres (1983) in the Brownian case.

By computations on generating functions, Szekeres proved in 1983 that the law of the diameter of a uniformly distributed rooted labelled tree with n vertices, rescaled by a factor n^{1/2} , converges to a distribution whose density is explicit. Aldous observed in 1991 that this limiting distribution is the law of the diameter of the Brownian tree. In our article, we provide a computation of this law which is directly based on the normalized Brownian excursion. Moreover, we provide an explicit formula for the joint law of the height and diameter of the Brownian tree, which is a new result.

Consider the Aldous--Pitman fragmentation process [Ann Probab, 26(4):1703--1726, 1998] of a Brownian continuum random tree ${\cal T}^{\mathrm{br}}$. The associated cut tree cut$({\cal T}^{\mathrm{br}})$, introduced by Bertoin and Miermont [Ann Appl Probab, 23:1469--1493, 2013], is defined in a measurable way from the fragmentation process, describing the genealogy of the fragmentation, and is itself distributed as a Brownian CRT. In this work, we introduce a shuffle transform, which can be considered as the reverse of the map taking ${\cal T}^{\mathrm{br}}$ to cut$({\cal T}^{\mathrm{br}})$., Comment: 22 pages, 13 figures

We study a fragmentation of the $\mathbf p$-trees of Camarri and Pitman [Elect. 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 theorems for the ICRT extend the ones by Bertoin and Miermont [Ann. Appl. Probab., vol. 23(4), pp. 1469--1493, 2013] about the cut tree of the Brownian continuum random tree., Comment: 44 pages, 6 figures