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 language | English (US) |
---|---|
Journal | Forum of Mathematics, Sigma |
Volume | 5 |
DOIs | |
State | Published - 2017 |
Externally published | Yes |
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