Random Networks Workshop
22nd May, 2024

09:30 - 10:20: Brett Kolesnik, University of Oxford, (Website)

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.

Session chair: Nic Freeman

10:20 - 10:50: Refreshments (tea/coffee + biscuits by PJTaste)

10:50 - 11:40: Dominic Yeo, King's College London, (Website)

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.

Session chair: Nic Freeman

11:40 - 11:50: Break

11:50 - 12:40: Open problem session (Session chair: Robin Stephenson)

Problem 1: Dominic Yeo
Problem 2: Brett Kolesnik
Problem 3: Debleena Thacker
Problem 4: Ayalvadi Ganesh
Problem 5: Bas Lodewijks
Problem 6: Alex Giles

12:40 - 13:40: Lunch (Sandwiches by PJTaste)

13:40 - 14:40: Contributed talks by PhD students (Session chair: Robin Stephenson)

13:40 - 14:00: Carmen van-de-l'Isle, University of Bath (Website)

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.

14:00 - 14:20: Benjamin Andrews, University of Sheffield

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.

14:20 - 14:40: Zsuzsa Baran, University of Cambridge

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.

14:40 - 15:10: Refreshments (tea/coffee + biscuits by PJTaste)

15:10 - 16:00: Debleena Thacker, Durham University, (Website)

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.

Session chair: Jonathan Jordan

16:00 - 16:10: Break

16:10 - 17:00: Bas Lodewijks, University of Augsburg, Germany (Website)