Computer Science/Discrete Mathematics Seminar II
Sharp Thresholds and Extremal Combinatorics
To connect to the CSDM Seminar via Zoom, please do the following:
1 - If you have Zoom installed on your device, enter the following meeting ID: 360043913 , click Join Meeting.
2 - If you do not have Zoom installed, click the following link to download and install: https://theias.zoom.us/j/360043913
3 - Once installed, click the very same link to connect to the meeting.
Consider the p-biased distribution over ${0,1}^n$, 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.