A sunflower with $r$ petals is a collection of $r$ sets so that the
intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ...
more >>>
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes ... more >>>
We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $\smash{2^{n^{\Omega(1)}}}$. This improves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.
more >>>