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 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 ω2

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 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 b! can be replaced by C^b for some constant C.

References

This article is issued from Wikipedia - version of the Tuesday, December 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.