Simons Collaboration on Algorithms and Geometry Monthly Meeting, February 2021

Date & Time


1:00 – 3:00 PM

  • 1:00 -1:55 PMShachar Lovett
    The Sunflower Conjecture: Part 1
    (Background, related results, general approach, etc)
    1:55 - 2:00 PMBreak
    2:00 - 3:00 PMShachar Lovett
    The Sunflower Conjecture: Part 2
    (Proof details)
  • Shachar Lovett
    The Sunflower Conjecture

    The sunflower conjecture is a famous open problem in combinatorics, asked by Erdos and Rado in 1960. A sunflower is a collection of sets with the same pairwise intersection pattern. The conjecture asks if given a large enough family of sets, it must contain a sunflower. Erdos and Rado proved that this is indeed true, but they conjectured that the quantitative bounds that they showed can be improved. In the last 60 years, many applications of sunflowers were found (both in math and in CS), but the original bounds were not significantly improved. I will describe recent work that gives a significant improvement to the quantitative bounds, getting closer to the conjectured bound.

    Surprisingly, the proof techniques turned out to have applications in other domains, such as random graph theory (proving the “fractional expectations conjecture” of Talagrand), and DNF compression in complexity theory. The talk will be composed of two parts:

    • Part 1 – general background, general proof strategy, and connection to these other fields
    • Part 2 – detailed proof

    No background knowledge is assumed.

    Based on joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.

Videos

February 19, 2021

Shachar Lovett- The Sunflower Conjecture: Part 1

Shachar Lovett- The Sunflower Conjecture: Part 2

Subscribe to MPS announcements and other foundation updates