Sunflower Lemma
   HOME

TheInfoList



OR:

In the mathematical fields of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
and extremal combinatorics, a sunflower or \Delta-system is a collection of sets in which all possible distinct pairs of sets share the same
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
. 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 A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
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 \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 is a
set system In set theory and related branches of mathematics, a family (or collection) can mean, depending upon the context, any of the following: set, indexed set, multiset, or class. A collection F of subsets of a given set S is called a family of subsets ...
over U, that is, a collection of
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s 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. Note that this intersection, S, 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

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
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s k, r, which is defined to be the smallest nonnegative
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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 Erdős, Erdos, or Erdoes is a Hungarian surname. Paul Erdős (1913–1996), Hungarian mathematician Other people with the surname * Ágnes Erdős (1950–2021), Hungarian politician * Brad Erdos (born 1990), Canadian football player * Éva Erd ...
and Rado, the Delta System Theorem, indicates that it does. Erdos-Rado Delta System Theorem(corollary of the Sunflower lemma): For each k>0, r>0, there is an integer f(k,r) such that if a set system F of k-sets is of cardinality greater than f(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 :f(k,r)\le k!(r-1)^k. That is, if k and r are positive
integers An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
, then a set system W of cardinality greater than or equal to k!(r-1)^ of sets of cardinality k contains a sunflower with at least r sets. The Erdős-Rado sunflower lemma can be proved directly through induction. First, f(1,r)\le r-1, since the set system W must be a collection of distinct sets of size one, and so r of these sets make a sunflower. In the general case, suppose W has no sunflower with r sets. Then consider A_1,A_2,\ldots,A_t \in W to be a maximal collection of pairwise disjoint sets (that is, A_i \cap A_j is the empty set unless i = j, and every set in W intersects with some A_i). Because we assumed that W had no sunflower of size r, and a collection of pairwise disjoint sets is a sunflower, t < r. 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 = \. 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_ , 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.


Erdős-Rado sunflower conjecture

The sunflower conjecture is one of several variations of the conjecture of that for each r>2, f(k,r)\le C^k for some constant C>0 depending only on r. The conjecture remains wide open even for fixed low values of r; for example r=3; it is not known whether f(k,3)\le C^k for some C>0. 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. Theorem. (r-1)^k \le f(k,r). Proof. For k = 1 a set of r-1 sequence of distinct elements is not a sunflower. Let h(k-1,r) denote the size of the largest set of k-1-sets with no r sunflower. Let H be such a set. Take an additional set of r-1 elements and add one element to each set in one of r-1 disjoint copies of H. Take the union of the r-1 disjoint copies with the elements added and denote this set H^*. The copies of H with an element added form an r-1 partition of H^*. We have that,(r-1), H, \le , H^*, . H^* is sunflower free since any selection of r sets if in one of the disjoint partitions is sunflower free by assumption of H being sunflower free. Otherwise, if 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 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 sets. A stronger result is the following theorem: Theorem. f(a+b,r) \ge (f(a,r)-1)(f(b,r)-1) Proof. Let F and F^* be two sunflower free families. For each set A in F, append every set in F^* to A to produce , F^*, many sets. Denote this family of sets F_A. Take the union of F_A over all A in F. This produces a family of , F^*, , F, sets which is sunflower free. The best existing lower bound for the Erdos-Rado Sunflower problem for r=3 is 10^ \le f(k,3) , due to Abott, Hansen, and Sauer.Lower Bounds for the Sunflower Problem https://mathoverflow.net/a/420288/12176 This bound has not been improved in over 50 years.


Applications of the sunflower lemma

The sunflower lemma has numerous applications in
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
. For example, in 1986, Razborov used the sunflower lemma to prove that the Clique language required n^ (superpolynomial) size monotone circuits, a breakthrough result in
circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
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 In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
of the
hitting set problem The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements (henceforth referred to as the universe, specifying all possible elements under consideratio ...
, to design
fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
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 In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger tha ...
collection of
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. Th ...
s contains an uncountable \Delta-system. The \Delta-lemma is a
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
set-theoretic Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathematics – is mostly ...
tool used in proofs to impose an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...
on the size of a collection of pairwise incompatible elements in a forcing
poset In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
. It may for example be used as one of the ingredients in a proof showing that it is consistent with
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes suc ...
that the
continuum hypothesis In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states: Or equivalently: In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...
does not hold. It was introduced by . If W is an \omega_2-sized collection of
countable In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
subsets of \omega_2, and if the continuum hypothesis holds, then there is an \omega_2-sized \Delta-subsystem. Let \langle A_\alpha:\alpha<\omega_2\rangle enumerate W. For \operatorname(\alpha)=\omega_1, let f(\alpha) = \sup(A_\alpha \cap \alpha). By
Fodor's lemma In mathematics, particularly in set theory, Fodor's lemma states the following: If \kappa is a regular, uncountable cardinal, S is a stationary subset of \kappa, and f:S\rightarrow\kappa is regressive (that is, f(\alpha)<\alpha for any ...
, fix S stationary in \omega_2 such that f is constantly equal to \beta on S. Build S'\subseteq S of
cardinality The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...
\omega_2 such that whenever i < j 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.


See also

*
Cap set In affine geometry, a cap set is a subset of the affine space \mathbb_3^n (the n-dimensional affine space over the three-element field) where no three elements sum to the zero vector. The cap set problem is the problem of finding the size of the ...


References

* * * * * * * * * * *


External links

* Thiemann, René
The Sunflower Lemma of Erdős and Rado (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)


Notes

{{reflist Forcing (mathematics) Set theory Intersection Combinatorics