skip to content

Timetable (RGMW03)

Random Graphs, Random Trees and Applications

Monday 16th March 2015 to Friday 20th March 2015

Monday 16th March 2015
09:00 to 09:50 Registration
09:50 to 10:00 Welcome from Christie Marr (INI Deputy Director) INI 1
10:00 to 11:00 J Bertoin (Universität Zürich)
Compensated Fragmentations
A new class of fragmentation type processes is introduced, in which the accumulation of small dislocations which would instantaneously shatter the entire mass into dust, is compensated by an adequate dilation of fragments. A main feature of these processes is that their evolution is govern by a dislocation measure which can be much more general than usual.
11:00 to 11:30 Morning Coffee
11:30 to 12:30 B Haas (Université Paris-Dauphine)
Random trees constructed by aggregation
Co-author: Nicolas Curien (Université Paris-Sud)

Starting from a sequence of positive numbers (a_n), we build an increasing sequence of random trees (T_n) by deciding that T_1 is a segment of length a_1, and then, recursively, attaching at step n a segment of length a_n on a uniform point of the tree T_{n-1}. We will see how the sequence (a_n) influences the geometric properties of the limiting tree: compactness, Hausdorff dimension, self-similarity.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 W Kendall (University of Warwick)
Google maps and improper Poisson line processes
I will review recent work on the construction of random metric spaces using a certain kind of improper Poisson line process.
15:00 to 15:30 Afternoon Tea
15:30 to 16:30 C Goldschmidt (University of Oxford)
A line-breaking construction of the stable trees
Co-author: Benedicte Haas (Universite Paris-Dauphine)

Consider a critical Galton-Watson tree whose offspring distribution lies in the domain of attraction of a stable law of parameter \alpha \in (1,2], conditioned to have total progeny n. The stable tree with parameter \alpha \in (1,2] is the scaling limit of such a tree, where the \alpha=2 case is Aldous' Brownian continuum random tree. In this talk, I will discuss a new, simple construction of the \alpha-stable tree for \alpha \in (1,2]. We obtain it as the completion of an increasing sequence of \mathbb{R}-trees built by gluing together line-segments one by one. The lengths of these line-segments are related to the increments of an increasing \mathbb{R}_+-valued Markov chain. For \alpha = 2, we recover Aldous' line-breaking construction of the Brownian continuum random tree based on an inhomogeneous Poisson process.

17:00 to 18:00 Welcome Wine Reception
Tuesday 17th March 2015
10:00 to 11:00 D Aldous (University of California, Berkeley)
The Compulsive Gambler process
Co-authors: Dan Lanoue (U.C. Berkeley), Justin Salez (Paris 7)

In the Compulsive Gambler process there are $n$ agents who meet pairwise at random times ($i$ and $j$ meet at times of a rate-$\nu_{ij}$ Poisson process) and, upon meeting, play an instantaneous fair game in which one wins the other's money. The process seems pedagogically interesting as being intermediate between coalescent-tree models and interacting particle models, and because of the variety of techniques available for its study. Some techniques are rather obvious (martingale structure; comparison with Kingman coalescent) while others are more subtle (an ``exchangeable over the money elements" property, and a ``token process" construction reminiscent of the Donnelly-Kurtz look-down construction). One can study both kinds of $n \to \infty$ limit. The process can be defined under weak assumptions on a countable discrete space (nearest-neighbor interaction on trees, or long-range interaction on the $d$-dimensional lattice) and there is also a continuous-space extension called the Metric Coalescent.

11:00 to 11:30 Morning Coffee
11:30 to 12:30 R Peled (Tel Aviv University)
Delocalization of two-dimensional random surfaces with hard-core constraints
Co-author: Piotr Milos (University of Warsaw)

We study the fluctuations of random surfaces on a two-dimensional discrete torus. The random surfaces we consider are defined via a nearest-neighbor pair potential which we require to be twice continuously differentiable on a (possibly infinite) interval and infinity outside of this interval. This includes the case of the so-called hammock potential, when the random surface is uniformly chosen from the set of all surfaces satisfying a Lipschitz constraint. Our main result is that these surfaces delocalize, having fluctuations whose variance is at least of order log n, where n is the side length of the torus. The main tool in our analysis is an adaptation to the lattice setting of an algorithm of Richthammer, who developed a variant of a Mermin-Wagner-type argument applicable to hard-core constraints. We rely also on the reflection positivity of the random surface model. The result answers a question mentioned by Brascamp, Lieb and Lebowitz on the hammock potential and a quest ion of Velenik. All terms will be explained in the talk. Joint work with Piotr Milos.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 A Turner (Lancaster University)
Small-particle limits in a regularized Laplacian random growth model
Co-authors: Fredrik Johansson Viklund (Uppsala University), Alan Sola (University of Cambridge)

In 1998 Hastings and Levitov proposed a one-parameter family of models for planar random growth in which clusters are represented as compositions of conformal mappings. This family includes physically occurring processes such as diffusion-limited aggregation (DLA), dielectric breakdown and the Eden model for biological cell growth. In the simplest case of the model (corresponding to the parameter alpha=0), James Norris and I showed how the Brownian web arises in the limit resulting from small particle size and rapid aggregation. In particular this implies that beyond a certain time, all newly aggregating particles share a single common ancestor. I shall show how small changes in alpha result in the emergence of branching structures within the model so that, beyond a certain time, the number of common ancestors is a random number whose distribution can be obtained. This is based on joint work with Fredrik Johansson Viklund (Uppsala) and Alan Sola (Cambridge).

15:00 to 15:30 Afternoon Tea
15:30 to 16:30 AE Holroyd (Microsoft Research)
Local graph coloring
Co-authors: Oded Schramm (), David B Wilson ()

How can we color the vertices of a graph by a local rule based on i.i.d. vertex labels? More precisely, suppose that the color of vertex v is determined by examining the labels within a finite (but perhaps random and unbounded) distance R of v, with the same rule applied at each vertex. (The coloring is then said to be a finitary factor of the i.i.d. labels). Focusing on Z^d, we investigate what can be said about the random variable R if the coloring is required to be proper, i.e. if adjacent vertices must have different colors. Depending on the dimension and the number of colors, the optimal tail decay is either a power law, or a tower of exponentials. I will briefly discuss generalizations to shifts of finite type and finitely dependent processes.

Wednesday 18th March 2015
10:00 to 11:00 A Etheridge (University of Oxford)
Branching Brownian motion, the Brownian net and selection in spatially structured populations
Co-authors: Nic Freeman (University of Bristol), Daniel Straulino (University of Oxford)

Our motivation in this work is to understand the influence of the spatial structure of a population on the efficacy of natural selection acting upon it. From a biological perspective, what is interesting is that whereas when population density is high, the probability that a selectively favoured genetic type takes over a population is independent of spatial dimension, when population density is low, this is no longer the case and spatial dimension plays an important role. The proofs are of independent mathematical interest: for example, in one dimension we find a new route to the Brownian net, from a continuum model of branching and coalescing lineages. In the biologically most interesting setting of two spatial dimensions, as we rescale our continuum model there is a finely balanced tradeoff between branching and coalescing lineages, eventually resulting in a branching Brownian motion.

11:00 to 11:30 Morning Coffee
11:30 to 12:30 J Schweinsberg (University of California, San Diego)
Rigorous results for a population model with selection
We consider a model of a population of fixed size $N$ in which each individual acquires beneficial mutations at rate $\mu$. Each individual dies at rate one, and when a death occurs, an individual is chosen with probability proportional to the individual's fitness to give birth. We obtain rigorous results for the rate at which mutations accumulate in the population, the distribution of the fitnesses of individuals in the population at a given time, and the genealogy of the population. Our results confirm predictions of Desai and Fisher (2007), Desai, Walczak, and Fisher (2013), and Neher and Hallatschek (2013).
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 A Veber ([CNRS - Ecole Polytechnique])
Genealogies with recombination in spatial population genetics
Co-author: Alison Etheridge (University of Oxford)

Discrete or continuous, the spatial structure of a population has an effect on the evolution of its genetic diversity. In recent studies, the random process of recombination (by which certain portions of a chromosome of interest are inherited from one's father and the complement from one's mother) has been used to reconstruct the recent past of a population. This reconstruction is based on the properties of the genealogical trees corresponding to such populations. We shall consider two examples (in continuous space) in which it is possible to use the information left by recombination to infer quantities such that the dispersal rate of a gene, or to test the presence of rare but recurrent catastrophes. (Partially supported by the European project INTEGER).

15:00 to 15:30 Afternoon Tea
15:30 to 16:30 J Berestycki (University of Oxford)
Branching processes with competition by pruning of Levy trees
Co-authors: Joaquin Fontbona (U. Chile), Maria Clara Fittipaldi (U. Chile), L. Doering (U. Zurich), L. Mytnik (Technion), L. Zambotti (UPMC)

There are several ways to describe the evolution of a population with no interactions between individuals. One approach is to use the local time process of a forrest of Lévy trees, or, following the work of Dawson and Li, one can construct the whole population flow as the solution to a certain system of Lévy driven stochastic differential equation. The equivalence between these two constructions is a generalization of the well-known Ray-Knight Theorem.

When one wants to introduce a form of competition in the population, the situation becomes more involved. The stochastic differential approach still works (with an added negative drift term) and the purpose of this talk is to present a novel construction based on the interactive pruning of the Lévy forrest.

The case of a positive drift, which corresponds to an interactive immigration, is also of interest as it is related to the question of existence of exceptional times for Generalized Fleming-Viot processes with mutations at which the number of genetic types in the population is finite.

Based on joint works with : a) L. Doering, L. Mytnik and L. Zambotti and b) J. Fontbona and M.C. Fittipaldi

19:30 to 22:00 Conference Dinner at Christ's College
Thursday 19th March 2015
10:00 to 11:00 N Kistler (City College of New York)
A multi-scale refinement of the second moment method Co-authors: L.P
Arguin, D. Belius, A. Bovier and M. Schmidt I will present a version of the second moment method which is particularly efficient to analyze the extremes of random fields where multiple scales can be identified. The method emerged from work on the extremes of branching Brownian motion, joint with Louis-Pierre Arguin (CUNY) and Anton Bovier (Bonn), and from work with David Belius (NYU) on the cover time by planar Brownian motion. I will also discuss a model which interpolates between Derrida's REM and branching random walks, thereby neatly showing how an increasing number of scales affects the extremes of random fields (joint with Marius Schmidt, Frankfurt). Time permitting, I will conclude with some pointers on a procedure of local projections which allows, in a number of models, to generate scales from first principles.
11:00 to 11:30 Morning Coffee
11:30 to 12:30 O Zindy (Université Pierre & Marie Curie-Paris VI)
Log-correlated Gaussian fields: study of the Gibbs measure
Co-author: Louis-Pierre ARUIN (CUNY)

Gaussian fields with logarithmically decaying correlations, such as branching Brownian motion and the two-dimensional Gaussian free field, are conjectured to form universality class of extreme value statistics (notably in the work of Carpentier & Le Doussal and Fyodorov & Bouchaud). This class is the borderline case between the class of IID random variables, and models where correlations start to affect the statistics. In this talk, I will describe a general approach based on rigorous works in spin glass theory to describe features of the Gibbs measure of these Gaussian fields. I will focus on the two-dimensional discrete Gaussian free field. At low temperature, we show that the normalized covariance of two points sampled from the Gibbs measure is either 0 or 1. This is used to prove that the joint distribution of the Gibbs weights converges in a suitable sense to that of a Poisson-Dirichlet variable.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 T Madaule (Université Paul Sabatier Toulouse III)
On the complex cascade and the complex branching Brownian motion
Co-authors: Rhodes (Université Paris Est), Vargas (ENS Paris)

In 2013, Lacoin, Rhodes and Vargas introduced the complex Gaussian multiplicative chaos and exhibited for this model a phase transition diagram. This diagram contains three phases and three frontiers. In this talk we will study the frontier I/II in the context of the complex dyadic Gaussian branching random walk (complex cascade) and the phase II in the context of the complex branching Brownian motion.

15:00 to 15:30 Afternoon Tea
15:30 to 16:30 L-P Arguin (Université de Montréal)
Maxima of log-correlated Gaussian fields and of the Riemann Zeta function on the critical line
Co-authors: David Belius (NYU), Adam Harper (Cambridge)

A recent conjecture of Fyodorov, Hiary & Keating states that the maxima of the Riemann Zeta function on a bounded interval of the critical line behave similarly to the maxima of a specific class of Gaussian fields, the so-called log-correlated Gaussian fields. These include important examples such as branching Brownian motion and the 2D Gaussian free field. In this talk, we will highlight the connections between the number theory problem and the probabilistic models. We will outline the proof of the conjecture in the case of a randomized model of the Zeta function. We will discuss possible approaches to the problem for the function itself. This is joint work with D. Belius (NYU) and A. Harper (Cambridge).

Friday 20th March 2015
10:00 to 11:00 R van der Hofstad (Technische Universität Eindhoven)
Scale-free percolation
Co-authors: Mia Deijfen (Stockholm University), Gerard Hooghiemstra (Delft University of Technology)

We propose and study a random graph model on the hypercubic lattice that interpolates between models of scale-free random graphs and long-range percolation. In our model, each vertex $x$ has a weight $W_x$, where the weights of different vertices are i.i.d.\ random variables. Given the weights, the edge between $x$ and $y$ is, independently of all other edges, occupied with probability $1-{\mathrm{e}}^{-\lambda W_xW_y/|x-y|^{\alpha}}$, where (a) $\lambda$ is the percolation parameter, (b) $|x-y|$ is the Euclidean distance between $x$ and $y$, and (c) $\alpha$ is a long-range parameter. The most interesting behavior can be observed when the random weights have a power-law distribution, i.e., when $\mathbb{P}(W_x>w)$ is regularly varying with exponent $1-\tau$ for some $\tau>1$. In this case, we see that the degrees are infinite a.s.\ when $\gamma =\alpha(\tau-1)/d \leq 1$ or $\alpha\leq d$, while the degrees have a power-law distribution with exponent $\gamma$ when $\gamma>1$. Our main results describe phase transitions in the positivity of the percolation critical value and in the graph distances in the percolation cluster as $\gamma$ varies. Our results interpolate between those proved in inhomogeneous random graphs, where a wealth of further results is known, and those in long-range percolation. We also discuss many open problems, inspired both by recent work on long-range percolation (i.e., $W_x=1$ for every $x$), and on inhomogeneous random graphs (i.e., the model on the complete graph of size $n$ and where $|x-y|=n$ for every $x\neq y$).

11:00 to 11:30 Morning Coffee
11:30 to 12:30 A Auffinger (Northwestern University)
Rate of convergence of the mean of sub-additive ergodic processes
Co-authors: Michael Damron (Indiana University), Jack T. Hanson (Indiana University)

For a subadditive ergodic sequence ${X_{m,n}}$, Kingman's theorem gives convergence for the terms $X_{0,n}/n$ to some non-random number $g$. In this talk, I will discuss the convergence rate of the mean $\mathbb EX_{0,n}/n$ to $g$. This rate turns out to be related to the size of the random fluctuations of $X_{0,n}$; that is, the variance of $X_{0,n}$, and the main theorems I will present give a lower bound on the convergence rate in terms of a variance exponent. The main assumptions are that the sequence is not diffusive (the variance does not grow linearly) and that it has a weak dependence structure. Various examples, including first and last passage percolation, bin packing, and longest common subsequence fall into this class. This is joint work with Michael Damron and Jack Hanson.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 P Sousi (University of Cambridge)
Uniformity of the late points of random walk on $\mathbb{Z}_d^n$ for $d \geq 3$
Co-author: Jason Miller (MIT)

Let $X$ be a simple random walk in $\mathbb{Z}_n^d$ and let $t_{\rm{cov}}$ be the expected amount of time it takes for $X$ to visit all of the vertices of $\mathbb{Z}_n^d$. For $\alpha\in (0,1)$, the set $\mathcal{L}_\alpha$ of $\alpha$-late points consists of those $x\in \mathbb{Z}_n^d$ which are visited for the first time by $X$ after time $\alpha t_{\rm{cov}}$. Oliveira and Prata (2011) showed that the distribution of $\mathcal{L}_1$ is close in total variation to a uniformly random set. The value $\alpha=1$ is special, because $|\mathcal{L}_1|$ is of order 1 uniformly in $n$, while for $\alpha<1$ the size of $\mathcal{L}_\alpha$ is of order $n^{d-\alpha d}$. In joint work with Jason Miller we study the structure of $\mathcal{L}_\alpha$ for values of $\alpha<1$. In particular we show that there exist $\alpha_0<\alpha_1 \in(0,1)$ such that for all $\alpha>\alpha_1$ the set $\mathcal{L}_\alpha$ looks uniformly random, while for $\alpha<\alpha_0$ it does not (in the total variation sense). In this talk I will try to explain the main ideas of our proof and what are the next steps in this direction.

15:00 to 15:30 Afternoon Tea
15:30 to 16:30 O Zeitouni (Weizmann Institute of Science)
Maxima of logarithmically correlated fields
Co-authors: Jian Ding (University of Chicago), Rishideep Roy (University of Chicago)

I will describe sufficient conditions that ensure the convergence in distribution of the centered maximum for logarithmically correlated Gaussian fields. This class includes the GFF, MBRW, and the circular logarithmic REM. No assumption is made on a Markov property of the fields.

University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons