Brett Kolesnik

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.

PDF || arXiv


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.

Submitted.

PDF || arXiv


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.

PDF || arXiv


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.

PDF || arXiv


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.

PDF || arXiv || Journal