Research

Consider a supercritical Bienaymé--Galton--Watson tree T  with geometric offspring distribution. Each vertex of this tree represents a parking spot which can accommodate at most one car. On the top of this tree, we add (Au : u ∈ T ) i.i.d. non negative integers sampled according to a given law μ, which are the car arrivals on T.  Each car tries to park on its arriving vertex and if the spot is already occupied, it drives towards the root and takes the first available spot. If no spot is found, then it exits the tree without parking. In this paper, we provide a criterion to determine the phase of the parking process (subcritical, critical, or supercritical) depending on the generating function of μ.

Consider a rooted tree on the top of which we let cars arrive on its vertices. Each car tries to park on its arriving vertex but if it is already occupied, it drives towards the root of the tree and parks as soon as possible. In this article, we establish a natural coupling between the parking process on trees with prescribed degrees and an oriented configuration model. As a consequence, we recover the location of the phase transition for parking on critical Bienaymé--Galton--Watson trees already proven by Curien and Hénard, and Contat. 

We consider the problem of finding the initial vertex (Adam) in a Barabási--Albert tree process  ( Tn  : n ⩾ 1) at large times. More precisely, given ε>0, one wants to output a subset Pε(n) of  vertices of  Tn so that the initial vertex belongs  to Pε(n) with probability at least 1- ε when n is large. It has been shown by Bubeck, Devroye & Lugosi, refined later  by Banerjee & Huang,  that one needs to output at least ε-1+o(1) and at most ε-1+o(1) vertices to succeed. We prove that the exponent in the lower bound is sharp and the key idea is that Adam is either a "large degree" vertex or is a neighbor of a "large degree" vertex (Eve). 

We study the Karp-Sipser core of a random graph made of a configuration model with vertices of degree 1,2 and 3. This core is obtained by recursively removing the leaves as well as their unique neighbors in the graph. We settle a conjecture of Bauer & Golinelli and prove that at criticality, the Karp-Sipser core has size ≈ cste θ-2 n3/5  where θ is the hitting time of the curve t ↦ t-2 by a linear Brownian motion started at 0. Our proof relies on a detailed multi-scale analysis of the Markov chain associated to Karp-Sipser leaf-removal algorithm close to its extinction time.

Let (Au : u ∈ 𝔹) be i.i.d. non-negative integers that we interpret as car arrivals on the vertices of the full binary tree 𝔹. Each car tries to park on its arrival node, but if it is already occupied, it drives towards the root and parks on the first available spot. It is known that the parking process on 𝔹 exhibits a phase transition in the sense that either a finite number of cars do not manage to park in expectation (subcritical regime) or all vertices of the tree contain a car and infinitely many cars do not manage to park (supercritical regime). We characterize those regimes in terms of the law of A in an explicit way. We also study in detail the critical regime as well as the phase transition which turns out to be “discontinuous”.

We give new equations which characterize the generating functions of planar quadrangulations and planar triangulations, with zero, one or two boundaries. The proof is inspired by the Lackner–Panholzer last car decomposition of parking trees (arXiv:1504.04972) and consists in applying a similar decomposition to the peeling trees of planar maps.

Consider a uniform rooted Cayley tree Tn with n vertices and let m cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. Lackner & Panholzer (arXiv:1504.04972) established a phase transition for this process when m ≈ n/2. In this work, we couple this model with a variant of the classical Erdös-Rényi random graph process. This enables us to describe the phase transition for the size of the components of parked cars using a modification of the multiplicative coalescent which we name the frozen multiplicative coalescent. The geometry of critical parked clusters is also studied. Those trees are very different from Bienaymé-Galton-Watson trees and should converge towards the growth-fragmentation trees canonically associated to the 3/2-stable process that already appeared in the study of random planar maps.

We prove a surprising symmetry between the law of the size Gn of the greedy independent set on a uniform Cayley tree Tn of size n and that of its complement. We show that Gn has the same law as the number of vertices at even height in Tn  rooted at a uniform vertex. This enables us to compute the exact law of the Gn. We also give a Markovian construction of the greedy independent set, which highlights the symmetry of Gn and whose proof uses a new Markovian exploration of rooted Cayley trees which is of independent interest.

Recently, a phase transition phenomenon has been established for parking on random trees. We extend the results of Curien and Hénard on general Galton--Watson trees and allow different car arrival distributions depending on the vertex outdegrees. We then prove that this phase transition is sharp by establishing a large deviations result for the flux of exiting cars. This has consequences on the offcritical geometry of clusters of parked spots which displays similarities with the classical Erdős-Renyi random graph model.