Let me mention two talks with very promising news by friends of the blog, Karim Adiprasito and Noam Lifshitz. As always, with the beginning of the academic year there are a lot of exciting activities, things are rather hectic around, and I hear a lot of exciting things (both news and things I was supposed to know long ago). I am quite sure that we will return to the topics of the two lectures in later posts and I also welcome discussing them in the comment section. (A few related older posts for Karim’s talk and seminar: F ≤ 4E; Beyond the g-conjecture. and for Noam’s seminar: Influence, Threshold and Noise; Boolean functions: Influence, threshold and noise; .)
Karim Adiprasito’s colloquium talks and course
HUJI Thu, 25/10/2018 – 14:30 to 15:30; TAU 29/10/2018 12:15-13:15
Combinatorics, topology and the standard conjectures beyond positivity
Abstract: Consider a simplicial complex that allows for an embedding into . How many faces of dimension or higher can it have? How dense can they be? This basic question goes back to Descartes. Using it and other rather fundamental combinatorial problems, I will motivate and introduce a version of Grothendieck’s “standard conjectures” beyond positivity (which will be explored in detail in the Sunday Seminar). All notions used will be explained in the talk (I will make an effort to be very elementary)
Sunday’s seminar refer to a HUJI Kazhdan seminar given by Karim on this topic. (3-5 Ross building’s seminar room.) This is a good opportunity to congratulate Karim Adiprasito and June Huh on receiving the New Horizon Prize, and congratulations also to Vincent Lafforgue who received the breakthrough prize and to all the other winners!
Noam Lifshitz’ combinatorics seminar
When: Monday Oct.29, 11:00–12:45
Where: Rothberg CS building, room B500, Safra campus, Givat Ram
Sharp thresholds for sparse functions with applications to extremal combinatorics. (based on a joint work by Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.)
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, where , and is the probability that on an input with independent coordinates, each taking the value 1 with probability p.
The dense regime, where , is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where 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 satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval , with . 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 such that .
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
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.
Alef: Koebe’s Karnaf