Mathematical analysis of strongly correlated processes on discrete dynamic structures

Lead Research Organisation: University of Bath
Department Name: Mathematical Sciences


This proposal embraces the broad theme of mathematical analysis of large interacting systems, which
consist of several small components that randomly interact with one another over space and time.
This concept arises in many fields, and paradigm examples studied in the probability, statistical physics and computer science literature include
percolation, spin systems, and random and dynamic networks.

The development of rigorous statistical mechanics and its influence on modern probability theory turned into a
remarkable success story in the second half of the last century, not only enriching both fields,
but at the same time stimulating and establishing new connections between probability theory, complex analysis, dynamical systems etc.
Many powerful theories and
techniques were produced on both sides, which led to deep understanding of equilibrium problems,
in particular for systems whose local interactions at microscopic level give rise to weak ``macroscopic independence''.

In parallel, demands from theoretical computer science, combinatorics and non-equilibrium statistical physics
offer a large class of models where local microscopic interactions either produce strong correlations at macroscopic levels,
or generate non-equilibrium dynamics, whose behavior changes drastically in time, breaking stationarity and ergodicity.
This prevents current methods based on ergodic theory and rigorous statistical mechanics techniques
(e.g., energy vs. entropy, finite energy and combinatorial arguments) to be applied, and puts us in front of great challenges.

Our overall objective is to develop mathematical techniques to analyze such important and difficult models,
producing ground-breaking results in this area, establishing new connections with other topics, and opening up future directions of research.
In order to make progress towards this broad goal,
we will concentrate on four specific models, which are interesting in their own right,
and exhibit important and challenging characteristics and phenomena that are common to a large class of systems.

Planned Impact

For academic impact, especially the impact in the probability, mathematical physics, combinatorics and theoretical computer science communities please refer to the summary "academic beneficiaries".

Furthermore we expect this research can be of interest to selected industrial partners, including British Telecom and Microsoft Research, Cambridge. We have already established initial contacts with those two groups in order to facilitate the communication of the results and help explore transference of knowledge.


10 25 50
publication icon
Candellero E (2021) Coexistence of competing first passage percolation on hyperbolic graphs in Annales de l'Institut Henri Poincaré, Probabilités et Statistiques

publication icon
Candellero E (2021) Abelian oil and water dynamics does not have an absorbing-state phase transition in Transactions of the American Mathematical Society

publication icon
CANNON S (2018) Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings in Combinatorics, Probability and Computing

publication icon
Caraceni A (2020) A polynomial upper bound for the mixing time of edge rotations on planar maps in Electronic Journal of Probability

publication icon
Caraceni A (2019) Polynomial mixing time of edge flips on quadrangulations in Probability Theory and Related Fields

publication icon
Cipriani A (2018) Scaling limit of the odometer in divisible sandpiles. in Probability theory and related fields

publication icon
Cipriani A (2018) The divisible sandpile with heavy-tailed variables in Stochastic Processes and their Applications

publication icon
Gracar P (2019) Random walks in random conductances: Decoupling and spread of infection in Stochastic Processes and their Applications

publication icon
Gracar P (2019) Multi-scale Lipschitz percolation of increasing events for Poisson random walks in The Annals of Applied Probability

Description * Activated Random Walks (ARW), a mathematical model introduced in the physics literature. We developed a new proof technique (called weak stabilization) that allowed us to study the phase transitions in this model. In particular, we derived several results, and gave the first proof that the model undergoes a phase transition for any value of the so-called sleeping rate on some types of graph, giving the first partial answer for this major open problem. The technique developed in our work has already been used in another paper on the topic.

* We studied the oil-and-water model (related to ARW above) and showed that this model (unlike ARW and all known related models in physics) does not undergoes an absorbing state phase transition. Our proof is very general, and works for all graphs.. This article was accepted for publication in a general mathematical journal.

* Multi-particle diffusion limited aggregation (MDLA). For this mathematical model for dielectric breakdown, we undertook the first analysis of the process in dimensions bigger than 1, a question that had been open for about 40 years. In particular, we showed that when the density of particles is large enough, then the aggregate grows with positive speed. In this project, we introduced a new process (called FPPHE) and analyze it. This process has mathematical interest on its own right.

* We further analyzed FPPHE in graphs different than Z^d that have geometrical properties common to some real-world networks. We showed that FPPHE behaves substantially different than on Z^d, and proved (for the first time in the model) the challenging regime of coexistence. For this, we had to develop new techniques of analysis.

* We also obtained novel results for the case of Z^d, where we showed the existence of a coexistence phase so that the two growing species growth indefinitely even for different growth rates (a quite rare phenomenon in growth processes). To do this we developed a general methodology of analysis, which allows the development of multi-scale analyses to models with non-equilibrium and non-local dynamics. We also showed that this model is non-monotone in general, giving rise to a counterintuitive regime where increasing the speed of propagation of a given type can actually be beneficial to the opposite type.

* Particle systems based on Poisson clouds of random walks. We developed a general framework (based on what we call a Two-sided Lipschitz Surface) that can be used to show space-time percolation of any increasing event. This framework can be used to proof several results in this model.

* Dyadic dissections. These are mathematical objects used in computer science as a tools to learning data. We studied a dynamics (Glauber dynamics) on such objects. Previous works considered only the biased cases for the dynamics, which is traditionally simpler for this and other dissection models (e.g., quadrangulations and triangulations). We gave the first proof for the mixing time of the dynamics in the unbiased case.

* We studied the mixing time of edge-flipping dynamics on random quadrangulations, an important object in physics, combinatorics and probability. This result can be applied in physics as a way to generate random quadrangulations for simulations. Also, the study of the mixing time of the edge-flipping dynamics is very challenging, and previously known results are restricted to very particular cases.

* We defined and studied the dispersion time of random walks on finite graphs, which is a self organizing process with application to load balancing.
Exploitation Route * The technique of non-equilibrium multi-scale analysis we developed to analyze the FPPHE process seems quite flexible and could be used to analyze a vast range of processes.

* The technique of weak stabilization seems powerful and can be adapted to solve problems in similar models.

* The First Passage Percolation in Hostile Environment can be seem as a model of competition between two types of particles. We believe that our proof technique can be used to analyze other models of competition. FPPHE has been adapted by other authors to analyze two challenging models of spread of infection.

* The two-sided Lipschitz surface is a quite general framework, and can be used to answer several questions in this model. In particular, it can be used to analyze algorithms on mobile networks.

* The technique we developed for studying the edge-flipping dynamics on quadrangulations is now been employed to study a related model.
Sectors Digital/Communication/Information Technologies (including Software),Other

Description Organization of the Oberwolfach meeting "Strongly Correlated Random Interacting Processes" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Oberwolfach meeting with researchers from all over the world and all career stages discussing recent developments and new avenues in the area of the proposal.
Year(s) Of Engagement Activity 2018
Description Organization of the School and Workshop on Random Interacting Systems 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact School and workshop with two mini-courses (one on first passage percolation by Michael Damron and the other on spin and loop O(n) models by Ron Peled), several invited lectures by leading researchers and several contributed talks by PhD students and post-docs.
Year(s) Of Engagement Activity 2016
Description Organization of the workshop on Random Processes in Discrete Structures 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Workshop containing several invited talks by leading researchers in the intersection of probability, combinatorics and theoretical computer science, and selected invited talks by UK PhD students.
Year(s) Of Engagement Activity 2016