Sunflower (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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?

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 the mathematical fields of set theory and extremal combinatorics, 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 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 the pairwise intersection of each set in is identical. 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 clear 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:[citation needed]

For each , is an integer such that 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 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 . It is known that . [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]

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.[9]

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
  • 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
  • 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, 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: 11887, doi:10.19086/da.11887
  • 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)

External links[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. 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. ^ "Intersection theorems for systems of sets". sciencedirect.com. Retrieved 2021-12-10.
  6. ^ Alweiss et al. (2020).
  7. ^ "Quanta Magazine - Illuminating Science". Quanta Magazine. Retrieved 2019-11-10.
  8. ^ Rao (2020).
  9. ^ Flum & Grohe (2006).