Home || Research || Teaching || CV || Contact

**Sharp Threshold for
K4-Percolation**

Graph bootstrap percolation is a variation of
bootstrap percolation introduced by Bollobás. Let
*H* be a graph. Edges are added to an initial graph *G=(V,E)* if
they are in a copy of *H* minus an edge, until no further edges can be
added. If eventually the complete graph on *V* is obtained, *G*
is said to *H*-percolate. We identify the sharp threshold for
*K4*-percolation on the Erdős–Rényi graph *G(n,p)*.
This refines an approximation due to Balogh, Bollobás and Morris, which
bounds the threshold up to multiplicative constants.

Submitted.

**Minimal Contagious Sets in Random
Graphs**

Bootstrap percolation with threshold
*r* on a graph *G=(V,E)* is the following process: Initially some
subset *I* of *V* is declared active. Subsequently, any vertex
with at least *r* active neighbours is activated. If all vertices in
*V* are eventually activated, we call *I* contagious for
*G*. We take *G* to be the Erdős–Rényi graph
*G(n,p)*. We obtain lower bounds for the size of the smallest contagious
sets, improving those recently obtained by Feige, Krivelevich and Reichman. A
key step is to identify the large deviations rate function for the number of
vertices eventually activated by small sets that are unlikely to be contagious.
This complements the central limit theorems of Janson, Łuczak,
Turova and Vallier, which describe the typical behaviour.

Joint work with Omer Angel.

**Thresholds for Contagious Sets in
Random Graphs**

For fixed *r*, we consider bootstrap
percolation with threshold *r* on the Erdős–Renyi graph
*G(n,p)*. We identify a threshold for *p* above which there is
with high probability a set of size *r* that can activate the entire
graph. This improves a result of Feige, Krivelevich and Reichman,
which gives bounds for this threshold, up to multiplicative constants. These
thresholds are closely related to the survival probabiliites of certain
time-varying branching processes, and we derive asymptotic formulae for these
survival probabilities which are interest in their own right. As an application
of our results, we also obtain an upper bound for the threshold for
*K4*-bootstrap percolation on *G(n,p)*, as studied by Balogh, Bollobás and
Morris.

Joint work with Omer Angel.

To appear in the *Annals of Applied
Probability*.

*Stability of Geodesics in the
Brownian Map*

The Brownian map is a random geodesic metric
space arising as the scaling limit of random planar maps. We strengthen the
confluence of geodesics phenomenon observed by Le Gall at the root of the map, and
with this, reveal several properties of its rich geodesic structure. Our main
result is the continuity of the cut locus at typical points. A small shift from
such a point results in a small, local modification to the cut locus. Moreover,
the cut locus is uniformly stable, in the sense that any two cut loci coincide
outside a closed, nowhere dense set of zero measure. We also classify the types
of geodesic networks that are dense in the Brownian map. For each
*k*=1,2,3,4,6,9, there is a dense set of pairs of points that are joined
by networks of exactly *k* geodesics and of a specific topological form.
We find the Hausdorff dimension of the set of pairs joined by each type of
network. All other geodesic networks are nowhere dense.

Joint work with Omer Angel and Grégory Miermont.

To appear in the *Annals of
Probability.*

*Lower Bounds for the Isoperimetric
Numbers of Random Regular Graphs*

The isoperimetric number of a graph is an
indicator of the notion generally called expansion. As mentioned by Hoory,
Linial and Wigderson, "there is great interest in the edge and vertex
expansion of sets of varying sizes." We obtain explicit bounds for the
expansion of sets with given size in random *d*-regular graphs, for all
*d*. We concentrate on the vertex version, which is more difficult and
less well studied than the edge version. Our results in the case of edge
expansion generalize the work of Bollobás.
We also study the asymptotics of our bounds for vertex and edge expansion, as
*d* tends to infinity.

Joint work with Nick Wormald.

Published in the *SIAM Journal on Discrete
Mathematics.*