A mathematical sunflower can be pictured as a flower. The kernel is the brown part, the intersection of every pair of sets. 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 Δ {\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 vaguously 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.

Erdős-Rado Delta System Theorem (corollary of the sunflower lemma)—For each k > 0 {\displaystyle k>0}, r > 0 {\displaystyle r>0}, there is an integer f ( k , r ) {\displaystyle f(k,r)} such that if a set system F {\displaystyle F} of k {\displaystyle k}-sets is of cardinality greater than f ( k , r ) {\displaystyle f(k,r)}, then F {\displaystyle F} contains a sunflower of size r {\displaystyle r}.

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.

Sunflower lemma

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

sunflower lemma (Erdős & Rado (1960, p. 86))—f ( k , r ) ≤ k ! ( r − 1 ) k . {\displaystyle f(k,r)\leq k!(r-1)^{k}.}

That is, if k {\displaystyle k} and r {\displaystyle r} are positive integers, then a set system W {\displaystyle W} of cardinality greater than k ! ( r − 1 ) k {\displaystyle k!(r-1)^{k}} of sets of cardinality k {\displaystyle k} contains a sunflower with at least r {\displaystyle r} sets.

Proof
Proof The Erdős-Rado sunflower lemma can be proved directly through induction. First, f ( 1 , r ) ≤ r − 1 {\displaystyle f(1,r)\leq r-1}, since the set system W {\displaystyle W} must be a collection of distinct sets of size one, and so r {\displaystyle r} of these sets make a sunflower. In the general case, suppose W {\displaystyle W} has no sunflower with r {\displaystyle r} sets. Then consider A 1 , A 2 , … , A t ∈ W {\displaystyle A_{1},A_{2},\ldots ,A_{t}\in W} to be a maximal collection of pairwise disjoint sets (that is, A i ∩ A j {\displaystyle A_{i}\cap A_{j}} is the empty set unless i = j {\displaystyle i=j}, and every set in W {\displaystyle W} intersects with some A i {\displaystyle A_{i}}). Because we assumed that W {\displaystyle W} had no sunflower of size r {\displaystyle r}, and a collection of pairwise disjoint sets is a sunflower, t < r {\displaystyle t<r}.Let A = A 1 ∪ A 2 ∪ ⋯ ∪ A t {\displaystyle A=A_{1}\cup A_{2}\cup \cdots \cup A_{t}}. Since each A i {\displaystyle A_{i}} has cardinality k {\displaystyle k}, the cardinality of A {\displaystyle A} is bounded by k t ≤ k ( r − 1 ) {\displaystyle kt\leq k(r-1)}. Define W a {\displaystyle W_{a}} for some a ∈ A {\displaystyle a\in A} to be W a = { S ∖ { a } ∣ a ∈ S , S ∈ W } . {\displaystyle W_{a}=\{S\setminus \{a\}\mid a\in S,\,S\in W\}.} Then W a {\displaystyle W_{a}} is a set system, like W {\displaystyle W}, except that every element of W a {\displaystyle W_{a}} has k − 1 {\displaystyle k-1} elements. Furthermore, every sunflower of W a {\displaystyle W_{a}} corresponds to a sunflower of W {\displaystyle W}, simply by adding back a {\displaystyle a} to every set. This means that, by our assumption that W {\displaystyle W} has no sunflower of size r {\displaystyle r}, the size of W a {\displaystyle W_{a}} must be bounded by f ( k − 1 , r ) − 1 {\displaystyle f(k-1,r)-1}.Since every set S ∈ W {\displaystyle S\in W} intersects with one of the A i {\displaystyle A_{i}}'s, it intersects with A {\displaystyle A}, and so it corresponds to at least one of the sets in a W a {\displaystyle W_{a}}: | W | ≤ ∑ a ∈ A | W a | ≤ | A | ( f ( k − 1 , r ) − 1 ) ≤ k ( r − 1 ) f ( k − 1 , r ) − | A | ≤ k ( r − 1 ) f ( k − 1 , r ) − 1. {\displaystyle |W|\leq \sum _{a\in A}|W_{a}|\leq |A|(f(k-1,r)-1)\leq k(r-1)f(k-1,r)-|A|\leq k(r-1)f(k-1,r)-1.} Hence, if | W | ≥ k ( r − 1 ) f ( k − 1 , r ) {\displaystyle |W|\geq k(r-1)f(k-1,r)}, then W {\displaystyle W} contains an r {\displaystyle r} set sunflower of size k {\displaystyle k} sets. Hence, f ( k , r ) ≤ k ( r − 1 ) f ( k − 1 , r ) {\displaystyle f(k,r)\leq k(r-1)f(k-1,r)} and the theorem follows.

Erdős-Rado sunflower conjecture

The sunflower conjecture is one of several variations of the conjecture of Erdős & Rado (1960, p. 86) that for each r > 2 {\displaystyle r>2}, f ( k , r ) ≤ C k {\displaystyle f(k,r)\leq C^{k}} for some constant C > 0 {\displaystyle C>0} depending only on r {\displaystyle r}. The conjecture remains open even for fixed low values of r {\displaystyle r}; for example r = 3 {\displaystyle r=3}; it is not known whether f ( k , 3 ) ≤ C k {\displaystyle f(k,3)\leq C^{k}} for some C > 0 {\displaystyle C>0}. A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that f ( k , r ) ≤ C k {\displaystyle f(k,r)\leq C^{k}} for C = O ( r 3 log ⁡ ( k ) log ⁡ log ⁡ ( k ) ) {\displaystyle C=O(r^{3}\log(k)\log \log(k))}. A month after the release of the first version of their paper, Rao sharpened the bound to C = O ( r log ⁡ ( r k ) ) {\displaystyle C=O(r\log(rk))}; the current best-known bound is C = O ( r log ⁡ k ) {\displaystyle C=O(r\log k)}.

Sunflower lower bounds

Erdős and Rado proved the following lower bound on f ( k , r ) {\displaystyle f(k,r)}. It is equal to the statement that the original sunflower lemma is optimal in r {\displaystyle r}.

Theorem (lower bound on f ( k , r ) {\displaystyle f(k,r)})—( r − 1 ) k ≤ f ( k , r ) . {\displaystyle (r-1)^{k}\leq f(k,r).}

For k = 1 {\displaystyle k=1} a set of r − 1 {\displaystyle r-1} sequence of distinct elements is not a sunflower. Let h ( k − 1 , r ) {\displaystyle h(k-1,r)} denote the size of the largest set of k − 1 {\displaystyle k-1}-sets with no r {\displaystyle r} sunflower. Let H {\displaystyle H} be such a set. Take an additional set of r − 1 {\displaystyle r-1} elements and add one element to each set in one of r − 1 {\displaystyle r-1} disjoint copies of H {\displaystyle H}. Take the union of the r − 1 {\displaystyle r-1} disjoint copies with the elements added and denote this set H ∗ {\displaystyle H^{*}}. The copies of H {\displaystyle H} with an element added form an r − 1 {\displaystyle r-1} partition of H ∗ {\displaystyle H^{*}}. We have that,( r − 1 ) | H | ≤ | H ∗ | {\displaystyle (r-1)|H|\leq |H^{*}|}. H ∗ {\displaystyle H^{*}} is sunflower free since any selection of r {\displaystyle r} sets if in one of the disjoint partitions is sunflower free by assumption of H being sunflower free. Otherwise, if r {\displaystyle r} sets are selected from across multiple sets of the partition, then two must be selected from one partition since there are only r − 1 {\displaystyle r-1} 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 r {\displaystyle r} sets.

A stronger result is the following theorem:

Theorem (stronger lower bound)—f ( a + b , r ) ≥ ( f ( a , r ) − 1 ) ( f ( b , r ) − 1 ) {\displaystyle f(a+b,r)\geq (f(a,r)-1)(f(b,r)-1)}

Let F {\displaystyle F} and F ∗ {\displaystyle F^{*}} be two sunflower free families. For each set A {\displaystyle A} in F {\displaystyle F}, append every set in F ∗ {\displaystyle F^{*}} to A {\displaystyle A} to produce | F ∗ | {\displaystyle |F^{*}|} many sets. Denote this family of sets F A {\displaystyle F_{A}}. Take the union of F A {\displaystyle F_{A}} over all A {\displaystyle A} in F {\displaystyle F}. This produces a family of | F ∗ | | F | {\displaystyle |F^{*}||F|} sets which is sunflower free.

For k = 2 {\displaystyle k=2}, f ( k , r ) = r ( r − 1 ) {\displaystyle f(k,r)=r(r-1)} if r {\displaystyle r} is odd, and ( r − 1 ) 2 + r / 2 − 1 {\displaystyle (r-1)^{2}+r/2-1} if r {\displaystyle r} is even. The only other known case outside of these determined families is for k = 3 {\displaystyle k=3}, r = 3 {\displaystyle r=3}, where f ( k , r ) = 20 {\displaystyle f(k,r)=20}.

The best existing lower bound for the Erdos-Rado Sunflower problem for r = 3 {\displaystyle r=3} is 10 k / 2 − O ( log ⁡ k ) ≤ f ( k , 3 ) {\displaystyle 10^{k/2-O(\log k)}\leq f(k,3)}, due to Abott, Hansen, and Sauer. This bound has not been improved in over 50 years.

Below is a table of known lower bounds for smaller r {\displaystyle r} and k {\displaystyle k}:

r\k3456
32054160600
4381143801444
58840017608000
6146730394221316

Weak sunflower conjecture

Another version of the problem, sometimes called the weak sunflower conjecture or the Erdős–Szemerédi sunflower conjecture, deals with the case where the family of sets is a subset of the power set of an n-element set. In this version, the size of the individual sets is not restricted. The conjecture states that if F {\displaystyle {\mathcal {F}}} is a family of subsets of 1 , 2 , … , n {\displaystyle {1,2,\ldots ,n}} and | F | > c n {\displaystyle |{\mathcal {F}}|>c^{n}} for some constant c < 2 {\displaystyle c<2}, then F {\displaystyle {\mathcal {F}}} must contain a sunflower of size 3 (the case where r = 3 {\displaystyle r=3}).

This conjecture was resolved as a consequence of a breakthrough on the cap set problem. Alon, Shpilka, and Umans had previously shown that an exponential upper bound for the cap set problem would imply a solution to the weak sunflower conjecture for r = 3 {\displaystyle r=3}. In 2016, Ellenberg and Gijswijt, building on the work of Croot, Lev, and Pach, used polynomial methods to prove a tight exponential upper bound on the size of cap sets.

Following this, Eric Naslund and Will Sawin adapted these methods to provide an explicit proof for the weak sunflower conjecture. They proved that the size of any family of subsets of 1 , 2 , … , n {\displaystyle {1,2,\ldots ,n}} without a 3-sunflower is at most 3 n ∑ k ≤ n / 3 ( n k ) {\displaystyle 3n\sum _{k\leq n/3}{\tbinom {n}{k}}}, which is bounded by ( 1.89 ) n {\displaystyle (1.89)^{n}} for large n {\displaystyle n}. This confirmed the conjecture that such families have a size of at most c n {\displaystyle c^{n}} for a constant c < 2 {\displaystyle c<2}.

Weak sunflowers

A family of sets F {\displaystyle {\mathcal {F}}} is called a weak sunflower (or weak Δ-system) if all pairwise intersections have the same size. That is, there exists an integer c ≥ 0 {\displaystyle c\geq 0} such that for any two distinct sets A , B ∈ F {\displaystyle A,B\in {\mathcal {F}}}, it holds that | A ∩ B | = c {\displaystyle |A\cap B|=c}.

Every strong sunflower is, by definition, a weak sunflower. However, the converse is not always true. For a family to be a strong sunflower, the pairwise intersections must be the exact same set, not just the same size. For example, consider the following family of four 3-uniform sets:

F = { { 1 , 2 , 3 } , { 1 , 4 , 5 } , { 1 , 6 , 7 } , { 2 , 4 , 6 } } {\displaystyle {\mathcal {F}}=\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\}\}}

This family is a weak sunflower because every pair of sets has an intersection of size 1. However, it is not a strong sunflower because the intersections are not all identical.

If a weak sunflower is sufficiently large, it is forced to be a strong sunflower through the pigeonhole principle. Specifically, any k {\displaystyle k}-uniform weak sunflower with more than ( r − 2 ) ( k c ) + 1 {\displaystyle (r-2){\tbinom {k}{c}}+1} sets must contain a strong sunflower with r {\displaystyle r} petals.

Relation to Ramsey's Theorem

By constructing a complete graph where vertices represent the sets and edges are colored by intersection size, Ramsey's theorem guarantees the existence of a large monochromatic clique, which corresponds to a weak sunflower the same size as the clique. So, for a case like f ( 3 , 5 ) {\displaystyle f(3,5)}, where a sunflower of size 5 using 3-uniform sets will always be both weak and strong, the multicolor Ramsey number R ( 5 , 5 , 5 ) {\displaystyle R(5,5,5)} serves as an upper bound for f ( 3 , 5 ) {\displaystyle f(3,5)}. While this method successfully proves the existence of sunflowers, the upper bounds it provides for the sunflower number f ( k , r ) {\displaystyle f(k,r)} are much weaker than those obtained from more direct combinatorial arguments.

Applications of the sunflower lemma

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 n log ⁡ ( n ) {\displaystyle n^{\log(n)}} (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-3 {\displaystyle 3} A C 0 {\displaystyle AC_{0}} 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.

Analogue for infinite collections of sets

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

The Δ {\displaystyle \Delta }-lemma states that every uncountable collection of finite sets contains an uncountable Δ {\displaystyle \Delta }-system.

The Δ {\displaystyle \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 {\displaystyle W} is an ω 2 {\displaystyle \omega _{2}}-sized collection of countable subsets of ω 2 {\displaystyle \omega _{2}}, and if the continuum hypothesis holds, then there is an ω 2 {\displaystyle \omega _{2}}-sized Δ {\displaystyle \Delta }-subsystem. Let ⟨ A α : α < ω 2 ⟩ {\displaystyle \langle A_{\alpha }:\alpha <\omega _{2}\rangle } enumerate W {\displaystyle W}. For cf ⁡ ( α ) = ω 1 {\displaystyle \operatorname {cf} (\alpha )=\omega _{1}}, let f ( α ) = sup ( A α ∩ α ) {\displaystyle f(\alpha )=\sup(A_{\alpha }\cap \alpha )}. By Fodor's lemma, fix S {\displaystyle S} stationary in ω 2 {\displaystyle \omega _{2}} such that f {\displaystyle f} is constantly equal to β {\displaystyle \beta } on S {\displaystyle S}. Build S ′ ⊆ S {\displaystyle S'\subseteq S} of cardinality ω 2 {\displaystyle \omega _{2}} such that whenever i < j {\displaystyle i<j} are in S ′ {\displaystyle S'} then A i ⊆ j {\displaystyle A_{i}\subseteq j}. Using the continuum hypothesis, there are only ω 1 {\displaystyle \omega _{1}}-many countable subsets of β {\displaystyle \beta }, so by further thinning we may stabilize the kernel.

Cap set problem

The solution to the cap set problem can be used to prove a partial form of the sunflower conjecture, namely that if a family of subsets of an n {\displaystyle n}-element set has no 3-sunflower (the case where r = 3 {\displaystyle r=3}), then the number of subsets in the family is at most c n {\displaystyle c^{n}} for a constant c < 2 {\displaystyle c<2}.

Notes

  • Abbott, H.L.; Hanson, D. (1974). . Discrete Mathematics. 8 (1): 1–12. doi:. ISSN .
  • Abbott, H.L.; Hanson, D. (1977). . Discrete Mathematics. 17 (2): 121–126. doi:. ISSN .
  • 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:. doi:. ISBN 978-1-4503-6979-4. S2CID .
  • Bell, Tolson; Chueluecha, Suchakree; Warnke, Lutz (2021). "Note on Sunflowers". Discrete Mathematics. 344 (7) 112367. arXiv:. doi:. MR . S2CID .
  • Deza, M.; Frankl, P. (1981). "Every large set of equidistant (0,+1,–1)-vectors forms a sunflower". Combinatorica. 1 (3): 225–231. doi:. ISSN . MR . S2CID .
  • Erdős, Paul; Rado, R. (1960). (PDF). Journal of the London Mathematical Society. Second Series. 35 (1): 85–90. doi:. ISSN . MR .
  • 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:. ISBN 978-3-540-29952-3. MR .
  • 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). . Discrete Analysis. 2020 (2) 11887. doi:. S2CID .
  • Rao, Anup (2023). (PDF). Bull. Amer. Math. Soc. 60 (1): 29–38. doi:.
  • 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). . What's new (personal blog).

External links

  • Thiemann, René.
  • The corresponding
  • (sequence A332077 in the OEIS)

Notes