Processes of coalescence and fragmentation: phase transitions, scaling limits and self-organised criticality
Lead Research Organisation:
University of Oxford
Department Name: Statistics
Abstract
This project is focused on a rich collection of probabilistic models
which involve phenomena of coalescence and fragmentation.
We propose a unified approach to the study of a large class of models
which have separately attracted significant attention in a variety of
contexts.
A particular goal is to give new and powerful descriptions of scaling
limits, and to understand phenomena of phase transition and
self-organised criticality. Such themes are of considerable
significance across a wide range of fields in physics, probability
theory, discrete mathematics and complex systems.
Some of the systems studied will also serve as tools in the analysis
of certain spatial models, which are of lively current interest due to
their relationship to quantum spin systems and physical topics such as
superfluidity.
The last part of the project centres on random interlacements, an
emerging model of percolation and erosion in which long-range
interactions play a significant role. We will combine a range of
probabilistic, geometric and analytic tools to describe the discrete
random structures that emerge, and to understand how their properties
differ from those of traditional percolation models.
which involve phenomena of coalescence and fragmentation.
We propose a unified approach to the study of a large class of models
which have separately attracted significant attention in a variety of
contexts.
A particular goal is to give new and powerful descriptions of scaling
limits, and to understand phenomena of phase transition and
self-organised criticality. Such themes are of considerable
significance across a wide range of fields in physics, probability
theory, discrete mathematics and complex systems.
Some of the systems studied will also serve as tools in the analysis
of certain spatial models, which are of lively current interest due to
their relationship to quantum spin systems and physical topics such as
superfluidity.
The last part of the project centres on random interlacements, an
emerging model of percolation and erosion in which long-range
interactions play a significant role. We will combine a range of
probabilistic, geometric and analytic tools to describe the discrete
random structures that emerge, and to understand how their properties
differ from those of traditional percolation models.
Planned Impact
The study of random graphs and networks, and the way in which they
change over time, has always been closely connected to a broad range
of applications. Applications of particular current significance
include:
- communication networks, especially ad-hoc mobile networks and
peer-to-peer networks as well as designed or fixed networks;
- the modelling of social networks;
- the study of the spread of epidemics;
- the study of the spread of digital viruses;
- the modelling of biological networks including protein interaction
networks;
- the modelling of systemic financial risk.
Phenomena such as percolation, erosion, and fragmentation studied in
this project are of particular relevance to questions concerning
stability and robustness of networks, both in the context of random
failure or degradation and in the context of targeted attack.
Many tools developed to answer theoretical questions about the
behaviour and evolution of random networks have found crucial
applications in the areas above, and far beyond. Expertise in this
field is in great demand in telecommunications companies and in
organisations such as Microsoft Research as well as in
governmental contexts such as the Heilbronn Institute (in
collaboration with GCHQ).
Beyond the academic context, the main impact of our research will be
on those who use the results of the field in their work for such
companies and organisations. This impact will centre around the particular
insights and results obtained from our own project, but will also derive
from the opportunities afforded to us to communicate other tools and
ideas from the broader research area during our interactions with
potential beneficiaries.
change over time, has always been closely connected to a broad range
of applications. Applications of particular current significance
include:
- communication networks, especially ad-hoc mobile networks and
peer-to-peer networks as well as designed or fixed networks;
- the modelling of social networks;
- the study of the spread of epidemics;
- the study of the spread of digital viruses;
- the modelling of biological networks including protein interaction
networks;
- the modelling of systemic financial risk.
Phenomena such as percolation, erosion, and fragmentation studied in
this project are of particular relevance to questions concerning
stability and robustness of networks, both in the context of random
failure or degradation and in the context of targeted attack.
Many tools developed to answer theoretical questions about the
behaviour and evolution of random networks have found crucial
applications in the areas above, and far beyond. Expertise in this
field is in great demand in telecommunications companies and in
organisations such as Microsoft Research as well as in
governmental contexts such as the Heilbronn Institute (in
collaboration with GCHQ).
Beyond the academic context, the main impact of our research will be
on those who use the results of the field in their work for such
companies and organisations. This impact will centre around the particular
insights and results obtained from our own project, but will also derive
from the opportunities afforded to us to communicate other tools and
ideas from the broader research area during our interactions with
potential beneficiaries.
Organisations
Publications
Addario-Berry L
(2016)
Inverting the cut-tree transform
Addario-Berry L
(2019)
Inverting the cut-tree transform
in Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
Ahlberg D
(2016)
Quenched Voronoi percolation
in Advances in Mathematics
Ahlberg D
(2018)
Competition in growth and urns
in Random Structures & Algorithms
Albenque M
(2015)
The Brownian continuum random tree as the unique solution to a fixed point equation
in Electronic Communications in Probability
Allen P
(2017)
Chromatic thresholds in dense random graphs
in Random Structures & Algorithms
Allen P
(2017)
Chromatic thresholds in sparse random graphs
in Random Structures & Algorithms
Amini O
(2015)
Explosion and linear transit times in infinite trees
in Probability Theory and Related Fields
Ball J
(2015)
A probabilistic model for martensitic avalanches
in MATEC Web of Conferences
Bhamidi S
(2018)
Critical random graphs and the differential equations technique
in Indian Journal of Pure and Applied Mathematics
| Description | Several of the discoveries funded by this grant concern the scaling limits of critical random trees and graphs. We found a new construction of the stable trees, which are the scaling limits of critical Galton-Watson trees with offspring distribution in the domain of attraction of a stable law. We also found a new characterisation of the Brownian continuum random tree, which is the scaling limit of critical Galton-Watson trees with finite variance offspring distributions. We proved a scaling limit for a critical Erdos-Renyi random graph conditioned to be a forest. We proved a scaling limit for the sizes of the components in critical random graphs with heavy-tailed degree distributions. Finally, we explored the geometry of the vacant set left by the trace of a random walk on a random d-regular graph, and showed that at criticality it has the same scaling limit as the Erdos-Renyi random graph, and is thus closely related to the multiplicative coalescent. In the setting of random graphs, we also considered the problem of moderate deviations for subgraph counts in both Erdos-Renyi random graph models (with both fixed and random numbers of edges) and proved state-of-the-art asymptotics. Processes of fragmentation and coalescence played a fundamental role in the work on this grant. We discovered the scaling limit behaviour near their extinction time a broad class of Markovian fragmentation processes with negative index (for which fragmentation occurs at a faster rate for smaller blocks), exhibiting along the way the first construction of a stationary measure for these processes. We studied the genealogy of fragmentation processes arising by Poissonian cutting of a random real tree, which is encoded by the so-called cut tree. For the Brownian and stable trees, the cut tree has the same law as the original tree; we showed that it is almost surely possible to recover the original tree. This gives some insight into the geometry of the cluster of a specified vertex in a mean-field forest fire model at stationarity. Processes of coagulation and fragmentation appeared also in the guise of forest-fire models and frozen percolation models. These are random graph processes in which connections appear over time (coagulation) and also "catastrophes" occur, which remove whole connected blocks of the process. We extended representations of the "multiplicative coalescent" in terms of excursions of stochastic processes, in order to describe this new situation where fragmentation also appears. We also developed tools to describe the equilibrium behaviour of such processes, which give new insights into phenomena of self-organised criticality. A further strand of the work on this project concerns percolation processes. Work funded by this grant resolved a major conjecture concerning critical Voronoi percolation, by showing that even in the quenched setting, the crossing probability of a large square converges to 1/2. We studied typical infection times in nucleation and growth processes such as first-passage percolation and bootstrap percolation. And we studied survival for competitive versions of bootstrap percolation with two types. |
| Exploitation Route | Our findings are of primary interest in an academic context. Work funded by the grant has expanded the state of knowledge in various different areas: random graphs and their scaling limits, processes of coagulation and fragmentation, random fractals, percolation, and growth models including bootstrap percolation. One systematic theme is to have helped to develop a more coherent general framework for scaling limits of random graph-type structures than was previously available. |
| Sectors | Other |