In mathematics, a sunflower or \( \Delta \) -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 \( \Delta \) -lemma, sunflower lemma, and sunflower conjecture give various conditions that imply the existence of a large sunflower in a given collection of sets.
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.
Formal definition
Suppose W is a set system, that is, a collection of subsets of a set 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. Note that this intersection, S, may be empty; a collection of disjoint subsets is also a sunflower.
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 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. A 2020 paper by Alweiss, Lovett, Wu, and Jiapeng Zhang gave a breakthrough towards the conjecture, Rao subsequently made a small improvement proving the result for \( {\displaystyle C=O(\log(ab))} \) (Alweiss et al. 2020)[2] (Rao 2020)[3].
Analogue for infinite collections of sets
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).
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 \( {\displaystyle \operatorname {cf} (\alpha )=\omega _{1}} \) , let \( {\displaystyle f(\alpha )=\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 \( {\displaystyle 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.
See also
Cap set
References
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
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.
"Quanta Magazine - Illuminating Science". Quanta Magazine. Retrieved 2019-11-10.
https://discreteanalysisjournal.com/article/11887-coding-for-sunflowers. Retrieved 2020-08-19.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
