Seminar Series

Title:  H-percolation with a random H

Abstract:  In H-percolation, we start with a random graph G(n,p) and then iteratively add edges that complete copies of H. The process percolates if all edges missing from G(n,p) are eventually added. We find the critical percolation threshold p_c when H=G(k,1/2) is a uniformly random graph. In this sense, we find p_c for most graphs H. This solves a problem of Balogh, Bollobás and Morris. Joint work with Zsolt Bartha and Gal Kronenberg.

Title:  The critical window for random transposition random walk

Abstract:  The random walk on the permutations of [N] generated by the transpositions was shown by Diaconis and Shahshahani to mix with sharp cutoff around N log N /2 steps. However, Schramm showed that the distribution of the rescaled relative lengths of the largest cycles converge considerably earlier. We show that this behaviour emerges precisely during the same critical window as for the Erdos-Renyi random graph process. Our methods are rather different, and include metric scaling limits and the structure of directed cycles within large 3-regular graphs. Ongoing joint work with Christina Goldschmidt.

Title:  The Symbiotic Contact Process on Galton-Watson Trees

Abstract: The symbiotic contact process can be thought of as a two type generalisation of the contact process which can be used to model the spread of two symbiotic diseases. Each site can either be infected with type A, type B, both, or neither. Infections of either type at a given site occur at a rate of lambda multiplied by the number of neighbours infected by that type. Recoveries of either type at a given site occur at rate 1 if only one type is present, or at a lower rate mu if both types are present, hence the symbiotic name. Both the contact process and the symbiotic contact process have two critical infection rates on a Galton-Watson tree, one determining weak survival, and the other strong survival. Here, weak survival refers to the event where at least one A infection and at least one B infection is present at all times. Strong survival is the event that the root of the tree is infected with both A and B infections at the same time infinitely often. In this talk, I will prove that for small values of mu the weak critical infection rate for the symbiotic model is strictly smaller than the critical rate for the contact process. I will also discuss the more complicated case of strong survival for both processes.

Title:  Competition between types in preferential attachment networks with fitness choice

Abstract:  Preferential attachment networks are a type of network where new vertices join over time at random. Preferential attachment means that the new vertices are more likely to connect to vertices that already have a lot of connections – ‘popular’ vertices. This can be thought of as modelling a real-world scenario such as a social network, where those who already have many friends are more likely to gain more friends in the future.

An extension to this model gives the vertices fitnesses and adds a ‘fitness choice’ mechanism. To decide the parents of new vertices, a sample of vertices is chosen, and the rank order of the fitnesses is used to determine which of them becomes the parent. This model allows for factors other than popularity to determine the speed at which vertices grow.

Our talk concerns the competition between ‘types’ in this model. Here, all vertices in the model are one of multiple possible types, and the type of a new vertex is chosen based on its parents. Some consequences of the fitness choice mechanism, such as a phenomenon known as condensation, can lead to surprising results in type competition, where weaker types are able to represent a larger proportion of the network than stronger ones in the limit.

Title:  Phase transition for random walks on graphs with added weighted random matching

Abstract:  Given a sequence $(G_n)$ of finite graphs, for each $G_n$ we add the edges of a uniform random matching with weight $\varepsilon_n$, obtaining a new graph $G_n^*$.

It has been shown by Hermon, Sousi and Sly that for $\varepsilon\equiv1$ this little random modification on $(G_n)$ is sufficient to guarantee that $(G_n^*)$ exhibits cutoff.

We consider how quickly one can let $\varepsilon_n\to0$ that still ensures cutoff. For a wide range of base graphs we answer this question, establishing a phase transition in $(\varepsilon_n)$.

Joint work with Jonathan Hermon, Anđela Šarković and Perla Sousi.

Title:  Long-range one-dimensional internal diffusion-limited aggregation

Abstract:  We study internal diffusion limited aggregation(IDLA) on $\Z$ where the underlying random walk driving the process is not simple, that is, the jump distribution of the random walk is not necessarily $\pm 1$ and can have infinite second moment. In this model, particles are dropped successively at the origin. Each particle performs an independent random walk until they visit a previously unvisited site and get stuck there. The collection of visited sites forms the current cluster. It is proven in Lawler, Bramson, Griffeath (1992) that the shape of the cluster for IDLA associated with simple symmetric random walks on $\Z^d, \, d \ge 2$ is a Euclidean ball. Our main goal is to study IDLA when the jump distribution of the underlying random walk either has finite second moment or is in the domain of normal attraction of a symmetric $\alpha$-stable distribution with characteristic function $\re^{\beta |t|^\alpha}$

for $1 < \alpha <2$, and thus has finite first moment but infinite second moment. We show that for some appropriate constant $C=C(\alpha)>0$, when we release $Cx$ random walks the largest symmetric interval around the origin to be completely contained in the cluster is $[-x, x]$ as $x \to \infty$ irrespective of whether the second moment is finite or not. Furthermore, we show that if for some $\epsilon>0$, the $3+\epsilon$ moment exists, then $C=2$. 

This talk is based on joint work with Conrado DaCosta and Andrew Wade.

Title:  Structural properties of explosive CMJ branching processes

Abstract:  CMJ branching processes are a large class of continuous-time branching processes that have received a wealth of attention over time, in particular in the so-called 'Malthusian regime', where exponential growth occurs. Motivated by applications such as Polya urns with super-linear feedback and super-linear preferential attachment models, I will discuss some recent work on the 'explosive regime'; branching processes that grow infinitely large in finite time with positive probability. We study a large family of processes for which we obtain results on the structure of the branching process, stopped at the time it reaches an infinite size; in particular how the process has grown infinitely large. We then apply these results to super-linear preferential attachment trees with fitness, where we recover and generalise earlier work of Spencer and Oliveira. Joint work with Tejas Iyer.

Title: Where do trees grow leaves?

Abstract: We study a model of random binary trees grown ``by the leaves" in the style of Luczak and Winkler (2004). If $\tau_n$ is a uniform plane binary tree of size $n$, Luczak and Winkler, and later explicitly Caraceni and Stauffer, constructed a measure $\nu_{\tau_n}$ such that the tree obtained by adding a cherry on a leaf sampled according to $\nu_{\tau_n}$ is still uniformly distributed on the set of all plane binary trees with size $n+1$. It turns out that the measure $\nu_{\tau_n}$, which we call the leaf-growth measure, is noticeably different from the uniform measure on the leaves of the tree $\tau_n$. In fact we prove that as $n \to \infty$, with high probability it is almost entirely supported by a subset of only $n^{3 ( 2 - \sqrt{3})+o(1)} \approx n^{0.8038...}$ leaves. In the continuous setting, we construct the scaling limit of this measure, which is a probability measure on the Brownian Continuum Random Tree supported by a fractal set of dimension $ 6 (2 - \sqrt{3})$. We also compute the full (discrete) multifractal spectrum. This work is a first step towards understanding the diffusion limit of the discrete leaf-growth procedure.

Title: Peierls bounds from Toom contours 

Abstract: In a monotone cellular automaton, each point in the d-dimensional integer lattice can be in one of two states, 0 and 1. In each time step, the states of all points in the lattice are updated simultaneously according to a function that depends monotonously on the previous states of the point and its neighbours. In 1980, Andrei Toom proved his celebrated stability theorem, which says that the upper invariant law of a monotone cellular automaton is stable under small random perturbations if and only if the automaton is an eroder, which means that the unperturbed system started with finitely many zeros returns to the all-one state after a finite number of steps. Import open problems remain for random cellular automata, in which the functions that determine the state of a given space-time point are random and i.i.d. In this talk, I will discuss recent progress on the question to what extent Toom's Peierls argument from 1980 can be used to prove stability of random monotone cellular automata. This is joint work in progress with Réka Szabó and Cristina Toninelli. 

Title: The random cluster graph

Abstract: A cluster graph is formed as the union of complete graphs. Put differently, in a cluster graph each connected component forms a clique. In this talk we consider the Erdős–Rényi random graph conditioned on the rare event that it forms a cluster graph. We call the resulting graph the random cluster graph. Despite the large deviation character of this object, the random cluster graph generalises set partitions in combinatorics and finds applications in community detection. We study key properties like the number of cliques, typical clique sizes and the number of edges when the number of vertices tends to infinity. We identify a phase transition at p=1/2 where the random cluster graph changes from the complete graph to one with many cliques. We further give some results about the critical window and the sparse regime. Finally, we sketch some applications in community detection.

Joint work with Martijn Gösgens, Elena Magnanini, Marc Noy, and Élie de Panafieu.

Title: Simonovits's theorem in random graphs. 

Abstract: Let H be a graph with chromatic number \chi(H) = r+1. Simonovits's theorem states that the unique largest H-free subgraph of K_n is its largest r-partite subgraph if and only if H is edge-critical. We show that the same holds with K_n replaced by G_{n,p} whenever H is also strictly 2-balanced and

        p \geq C n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)},

for some constant C > 0. This is best possible up to the choice of the constant C.

This (partially) resolves a conjecture of DeMarco and Kahn, who proved the result in the case where H is a complete graph.

Moreover, we prove the result with explicit constant C = C(H) that we believe to be optimal.

Joint work with Wojciech Samotij.

Title: Creating change when everyone thinks they’re an outlier: Convincing local authority audiences to care about abstract statistical models using interactive data visualisation

Abstract: You’ve just finished a large research project, published papers in academic journals containing interesting statistical models about an important social problem, and now you’re presenting the findings to local policymakers and directors of services to try and create a positive impact. The only problem is everyone you speak to tells you that they’re glad they’re not the average that your models are referring to; in fact, they’re the exception, they say.

This short presentation will talk about how I have tried to use interactive data visualisation tools developed with the Shiny package in R to try to encourage local authorities to engage with the implications from the statistical models in my research. The presentation will showcase the Child Welfare Inequalities Project App (www.cwip-app.co.uk); discuss my experiences as an amateur learning the tools used to build it as well as its reception; and explain where I see the potential benefits of such applications for quantitative research as a way to allow audiences to engage with questions about counterfactuals, interactions, and random effects in a bespoke way.

Title: Creating change when everyone thinks they’re an outlier: Convincing local authority audiences to care about abstract statistical models using interactive data visualisation

Abstract: You’ve just finished a large research project, published papers in academic journals containing interesting statistical models about an important social problem, and now you’re presenting the findings to local policymakers and directors of services to try and create a positive impact. The only problem is everyone you speak to tells you that they’re glad they’re not the average that your models are referring to; in fact, they’re the exception, they say.

This short presentation will talk about how I have tried to use interactive data visualisation tools developed with the Shiny package in R to try to encourage local authorities to engage with the implications from the statistical models in my research. The presentation will showcase the Child Welfare Inequalities Project App (www.cwip-app.co.uk); discuss my experiences as an amateur learning the tools used to build it as well as its reception; and explain where I see the potential benefits of such applications for quantitative research as a way to allow audiences to engage with questions about counterfactuals, interactions, and random effects in a bespoke way.

Title: Monetising Data

Abstract: The talk will showcase a variety of engagement studies where value is reclaimed from routinely collected data as well as from planned experimental investigations. With the increasing focus on digitalisation, the ability to extract meaning from data has become highly valued. Knowledge Transfer Partnerships between academics and companies are an effective way of delivering change. Using statistical analysis to monetise data can improve the profitability of a business or industry, help with sustainability and reduce waste. Despite the hard-nosed name, monetising data is about altruism rather than avarice.

Title: Fringe trees for random trees with given vertex degrees 

Abstract: In this talk, we consider fringe trees of random plane trees with given vertex statistics (i.e., a given number of vertices of each degree). The main results are laws of large numbers and central limit theorems for the number of fringe trees of a given type.

The key tool for our proofs is an extension to the multivariate setting of a theorem by Gao and Wormald (2004), which provides a way to show asymptotic normality by analyzing the behavior of sufficiently high factorial moments.

Our results also apply to random simply generated trees (or conditioned Galton–Watson trees) by conditioning on their degree statistic.

Joint work with Cecilia Holmgren and Svante Janson (Uppsala University)

Title: Scaling limit of a branching process in a varying environment 

Abstract: A branching process in varying environment is a Galton-Watson tree whose offspring distribution can change at each generation. The evolution of the size of successive generations has drawn a lot of attention in recent years, both from the discrete and continuum points of view (as the scaling limit is a modified Continuous State Branching Process).

We focus on the limiting genealogical structure, which is much more delicate to study. In the critical case (all distributions have average offspring 1), we show that under mild second moment assumptions on the sequence of offspring distributions, a BPVE conditioned to be large converges to the Brownian Continuum Random Tree, as in the standard Galton-Watson setting. The varying environment adds asymmetry and dependencies in many places. This requires numerous changes to the usual arguments. In particular we employ a (to our knowledge) new connexion between the Łukasiewicz path and the height process.

This is a joint work with Daniel Kious and Cécile Mailler.

Title: Disorder relevance for non-convex random gradient Gibbs measures in d=2

Abstract: It is a famous result of statistical mechanics that, at low enough temperature, the random field Ising model is disorder relevant for d=2, i.e. the phase transition between uniqueness/ non-uniqueness of Gibbs measures disappears,  and disorder irrelevant otherwise (Aizenman-Wehr 1990). Generally speaking, adding disorder to a model tends to destroy the non-uniqueness of Gibbs measures.

In this talk we consider - in non-convex potential regime - a random gradient model with disorder in which the interface feels like a bulk term of random fields. We show that this model is disorder relevant with respect to the question of uniqueness of gradient Gibbs measures for a class of non-convex potentials and  disorders. No previous knowledge of gradient models will be assumed in the talk

This is joint work with Simon Buchholz.

Title: Random Spatial Graphs

Abstract: We study random spatial graphs constructed on the points of a Poisson point process in the unit square, in which each point is joined by an edge to its nearest neighbour in a given direction specified by a cone. The unrestricted case is the ordinary nearest-neighbour graph; the restricted case is a version of the minimal directed spanning forest (MDSF) introduced by Bhatt & Roy. For the ordinary nearest-neighbour graph, Avram & Bertsimas obtained a central limit theorem for the total edge length. For the MDSF, the limit theory is known (Penrose & Wade) in two special cases, namely the `south' and `south-west' versions.

In this talk, I will describe ongoing work to extend the limit theory to the case of general cones; depending on the parameters, the limit distribution may be normal, or the convolution of a normal distribution with a non-normal element due to boundary effects.

Title: Interlacement limit of a stopped random walk trace on a torus

Abstract: This talk will consider a simple random walk on the d-dimensional integer lattice Z^d to start at the origin and stop on its first exit time from (-L, L)^d. Write L in the form L = mN with m = m(N) and N, an integer going to infinity in such a way that L^2 ~ AN^d for some real constant A > 0. The main result is that for dimensions higher than and equal to 3, the projection of the stopped trajectory to the N-torus locally converges, away from the origin, to an interlacement process at level Ad\sigma_1, where \sigma_1 is the exit time of a Brownian motion from (-1, 1)^d that is independent of the interlacement process. The talk is based on joint work with Antal A. Jarai.

Title: Playing with Fire: The Necessary Evil of Self-organised Criticality

Abstract: Consider a mean field Erdős-Rényi random digraph process on n vertices. Let each possible directed edge arrive with rate 1/2n. Without opposition, this process is guaranteed to result in the n-complete graph. Hence we introduce a Poisson rain of “lightning strikes” to each vertex with rate λ(n) which propagates across its out-graph, burning all edges of an affected vertex. Subsequently, the system continues to fluctuate to no end in a battle between creation and destruction.

Title: Clique Asymptotics in Scale-Free Social Networks

Abstract: How does the number of friend groups change as more people join a social network? Are individuals with a mutual popular friend more likely to be friends with each other? How can we apply this to non-social settings? 

During this talk we will investigate results for the asymptotic expected number of cliques in the Chung-Lu Inhomogeneous Random Graph Model (in which nodes are independently assigned "popularity" weights with tail probabilities h1−al(h), where a>2 and l is a slowly varying function) as the graph grows, the probability of triangles given one node's popularity, and how to interpret those results in a social context. 

Title: Tangled Paths: a new random graph model from Mallows permutations.

Abstract: The main idea of this talk will be to explore what happens when you take the union of two graphs on {1,...,n}, and the vertex set of one graph has been labelled by a random permutation. To begin we shall see that combining simple structures (e.g. paths, matchings) using a uniformly random permutation often results in graphs with complex structure (e.g. high treewidth). Is then natural to ask what happens under non-uniform models for random permutations. 

We introduce a new random graph model, the tangled path, which results from taking the union of two paths where the vertices of one have been relabelled according to a (non-uniform) random permutation sampled from the Mallows distribution with real parameter 0 < q(n) < 1. Increasing the parameter q in the Mallows distribution has the effect of increasing the number of inverted pairs of elements in the permutation. This has the following effect on the resulting graph: if q is close to 0 the tangled path bears resemblance to a path (if q<1 is fixed then the diameter is linear) and as q tends to 1 it becomes an expander.

In order to further understand the effect of the parameter q on the structure we obtain bounds on the treewidth in terms of q. We also give a sharp threshold for the property of having a balanced separator of size one.

The talk is based on joint work with Jessica Enright, Kitty Meeks and William Pettersson.

Title: A tale of two randomly dividing graphs

Abstract: I will discuss two versions of a random multigraph process that evolve by division of vertices. When a vertex divides, it is replaced by two new vertices with its existing connections distributed randomly between them, and some new connections form between these offspring.

One version evolves by synchronised divisions in discrete time and the other by asynchronous divisions in continuous time. The former is closely related to long-range percolation on an infinitely-generated group; the latter is perhaps more natural as a model for real-world networks, but significantly harder to analyse.

In both versions, we prove that the component of the root converges in distribution to a unique (but different) invariant random multigraph. We consider the expected size of this component, and the threshold for connectedness.

This is joint work with Agelos Georgakopoulos (Warwick).

Title: Scaling limits of critical inhomogeneous random graphs

Abstract: The so-called continuum multiplicative graphs are a family of random metric spaces that arise naturally in the scaling limits of various inhomogeneous random graphs, including the Poissonian model and the configuration model. I'll present a construction of these graphs with an emphasis on its connections with more familiar objects from the branching world: Bienaymé-Galton-Watson tree, Lévy process and Lévy trees. Thanks to these connections, we can identify near optimal conditions for the convergence of discrete graphs in the case of Poissonian model. I’ll also comment on the universality of the limit graphs, in light of some latest developments. 

Based on joint works with Nicolas Broutin and Thomas Duquesne.

Title: Voter models on subcritical inhomogeneous random graphs 

Abstract: The voter model is a classical interacting particle system modelling how consensus is formed across a network. We analyse the time to consensus for the voter model when the underlying graph is a subcritical scale-free random graph. Moreover, we generalise the model to include a `temperature' parameter. The interplay between the temperature and the structure of the random graph leads to a very rich phase diagram, where in the different phases different parts of the underlying geometry dominate the time to consensus. Our proofs rely on the well-known duality to coalescing random walks and a detailed understanding of the structure of the random graphs in terms of a thinned Galton-Watson forest. 

Title: Stein's Method on Testing Goodness-of-fit for Exponential Random Graph Models

Abstract: In this talk, I will introduce a novel nonparametric goodness-of-fit testing procedure for exchangeable exponential random graph models (ERGMs) when a single network realisation is observed. The test determines how likely it is that the observation is generated from a target unnormalised ERGM density. The test statistics are derived from a kernel Stein discrepancy, a divergence constructed via Stein’s method using functions in a reproducing kernel Hilbert space, combined with a discrete Stein operator for ERGMs. Theoretical properties for the testing procedure for a class of ERGMs will be discussed; simulation studies and real network applications will be presented.

Title: Voter models on subcritical inhomogeneous random graphs 

Abstract: The voter model is a classical interacting particle system modelling how consensus is formed across a network. We analyse the time to consensus for the voter model when the underlying graph is a subcritical scale-free random graph. Moreover, we generalise the model to include a `temperature' parameter. The interplay between the temperature and the structure of the random graph leads to a very rich phase diagram, where in the different phases different parts of the underlying geometry dominate the time to consensus. Our proofs rely on the well-known duality to coalescing random walks and a detailed understanding of the structure of the random graphs in terms of a thinned Galton-Watson forest. 

Title: Longest and heaviest paths in directed random graph 

Abstract: In this talk, I will give an overview of results regarding the behaviour of longest paths in Barak-Erdos graphs as well as weighted versions of them, examining their connections to particle systems such as the infinite bin model and to regenerative techniques. 

Title: Hybrid zones and the effect of barriers. 

Abstract: Hybrid zones are narrow regions in which two distinct types of individuals reproduce and produce offspring of mixed type. Some mathematical models conclude that hybrid zones of populations with asymmetric selection against heterozygotes evolve, when correctly rescaled, as mean curvature flow plus a constant flow. This conclusion rests on modelling the density of a particular allele as the solution of a partial differential equation in the euclidean space, proving the result in that deterministic setting and finally showing the presence of genetic drift does not disrupt the conclusion. In this talk, I will sketch the main ingredients to adapt this result to capture an effect one would see in a real-life population; the presence of barriers. Barriers refer to environmental obstacles that prevent individuals from invading certain zones. Mathematically this translates into studying the dynamics in a subset of the euclidean space with reflecting conditions on the boundary. We show that in a particular family of domains there is a phase transition; if the domain presents an opening bigger than an explicit constant there is an invasion of the fittest type, but if the opening is smaller than said constant then there is coexistence between the two types of individuals. As a consequence, we get that barriers can provide survival of the less fit homozygote, even if at the initial time the fittest homozygote dominates an unbounded region of the domain. We also mention how the presence of genetic drift (modelled by a Spatial-Lambda-Fleming Viot type process) may change these results. This is work under the supervision of Alison Etheridge.

Title: Polynomial mixing time for edge flips via growing random planar maps 

Abstract: A long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called “triangulation walk”, a Markov chain defined on the set of all possible triangulations of the regular n-gon. A single step of the chain consists in performing a random edge flip, i.e. in choosing an (internal) edge of the triangulation uniformly at random and, with probability 1/2, replacing it with the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge in question (with probability 1/2, the triangulation is left unchanged).

While it has been shown that the relaxation time for the triangulation walk is polynomial in n and bounded below by a multiple of n^{3/2}, the conjectured sharpness of the lower bound remains firmly out of reach in spite of the apparent simplicity of the chain. For edge flip chains on different models -- such as planar maps, quadrangulations of the sphere, lattice triangulations and other geometric graphs -- even less is known.

We shall discuss results concerning the mixing time of random edge flips on rooted quadrangulations of the sphere, partly obtained in joint work with Alexandre Stauffer. A “growth scheme” for quadrangulations which generates a uniform quadrangulation of the sphere by adding faces one at a time at appropriate random locations can be combined with careful combinatorial constructions to build probabilistic canonical paths in a relatively novel way. This method has immediate implications for a range of interesting edge-manipulating Markov chains on so-called Catalan structures, from “leaf translations” on plane trees to “edge rotations” on general planar maps. Moreover, we are able to apply it to flips on 2p-angulations and simple triangulation of the sphere, via newly developed “growth schemes” to appear in an upcoming paper.