Random Networks Workshop
22nd May, 2024
The University of Sheffield Probability Group invites you to attend a one-day workshop on the broad topic of Random Networks.
This workshop is the second in a series which aims to bring together academics interested in random graphs regularly to hear about exciting advancements in the field. The first event in this series was held in 2022. Plans are in place to run this workshop in 2024, 2025, and 2026.
Please see below for details of this workshop as well as information about how to register.
Programme
09:00 - 09:30: Registration (tea/coffee + Pastries by PJTaste)
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)
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)
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)
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
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.
Session chair: Jonathan Jordan
Registration
Registration closed at noon on Wednesday May 8th. This event will be running in 2025 (and 2026); do check back next year for more information on those events.
Location
All talks will take place in Lecture Theatre A of the School of Mathematics and Statistics located in Hicks Building. This room is located at the south entrance to the Hicks Building by the Harley Pub (down the hill from the main entrance.) Helpful images are below.
Address: Hicks Building, Hounsfield Road, Sheffield, S3 7RH
The red box on the right hand side is Sheffield's train station. The red circle on the left is the School of Mathematics and Statistics. Distance between the two is a 15-20 minute walk. You can also take the tram (blue line) from the station to the University.
Here you can see the School of Mathematics and Statistics (Hicks Building) and a red arrow indicating the entrance where you will find Lecture Theatre A. The Black pentagon is where lunch will be served.
Hotels in the area
Below are a few hotels in the area for those of you who intend to stay overnight in Sheffield.
Funding bodies
This meeting is generously supported by a grant from the Heilbronn Institute for Mathematical Research and the Engineering and Physical Sciences Research Council. The University of Sheffield has supplied physical and online facilities for this workshop. The Applied Probability Trust is providing administrative and organisational support for this meeting.
