Combinatorics: Noam Lifshitz, BIU, "Sharp thresholds for sparse functions with applications to extremal combinatorics."

Speaker: Noam Lifshitz, BIU Title: Sharp thresholds for sparse functions with applications to extremal combinatorics. Abstract: The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function $f$ to satisfy $\mu_{p}(f)=o(\mu_{q}(f))$, where $q = p + o(p)$, and $\mu_{p}(f)$ is the probability that $f=1$ on an input with independent coordinates, each taking the value $1$ with probability $p$. The dense regime, where $\mu_{p}(f)=\Theta(1)$, is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where $\mu_{p}(f)=o(1)$ was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006. In this talk we show that if a monotone Boolean function $f$ with $\mu_{p}(f)=o(1)$ satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval $[p,q]$, with $q = p+o(p)$. More specifically, our mild pseudo-randomness hypothesis is that the $p$-biased measure of $f$ does not bump up to $\Theta(1)$ whenever we restrict $f$ to a sub-cube of constant co-dimension, and our conclusion is that we can find $q=p+o(p)$, such that $\mu_p(f)=o(\mu_q(f))$ At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences'. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where $p = o(1)$. We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang--Loh--Sudakov and Furedi--Jiang for a new wide range of the parameters. Based on a joint work with Keevash, Long, and Minzer.

Date: 

Mon, 29/10/2018 - 11:00 to 13:00

Location: 

Rothberg CS blgd, room B500, Safra campus, Givat, Ram