Keith Frankston, Rutgers University

Abstract

Given an increasing family F of subsets of a finite set X, its measure according to mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. These thresholds have been a central focus of the study of random discrete structures, with estimation of thresholds for specific properties the subject of some of the most challenging work in the area.

In 2006, Kahn and Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we call the ``expectation-threshold'') for p_c is never far from its actual value. We prove a fractional version (proposed by Talagrand) of this so called ``expectation-threshold'' conjecture showing that for any increasing family we have p_c(F) = O(q_f(F) log ell(F)), where q_f is the ``fractional expectation-threshold'' and ell(F) is the maximum size of a minimal element of F.

This result easily implies previously difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ``Sunflower Conjecture.''

Joint with Jeff Kahn, Bhargav Narayanan, and Jinyoung Park.