University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Sharp thresholds for sparse functions with applications to extremal combinatorics

## Sharp thresholds for sparse functions with applications to extremal combinatoricsAdd 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:Note that ex-directory lists are not shown. |
## Other listsEPS - College Research and KT Support Activities Analysis Seminar Analysis Reading Seminar 2019/2020## Other talksRSC 2019 Dalton Emerging Researcher Award Lecture The Leech Lattice and the Conway Groups Evaluation of sources of intelligence using a multi-armed bandit framework Subgroups of the Monster Privileged side-channel attacks for enclave adversaries The Griess Algebra and the Monster |