UPPER BOUNDS FOR SUNFLOWER-FREE SETS

By Eric Naslund, W. Sawin. Forum of Mathematics, Sigma, 2016

65 citations recorded by the source corpus.

A collection of $k$ sets is said to form a $k$ -sunflower, or $\unicode[STIX]{x1D6E5}$ -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 $3$ -sunflowers. Following the recent breakthrough of Ellenberg and Gijswijt (‘On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression’, Ann. of Math. (2) 185 (2017), 339–343); (‘Progression-free sets in $\mathbb{Z}_{4}^{n}$ are exponentially small’, Ann. of Math. (2) 185 (2017), 331–337) we apply the polynomial method directly to Erdős–Szemerédi sunflower problem (Erdős and Szemerédi, ‘Combinatorial properties of systems of sets’, J. Combin. Theory Ser. A 24 (1978), 308–313) and prove that any sunflower-free family ${\mathcal{F}}$ of subsets of $\{1,2,\ldots ,n\}$ has size at most $$\begin{eqnarray}|{\mathcal{F}}|\leqslant 3n\mathop{\sum }_{k\leqslant n/3}\binom{n}{k}\leqslant \left(\frac{3}{2^{2/3}}\right)^{n(1+o(1))}.\end{eqnarray}$$ We say that a set $A\subset (\mathbb{Z}/D\mathbb{Z})^{n}=\{1,2,\ldots ,D\}^{n}$ for $D>2$ is sunflower-free if for 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 $\unicode[STIX]{x1D712}:\mathbb{Z}/D\mathbb{Z}\rightarrow \mathbb{C}$ instead of polynomials, we show that any sunflower-free set $A\subset (\mathbb{Z}/D\mathbb{Z})^{n}$ has size $$\begin{eqnarray}|A|\leqslant c_{D}^{n}\end{eqnarray}$$ 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 and Rado sunflower conjecture (‘Intersection theorems for systems of sets’,J. Lond. Math. Soc. (2) 35 (1960), 85–90), which by the work of Alon et al. (‘On sunflowers and matrix multiplication’, Comput. Complexity 22 (2013), 219–243; Theorem 2.6) is equivalent to proving that $c_{D}\leqslant C$ for some constant $C$ independent of $D$ .

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/7a72fa912d699fc89862823e7f6ec242218b5c53

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. Pushmeet Kohli
  2. Alhussein Fawzi
  3. Jordan S. Ellenberg

In Discrete Mathematics and Combinatorics

  1. Jordan S. Ellenberg

Citations in the corpus