Instructor: Eleanor Archer (Université Paris-Nanterre)
Title: Random walks and electrical networks
Description: In this course we will give an introduction to the theory of electrical networks and their applications to the study of random walks on networks. This theory is completely elementary and dates back to works of Kirchhoff, Rayleigh and Maxwell in the 1800s. In particular we will introduce the notion of effective resistance on a network and explain how this can be used to characterize random walk hitting times, transience/recurrence and even the law of a simple random walk. We will accompany the general theory with several interesting examples (for example, we will show that Z^d is transient if and only if d is at least 3). Time permitting, we may also discuss applications to uniform spanning trees via a celebrated formula of Kirchhoff.
Instructor: Matteo D’Achille (Université Paris-Saclay)
Title: An invitation to random assignment problems
Description: What is the optimal way to assign n tasks to n workers? If the cost of assigning each task to each worker is given, the above question is an example of assignment problem.
When n becomes large, one is naturally tempted to adopt a probabilistic approach to
this problem. Probabilistic extensions of the assignment problem have been introduced in Statistical Physics in the 80s, motivated by a surprising and still largely unexplored connection with the physics of spin-glasses. Later on, the topic of random assignment problems became a classic in Probability and it has since developed further interesting connections especially in Analysis.
The aim of the course is to provide a gentle introduction to random assignment problems, depending on whether the assignment costs are independent identically distributed random variables or instead share correlations due to constraints imposed by the underlining geometry in which tasks and workers live.
The course covers the following topics,
1. The Assignment Problem from von Neumann to the Hungarian algorithm
2. Adding Probability: Random Assignment Problems (RAPs)
3. Adding Geometry: Euclidean Random Assignment Problems (ERAPs) and extensions, featuring a crash course on point processes
4. The phase diagram of ERAPs in d = 1
5. ERAPs in d=2: recent results and open questions.
Instructor: Paul Melotti (Université Paris-Saclay)
Title : Random tilings
Description : Given a finite subregion of the square lattice, is it possible to tile it with dominos so that there is no hole and no superposition? And if so, in how many ways can we do it? And can we say something on the typical behavior of a tiling taken randomly, uniformly among all tilings? We will see that these questions naturally lead to discovering methods of statistical physics, more precisely exactly solvable models, originating in the works of Kasteleyn, Temperley and Fisher in the 60s. Such objects will include determinantal measures, limit shapes, and the influence of boundary conditions, in particular with the celebrated "Aztec diamond" tilings.
Instructor: Meltem Unel (Université Paris-Saclay)
Title : Introduction to Galton-Watson trees and their local limits
Description : Galton-Watson (GW) process is the first stochastic model for population evolution introduced in 1873, where every individual reproduces individually and independently according to some offspring distribution. One can ‘visualize’ the growing population by rooted planar trees. Given an offspring distribution, what do these trees look like? Are they short, fat? Do they live forever or do they go extinct at some point? How many different trees (populations) does one have with, say, N vertices (individuals)?
One can then go on and ask questions about bigger trees: what do I get if pick a tree uniformly at random among the ones with N vertices and let N go to infinity? More precisely, does this finite random object converge to an infinite one? If so, what does this infinite tree look like?
In this course, we will take a look at the construction and basic properties of GW trees, then explore their local limit as their size tends to infinity. To enhance our intuition, we will proceed by discussing the local limit of uniform triangulations and compare certain quantities one can calculate in the limit to the ones in case of trees. Time permitting, we will introduce the main idea of a different type of limit, namely the scaling limit, whose study relies on a set of (very) different probabilistic techniques.