BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:Sharp thresholds for sparse functions with applica
tions to extremal combinatorics - Noam Lifshitz (H
ebrew University)
DTSTART:20191003T130000Z
DTEND:20191003T140000Z
UID:TALK3898AT
URL:/talk/index/3898
DESCRIPTION: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 p
robability that f=1 on an input with independent c
oordinates\, each taking the value 1 with probabil
ity p. \n\nThe dense regime\, where μ_p(f)=Θ(1)\,
is somewhat understood due to seminal works by Bou
rgain\, Friedgut\, Hatami\, and Kalai. On the oth
er hand\, the sparse regime where μ_p(f)=o(1) was
out of reach of the available methods. However\, t
he potential power of the sparse regime was envisi
oned by Kahn and Kalai already in 2006.\n\nIn this
talk we show that if a monotone Boolean function
f with μ_p(f)=o(1) satisfies some mild pseudo-rand
omness conditions then it exhibits a sharp thresho
ld in the interval [p\,q]\, with q = p+o(p). More
specifically\, our mild pseudo-randomness hypothes
is is that the p-biased measure of f does not bump
up to Θ(1) whenever we restrict f to a sub-cube o
f constant co-dimension\, and our conclusion is th
at we can find q=p+o(p)\, such that μ_p(f)=o(μ_q(f
)) \n\nAt its core\, this theorem stems from a n
ovel hypercontactive theorem for Boolean functions
satisfying pseudorandom conditions\, which we cal
l `small generalized influences'. This result take
s on the role of the usual hypercontractivity theo
rem\, but is significantly more effective in the r
egime where p = o(1). \n\nWe demonstrate the power
of our sharp threshold result by reproving the re
cent breakthrough result of Frankl on the celebrat
ed Erdos matching conjecture\, and by proving conj
ectures of Huang--Loh--Sudakov and Furedi--Jiang f
or a new wide range of the parameters.\n\nBased on
a joint work with Peter Keevash\, Eoin Long\, and
Dor Minzer.
LOCATION:Watson LTB
CONTACT:Eoin Long
END:VEVENT
END:VCALENDAR