Sunflower (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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[1] is a collection of sets whose pairwise intersection is constant. This constant intersection is called the kernel of the sunflower.

The main research question related to sunflowers is: under what conditions does there exist a large sunflower (a sunflower with many sets)? The -lemma, sunflower lemma, and sunflower conjecture give various conditions that imply the existence of a large sunflower in a given collection of sets.

Formal definition[edit]

Suppose is a set system, that is, a collection of subsets of a set . 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. Note that this intersection, , may be empty; a collection of disjoint subsets is also a sunflower.

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 . A 2020 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving the result for (Alweiss et al. 2020).[2]

Analogue for infinite collections of sets[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).

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.

See also[edit]

References[edit]

  • Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (June 2020), "Improved bounds for the sunflower lemma", Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, pp. 624–630, arXiv:1908.08483, doi:10.1145/3357713.3384234, ISBN 978-1-4503-6979-4
  • 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 0637827
  • 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 978-0-444-85401-8
  • Shanin, N. A. (1946), "A theorem from the general theory of sets", C. R. (Doklady) Acad. Sci. URSS (N.S.), 53: 399–400
  • Tao, Terence (2020), The sunflower lemma via Shannon entropy, What's new (personal blog)

Notes[edit]

  1. ^ The original term for this concept was "-system". More recently the term "sunflower", possibly introduced by Deza & Frankl (1981), has been gradually replacing it.
  2. ^ "Quanta Magazine - Illuminating Science". Quanta Magazine. Retrieved 2019-11-10.