Sharp thresholds for sparse functions with applications to extremal combinatorics

Add to your list(s) Download to your calendar using vCal

• Noam Lifshitz (Hebrew University)
• Thursday 03 October 2019, 14:00-15:00
• Watson LTB.

If you have a question about this talk, please contact Eoin Long.

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 μ_p(f)=o(μ_q(f)), where q = p + o(p), and μ_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 μ_p(f)=Θ(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where μ_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was envisioned by Kahn and Kalai already in 2006.

In this talk we show that if a monotone Boolean function f with μ_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 Θ(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 μ_p(f)=o(μ_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 Peter Keevash, Eoin Long, and Dor Minzer.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTB

Note that ex-directory lists are not shown.