Mini-courses:

​

Daniel Ahlberg​​

Title: Competing growth with reinforcement​

Abstract: In this series of lectures we will study competition between growing entities with a reinforcement effect. More precisely, we shall consider competing growth on an underlying discrete structure that can be described in terms of interacting Polya urns, or as a multi-type branching random walk (BRW) where particles of different type annihilate upon contact. A continuous space version of this process can be described as annihilating branching Brownian motion (ABBM). We shall foremost be concerned with the possible coexistence between two or more types, and investigate how this depends on the underlying graph on which they evolve. Along the way we shall describe some key techniques involving martingales and couplings, as well as several open problems and conjectures.

​

Igor Kortchemski: 

Title: Limits of random trees

Abstract: We will first sketch a landscape of scaling limits and local limits of random Bienaymé-Galton-Watson (BGW) trees. We will then see how to code BGW trees by random walks, which will allow us to study the behavior of large size-conditioned BGW trees in the vicinity of their root (local limits and Kesten's tree) based on the so-called strong ratio limit theorem for random walks. As an application, we shall study combinatorial properties of random dissections of polygons (a dissection of a polygon is a collection of non-intersecting diagonals). 

​​link to slides

link to lecture notes

​

​

Cécile Mailler

Title: Pólya urns

Abstract:  In the first part of the course, we will review classical results on Pólya urns, from Markov’s results on the standard urn (1906), to Janson’s results on “irreducible” urns (2004). In the second part, we will focus on more recent developments of the theory, and in particular the generalisation to infinitely-many colours.

​

​

 

​

​

​​​

Invited talks:

​

Gabriel Hernán Berzunza Ojeda​:

Title: Convergence of the Aldous-Broder Markov chain on high-dimensional regular graphs

Abstract: 

The Brownian continuum random tree emerges as a fundamental limit shape for various discrete tree models. It arises as the scaling limit of, for instance, the uniform spanning tree on the complete graph with $N$ vertices or on the torus $\mathbb{Z}^d_N$ of size-length $N$, for $d\geq 5$ (Peres and Revelle (2005)). Furthermore, the study of uniform spanning trees on connected graphs exhibits deep connections to several other key areas within probability theory. These include loop-erased random walks, potential theory, conformally invariant scaling limits, domino tilings, the Abelian sandpile model, and Sznitman's interlacement process.

 

The Aldous-Broder Markov chain is a simple algorithm for generating random spanning trees. This Markov chain, defined on a graph $G=(V,E)$, evolves through a sequence of rooted trees, each with a subset of $V$ as its vertex set. In Evans, Pitman and Winter (2006), it was shown that the suitable rescaled Aldous-Broder Markov chain on a complete graph converges to the so-called root growth with regrafting process (RGRG process) weakly with respect to the Gromov-Hausdorff topology.

 

In this talk, we study the convergence of the rescaled Aldous-Broder Markov chain on high-dimensional regular graphs, such as $\mathbb{Z}^d_N$, towards the RGRG process.

 

Joint work with Osvaldo Angtuncio-Hern\'andez (Centro de Investigaci\'on en Matem\'aticas (CIMAT)) and Anita Winter (Universit\"at Duisburg-Essen). 

​

Sam Olesker-Taylor: 

Title: A Randomised Approach to Sorting

Abstract: We introduce and analyse a new, extremely simple, randomised sorting algorithm:

• choose a pair of indices {i,j} according to some distribution q;

• sort the elements in positions i and j of the array in ascending order.

We prove that taking q_{i,j} proportional to |i-j|^-1, the harmonic sorter, leads to an order-n(log n)^2 sorting time.

The sorter trivially parallelises in the asynchronous setting, yielding a linear speed-up. We also exhibit a low-communication, synchronous version with a linear speed-up.

​

Gesine Reinert: 

Title: Exponential random graph models analysed using Stein's method

Abstract: Exponential random graph models are popular models for the analysis of social networks, due to their flexibility and to their ability of capturing some complex dependence in networks. Mathematically, their analysis is hindered by their probability distribution given only up to a normalising constant. Moreover usually only one observation from the network is available. Using ideas from Stein's method we can make progress though; we can characterize the model using a Stein operator and devise a kernelized Stein goodness-of-fit test based on this characterisation. We generate synthetic samples from the model underlying  the observed data by mimicking the Stein operator dynamics. Finally, in a simplified model we  use Stein equations to estimate the model parameters via a so-called Stein estimator.

 

This is based on joint works with Nathan Ross, Wenkai Xu, and Adrian Fischer.

​

Minmin Wang: 

Title: Random bipartite graphs with i.i.d. weights

Abstract: We propose a model of random bipartite graphs with i.i.d. weights assigned to both parts of the vertex sets. Edges are formed independently with probabilities that depend on these weights. Part of the appeal of this graph model comes from its closely associated intersection graph, which exhibits nontrivial clustering properties and inhomogeneous vertex degrees. We study the scaling limit for the largest connected components when the underlying graphs are at criticality, and we show that the limit graphs depend on the tail behaviours of the weight distributions of both parts.

​