Papers/Preprints

with Olivier Bernardi and Grégory Miermont PDF
Published in

We study the percolation model on Boltzmann triangulations using a generating function approach. More precisely, we consider a Boltzmann model on the set of finite planar triangulations, together with a percolation configuration (either site-percolation or bond-percolation) on this triangulation. By enumerating triangulations with boundaries according to both the boundary length and the number of vertices/edges on the boundary, we are able to identify a phase transition for the geometry of the origin cluster. For instance, we show that the probability that a percolation interface has length $n$ decays exponentially with $n$ except at a particular value $p_c$ of the percolation parameter $p$ for which the decay is polynomial (of order $n^{-10/3}$). Moreover, the probability that the origin cluster has size $n$ decays exponentially if $p < p_c$ and polynomially if $p\geq p_c$.
The critical percolation value is $$ p_c=1/2 \mbox{ for site percolation, and} \ \ p_c=\frac{2\sqrt{3}-1}{11} \mbox{ for bond percolation.}$$ These values coincide with critical percolation thresholds for infinite triangulations identified by Angel for site-percolation, and by Angel & Curien for bond-percolation, and we give an independent derivation of these percolation thresholds.
Lastly, we revisit the criticality conditions for random Boltzmann maps, and argue that at $p_c$, the percolation clusters conditioned to have size $n$ should converge toward the stable map of parameter $ \frac{7}{6}$ introduced by Le Gall & Miermont. This enables us to derive heuristically some new critical exponents.
with Timothy Budd and Cyril Marzouk PDF
Published in

We study the geometry of infinite random Boltzmann planar maps having weight of polynomial decay of order $k^{-2}$ for each vertex of degree $k$. These correspond to the dual of the discrete "stable maps" of Le Gall and Miermont [Scaling limits of random planar maps with large faces, Ann. Probab. 39, 1 (2011), 1-69] studied in [Budd & Curien, Geometry of infinite planar maps with high degrees, Electron. J. Probab.] related to a symmetric Cauchy process, or alternatively to the maps obtained after taking the gasket of a critical $O(2)$-loop model on a random planar map. We show that these maps have a striking and uncommon geometry. In particular we prove that the volume of the ball of radius $r$ for the graph distance has an intermediate rate of growth and scales as $e^{\sqrt{r}}$. We also perform first passage percolation with exponential edge-weights and show that the volume growth for the fpp-distance scales as $e^r$. Finally we consider site percolation on these lattices: although percolation occurs only at $p=1$, we identify a phase transition at $p=1/2$ for the length of interfaces. On the way we also prove new estimates on random walks attracted to an asymmetric Cauchy process.
with Linxiao Chen and Pascal Maillard PDF
Published in

We study the branching tree of the perimeters of the nested loops in critical $O(n)$ model for $n \in (0,2)$ on random quadrangulations. We prove that after renormalization it converges towards an explicit continuous multiplicative cascade whose offspring distribution $(x_i)_{i \geq 1}$ is related to the jumps of a spectrally positive $\alpha$-stable Lévy process with $\alpha= \frac{3}{2} \pm \frac{1}{\pi} \arccos(n/2)$ and for which we can compute explicitly the transform $$ \mathbb{E}\left[ \sum_{i \geq 1}(x_i)^\theta \right] = \frac{\sin(\pi (2-\alpha))}{\sin (\pi (\theta - \alpha))} \quad \mbox{for }\theta \in (\alpha, \alpha+1).$$ An important ingredient in the proof is a new formula on first moments of additive functionals of the jumps of a left-continuous random walk stopped at a hitting time.
with Gady Kozma, Vladas Sidoravicius and Laurent Tournier PDF
Published in

Consider the graph obtained by superposition of an independent pair of uniform infinite non-crossing perfect matchings of the set of integers. We prove that this graph contains at most one infinite path. Several motivations are discussed..
with Alessandra Caraceni PDF
Published in

We study an annealed model of Uniform Infinite Planar Quadrangulation (UIPQ) with an infinite two-sided self-avoiding walk (SAW), which can also be described as the result of glueing together two independent uniform infinite quadrangulations of the half-plane (UIHPQs). We prove a lower bound on the displacement of the SAW which, combined with estimates from our previous paper, shows that the self-avoiding walk is diffusive. As a byproduct this implies that the volume growth exponent of the lattice in question is 4 (as is the case for the standard UIPQ); nevertheless, using our previous work we show its law to be singular with respect to that of the standard UIPQ, that is -- in the language of statistical physics -- the fact that disorder holds.
with Jean Bertoin, Timothy Budd and Igor Kortchemski PDF
Published in

The purpose of the present work is twofold. First, we develop the theory of general self-similar growth-fragmentation processes by focusing on martingales which appear naturally in this setting. As an application, we establish many-to-one formulas for growth-fragmentations and define the notion of intrinsic area of a growth-fragmentation. Second, we identify a distinguished family of growth-fragmentations closely related to stable Levy processes, which are then shown to arise as the scaling limit of the perimeter process in Markovian explorations of certain random planar maps with large degrees (which are, roughly speaking, the dual maps of the stable maps of Le Gall & Miermont). This generalizes a geometric connection between large Boltzmann triangulations and a certain growth-fragmentation process, which was established in arXiv:1507.02265 .
with Timothy Budd PDF
Published in Electronic J. of Probab.

We study the geometry of infinite random Boltzmann planar maps with vertices of high degree. These correspond to the duals of the Boltzmann maps associated to a critical weight sequence $(q_k)_{k \geq 1}$ for the faces with polynomial decay $k^a$ with $a \in (3/2,5/2)$ which have been studied by Le Gall & Miermont as well as by Borot, Bouttier & Guitter. We show the existence of a phase transition for the geometry of these maps at a=2. In the dilute phase corresponding to $a \in (2,5/2)$ we prove that the volume of the ball of radius r (for the graph distance) is of order $r^d$ with $$d=\frac{a-1/2}{a-2},$$ and we provide distributional scaling limits for the volume and perimeter process. In the dense phase corresponding to $a \in (3/2,2)$ the volume of the ball of radius $r$ is exponential in $r$. We also study the first-passage percolation (FPP) distance with exponential edge weights and show in particular that in the dense phase the FPP distance between the origin and infinity is finite. The latter implies in addition that the random lattices in the dense phase are transient. The proofs rely on the recent peeling process introduced in arXiv:1506.01590 and use ideas of arXiv:1412.5509 in the dilute phase.
with Jean-François Le Gall PDF
Published in

We study local modifications of the graph distance in large random triangulations. Our main results show that, in large scales, the modified distance behaves like a deterministic constant $c \in (0,\infty)$ times the usual graph distance. This applies in particular to the first-passage percolation distance obtained by assigning independent random weights to the edges of the graph. We also consider the graph distance on the dual map, and the first-passage percolation on the dual map with exponential edge weights, which is closely related to the so-called Eden model. In the latter two cases, we are able to compute explicitly the constant c by using earlier results about asymptotics for the peeling process. In general however, the constant c is obtained from a subadditivity argument in the infinite half-plane model that describes the asymptotic shape of the triangulation near the boundary of a large ball. Our results apply in particular to the infinite random triangulation known as the UIPT, and show that balls of the UIPT for the modified distance are asymptotically close to balls for the graph distance.
with Alessandra Caraceni PDF
Published in Random Structures and Algorithms

We give a new construction of the uniform infinite half-planar quadrangulation with a general boundary (or UIHPQ), analogous to the construction of the UIPQ presented by Chassaing and Durhuus, which allows us to perform a detailed study of its geometry. We show that the process of distances to the root vertex read along the boundary contour of the UIHPQ evolves as a particularly simple Markov chain and converges to a pair of independent Bessel processes of dimension 5 in the scaling limit. We study the "pencil" of infinite geodesics issued from the root vertex as Ménard, Miermont and the second author did for the UIPQ, and prove that it induces a decomposition of the UIHPQ into three independent submaps. We are also able to prove that balls of large radius around the root are on average $7/9$ times as large as those in the UIPQ, both in the UIHPQ and in the UIHPQ with a simple boundary; this fact we use in a companion paper to study self-avoiding walks on large quadrangulations.
with Jean Bertoin and Igor Kortchemski PDF
Published in Annals of Probab.

We are interested in the cycles obtained by slicing at all heights random Boltzmann triangulations with a simple boundary. We establish a functional invariance principle for the lengths of these cycles, appropriately rescaled, as the size of the boundary grows. The limiting process is described using a self-similar growth-fragmentation process with explicit parameters. To this end, we introduce a branching peeling exploration of Boltzmann triangulations, which allows us to identify a crucial martingale involving the perimeters of cycles at given heights. We also use a recent result concerning self-similar scaling limits of Markov chains on the nonnegative integers. A motivation for this work is to give a new construction of the Brownian map from a growth-fragmentation process.
with Jean-François Le Gall PDF
Published in Ann. Institut Henri Poincaré

We study the scaling limit of the volume and perimeter of the discovered regions in the Markovian explorations known as peeling processes for infinite random planar maps such as the uniform infinite planar triangulation (UIPT) or quadrangulation (UIPQ). In particular, our results apply to the metric exploration or peeling by layers algorithm, where the discovered regions are (almost) completed balls, or hulls, centered at the root vertex. The scaling limits of the perimeter and volume of hulls can be expressed in terms of the hull process of the Brownian plane studied in our previous work. Other applications include the metric exploration of the dual graph of our infinite random lattices, and first-passage percolation with exponential edge weights on the dual graph, also known as the Eden model or uniform peeling.
with Bénédicte Haas PDF
Published in Annales de l'Institut Fourier

We study a general procedure that builds random real trees by gluing recursively a new branch on a uniform point of the pre-existing tree. The aim of this paper is to see how the asymptotic behavior of the sequence of lengths of branches influences some geometric properties of the limiting tree, such as compactness and Hausdorff dimension. In particular, when the sequence of lengths of branches behaves roughly like $n^{-a}$ for some $a \in (0,1]$, we show that the limiting tree is a compact random tree of Hausdorff dimension $ 1/a$. This encompasses the famous construction of the Brownian tree of Aldous. When $a>1$, the limiting tree is thinner and its Hausdorff dimension is always 1. In that case, we show that $1/a$ corresponds to the dimension of the set of leaves of the tree.
with Jean-François Le Gall PDF
Published in PTRF

We study the random metric space called the Brownian plane, which is closely related to the Brownian map and is conjectured to be the universal scaling limit of many discrete random lattices such as the uniform infinite planar triangulation. We obtain a number of explicit distributions for the Brownian plane. In particular, we consider, for every $r>0$, the hull of radius $r$, which is obtained by "filling in the holes" in the ball of radius $r$ centered at the root. We introduce a quantity $Z_r$ which is interpreted as the (generalized) length of the boundary of the hull of radius $r$. We identify the law of the process $(Z_r)_{r>0}$ as the time-reversal of a continuous-state branching process starting from infinity at time - infinity and conditioned to hit 0 at time 0, and we give an explicit description of the process of hull volumes given the process $(Z_r)$. We obtain an explicit formula for the Laplace transform of the volume of the hull of radius $r$, and we also determine the conditional distribution of this volume given the length of the boundary. Our proofs involve certain new formulas for super-Brownian motion and the Brownian snake in dimension one, which are of independent interest.
with Thomas Duquesne, Igor Kortchemski and Ioan Manolescu PDF
Published in J. Ecole Polytechnique

We are interested in the asymptotics of random trees built by linear preferential attachment, also known in the literature as Barabasi-Albert trees or plane-oriented recursive trees. We first prove a conjecture of Bubeck, Mossel & Racz concerning the influence of the seed graph on the asymptotic behavior of such trees. Separately we study the geometric structure of nodes of large degrees in a plane version of Barabasi-Albert trees via their associated looptrees. As the number of nodes grows, we show that these looptrees, appropriately rescaled, converge in the Gromov-Hausdorff sense towards a random compact metric space which we call the Brownian looptree. The latter is constructed as a quotient space of Aldous' Brownian Continuum Random Tree and is shown to have almost sure Hausdorff dimension 2.
PDF
Published in PTRF

Pursuing the approach of Angel & Ray, we introduce and study a family of random infinite triangulations of the full-plane that satisfy a natural spatial Markov property. These new random lattices naturally generalize Angel & Schramm's Uniform Infinite Planar Triangulation (UIPT) and are hyperbolic in flavor. We prove that they exhibit a sharp exponential volume growth, are non-Liouville, and that the simple random walk on them has positive speed almost surely. We conjecture that these infinite triangulations are the local limits of uniform triangulations whose genus is proportional to the size.
with Omer Angel, Guillaume Chapuy and Gourab Ray PDF
Published in ECP

We show that the local limit of unicellular maps whose genus is proportional to the number of edges is a supercritical geometric Galton-Watson tree conditioned to survive. The proof relies on enumeration results obtained via the recent bijection given by the second author together with Feray and Fusy.
PDF

We present a way to study the conformal structure of random planar maps. The main idea is to explore the map along an SLE (Schramm--Loewner evolution) process of parameter k=6 and to combine the locality property of the SLE_{6} together with the spatial Markov property of the underlying lattice in order to get a non-trivial geometric information. We follow this path in the case of the conformal structure of random triangulations with a boundary. Under a reasonable assumption called (*) that we have unfortunately not been able to verify, we prove that the limit of uniformized random planar triangulations has a fractal boundary measure of Hausdorff dimension 13 almost surely. This agrees with the physics KPZ predictions and represents a first step towards a rigorous understanding of the links between random planar maps and the Gaussian free field (GFF).
with Igor Kortchemski PDF
Published in PTRF

We study site percolation on Angel & Schramm's uniform infinite planar triangulation. We compute several critical and near-critical exponents, and describe the scaling limit of the boundary of large percolation clusters in all regimes (subcritical, critical and supercritical). We prove in particular that the scaling limit of the boundary of large critical percolation clusters is the random stable looptree of index 3/2, which was introduced in a companion paper. We also give a conjecture linking looptrees of any index in (1,2) with scaling limits of cluster boundaries in random triangulations decorated with O(N) models.
with Bénédicte Haas and Igor Kortchemski PDF
Published in Rand. Struc. Algo.

We study the graph structure of large random dissections of polygons sampled according to Boltzmann weights, which encompasses the case of uniform dissections or uniform p-angulations. As their number of vertices n goes to infinity, we show that these random graphs, rescaled by $n^{-1/2}$, converge in the Gromov--Hausdorff sense towards a multiple of Aldous' Brownian tree when the weights decrease sufficiently fast. The scaling constant depends on the Boltzmann weights in a rather amusing and intriguing way, and is computed by making use of a Markov chain which compares the length of geodesics in dissections with the length of geodesics in their dual trees.
with Jean-François Le Gall PDF
Published in AOP

We study properties of the harmonic measure of balls in typical large discrete trees. For a ball of radius n centered at the root, we prove that, although the size of the boundary is of order $n$, most of the harmonic measure is supported on a boundary set of size approximately equal to $n^\beta$, where ${\beta} =0.78$... is a universal constant. To derive such results, we interpret harmonic measure as the exit distribution of the ball by simple random walk on the tree, and we first deal with the case of critical Galton-Watson trees conditioned to have height greater than n. An important ingredient of our approach is the analogous continuous model (related to Aldous' continuum random tree), where the dimension of harmonic measure of a level set of the tree is equal to $\beta$, whereas the dimension of any level set is equal to 1. The constant ${\beta}$ is expressed in terms of the asymptotic distribution of the conductance of large critical Galton-Watson trees
with Igor Kortchemski PDF
Published in EJP

We introduce a class of random compact metric spaces $L(\alpha)$ indexed by $\alpha \in (1,2)$ and which we call stable looptrees. They are made of a collection of random loops glued together along a tree structure, and can be informally be viewed as dual graphs of $\alpha$-stable L\'evy trees. We study their properties and prove in particular that the Hausdorff dimension of $L(\alpha)$ is almost surely equal to $\alpha$. We also show that stable looptrees are universal scaling limits, for the Gromov-Hausdorff topology, of various combinatorial models. In a companion paper, we prove that the stable looptree of parameter 3/2 is the scaling limit of cluster boundaries in critical site-percolation on large random triangulations.
with Omer Angel PDF
Published in Ann. Instit. Henri Poincaré

We study Bernoulli percolations on random lattices of the half-plane obtained as local limit of uniform planar triangulations or quadrangulations. Using the characteristic spatial Markov property or peeling process of these random lattices we prove a surprisingly simple universal formula for the critical threshold for bond and face percolations on these graphs. Our techniques also permit us to compute off-critical and critical exponents related to percolation clusters such as the volume and the perimeter.
with Bénédicte Haas PDF
Published in PTRF

We show that we can construct simultaneously all the stable trees as a nested family. More precisely, if $1 \le a \le a' \leq 2$ we prove that hidden inside any $a$-stable we can find a version of an $a'$-stable tree rescaled by an independent Mittag-Leffler type distribution. This tree can be explicitly constructed by a pruning procedure of the underlying stable tree or by a modification of the fragmentation associated with it. Our proofs are based on a recursive construction due to Marchal which is proved to converge almost surely towards a stable tree.
with Jean-François Le Gall PDF
Published in J. Theoret. Prob.

We introduce and study the random non-compact metric space called the Brownian plane, which is obtained as the scaling limit of the uniform infinite planar quadrangulation. Alternatively, the Brownian plane is identified as the Gromov-Hausdorff tangent cone in distribution of the Brownian map at its root vertex, and it also arises as the scaling limit of uniformly distributed (finite) planar quadrangulations with n faces when the scaling factor tends to 0 less fast than $n^{-1/4}$. We discuss various properties of the Brownian plane. In particular, we prove that the Brownian plane is homeomorphic to the plane, and we get detailed information about geodesic rays to infinity.
with Itai Benjamini and Agelos Georgakopoulos PDF
Published in ECP

It is shown that if a planar graph admits no non-constant bounded harmonic functions then the trajectories of two independent simple random walks intersect almost surely.
with Itai Benjamini PDF
Published in GAFA

We study the pioneer points of the simple random walk on the uniform infinite planar quadrangulation (UIPQ) using an adaptation of the peeling procedure of Angel to the quadrangulation case. Our main result is that, up to polylogarithmic factors, $n^3$ pioneer points have been discovered before the walk exits the ball of radius n in the UIPQ. As a result we verify the KPZ relation in the particular case of the pioneer exponent and prove that the walk is subdiffusive with exponent less than 1/3. Along the way, new geometric controls on the UIPQ are established.
with Grégory Miermont PDF
Published in Rand. Struc. Algo.

We introduce and study the uniform infinite planar quadrangulation (UIPQ) with a boundary via an extension of the construction of arXiv:1201.1052. We then relate this object to its simple boundary analog using a pruning procedure. This enables us to study the aperture of these maps, that is, the maximal distance between two points on the boundary, which in turn sheds new light on the geometry of the UIPQ. In particular we prove that the self-avoiding walk on the UIPQ is diffusive.
with Igor Kortchemski PDF
Published in Rand. Struct. Algo.

We study various models of random non-crossing configurations consisting of diagonals of convex polygons, and focus in particular on uniform dissections and non-crossing trees. For both these models, we prove convergence in distribution towards Aldous' Brownian triangulation of the disk. In the case of dissections, we also refine the study of the maximal vertex degree and validate a conjecture of Bernasconi, Panagiotou and Steger. Our main tool is the use of an underlying Galton-Watson tree structure.
with Laurent Ménard and Grégory Miermont PDF
Published in Lat. Am. J. Probab. Math. Stat.

We introduce a new construction of the Uniform Infinite Planar Quadrangulation (UIPQ). Our approach is based on an extension of the Cori-Vauquelin-Schaeffer mapping in the context of infinite trees, in the spirit of previous work. However, we release the positivity constraint on the labels of trees which was imposed in these references, so that our construction is technically much simpler. This approach allows us to prove the conjectures of Krikun pertaining to the "geometry at infinity" of the UIPQ, and to derive new results about the UIPQ, among which a fine study of infinite geodesics.
with Takis Konstantopoulos PDF
Published in J. Theoret. Probab.

Let $B_1,B_2, $... be independent one-dimensional Brownian motions defined over the whole real line such that $B_i(0)=0$. We consider the nth iterated Brownian motion $$W_n(t)= B_n(B_{n-1}(...(B_2(B_1(t)))...)).$$ Although the sequences of processes $(W_n)$ do not converge in a functional sense, we prove that the finite-dimensional marginals converge. As a consequence, we deduce that the random occupation measures of $W_n$ converge towards a random probability measure $\mu_\infty$. We then prove that $\mu_\infty$ almost surely has a continuous density which must be thought of as the local time process of the infinite iteration of independent Brownian motions.
PDF
Published in Comb. Probab. Comp.

We prove that the rescaled costs of partial match queries in a random two-dimensional quadtree converge almost surely towards a random limit which is identified as the terminal value of a martingale. Our approach shares many similarities with the theory of self-similar fragmentations.
with Itai Benjamini PDF
Published in ECP

We use the concept of unimodular random graph to show that the branching simple random walk on $\mathbb{Z}^d$, indexed by a critical geometric Galton-Watson tree conditioned to survive is recurrent if and only if $d\leq4$.
with Wendelin Werner PDF
Published in J. EMS

We construct and study the unique random tiling of the hyperbolic plane into ideal hyperbolic triangles (with the three corners located on the boundary) that is invariant (in law) with respect to Moebius transformations, and possesses a natural spatial Markov property that can be roughly described as the conditional independence of the two parts of the triangulation on the two sides of the edge of one of its triangles.
with Yuval Peres PDF
Published in ECP

We consider multitype branching processes arising in the study of random laminations of the disk. We classify these processes according to their subcritical or supercritical behavior and provide Kolmogorov-type estimates in the critical case corresponding to the random recursive lamination process of Curien & Le Gall. The proofs use the infinite dimensional Perron-Frobenius theory and quasi-stationary distributions.
with Jean-François Le Gall and Grégory Miermont PDF
Published in Ann. Instit. Henri Poincaré

The cactus of a pointed graph is a discrete tree associated with this graph. Similarly, with every pointed geodesic metric space E, one can associate an $\mathbb{R}$-tree called the continuous cactus of E. We prove under general assumptions that the cactus of random planar maps distributed according to Boltzmann weights and conditioned to have a fixed large number of vertices converges in distribution to a limiting space called the Brownian cactus, in the Gromov-Hausdorff sense. Moreover, the Brownian cactus can be interpreted as the continuous cactus of the so-called Brownian map.
with Itai Benjamini PDF
Published in EJP

A stationary random graph is a random rooted graph whose distribution is invariant under re-rooting along the simple random walk. We adapt the entropy technique developed for Cayley graphs and show in particular that stationary random graphs of subexponential growth are almost surely Liouville, that is, admit no non constant bounded harmonic function. Applications include the uniform infinite planar quadrangulation and long-range percolation clusters.
with Adrien Joseph PDF
Published in J. Applied Probab.

We analyze the mean cost of the partial match queries in random two-dimensional quadtrees. The method is based on fragmentation theory. The convergence is guaranteed by a coupling argument of Markov chains, whereas the value of the limit is computed as the fixed point of an integral equation.
with Jean-François Le Gall PDF
Published in AOP

We introduce and study an infinite random triangulation of the unit disk that arises as the limit of several recursive models. This triangulation is generated by throwing chords uniformly at random in the unit disk and keeping only those chords that do not intersect the previous ones. After throwing infinitely many chords and taking the closure of the resulting set, one gets a random compact subset of the unit disk whose complement is a countable union of triangles. We show that this limiting random set has Hausdorff dimension $b+1$, where $$b=(\sqrt{17}-3)/2,$$ and that it can be described as the geodesic lamination coded by a random continuous function which is Hölder continuous with exponent $b-\varepsilon$, for every $\varepsilon>0$. We also discuss recursive constructions of triangulations of the n-gon that give rise to the same continuous limit when n tends to infinity.
with Itai Benjamini PDF
J. Europ. Combin.

The core of this note is the observation that links between circle packings of graphs and potential theory developed in Benjamini - Schramm and He - Schramm can be extended to higher dimensions. In particular, it is shown that every limit of finite graphs sphere packed in $\mathbb{R}^d$ with a uniformly-chosen root is d-parabolic. We then derive few geometric corollaries. E.g.\,every infinite graph packed in $\mathbb{R}^{d}$ has either strictly positive isoperimetric Cheeger constant or admits arbitrarily large finite sets W with boundary size which satisfies a d-dimensional isoperimetric inequality. Some open problems and conjectures are gathered at the end.
Le manuscrit de ma thèse réalisée sous la direction de Jean-Francois Le Gall est disponible ici.
Le manuscrit de mon HDR est disponible ici.