Sunflower (mathematics)
In the mathematical fields of set theory and extremal combinatorics, a sunflower or
This common intersection is called the kernel of the sunflower.
The naming arises from a visual similarity to the botanical sunflower, arising when a Venn diagram of a sunflower set is arranged in an intuitive way.
Then when the Venn diagram is completed, the lobe-shaped subsets, which encircle the common elements and one or more unique elements, take on the appearance of the petals of a flower.
-lemma, sunflower lemma, and the Erdős-Rado sunflower conjecture give successively weaker conditions which would imply the existence of a large sunflower in a given collection, with the latter being one of the most famous open problems of extremal combinatorics.
, may be empty; a collection of pairwise disjoint subsets is also a sunflower.
Similarly, a collection of sets each containing the same elements is also trivially a sunflower.
must exist, a basic and simple result of Erdős and Rado, the Delta System Theorem, indicates that it does.
Erdos-Rado Delta System Theorem(corollary of the Sunflower lemma): For each
By adding dummy elements, it suffices to only consider set systems
, so often the sunflower lemma is equivalently phrased as holding for "
[3] Erdős & Rado (1960, p. 86) proved the sunflower lemma, which states that[4] That is, if
are positive integers, then a set system
The Erdős-Rado sunflower lemma can be proved directly through induction.
to be a maximal collection of pairwise disjoint sets (that is,
, and a collection of pairwise disjoint sets is a sunflower,
The conjecture remains wide open even for fixed low values of
[5] A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that
[6][7] A month after the release of the first version of their paper, Rao sharpened the bound to
[9] Erdős and Rado proved the following lower bound on
It is equal to the statement that the original sunflower lemma is optimal in
disjoint copies with the elements added and denote this set
The best existing lower bound for the Erdos-Rado Sunflower problem for
The sunflower lemma has numerous applications in theoretical computer science.
For example, in 1986, Razborov used the sunflower lemma to prove that the Clique language required
(superpolynomial) size monotone circuits, a breakthrough result in circuit complexity theory at the time.
Håstad, Jukna, and Pudlák used it to prove lower bounds on depth-
It has also been applied in the parameterized complexity of the hitting set problem, to design fixed-parameter tractable algorithms for finding small sets of elements that contain at least one element from a given family of sets.
-lemma is a combinatorial set-theoretic tool used in proofs to impose an upper bound on the size of a collection of pairwise incompatible elements in a forcing poset.
It may for example be used as one of the ingredients in a proof showing that it is consistent with Zermelo–Fraenkel set theory that the continuum hypothesis does not hold.
