The next TCS+ talk will take place this coming Wednesday, October 2th (next week!) at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shachar Lovett from UCSD will lead us “Towards the sunflower conjecture” (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: A sunflower with petals is a collection of sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed , any family of sets of size , with at least about sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to for some constant . Despite much research, the best bounds until recently were all of the order of for some constant c. In this work, we improve the bounds to about .
There are two main ideas that underlie our result. The first is a structure vs pseudo-randomness paradigm, a commonly used paradigm in combinatorics. This allows us to either exploit structure in the given family of sets, or otherwise to assume that it is pseudo-random in a certain way. The second is a duality between families of sets and DNFs (Disjunctive Normal Forms). DNFs are widely studied in theoretical computer science. One of the central results about them is the switching lemma, which shows that DNFs simplify under random restriction. We show that when restricted to pseudo-random DNFs, much milder random restrictions are sufficient to simplify their structure.
Joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.