Upper bounds for sunflower-free sets

Eric Naslund, Will Sawin

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

A collection of k sets is said to form a k-sunflower, or κ-system, if the intersection of any two sets from the collection is the same, and we call a family of sets F sunflower-free if it contains no 3-sunflowers. Following the recent breakthrough of Ellenberg and Gijswijt ('On large subsets of Fn q with no three-term arithmetic progression', Ann. of Math. (2) 185 (2017), 339-343); ('Progression-free sets in Zn 4 are exponentially small', Ann. of Math. (2) 185 (2017), 331-337) we apply the polynomial method directly to Erdos-Szemerédi sunflower problem (Erdos 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 F of subsets of {1; 2; ; n} has size at most |F| ≤ 3nΣk≥n/3 (n k) ≤ (3/22/3)n(1+o(1)) : We say that a set A ⊂ (Z/DZ/)n = {1; 2; ; D}n for D > 2 is sunflower-free if for every distinct triple x; y; z ∈ A there exists a coordinate i where exactly two of xi ; yi ; zi are equal. Using a version of the polynomial method with characters χ V Z/DZ → C instead of polynomials, we show that any sunflower-free set A ⊂ (Z/DZ)n has size |A| ≤ cn D where cD = 3/22/3 (D - 1)2/3. This can be seen as making further progress on a possible approach to proving the Erdos 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 cD 6 C for some constant C independent of D.

Original languageEnglish (US)
JournalForum of Mathematics, Sigma
Volume5
DOIs
StatePublished - 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Theoretical Computer Science
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Upper bounds for sunflower-free sets'. Together they form a unique fingerprint.

Cite this