In the mathematical fields of set theory and extremal combinatorics, a sunflower or Δ {\displaystyle \Delta } -system is a collection of sets in which the intersection of any two distinct sets is the same. This common intersection is called the kernel of the sunflower. 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 Δ {\displaystyle \Delta } -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.
Formal definition Suppose W {\displaystyle W} is a set system over U {\displaystyle U} , that is, a collection of subsets of a set U {\displaystyle U} . The collection W {\displaystyle W} is a sunflower (or Δ {\displaystyle \Delta } -system) if there is a subset S {\displaystyle S} of U {\displaystyle U} such that for each distinct A {\displaystyle A} and B {\displaystyle B} in W {\displaystyle W} , we have A ∩ B = S {\displaystyle A\cap B=S} . In other words, a set system or collection of sets W {\displaystyle W} is a sunflower if all sets in W {\displaystyle W} share the same common subset of elements. An element in U {\displaystyle U} is either found in the common subset S {\displaystyle S} or else appears in at most one of the W {\displaystyle W} elements. No element of U {\displaystyle U} is shared by just some of the W {\displaystyle W} subset, but not others.
Basic examples If W {\displaystyle W} contains 0, 1, or 2 subsets, then it is vacuously a sunflower. If W {\displaystyle W} contains disjoint subsets, then it is a sunflower, with an empty kernel.
Sunflower lemma and conjecture 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 f ( k , r ) {\displaystyle f(k,r)} for nonnegative integers k , r {\displaystyle k,r} , which is defined to be the smallest nonnegative integer n {\displaystyle n} such that, for any set system W {\displaystyle W} such that every set S ∈ W {\displaystyle S\in W} has cardinality at most k {\displaystyle k} , if W {\displaystyle W} has more than n {\displaystyle n} sets, then W {\displaystyle W} contains a sunflower of r {\displaystyle r} sets. Though it is not obvious that such an n {\displaystyle n} must exist, a basic and simple result of Erdős and Rado, the Delta System Theorem, indicates that it does.
An alternative to f ( k , r ) {\displaystyle f(k,r)} is sometimes used, S u n ( k , r ) {\displaystyle Sun(k,r)} , where f ( k , r ) = S u n ( k , r ) − 1 {\displaystyle f(k,r)=Sun(k,r)-1} . This is the same as saying if F {\displaystyle F} is of cardinality greater than or equal to S u n ( k , r ) {\displaystyle Sun(k,r)} , then F {\displaystyle F} contains a sunflower of size r {\displaystyle r} . In the literature, W {\displaystyle W} is often assumed to be a set rather than a collection, so any set can appear in W {\displaystyle W} at most once. By adding dummy elements, it suffices to only consider set systems W {\displaystyle W} such that every set in W {\displaystyle W} has cardinality k {\displaystyle k} , so often the sunflower lemma is equivalently phrased as holding for " k {\displaystyle k} -uniform" set systems.
… excerpt ends here. Continue reading the full article.
