Hausdorff School: Large Random Graphs: Geometry and Applications

 

 

Monday, April 3

09:00 Self-Registration
09:30 - 10:30 Matthias Schulte: Limit theorems for random geometric graphs (Part 1)
10:30 - 11:00 Coffee Break
11:00 - 12:00 Julia Komjathy: Topology of weighted scale-free random graphs (Part 1)
12:00 - 13:00 Lunch Break
14:00 - 15:00 Tobias Mueller: Gilbert Random Geometric Graphs: the giant, connectivity, Hamilton cycles, colouring and sharp thresholds (Part 1)
15:00 - 15:30 Coffee Break
15:30 - 16:30 Problem Session

Tuesday, April 4

09:30 - 10:30 Tobias Mueller: Gilbert Random Geometric Graphs: the giant, connectivity, Hamilton cycles, colouring and sharp thresholds (Part 2)
10:30 - 11:00 Coffee Break
11:00 - 12:00 Matthias Schulte: Limit theorems for random geometric graphs (Part 2)
12:00 - 13:00 Lunch Break
14:00 - 15:00 Francois Massol: Dispersal and the stability of ecosystems
15:00 - 15:30 Coffee Break
15:30 - 16:30 Problem Session

Wednesday, April 5

09:30 - 10:30 Julia Komjathy: Topology of weighted scale-free random graphs (Part 2)
10:30 - 11:00 Coffee Break
11:00 - 12:00 Victor Veitch: (Sparse) Exchangeable Graphs
12:00 - 13:00 Lunch
14:00 - 16:30 Excursion

Thursday, April 6

09:30 - 10:30 Tobias Mueller: Gilbert Random Geometric Graphs: the giant, connectivity, Hamilton cycles, colouring and sharp thresholds (Part 3)
10:30 - 11:00 Coffee Break
11:00 - 12:00 Domenico Marinucci: The geometry of random eigenfunctions
12:00 - 13:00 Lunch Break
14:00 - 15:00 Problems Afternoon
15:00 - 15:30 Coffee Break
15:30 - 16:30 Problems Afternoon

Abstracts

Julia Komjathy: Topology of weighted scale-free random graphs

In this lecture series we will study scale-free random graphs. These are random graphs where the degree distribution follows a power-law with infinite (asymptotic) variance, which is commonly observed in real life networks. The main focus is on studying typical distances, when additionally each existing edge (might) carry an i.i.d. length from some distribution. The interesting phenomenon that can occur in scale-free random graphs is that the number of vertices within distance t from an initial vertex grows so rapidly with t that two typical vertices can find each other within bounded distance, (a number that does not grow with the number of vertices). This phenomenon is called explosion and is closely related to the same phenomena observed in infinite mean branching processes. To prove explosion in a random graph, one has to reveal a robust `core-structure' within the graph. The core structure is also useful in studying spreading processes such as epidemics or bootstrap percolation on these networks, and is rather universal in various scale-free random graph models.

 

The configuration model is our toy example, but if time allows we will also study geometric models such as scale-free percolation, a model on Z^d, where explosion can also occur but the proof techniques are somewhat different, due to the non-compactness of the space and the infinite number of vertices.

Domenico Marinucci: The geometry of random eigenfunctions

The characterization of the geometric properties for the excursion sets of
random fields on generic manifolds is a classical topic of probability
theory; it has been very much revived recently by the discovery of the
Gaussian Kinematic Formula by Adler and Taylor (2007). This formula provides
a fully explicit characterization of the expected value for so-called
Minkowski functionals of excursion sets under very broad circumstances. In
this talk, we review some very recent results pointing at a generalization
of this formula to the variance of Minkowski functionals and to a
corresponding Central Limit Theorem, in the case of random eigenfunctions.

The talk is based on a recent paper with Valentina Cammarota;  if time
permits, we will also discuss some related results involving also Giovanni
Peccati, Maurizia Rossi and Igor Wigman.

Francois Massol: Dispersal and the stability of ecosystems

Robert May questioned ecologists forty years ago by showing that random Jacobian matrices, aimed at representing dynamics around an ecological equilibrium, were more prone to show instability with more complex ecosystems. Since then, this famous question has been re-asked under different forms, but the initial observation of May was right in the sense that there is an asymptotic theory for very large Jacobian matrices that constrain the stability of equilibrium. Recently, Allesina and Tang detailed May’s results by looking at different types of interactions (predation, mutualism, …), thus highlighting the fact that some interaction types are more stabilizing than others. Here, I will present results obtained in the case of spatially structured ecosystems, dubbed meta-ecosystems in current ecological jargon. I will show how the initial species-to-species problem can be transposed to a population-to-population one, and present some results on the effects of spatial structure for the stability of large interaction networks. In particular, I will present a stability criterion in species-rich meta-ecosystems which explains under which conditions dispersal stabilizes ecosystems. The combination of theoretical analyses of large Jacobian matrices and simulations of equivalent Lotka-Volterra systems allows to conclude on the optimal dispersal rates minimizing instability of meta-ecosystems.

Tobias Mueller: Gilbert Random Geometric Graphs: the giant, connectivity, Hamilton cycles, colouring and sharp thresholds.

I will explain some classical results on the (standard) random
geometric graph, sometimes also called the Gilbert random graph after
E.N. Gilbert who invented a very similar model in 1961, in which we
take n points at random according to some probability distribution on
d-dimensional Euclidean space and we draw an edge between any two
points that have distance less than r, where r is some parameter that
may -- and usually does -- depend on n.

Matthias Schulte: Limit theorems for random geometric graphs

The topic of this lecture series are random graphs whose vertices are the points of a Poisson or binomial point process and whose edges are determined by the geometry of the points. Examples are the random geometric graph, the nearest neighbour graph or the random connection model. The asymptotic behaviour of such random graphs for increasing intensity of the underlying point process is studied. In particular, limit theorems for related random variables such as the total edge length or subgraph and component counts are derived. In order to prove such results, an introduction to the Malliavin-Stein method is given.

Victor Veitch: (Sparse) Exchangeable Graphs

Many of the most widely used random graph models currently in
use---including stochastic block models, latent feature models and many
others---have their foundations in the graphon framework for dense
graphs. We introduce a new class of models for random graphs that
extends the dense graphon models to the sparse graph regime, and we
argue that this meets many of the desiderata one would demand of a model
to serve as the foundation for a statistical analysis of real-world
networks. The key technical insight is a novel notion of exchangeability
that is used to define the class of models. We also explain sampling and
estimation of these models. Finally, we explain connections with large
graph limit theories.