The Third Bath-Paris Branching Structures Meeting

We use a growth procedure for binary trees due to Luczak and Winkler, a bijection between binary trees and irreducible quadrangulations of the hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular mapping between quadrangulations and maps, to define a growth procedure for maps. The growth procedure is local, in that every map is obtained from its predecessor by an operation that only modifies vertices lying on a common face with some fixed vertex. The sequence of maps has an almost sure limit G; we show that G is the distributional local limit of large, uniformly random 3-connected graphs. A classical result of Brooks, Smith, Stone and Tutte associates squarings of rectangles to edge-rooted planar graphs. Our map growth procedure induces a growing sequence of squarings, which we show has an almost sure limit: an infinite squaring of a finite rectangle, which almost surely has a unique point of accumulation. We know almost nothing about the limit, but it should be in some way related to "Liouville quantum gravity". Parts joint with Nicholas Leavitt.

In this talk we will introduce the concepts of "end" of a graph and "trace" of a branching random walk (BRW). We will discuss examples showing that, on some one-ended Cayley graphs, the trace of a transient (symmetric) BRW has infinitely many ends almost surely. (Joint work with Matt Roberts, University of Bath.)

Among search trees, B-trees are very popular in computer science to search and sort data. Their particularity is to have their leaves at the same level and to grow by uniform insertion at their leaves. Their branching number is between m and 2m for values of m more than 100 in concrete cases. Mathematically speaking, the leaves are of different types, and the composition vector of the B-tree happens to behave like a Pólya urn with m colors. The classical phase transition in Pólya urns, between small urns with gaussian asymptotics and large urns with non gaussian asymptotics, occurs for m=59. For the large case, m >= 60, many properties of the limit distribution can be showed, though a lot of mysteries remain. Methods cover linear algebra, embedding in continuous time, martingales, contraction method and smoothing equations.

In this talk, I will first recall the definition of the "true self repelling motion" (TSRM), a rather unusual one-dimensional process that has been shown by Balint Toth and Wendelin Werner to be the continuous counterpart of certain self repelling random walks. Its construction uses a family of coalescing Brownian motions now called the "Brownian Web" which is interesting for its own sake and has been largely studied since. I will then show how to derive properties of the TSRM such as large deviation estimates or local fluctuations, using properties of this Brownian web.

The purpose of my talk is to discuss some asymptotic properties of the Lambda-Wright-Fisher process when an extra selection (logistic) pressure is incorporated. A dual process of the latter is given by a branching-coalescing Markov chain. The study of this chain and its recurrence/transience property leads to a dichotomy in the Lambda-WF model with selection. This Markov chain is also interesting in itself, since its study involves a function which has recently appeared in the study of coming down from infinity.

Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erdös-Rényi random graph in order to prove that M_n, the MST of the complete graph, possesses a scaling limit as n tends to infinity. In particular, if we think of M_n as a metric space (using the graph distance), rescale edge-lengths by n^{-1/3}, and endow the vertices with the uniform measure, then M_n converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree. This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).

We study random (discrete) trees which are invariant in law under the operation of contracting each edge independently with probability p \in (0,1). We show that all such trees can be constructed through Poissonian sampling from random (continuous) measured real trees that satisfy a natural scale invariance property. These trees are different from the usual trees considered in the literature: they are very elongated, with long chains of vertices of degree 2, to which might be attached some bouquets of edges. This is joint work with Pascal Maillard.

Consider a continuous-time branching random walk on the N-dimensional hypercube with random site-dependent branching rates which are i.i.d. and unbounded. We are interested in the growth of the expected number of particles at time t when t and the spacial dimension N tend to infinity simultaneously. We observe the following phase transition: if t increases moderately in relation to N, then the growth rate only depends on the value of the environment at the site of the initial particle; if t increases faster than N, then the growth rate is determined by the maximum value of the environment over all sites of the hypercube. This is joint work with Luca Avena and Onur Gun.

This talk is based on a joint work with Zhan Shi. Biased random walks on supercritical Galton-Watson trees are introduced and studied in depth by Lyons (1990) and Lyons, Pemantle and Peres (1996). We investigate the slow regime, in which case the random walk in random environment $(X_n)$ are known to possess an exotic maximal displacement of order $(\log n)^3$ in the first $n$ steps. Our main result is another - and in some sense even more - exotic property of $(X_n)$: upon the system's non-extinction, the ratio between the maximal potential energy $\max_{0\le k \le n} V(X_k)$ and $(\log n)^2$ converges almost surely to $\frac12$, when $n$ goes to infinity.

We study the mass of a d-dimensional super-Brownian motion as it first exits an increasing sequence of balls. The mass process is a time-inhomogeneous continuous-state branching process, where the increasing radii of the balls are taken as the time-parameter. We characterise its time-dependent branching mechanism and show that it converges, as time goes to infinity, towards the branching mechanism of the mass of a one-dimensional super-Brownian motion as it first crosses above an increasing sequence of levels. Our results identify the compact support criterion in Sheu (1994) as Grey's condition (1974) for the aforementioned limiting branching mechanism. This is based on joint work with Marion Hesse.

Consider the minimal positon of a real-valued branching random walk. In the boundary case, Aidekon obtained the convergence in law of the minimum after a suitable renormalization. We study here the situation outside the Cramér zone which cannot be reduced to the boundary case. Assuming that the step distribution has a heavy tail, we prove a tightness result for the minimum, by showing that all particles near to the minimum are such that their ancestors have exactly one huge drop.

In several models of applied probability such as cyclic Pólya urns, m-ary search trees, and fragmentation processes, limiting distributions of quantities of interest are solutions to smoothing equations in the complex plane. Further, the stationary solutions of certain 3-dimensional kinetic-type evolution equations satisfy smoothing equations with random similarities as coefficients.
In my talk, I will consider smoothing equations in dimension d with random similarities as coefficients. This is a unified framework which contains all examples listed above. The main focus of the talk is on the problem of determining all solutions to these equations and to compare the set of solutions with the corresponding ones in one dimension.
The talk is based on ongoing joint research with Sebastian Mentemeier (Wroclaw).

Preferential attachment networks are a class of dynamical networks in which new nodes are connected to existing nodes with a probability proportional to an increasing function of their degree. In this talk I survey results, obtained in collaboration with Steffen Dereich and Maren Eckhoff, on robustness and vulnerability of these networks. Key to the results is a local approximation of the network by a branching random walk with a killing boundary.

We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. Our main tool is the notion of Ricci curvature, introduced by Ollivier. For instance in the case of transpositions, we show that curvature incurs a phase transition asymptotically: at time cn/2, the curvature is asymptotically zero for c<1 and positive for c>1. To do this we exploit a connection with coalescence and fragmentation processes and a coupling of O. Schramm. This is joint work with Nathanael Berestycki.

In this talk, I will review recent results on the problem of constructing a Brownian motion out of a metric tensor formally given by the exponential of the two dimensional Gaussian Free Field (called Liouville metric). I will explain how to construct such an object and explain why it leads to the existence of a continuous heat kernel. This heat kernel gives rise to a notion of capacity dimension, which is intrinsic to the geometry of the metric tensor. This allows one to derive rigorously a heat kernel based Knizhnik-Polyakov-Zamolodchikov formula, as formulated by the physicists David and Bauer. I will also explain how one can get non trivial bounds for the intrinsic Hausdorff dimension of the Liouville metric through the short time asymptotics of the heat kernel. Joint works with N.Berestycki, C.Garban, P.Maillard, V.Vargas and O.Zeitouni.

The mathematical theory of Gaussian multiplicative chaos was founded by J.P. Kahane in 1985. This theory has numerous applications in mathematical physics: 2d Liouville quantum gravity in the conformal gauge (boundary and non boundary Liouville measure, KPZ equation), the Kolmogorov-Obukhov model of energy dissipation in 3d turbulence, the maximum of log-correlated fields, etc... In this talk, we will review the theory and discuss numerous extensions that have been developed the past few years, in particular to the complex case. Special emphasis will be made on applications which motivate these extensions. This is based on joint works with B. Duplantier, H. Lacoin, T. Madaule, R. Rhodes, S. Sheffield.

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. We shall consider two examples (mainly 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. Joint work with Alison Etheridge and Nick Barton.