Sharp Thresholds and Extremal Combinatorics

Sharp Thresholds and Extremal Combinatorics - Dor Minzer

Dor Minzer
Member, Institute for Advanced Study
March 17, 2020
Consider the p-biased distribution over 0,1n, in which each coordinate independently is sampled according to a p-biased bit. A sharp-threshold result studies the behavior of Boolean functions over the hypercube under different p-biased measures, and in particular whether the function experiences a phase transition between two, close p's. While the theory of sharp-thresholds is well understood for p's that are bounded away from 0 and 1, it is much less so for values of p that are close to 0 or 1.

In this talk, we will first discuss classical sharp-threshold results, and demonstrate an application of them in Extremal Combinatorics [Dinur-Friedgut]. We will then discuss newer sharp-threshold results. Time permitting, we will mention applications to two problems in extremal combinatorics: the Erdos matching conjecture, and the problem of determining the largest family of vectors in [m]^n that avoids a fixed, constant-sized intersections.

Based on joint works with Peter Keevash, Noam Lifshitz and Eoin Long.