Sunflower (mathematics)

A mathematical sunflower can be pictured as a flower. The kernel of the sunflower is the brown part in the middle, and each set of the sunflower is the union of a petal and the kernel.

In mathematics, a sunflower or $\Delta$-system is a collection of sets whose pairwise intersection is constant, and called the kernel.

The $\Delta$-lemma, sunflower lemma, and sunflower conjecture give various conditions that imply the existence of a large sunflower in a given collection of sets.

The original term for this concept was "$\Delta$-system". More recently the term "sunflower", possibly introduced by Deza & Frankl (1981), has been gradually replacing it.

Formal definition

Suppose $U$ is a universe set and $W$ is a collection of subsets of $U$. The collection $W$ is a sunflower (or $\Delta$-system) if there is a subset $S$ of $U$ such that for each distinct $A$ and $B$ in $W$, we have ${\displaystyle A\cap B=S}$. In other words, $W$ is a sunflower if the pairwise intersection of each set in $W$ is constant.

Δ-lemma

The $\Delta$-lemma states that every uncountable collection of finite sets contains an uncountable $\Delta$-system.

The $\Delta$-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. It was introduced by Shanin (1946).

Δ-lemma for ω₂

If $W$ is an $\omega _{2}$-sized collection of countable subsets of $\omega _{2}$, and if the continuum hypothesis holds, then there is an $\omega _{2}$-sized $\Delta$-subsystem. Let $\langle A_{\alpha }:\alpha <\omega _{2}\rangle$ enumerate $W$. For ${{\rm {cf}}}(\alpha )=\omega _{1}$, let $f(\alpha )={{\rm {sup}}}(A_{\alpha }\cap \alpha )$. By Fodor's lemma, fix $S$ stationary in $\omega _{2}$ such that $f$ is constantly equal to $\beta$ on $S$. Build $S'\subseteq S$ of cardinality $\omega _{2}$ such that whenever $i<j$ are in $S'$ then $A_{i}\subseteq j$. Using the continuum hypothesis, there are only $\omega _{1}$-many countable subsets of $\beta$, so by further thinning we may stabilize the kernel.

Sunflower lemma and conjecture

Erdős & Rado (1960, p. 86) proved the sunflower lemma, stating that if $a$ and $b$ are positive integers then a collection of ${\displaystyle b!a^{b+1}}$ sets of cardinality at most $b$ contains a sunflower with more than $a$ sets. The sunflower conjecture is one of several variations of the conjecture of (Erdős & Rado 1960, p. 86) that the factor of ${\displaystyle b!}$ can be replaced by ${\displaystyle C^{b}}$ for some constant $C$.

References

• Deza, M.; Frankl, P. (1981), "Every large set of equidistant (0,+1,–1)-vectors forms a sunflower", Combinatorica, 1 (3): 225–231, doi:10.1007/BF02579328, ISSN 0209-9683, MR 637827
• Erdős, Paul; Rado, R. (1960), "Intersection theorems for systems of sets", Journal of the London Mathematical Society, Second Series, 35 (1): 85–90, doi:10.1112/jlms/s1-35.1.85, ISSN 0024-6107, MR 0111692
• Jech, Thomas (2003). Set Theory. Springer.
• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0.
• Shanin, N. A. (1946), "A theorem from the general theory of sets", C. R. (Doklady) Acad. Sci. URSS (N.S.), 53: 399–400