In the mathematical fields of

set theory 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 concer ...

and

extremal combinatorics Extremal combinatorics is a field of combinatorics, which is itself a part of mathematics. Extremal combinatorics studies how large or how small a collection of finite objects (numbers, graphs, vectors, sets, etc.) can be, if it has to satisfy cer ...

, a sunflower or

\Delta

-system is a collection of sets whose pairwise

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, thei ...

is constant. This constant intersection is called the kernel of the sunflower. 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 collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fa ...

over

U

, that is, a collection of

subset In mathematics, set ''A'' is a subset of a set ''B'' if all 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 are unequal, then ''A'' is a proper subset o ...

s of a set

U

. The collection

W

is a ''sunflower'' (or ''

\Delta

-system'') if there is a subset

S

U

such that for each distinct

A

and

B

W

, we have

A \cap B = S

. In other words, a set system or collection of sets

W

is a sunflower if the pairwise intersection of each set in

W

is identical. Note that this intersection,

S

, may be empty; a collection of pairwise

disjoint Disjoint may refer to: *Disjoint sets, sets with no common elements *Mutual exclusivity, the impossibility of a pair of propositions both being true See also *Disjoint union *Disjoint-set data structure {{disambig That is, if

k

and

r

are positive

integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

, then a set system

W

of cardinality greater than

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)

. 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) \leq k(r-1)f(k-1, r).

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))

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^*

A

to produce

, F^*,

many sets. Denote this family of sets

F_A

. Take the union of

F_A

over all

A

F

. This produces a family of

, F^*, , F,

sets which is sunflower free. It is also known that

10^ \le f(k,3)

Applications of the sunflower lemma

The sunflower lemma has numerous applications in

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

. 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 ci ...

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, 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 (or uncountably infinite set) 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 numb ...

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. ...

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 an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...

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 concer ...

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 greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elem ...

on the size of a collection of pairwise incompatible elements in a

forcing Forcing may refer to: Mathematics and science * Forcing (mathematics), a technique for obtaining independence proofs for set theory *Forcing (recursion theory), a modification of Paul Cohen's original set theoretic technique of forcing to deal with ...

poset In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...

. 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 such ...

that the

continuum hypothesis In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent ...

does not hold. It was introduced by . If

W

is an

\omega_2

-sized collection of

countable In mathematics, a set is countable if either it is 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 from it into the natural number ...

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

S

. Build

S'\subseteq S

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

\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.

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