Sunflower (mathematics)

Suppose W is a set system over U, 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 A \cap B = S. In other words, a set system or collection of sets W is a sunflower if all sets in W share the same common subset of elements. An element in U is either found in the common subset S or else appears in at most one of the W elements. No element of U is shared by just some of the W subset, but not others. Basic examples If W contains 0, 1, or 2 subsets, then it is vaguously a sunflower. If 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) for nonnegative integers k, r, which is defined to be the smallest nonnegative integer n such that, for any set system W such that every set S \in W has cardinality at most k, if W has more than n sets, then W contains a sunflower of r sets. Though it is not obvious that such an 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) is sometimes used, Sun(k,r), where f(k,r) = Sun(k,r) - 1. This is the same as saying if F is of cardinality greater than or equal to Sun(k,r), then F contains a sunflower of size r. In the literature, W is often assumed to be a set rather than a collection, so any set can appear in W at most once. By adding dummy elements, it suffices to only consider set systems W such that every set in W has cardinality k, so often the sunflower lemma is equivalently phrased as holding for "k-uniform" set systems. Sunflower lemma proved the sunflower lemma, which states that {{Math theorem That is, if k and r are positive integers, then a set system W of cardinality greater than k!(r-1)^{k} of sets of cardinality k contains a sunflower with at least r sets. }} {{Math proof Let A = A_1 \cup A_2 \cup \cdots \cup A_t. Since each A_i has cardinality k, the cardinality of A is bounded by kt \leq k(r-1). Define W_a for some a \in A to be :W_a = \{S \setminus \{a\} \mid a \in S,\, S \in W\}. Then W_a is a set system, like W, except that every element of W_a has k-1 elements. Furthermore, every sunflower of W_a corresponds to a sunflower of W, simply by adding back a to every set. This means that, by our assumption that W has no sunflower of size r, the size of W_a must be bounded by f(k-1,r)-1. Since every set S \in W intersects with one of the A_i's, it intersects with A, and so it corresponds to at least one of the sets in a W_a: :|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| \ge k(r-1)f(k-1,r), then W contains an r set sunflower of size k sets. Hence, f(k,r) \le k(r-1)f(k-1,r) and the theorem follows. A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that f(k,r)\le C^k for A month after the release of the first version of their paper, Rao sharpened the bound to C=O(r\log(rk)); the current best-known bound is C=O(r\log k). Sunflower lower bounds Erdős and Rado proved the following lower bound on f(k,r). It is equal to the statement that the original sunflower lemma is optimal in r. A stronger result is the following theorem: For k = 2, f(k,r) = r(r-1) if r is odd, and (r-1)^2+r/2 - 1 if r is even. The only other known case outside of these determined families is for k=3, r=3, where f(k,r)=20. The best existing lower bound for the Erdos-Rado Sunflower problem for r=3 is 10^{k/2-O(\log k)} \le 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 and k: ==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 \mathcal{F} is a family of subsets of {1, 2, \ldots, n} and |\mathcal{F}| > c^n for some constant c, then \mathcal{F} must contain a sunflower of size 3 (the case where 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. 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, \ldots, n} without a 3-sunflower is at most 3n \sum_{k \le n/3} \tbinom{n}{k}, which is bounded by (1.89)^n for large n. This confirmed the conjecture that such families have a size of at most c^n for a constant c. == Weak sunflowers ==

A family of sets \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 \ge 0 such that for any two distinct sets A, B \in \mathcal{F}, it holds that |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: :\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-uniform weak sunflower with more than (r-2)\tbinom{k}{c}+1 sets must contain a strong sunflower with r petals.{{cite book 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), 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) serves as an upper bound for f(3,5). While this method successfully proves the existence of sunflowers, the upper bounds it provides for the sunflower number 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)} (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 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 \Delta-lemma which is essentially equivalent to the Erdős-Rado \Delta-system theorem states that a countable collection of k-sets contains a countably infinite sunflower or \Delta-system. 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 . 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 enumerate W. For \operatorname{cf}(\alpha)=\omega_1, let 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 are in S' then 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. ==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-element set has no 3-sunflower (the case where r=3), then the number of subsets in the family is at most c^n for a constant c. ==Notes==