
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
-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
-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
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
, 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
. 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 all sets in
share the same common subset of elements. An element in
is either found in the common subset
or else appears in at most one of the
elements. No element of
is shared by just some of the
subset, but not others. 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
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
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
, 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 ...
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 obvious that such an
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
,
, there is an integer
such that if 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.
Sunflower lemma
proved the sunflower lemma, which states that
:
That is, if
and
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
of cardinality greater than or equal to
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.
Erdős-Rado sunflower conjecture
The sunflower conjecture is one of several variations of the conjecture of 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
. A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that
for A month after the release of the first version of their paper, Rao sharpened the bound to
; the current best-known bound is
.
Sunflower lower bounds
Erdős and Rado proved the following lower bound on
. It is equal to the statement that the original sunflower lemma is optimal in
.
Theorem.
Proof.
For
a set of
sequence of distinct elements is not a sunflower.
Let
denote the size of the largest set of
-sets with no
sunflower. Let
be such a set. Take an additional set of
elements and add one element to each set in one of
disjoint copies of
. Take the union of the
disjoint copies with the elements added and denote this set
. The copies of
with an element added form an
partition of
. We have that,
.
is sunflower free since any selection of
sets if in one of the disjoint partitions is sunflower free by assumption of H being sunflower free. Otherwise, if
sets are selected from across multiple sets of the partition, then two must be selected from one partition since there are only
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
sets.
A stronger result is the following theorem:
Theorem.
Proof. Let
and
be two sunflower free families. For each set
in F, append every set in
to
to produce
many sets. Denote this family of sets
. Take the union of
over all
in
. This produces a family of
sets which is sunflower free.
The best existing lower bound for the Erdos-Rado Sunflower problem for
is
, 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
(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-
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
-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
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
-system.
The
-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
is an
-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
, and if the continuum hypothesis holds, then there is an
-sized
-subsystem. Let
enumerate
. For
, let
. 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
stationary in
such that
is constantly equal to
on
.
Build
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 ...
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
*
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