Sunflower (mathematics)

(Redirected from Delta system lemma)
Unsolved problem in mathematics:
For any sunflower size, does every set of uniformly sized sets which is of cardinality greater than some exponential in the set size contain a sunflower?

In the mathematical fields of set theory and extremal combinatorics, a sunflower or -system[1] is a collection of sets in which all possible distinct pairs of sets share the same intersection. This common intersection is called the kernel of the sunflower.

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.

The naming arises from a visual similarity to the botanical sunflower, arising when a Venn diagram of a sunflower set is arranged in an intuitive way. Suppose the shared elements of a sunflower set are clumped together at the centre of the diagram, and the nonshared elements are distributed in a circular pattern around the shared elements. Then when the Venn diagram is completed, the lobe-shaped subsets, which encircle the common elements and one or more unique elements, take on the appearance of the petals of a flower.

The main research question arising in relation to sunflowers is: under what conditions does there exist a large sunflower (a sunflower with many sets) in a given collection of sets? The -lemma, sunflower lemma, and the Erdős-Rado sunflower conjecture give successively weaker conditions which would imply the existence of a large sunflower in a given collection, with the latter being one of the most famous open problems of extremal combinatorics.[2]

Formal definition

edit

Suppose   is a set system over  , 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, a set system or collection of sets   is a sunflower if all sets in   share the same common subset of elements. An element in   is either found in the common subset   or else appears in at most one of the   elements. No element of   is shared by just some of the   subset, but not others. Note that this intersection,  , may be empty; a collection of pairwise disjoint subsets is also a sunflower. Similarly, a collection of sets each containing the same elements is also trivially a sunflower.

Sunflower lemma and conjecture

edit

The study of sunflowers generally focuses on when set systems contain sunflowers, in particular, when a set system is sufficiently large to necessarily contain a sunflower.

Specifically, researchers analyze the function   for nonnegative integers  , which is defined to be the smallest nonnegative integer   such that, for any set system   such that every set   has cardinality at most  , if   has more than   sets, then   contains a sunflower of   sets. Though it is not obvious that such an   must exist, a basic and simple result of Erdős and Rado, the Delta System Theorem, indicates that it does.

Erdos-Rado Delta System Theorem(corollary of the Sunflower lemma):

For each  ,  , there is an integer   such that if a set system   of  -sets is of cardinality greater than  , then   contains a sunflower of size  .

In the literature,   is often assumed to be a set rather than a collection, so any set can appear in   at most once. By adding dummy elements, it suffices to only consider set systems   such that every set in   has cardinality  , so often the sunflower lemma is equivalently phrased as holding for " -uniform" set systems.[3]

Sunflower lemma

edit

Erdős & Rado (1960, p. 86) proved the sunflower lemma, which states that[4]

 

That is, if   and   are positive integers, then a set system   of cardinality greater than or equal to   of sets of cardinality   contains a sunflower with at least   sets.

The Erdős-Rado sunflower lemma can be proved directly through induction. First,  , since the set system   must be a collection of distinct sets of size one, and so   of these sets make a sunflower. In the general case, suppose   has no sunflower with   sets. Then consider   to be a maximal collection of pairwise disjoint sets (that is,   is the empty set unless  , and every set in   intersects with some  ). Because we assumed that   had no sunflower of size  , and a collection of pairwise disjoint sets is a sunflower,  .

Let  . Since each   has cardinality  , the cardinality of   is bounded by  . Define   for some   to be

 

Then   is a set system, like  , except that every element of   has   elements. Furthermore, every sunflower of   corresponds to a sunflower of  , simply by adding back   to every set. This means that, by our assumption that   has no sunflower of size  , the size of   must be bounded by  .

Since every set   intersects with one of the  's, it intersects with  , and so it corresponds to at least one of the sets in a  :

 

Hence, if  , then   contains an   set sunflower of size   sets. Hence,   and the theorem follows.[2]

Erdős-Rado sunflower conjecture

edit

The sunflower conjecture is one of several variations of the conjecture of Erdős & Rado (1960, p. 86) that for each  ,   for some constant   depending only on  . The conjecture remains wide open even for fixed low values of  ; for example  ; it is not known whether   for some  .[5] A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that   for  .[6][7] A month after the release of the first version of their paper, Rao sharpened the bound to  ;[8] the current best-known bound is  .[9]


Sunflower lower bounds

edit

Erdős and Rado proved the following lower bound on  . It is equal to the statement that the original sunflower lemma is optimal in  .

Theorem.  

Proof. For   a set of   sequence of distinct elements is not a sunflower. Let   denote the size of the largest set of  -sets with no   sunflower. Let   be such a set. Take an additional set of   elements and add one element to each set in one of   disjoint copies of  . Take the union of the   disjoint copies with the elements added and denote this set  . The copies of   with an element added form an   partition of  . We have that, .   is sunflower free since any selection of   sets if in one of the disjoint partitions is sunflower free by assumption of H being sunflower free. Otherwise, if   sets are selected from across multiple sets of the partition, then two must be selected from one partition since there are only   partitions. This implies that at least two sets and not all the sets will have an element in common. Hence this is not a sunflower of   sets.

A stronger result is the following theorem:

Theorem.  

Proof. Let   and   be two sunflower free families. For each set   in F, append every set in   to   to produce   many sets. Denote this family of sets  . Take the union of   over all   in  . This produces a family of   sets which is sunflower free.

The best existing lower bound for the Erdos-Rado Sunflower problem for   is  , due to Abott, Hansen, and Sauer.[10][11] This bound has not been improved in over 50 years.

Applications of the sunflower lemma

edit

The sunflower lemma has numerous applications in theoretical computer science. For example, in 1986, Razborov used the sunflower lemma to prove that the Clique language required   (superpolynomial) size monotone circuits, a breakthrough result in circuit complexity theory at the time. Håstad, Jukna, and Pudlák used it to prove lower bounds on depth-    circuits. It has also been applied in the parameterized complexity of the hitting set problem, to design fixed-parameter tractable algorithms for finding small sets of elements that contain at least one element from a given family of sets.[12]

Analogue for infinite collections of sets

edit

A version of the  -lemma which is essentially equivalent to the Erdős-Rado  -system theorem states that a countable collection of k-sets contains a countably infinite sunflower or  -system.

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, S2CID 201314765
  • Bell, Tolson; Chueluecha, Suchakree; Warnke, Lutz (2021), "Note on Sunflowers", Discrete Mathematics, 344 (7): 112367, arXiv:2009.09327, doi:10.1016/j.disc.2021.112367, MR 4240687, S2CID 221818818
  • 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, S2CID 14043028
  • 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
  • Flum, Jörg; Grohe, Martin (2006), "A Kernelization of Hitting Set", Parameterized Complexity Theory, EATCS Ser. Texts in Theoretical Computer Science, Springer, pp. 210–212, doi:10.1007/3-540-29953-X, ISBN 978-3-540-29952-3, MR 2238686
  • Jech, Thomas (2003), Set Theory, Springer
  • Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, North-Holland, ISBN 978-0-444-85401-8
  • Rao, Anup (2020-02-25), "Coding for Sunflowers", Discrete Analysis, 2020 (2): 11887, doi:10.19086/da.11887, S2CID 202558957
  • Rao, Anup (2023), "Sunflowers: from soil to oil" (PDF), Bull. Amer. Math. Soc., 60 (1): 29–38, doi:10.1090/bull/1777
  • Shanin, N. A. (1946), "A theorem from the general theory of sets", C. R. (Doklady) Acad. Sci. URSS, New Series, 53: 399–400
  • Tao, Terence (2020), The sunflower lemma via Shannon entropy, What's new (personal blog)
edit

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. ^ a b "Extremal Combinatorics III: Some Basic Theorems". Combinatorics and more. 28 September 2008. Retrieved 2021-12-10.
  3. ^ Alweiss et al. (2020), p. 3.
  4. ^ Kostochka, Alexandr V. (2000), Althöfer, Ingo; Cai, Ning; Dueck, Gunter; Khachatrian, Levon (eds.), "Extremal Problems on Δ-Systems", Numbers, Information and Complexity, Boston, MA: Springer US, pp. 143–150, doi:10.1007/978-1-4757-6048-4_14, ISBN 978-1-4757-6048-4, retrieved 2022-05-02
  5. ^ Abbott, H.L; Hanson, D; Sauer, N (May 1972). "Intersection theorems for systems of sets". Journal of Combinatorial Theory, Series A. 12 (3): 381–389. doi:10.1016/0097-3165(72)90103-3.
  6. ^ Alweiss et al. (2020).
  7. ^ "Quanta Magazine - Illuminating Science". Quanta Magazine. Retrieved 2019-11-10.
  8. ^ Rao (2020).
  9. ^ Bell, Chueluecha & Warnke (2021).
  10. ^ Abbott, H.L; Hanson, D; Sauer, N (May 1972). "Intersection theorems for systems of sets". Journal of Combinatorial Theory, Series A. 12 (3): 381–389. doi:10.1016/0097-3165(72)90103-3.
  11. ^ Lower Bounds for the Sunflower Problem https://mathoverflow.net/a/420288/12176
  12. ^ Flum & Grohe (2006).