Upper bounds for sunflower-free sets

Abstract

A collection of $k$ sets is said to form a $k$-sunflower, or $\Delta$-system, if the intersection of any two sets from the collection is the same, and we call a family of sets $\mathcal{F}$ sunflower-free if it contains no sunflowers. Following the recent breakthrough of Ellenberg and Gijswijt and Croot, Lev and Pach we apply the polynomial method directly to Erdős-Szemerédi sunflower problem and prove that any sunflower-free family $\mathcal{F}$ of subsets of $\{1,2,\dots ,n\}$ has size at most \[ |\mathcal{F}|\leq3n\sum_{k\leq n/3}\binom{n}{k}\leq\left(\frac{3}{2^{2/3}}\right)^{n(1+o(1))}. \] We say that a set $A\subset (\mathbb{Z}/D\mathbb{Z}{)}^n=\{1,2,\dots ,D{\}}^n$ for $D>2$ is sunflower-free if every distinct triple $x,y,z\in A$ there exists a coordinate $i$ where exactly two of $x_i,y_i,z_i$ are equal. Using a version of the polynomial method with characters $\chi :\mathbb{Z}/D\mathbb{Z}\to \mathbb{C}$ instead of polynomials, we show that any sunflower-free set $A\subset (\mathbb{Z}/D\mathbb{Z}{)}^n$ has size \[ |A|\leq c_{D}^{n} \] where $c_D=\frac{3}{2^{2/3}}(D-1{)}^{2/3}$. This can be seen as making further progress on a possible approach to proving the Erdős-Rado sunflower conjecture, which by the work of Alon, Sphilka and Umans is equivalent to proving that $c_D\le C$ for some constant $C$ independent of $D$.

5 pages

References in corpus (2)

• Progression-free sets in Z_4^n are exponentially small
• On cap sets and the group-theoretic approach to matrix multiplication

Cited by in corpus (11)

• The Partition Rank of a Tensor and $k$-Right Corners in ${\mathbb{F}}_q^n$
• Monochromatic Equilateral Triangles in the Unit Distance Graph
• A lower bound for the $k$-multicolored sum-free problem in ${\mathbb{Z}}_m^n$
• A Gap in the Subrank of Tensors
• Exponential Bounds for the Erdős-Ginzburg-Ziv Constant
• Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
• Improved bounds for the sunflower lemma
• Lonely runners in function fields
• A new upper bound for the size of a sunflower-free family
• Larger Corner-Free Sets from Combinatorial Degenerations
• Multicolor Sunflowers