Multicolour sunflowers

Abstract: A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection

C

of all of them, and

| C |

is smaller than each of the sets. A longstanding conjecture due to ErdH{o}s and Szemer'edi states that the maximum size of a family of subsets of

[n]

that contains no sunflower of fixed size

k > 2

is exponentially smaller than

2^{n}

as

n i g h t a r r o w i n f t y

. We consider this problem for multiple families. In particular, we obtain sharp or almost sharp bounds on the sum and product of

k

families of subsets of

[n]

that together contain no sunflower of size

k

with one set from each family. For the sum, we prove that the maximum is

(k-1)2^n+1+sum_{s=n-k+2}^{n}�inom{n}{s}

for all

n g e k g e 3

, and for the

k = 3

case of the product, we prove that it is between

left(frac{1}{8}+o(1) ight)2^{3n}qquad hbox{and} qquad (0.13075+o(1))2^{3n}.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Multicolour sunflowers