Sunflower (mathematics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 -system is a collection of sets whose pairwise intersection is constant, and called the kernel.

The -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 "-system". More recently the term "sunflower", possibly introduced by Deza & Frankl (1981), has been gradually replacing it.

Formal definition[edit]

Suppose is a universe set and is a collection of subsets of . The collection is a sunflower (or -system) if there is a subset of such that for each distinct and in , we have . In other words, is a sunflower if the pairwise intersection of each set in is constant.

Δ-lemma[edit]

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

The -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 ω2[edit]

If is an -sized collection of countable subsets of , and if the continuum hypothesis holds, then there is an -sized -subsystem. Let enumerate . For , let . By Fodor's lemma, fix stationary in such that is constantly equal to on . Build of cardinality such that whenever are in then . Using the continuum hypothesis, there are only -many countable subsets of , so by further thinning we may stabilize the kernel.

Sunflower lemma and conjecture[edit]

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

References[edit]