WORKSHOP at IMéRA
Random Walk in Random Graphs, DLA, and Related Topics
12, 13, and 14th of OCTOBER 2015
Maison des Astronomes, 2 Place Le Verrier.
imera.univ-amu.fr
MARSEILLE |

GOALS

This workshop gathers probabilists around two mini-courses of Nathanel Berestycki and Vittoria Silvestri, respectively on random walk on random graph, and diffusion limited aggregation.

PARTICIPANTS

Amine Asselah, Nathanael Berestycki, Charles Bordenave, Djalil Chafai, Sebastien Darses, Pierre Mathieu, Laurent Miclo, Sebastian Muller, Justin Salez, Bruno Schapira, Vittoria Silvestri.

MINI-COURSES

Random walks on random graphs, by Nathanel Berestycki, Cambridge

What is the mixing time of a random walk on the giant component of an Erdos-Renyi random graph? Starting from the worst vertex, it was proved by Benjamini, Kozma and Wormwald, and independently by Fountoulakis and Reed, that mixing occurs in roughly (log n)^2 steps and convergence to equlibrium takes place without cutoff. The goal of this series of lectures will be to explain a recent result (joint work with E. Lubetzky, Y. Peres and A. Sly) which studies the question in the case of a typical starting point. By contrast with the previous case, we will see that mixing occurs in about log n steps, and the cutoff phenomenon occurs. The plan for the lectures is roughly as follows. In the first lecture, we will introduce the contiguous model of Ding, Lubetzky and Peres which gives a tractable decomposition of the giant component of the random graph, and which frames the problem in the larger context of random graphs with given degree sequence. (From this the behaviour of the random walk from the worst starting point is also easy to see.) In the second lecture we will go over the case of d-regular graphs which provided a fertile ground for testing ideas and conjectures. In 2005, Durrett and I approached the question of mixing on such graphs by studying the distance of a random walk from its starting point. We showed a phase transition in the behaviour of this distance and conjectured that this was where the mixing took place. This conjecture was subsequently proved by Lubetzky and Sly. I plan to discuss some of the main ideas in these two papers. In the third lecture we will return to Erdos-Renyi random graphs. I will explain why the natural analogue of the above conjecture on d-regular graphs fails. This will lead us to the main phenomenon responsible for the occurrence of the cutoff phenomenon on random graphs. I will start with the case of the non bactracking random walk which is easier. I will then finish by explaining the main arguments needed to handle the case of random walks on fairly general random graphs.

Hastings-Levitov growth and the GFF, by Vittoria Silvestri, Cambridge

The so called Hastings-Levitov (HL) models are a one parameter family of planar aggregation models defined directly in the continuum, where clusters are built by iterated composition of conformal maps. We will focus on the case of i.i.d. maps, so called HL(0). In 2012 Norris and Turner showed that, as the number of particles diverges and their size is sent to zero, HL(0) clusters look like discs. In this mini-course I will review some recent results about fluctuations around this limiting shape. These are given by a continuous Gaussian process taking values in the space of holomorphic functions outside the unit disc, of which we will see an explicit construction. The boundary values of this field, corresponding to the actual boundary of the cluster, perform an Ornstein-Uhlenbeck process in a suitable infinite-dimensional Hilbert space, which, when the cluster is allowed to grow indefinitely, converges to the restriction of the whole plane Gaussian Free Field to the unit circle.

PROGRAMME

Monday and Tuesday 9:30-12:30 2 courses, and 14:00 to 17:00 three talks.

Wednesday 9:30-12:30 2 courses, and we end after lunch.

Monday 12th of October 2015:

9:30-10:50 N.Berestycki, I

10:50-11:10 Coffee

11:10-12:30 V.Silvestri, I

12:30-14:00 LUNCH.

14:00-17:00, Three Talks: L.Miclo, J.Salez, S.Muller

Tuesday 13th of October 2015:

9:30-10:50 V.Silvestri, II

10:50-11:10 Coffee

11:10-12:30 N.Berestycki, II

12:30-14:00 LUNCH.

14:00-17:00, Three Talks: C.Bordenave, D.Chafai, B.Schapira

Wednesday 14th of October 2015:

9:30-10:50 N.Berestycki, III

10:50-11:10 Coffee

11:10-12:30 V.Silvestri, III

12:30-14:00 LUNCH.

Laurent Miclo, Toulouse

On the speed of convergence to equilibrium for random walks on finite Heisenberg groups.

Let H(n) be the multiplicative group of above diagonal 3x3 matrices whose entries belong to Z/(nZ), and n an integer larger than 2 and whose diagonal entries are equal to 1. Consider as group generators the four matrices containing only one non-zero entry strictly above the diagonal, 1 or -1 in the first above diagonal. It takes a time of order n^2 for the associated random walk to converge to equilibrium, but the centrum converges in n.log(n). It will be shown how to recover this result with the help of representation theory and of spectral estimates on three-diagonal matrices indexed by Z/(nZ). What was initially thought to be a simple exercise on Fourier analysis on discrete Heisenberg groups turn out to have links with numerous other domains. Work in collaboration with Dan Bump, Persi Diaconis, Angela Hicks and Harold Widom.

Justin Salez, Paris

Random walk on random directed graphs.

Roughly speaking, a finite Markov chain exhibits cutoff if the distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near zero on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. In this talk we consider the non-reversible case of random walks on sparse random directed graphs, for which even the equilibrium measure is far from being understood. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a simple, universal shape. We also provide a detailed description of the equilibrium measure. This is joint work with Charles Bordenave and Pietro Caputo.

Bruno Schapira, Marseille

Boundary of the Range of a Transient Walk.

We study the ways in which the simple random walk on the euclidean lattice in dimension 3 and larger, manages to produce a small boundary of its range. This is joint work with Amine Asselah.

Charles Bordenave, Toulouse

A new Proof of Friedman's second eigenvalue Theorem

It was conjectured by Alon and proved by Friedman that a random d-regular graph has nealy the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most 2\sqrt{d-1} +o(1) with probability tending to one as the size of the graph tends to infinity. We will discuss a new method to prove this statement and extend it to random lifts of graphs.

Djalil Chafai, Paris

At the edge of Coulomb gases

A Coulomb gas is a static particle system in which the interaction is Coulombic (typically repulsive). Such structure appear in the spectra of random matrix models and random polynomials. Their asymptotic analysis reveals a variety of universal phenomena. This talk will focus on the behavior at the edge of some models of such gases. Some results and some open problems will be presented.

Sebastian Muller, Marseille

Periodic router walks on trees - recurrence and transience

Router walks are deterministic counterparts of random walks. Router walks capture in many aspects the expected behavior of simple random walks, but with significantly reduced fluctuations compared to a typical random walk trajectory. However, this similarity breaks down when one looks at the properties of being recurrent or being transient, where the router walk may behave differently than the corresponding random walk. For a better understanding of this phenomenon we consider these questions for general periodic router walks on trees and give a classification for recurrence and transience. (joint work with Tal Orenshtein)

This workshop gathers probabilists around two mini-courses of Nathanel Berestycki and Vittoria Silvestri, respectively on random walk on random graph, and diffusion limited aggregation.

PARTICIPANTS

Amine Asselah, Nathanael Berestycki, Charles Bordenave, Djalil Chafai, Sebastien Darses, Pierre Mathieu, Laurent Miclo, Sebastian Muller, Justin Salez, Bruno Schapira, Vittoria Silvestri.

MINI-COURSES

Random walks on random graphs, by Nathanel Berestycki, Cambridge

What is the mixing time of a random walk on the giant component of an Erdos-Renyi random graph? Starting from the worst vertex, it was proved by Benjamini, Kozma and Wormwald, and independently by Fountoulakis and Reed, that mixing occurs in roughly (log n)^2 steps and convergence to equlibrium takes place without cutoff. The goal of this series of lectures will be to explain a recent result (joint work with E. Lubetzky, Y. Peres and A. Sly) which studies the question in the case of a typical starting point. By contrast with the previous case, we will see that mixing occurs in about log n steps, and the cutoff phenomenon occurs. The plan for the lectures is roughly as follows. In the first lecture, we will introduce the contiguous model of Ding, Lubetzky and Peres which gives a tractable decomposition of the giant component of the random graph, and which frames the problem in the larger context of random graphs with given degree sequence. (From this the behaviour of the random walk from the worst starting point is also easy to see.) In the second lecture we will go over the case of d-regular graphs which provided a fertile ground for testing ideas and conjectures. In 2005, Durrett and I approached the question of mixing on such graphs by studying the distance of a random walk from its starting point. We showed a phase transition in the behaviour of this distance and conjectured that this was where the mixing took place. This conjecture was subsequently proved by Lubetzky and Sly. I plan to discuss some of the main ideas in these two papers. In the third lecture we will return to Erdos-Renyi random graphs. I will explain why the natural analogue of the above conjecture on d-regular graphs fails. This will lead us to the main phenomenon responsible for the occurrence of the cutoff phenomenon on random graphs. I will start with the case of the non bactracking random walk which is easier. I will then finish by explaining the main arguments needed to handle the case of random walks on fairly general random graphs.

Hastings-Levitov growth and the GFF, by Vittoria Silvestri, Cambridge

The so called Hastings-Levitov (HL) models are a one parameter family of planar aggregation models defined directly in the continuum, where clusters are built by iterated composition of conformal maps. We will focus on the case of i.i.d. maps, so called HL(0). In 2012 Norris and Turner showed that, as the number of particles diverges and their size is sent to zero, HL(0) clusters look like discs. In this mini-course I will review some recent results about fluctuations around this limiting shape. These are given by a continuous Gaussian process taking values in the space of holomorphic functions outside the unit disc, of which we will see an explicit construction. The boundary values of this field, corresponding to the actual boundary of the cluster, perform an Ornstein-Uhlenbeck process in a suitable infinite-dimensional Hilbert space, which, when the cluster is allowed to grow indefinitely, converges to the restriction of the whole plane Gaussian Free Field to the unit circle.

PROGRAMME

Monday and Tuesday 9:30-12:30 2 courses, and 14:00 to 17:00 three talks.

Wednesday 9:30-12:30 2 courses, and we end after lunch.

Monday 12th of October 2015:

9:30-10:50 N.Berestycki, I

10:50-11:10 Coffee

11:10-12:30 V.Silvestri, I

12:30-14:00 LUNCH.

14:00-17:00, Three Talks: L.Miclo, J.Salez, S.Muller

Tuesday 13th of October 2015:

9:30-10:50 V.Silvestri, II

10:50-11:10 Coffee

11:10-12:30 N.Berestycki, II

12:30-14:00 LUNCH.

14:00-17:00, Three Talks: C.Bordenave, D.Chafai, B.Schapira

Wednesday 14th of October 2015:

9:30-10:50 N.Berestycki, III

10:50-11:10 Coffee

11:10-12:30 V.Silvestri, III

12:30-14:00 LUNCH.

Laurent Miclo, Toulouse

On the speed of convergence to equilibrium for random walks on finite Heisenberg groups.

Let H(n) be the multiplicative group of above diagonal 3x3 matrices whose entries belong to Z/(nZ), and n an integer larger than 2 and whose diagonal entries are equal to 1. Consider as group generators the four matrices containing only one non-zero entry strictly above the diagonal, 1 or -1 in the first above diagonal. It takes a time of order n^2 for the associated random walk to converge to equilibrium, but the centrum converges in n.log(n). It will be shown how to recover this result with the help of representation theory and of spectral estimates on three-diagonal matrices indexed by Z/(nZ). What was initially thought to be a simple exercise on Fourier analysis on discrete Heisenberg groups turn out to have links with numerous other domains. Work in collaboration with Dan Bump, Persi Diaconis, Angela Hicks and Harold Widom.

Justin Salez, Paris

Random walk on random directed graphs.

Roughly speaking, a finite Markov chain exhibits cutoff if the distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near zero on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. In this talk we consider the non-reversible case of random walks on sparse random directed graphs, for which even the equilibrium measure is far from being understood. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a simple, universal shape. We also provide a detailed description of the equilibrium measure. This is joint work with Charles Bordenave and Pietro Caputo.

Bruno Schapira, Marseille

Boundary of the Range of a Transient Walk.

We study the ways in which the simple random walk on the euclidean lattice in dimension 3 and larger, manages to produce a small boundary of its range. This is joint work with Amine Asselah.

Charles Bordenave, Toulouse

A new Proof of Friedman's second eigenvalue Theorem

It was conjectured by Alon and proved by Friedman that a random d-regular graph has nealy the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most 2\sqrt{d-1} +o(1) with probability tending to one as the size of the graph tends to infinity. We will discuss a new method to prove this statement and extend it to random lifts of graphs.

Djalil Chafai, Paris

At the edge of Coulomb gases

A Coulomb gas is a static particle system in which the interaction is Coulombic (typically repulsive). Such structure appear in the spectra of random matrix models and random polynomials. Their asymptotic analysis reveals a variety of universal phenomena. This talk will focus on the behavior at the edge of some models of such gases. Some results and some open problems will be presented.

Sebastian Muller, Marseille

Periodic router walks on trees - recurrence and transience

Router walks are deterministic counterparts of random walks. Router walks capture in many aspects the expected behavior of simple random walks, but with significantly reduced fluctuations compared to a typical random walk trajectory. However, this similarity breaks down when one looks at the properties of being recurrent or being transient, where the router walk may behave differently than the corresponding random walk. For a better understanding of this phenomenon we consider these questions for general periodic router walks on trees and give a classification for recurrence and transience. (joint work with Tal Orenshtein)