Multicolor 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 Erdős and Szemerédi 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\to \infty$. 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\left(\genfrac{}{}{0ex}{}{n}{s}\right)$$ for all $n\ge k\ge 3$, and for the $k=3$ case of the product, we prove that it is between $$\left(\frac{1}{8}+o(1)\right)2^{3n}and(0.13075+o(1))2^{3n}.$$

16 pages, 1 figure

References in corpus (1)

• Upper bounds for sunflower-free sets