Title: Randomized algorithms, well-spread distributions, and robust thresholds
Abstract: Finding thresholds has been a central study in random (hyper)graph theory since the field's inception. Traditionally, lower bounds follow from a general and straightforward first moment calculation whereas upper bounds involve a more difficult and problem-specific argument.
The recent proof of the fractional Kahn--Kalai conjecture, by Frankston, Kahn, Narayanan, and Park (with the full conjecture subsequently proved by Pham and Park) relates the lower and upper bounds via the notion of "well-spread distributions". These are distributions on graphs with the desired property that exhibit only weak correlations between the appearance of different edges. For many properties (such as bounded-degree spanning trees and high-dimensional perfect matchings) the uniform distribution is easily seen to be well-spread. However, for many natural properties (such as a 3-uniform hypergraph containing a spanning Steiner triple system) we lack the necessary tools to analyze the uniform distribution.
I will show how randomized algorithms can be harnessed to construct (non-uniform) distributions with the desired spread. I will focus on the phenomenon that as soon as a graph satisfies the minimum degree condition for some property P (such as containing a perfect matching or bounded-degree spanning tree) then it is also robust for P in the sense that a percolation of its edges fails to satisfy P only at the same density that G(n;p) fails to satisfy P as well.
Based on joint work with Huy Tuan Pham, Ashwin Sah, and Mehtaab Sawhney.