Skip to main content Skip to navigation

Program of the Workshop

The schedule can be found at the following link:

http://www2.warwick.ac.uk/fac/sci/statistics/crism/workshops/randomprocesses/program/workshop.pdf

 

 

Titles and Abstracts


Daniel Ahlberg: Random coalescing geodesics in first-passage percolation
Abstract: A metric on Z^2 is obtained by assigning non-negative i.i.d. weights to the edges of the nearest neighbour lattice. We discuss the properties of geodesics in this metric. Via the study of 'random coalescing geodesics', we address a question posed in 2003 by Benjamini, Kalai and Schramm that has come to be known as the 'midpoint problem'.

Adam Bowditch: Random walks on Galton-Watson trees
Abstract: In this talk, I will discuss biased random walks on Galton-Watson trees conditioned to survive; in particular, the time taken for the walk to reach the nth generation of the tree. Due to trapping phenomena in the random environment, there are various escape regimes that the walk may follow depending on the bias and the offspring distribution. I will explain how several of these regimes arise noting how changes in certain parameters influence the limiting behaviour.

Angus Davidson: The Robot Crawler Model
Abstract: Web crawlers are used by internet search engines to gather information about the web graph. In this talk we investigate a simple process which models this software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, complete k-partite graphs and secondly, sparse Erdos-Renyi random graphs. Our work follows on from a paper of Bonato et. al. who introduced the model.

Maria Deijfen: The speed and shape of first passage percolation on Z^2
Abstract: First passage percolation on Z^2 is a model for the spread of an infection on the sites of the square lattice. The infection is spread via nearest neighbor sites and the time dynamic is specified by random passage times attached to the edges. We have studied the speed of the growth and the shape of the infected set by aid of large-scale computer simulations, with focus on continuous passage time distributions. I will report on our findings and speculate on implications for a version of the model with two competing infection types. (Joint work with Sven Erick Alm.)

Nikolaos Fontoulakis: Critical phenomena for bootstrap percolation on inhomogeneous random graphs
Abstract: The bootstrap percolation processes were introduced in the late 1970 by Chalupa, Leath and Reich in the context of statistical physics. Besides their significance in that context, nowadays these are viewed as epidemic or dissemination processes on graphs. In this talk, I will discuss a phase transition on the evolution of a bootstrap percolation process on the class of inhomogeneous random graphs that have a kernel of rank 1. These resemble the metastability phenomena of the bootstrap process, that were first observed by Aizenman and Lebowitz on large but finite boxes of the integer lattice. (Joint work with M. Kang, C. Koch and T. Makai.)

George Giakkoupis: Amplifiers and Suppressors of Evolutionary Dynamics on Undirected Graphs
Abstract: We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al. (Nature, 2005). In this process, individuals are the vertices of a connected graph. Initially, a uniformly random vertex is a mutant, and in each step of the process, a vertex is chosen for reproduction at random, with probability proportional to its fitness: mutants have fitness r>1, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor, replacing the individual that was there. The process ends when all vertices are mutants (fixation), or none is (extinction). A principal quantity of study is the probability that fixation is reached. Of particular interest is the existence of families of amplifier graphs, for which this probability tends to 1 as the graph size increases, and the existence of suppressors, for which the probability tends to 0. For the case of directed graphs, it is known that both amplifiers and suppressors exist. For undirected graphs, however, the problem has remained open, and the general belief has been that neither undirected amplifiers nor suppressors exist. In this talk we disprove this belief, by providing the first examples of such graphs.

Peter Gracar: Spread of information by random walks - Multi-scale percolation along a Lipschitz surface
Abstract: A conductance graph on Z^d is a nearest-neighbour graph where all of the edges have non-negative weights assigned to them. In this talk, I will consider the spread of information between particles performing continuous time simple random walks on a conductance graph. I do this by developing a general multi-scale percolation argument using Lipschitz surfaces that can also be used to answer other questions of this nature. (Joint work with Alexandre Stauffer.)

Markus Heydenreich: Scale-free percolation
Abstract: Scale-free percolation, as introduced by Deijfen, van der Hofstad, and Hooghiemstra (2013) denotes a percolation model on Z^d, where two points x and y are connected by an edge with probability
1-exp{-p W_x W_y / dist(x,y)^b }
where p>0 is a percolation parameter, W_x and W_y are i.i.d. edge weights with power law distribution and b denotes the exponent for the long-range connections.
The specific feature of scale-free percolation are (for suitable parameter ranges):
* the length of a shortest path between two vertices x and y is bounded by the O( log |x-y| ) (a 'small world network’)
* the degree of vertices exhibit a power law (a 'scale-free network’)
After an introduction to the model, I shall focus on the regime when the expected degrees are infinite. I present criteria for transience vs. recurrence, and the emergence of a specific hierarchical network as subgraph of the infinite cluster. (Joint work with Joost Jorritsma and Tim Hulshof.)

Marcelo Hilario: Independent bond percolation on Z^2 with one-dimensional inhomogeneities
Abstract: We study bond percolation on the square lattice with one-dimensional inhomogeneities.
Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on Z. Select vertical columns at random independently with a given positive
probability. Keep (resp. remove) vertical edges in the selected columns, with probability p, (resp. 1-p).
All horizontal edges and vertical edges lying in unselected columns are kept (resp. removed) with probability q, (resp. 1-q). We show that, if p > p_c(Z^2) (the critical point for homogeneous Bernoulli bond percolation) then q can be taken strictly smaller than p_c(Z^2) in such a way that the probability that the origin percolates is still positive. (Joint work with Hugo Duminil-Copin, Gady Kozma and Vladas Sidoravicius).

Alexander Holroyd: Random Games
Abstract: Alice and Bob compete in a game of skill, making moves alternately until one or other reaches a winning position, at which the game ends. Or, perhaps neither player can force a win, in which case optimal play continues forever, and we say that the game is drawn. What is the outcome of a typical game? That is, what happens if the game itself is chosen randomly, but is known to both players, who play optimally?
I will provide some answers (any many questions) in several settings, including trees, directed and undirected lattices, and point processes. The competitive nature of game play frequently brings out some of the subtlest and most fundamental properties of probabilistic models. We will encounter continuous and discontinuous phase transitions, hard-core models, probabilistic cellular automata, bootstrap percolation, maximum matching, and stable marriage. (Based on joint works with Riddhipratim Basu, Maria Deijfen, Irene Marcovici, James Martin and Johan Wastlund.)

James Martin: Stable matchings in R^d and on the Poisson-weighted infinite tree
Abstract: We study multi-type stable matching problems for the points of a Poisson process in R^d. For example, consider the following asymmetric two-type model. Take \epsilon in (0,1), and let each point independently be coloured red with probability 1-\epsilon and blue with probability \epsilon; allow red points to be matched either to red or blue points, but forbid blue-blue matches. Under this rule, there exists a unique stable matching.
If \epsilon is sufficiently large, then certainly some blue points will remain unmatched; we conjecture that the same is true for any positive \epsilon, but this is not known for any d. We show that for any fixed \epsilon, there are unmatched blue points with probability 1 when d is sufficiently large.
The analysis involves considering stable matching models on the "Poisson-weighted infinite tree" (or PWIT). The PWIT has been used in many settings as a scaling limit for models involving complete graphs with independent edge weights. I'll explain how it also arises naturally as a scaling limit of Poisson processes in high-dimensional Euclidean space. (Joint work with Alexander Holroyd and Yuval Peres.)

Thomas Mountford: Dynamic random walks in a contact process environment
Abstract: This work, joint with Eulalia Vares of UFRJ, considers a random motion on the integer lattice where jump rates depend on a supercritical contact process in equilibrium. We build on previous work by den Hollander and dos Santos and Sidoravicius to show an invariance principle for all super critical parameter values of the contact process.

Tobias Mueller: Hyperbolic Random Geometric Graphs
Abstract: In my talk, I will describe some recent and ongoing work on hyperbolic random geometric graphs. The talk is partly based on joint works with Michel Bode, Erik Broman, Nikolaos Fountoulakis and Johan Tykesson.
Random geometric graphs are obtained by taking a random set of points in the plane (usually either generated by a Poisson process or sampled i.i.d. uniformly from a large disk or square), and then joining any pair of points by an edge whose distance is less than some parameter r>0. The subject essentially goes back to the work of E.N. Gilbert, who defined a very similar model in 1961. They have since become the focus of considerable research effort and very precise answers are now known to many of the natural questions for this model. A natural question is what happens if we define this model not on the ordinary euclidean plane but instead on the hyperbolic plane. There are different, inequivalent ways in which one might define a finite random geometric graphs on the hyperbolic plane. In an ongoing joint work with Erik Broman and Johan Tykesson we consider one possible and natural definition of hyperbolic random geometric graphs: We take a constant intensity Poisson process on the hyperbolic plane, join two points by an edge if the distance is less than some (constant) r>0, and we discard all points outside of a disk of (large) radius. We then consider the number of points in the largest component. It turns out that, perhaps surprisingly, strikingly different behaviour occurs from the euclidean case. Perhaps even more surprisingly, it turns out that for some choices of the parameters hyperbolic random geometric graphs display features that are usually associated with so-called complex networks. Famously, around the turn of the century it was noted that many ''real'' networks stemming from diverse fields (chemical reaction networks, the internet and social networks) share certain characteristics. Ordinary, euclidean random geometric graphs, as well as the hyperbolic version we study with Broman and Tykesson, are very far from showing these characteristics, but recently Krioukov-Papadopoulos-Kitsak-Vahdat-Boguna observed that there is a way to define random geometric graphs on the hyperbolic plane such that they display these characteristics. In two joint works with Michel Bode and Nikolaos Fountoulakis we studied the largest component and the transition from a disconnected to a connected graph in this model. In both cases our results are very different from the results for all other models in the literature as far as we are aware.

Stephen Muirhead: Localisation properties of trapped, branching random walks
Abstract: Random walks with branching and trapping mechanisms are well-studied in population dynamics, where these mechanisms can be recast as, respectively, the fitness and stability of geographic locations or genetic configurations. One important characteristic of these models is the so-called 'fit and stable hypothesis': that populations eventually concentrate on sites that are both fit and stable. In this talk I will discuss some recent progress in gaining a rigorous understanding of the 'fit and stable' phenomenon in the case in which the branching and trapping rates are assumed to be i.i.d. random fields.

Emanuele Natale: Find Your Place: Simple Distributed Algorithms for Community Detection
Abstract: Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {−1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node.
We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities.
Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.

Pierre Nolin: Frozen percolation in two dimensions
Abstract: We discuss frozen percolation, and related models. This growth process, where the connected components (clusters) stop growing ("freeze") as soon as they become infinite, was introduced by Aldous in 1999 on the binary tree. We investigate an analogous process in two dimensions, where the clusters freeze as soon as they contain at least N vertices, for some finite parameter N. In particular, we prove that the density of frozen sites vanishes as N tends to infinity, and we establish a deconcentration property for the cluster sizes.
Our results are based on a precise understanding of 2D percolation near criticality, and they also give insight into forest-fire processes (where lightning hits independently each tree with a small rate, and burns its entire cluster immediately). This talk is based on joint works with Rob van den Berg (CWI and VU, Amsterdam) and Demeter Kiss (U. Cambridge).

Thomas Sauerwald: On coalescence time in graphs - When is coalescing as fast as meeting?
Abstract: Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. The meeting time is defined as the worst-case expected time required for coalescing two random walks. We will present necessary and sufficient conditions on the mixing time and meeting time under which the coalescing time is equal to the meeting time. We will also investigate the worst-case coalescing time for different graph classes.

Bruno Schapira: Contact process on finite graphs
Abstract: We show that the extinction time for the contact process on any finite graph is (almost) exponential in the number of vertices of the graph. We also prove a general metastability result. The proof uses coupling techniques and induction on the size of the graph. (Based on a joint work with Daniel Valesin.)

Vittoria Silvestri: Hastings-Levitov growth and the GFF
Abstract: The so called Hastings-Levitov (HL) planar aggregation models consist of growing random clusters in the complex plane, built by iterated composition of random conformal maps. When these maps are chosen in i.i.d. fashion, it was proved by Norris and Turner that the limiting shape of HL clusters is a disc. In this talk I will consider fluctuations around this asymptotic behaviour, showing that these are given by a random holomorphic Gaussian field F, which can be explicitly constructed. The boundary values of F perform a Gaussian Markov process in the space of distributions, which is conveniently described as the solution of a stochastic PDE. When the cluster is allowed to grow indefinitely, this process converges to the restriction of a (complex) Gaussian Free Field to the unit circle.

John Sylvester: Hitting times and effective resistances in Erdős-Rényi random graphs
Abstract: In this talk I will discuss effective resistance in graphs and how this is related to the strength of connectivity. In particular, I determine the expectation for random walk hitting times and effective resistances in G(n,p) where c log(n) ≤ np < n^{1/10}, c>1. I also show concentration results for hitting times and effective resistances then explain how these follow from showing a certain strong edge-connectedness property holds with high probability for G(n,p) in this regime.

Augusto Teixeira: Critical oriented percolation on the plane
Abstract: In this talk we are going to discuss some recent results concerning critical oriented percolation on Z^2. Since the seminal work by Bezuidenhout and Grimmett, it was known that this model does not percolate at criticality. Here we strengthen such result, in particular by showing that the one arm event has a polynomially small probability. The techniques that we will present in the talk also help us understand the shape and behavior of large critical components, similarly to the Russo-Seymour-Welsh theory developed for the non-oriented case.
(This talk will be based on a joint work with Hugo Duminil-Copin and Vincent Tassion.)

Tatyana Turova: Phase Transitions in the One-dimensional Coulomb Gas Ensembles
Abstract: We consider the system of particles on a finite interval with pair-wise nearest neighbours interaction and external force. This model was introduced by Malyshev to study the flow of charged particles on a rigorous mathematical level. It is a simplified version of a 3-dimensional classical Coulomb gas model.
We study Gibbs distribution at finite positive temperature extending recent results on the zero temperature case (ground states) with external force. We derive the asymptotic for the mean and for the variances of the distances between the neighbouring charges. We prove that depending on the strength of the external force there are several phase transitions in the local structure of the configuration of the particles in the limit when the number of particles goes to infinity.

Daniel Valesin: Spatial Gibbs random graphs
Abstract: Many real-world networks of interest are embedded in physical space. We present a new random graph model aiming to reflect the interplay between the geometries of the graph and of the underlying space. The model favors configurations with small average graph distance between vertices, but adding an edge comes at a cost measured according to the geometry of the ambient physical space. In most cases, we identify the order of magnitude of the average graph distance as a function of the parameters of the model. As the proofs reveal, hierarchical structures naturally emerge from our simple modeling assumptions. Moreover, a critical regime exhibits an infinite number of discontinuous phase transitions. (Joint work with Jean-Christophe Mourrat, ENS Lyon).

Dominic Yeo: Mean-field frozen percolation with k types
Abstract: We study a model for the effect of infections on a population where individuals have one of k types. An inhomogeneous random graph represents the initial connections between these individuals, and over time new connections are made homogeneously, as in the classical random graph process. Each vertex is infected at some rate, resulting in the removal of its entire component. This is a version of a frozen percolation model which (under mild conditions) exhibits self-organised criticality: the dynamics first drive the system to a critical state, and from then on maintain it in criticality. We prove concentration results for the sizes of the components and a local limit theorem, in terms of a multitype branching process whose parameters are critical and described by the solution to an unusual differential equation.