UPPER BOUNDS FOR SUNFLOWER-FREE SETS

DOI10.1017/FMS.2017.12zbMATH Open1366.05113arXiv1606.09575OpenAlexW2963589591MaRDI QIDQ5280253FDOQ5280253

Authors: Eric Naslund, William F. Sawin 

Publication date: 20 July 2017

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

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 $mathcalF$ 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 ErdH{o}s-Szemer'{e}di sunflower problem and prove that any sunflower-free family $mathcalF$ of subsets of $1,2,dots,n$ has size at most [ |mathcal{F}|leq3nsum_{kleq n/3}�inom{n}{k}leqleft(frac{3}{2^{2/3}} ight)^{n(1+o(1))}. ] We say that a set $Asubset(mathbbZ/DmathbbZ{)}^n={1,2,dots,D}^n$ for $D>2$ is sunflower-free if every distinct triple $x,y,zinA$ 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:mathbbZ/DmathbbZightarrowmathbbC$ instead of polynomials, we show that any sunflower-free set $Asubset(mathbbZ/DmathbbZ{)}^n$ has size [ |A|leq c_{D}^{n} ] where $c_D=frac32^{2/3}(D-1{)}^{2/3}$. This can be seen as making further progress on a possible approach to proving the ErdH{o}s-Rado sunflower conjecture, which by the work of Alon, Sphilka and Umans is equivalent to proving that $c_{D}leqC$ for some constant $C$ independent of $D$.

Full work available at URL: https://arxiv.org/abs/1606.09575

Recommendations

• An improved upper bound for the size of a sunflower-free family
• Sunflowers in set systems of bounded dimension
• Improved bounds for the sunflower lemma
• Improved bounds for the sunflower lemma
• Sunflowers and \(L\)-intersecting families
• Bounds on the number of maximal sum-free sets
• Bounds on the Number of Maximal Sum-Free Sets
• Sunflowers and testing triangle-freeness of functions
• Sunflowers and testing triangle-freeness of functions
• scientific article; zbMATH DE number 7250167

zbMATH Keywords

matrix multiplicationsunflower conjecture

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Extremal set theory (05D05)

Cites Work

• Intersection Theorems for Systems of Sets
• Combinatorial properties of systems of sets
• On sunflowers and matrix multiplication
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Title not available (Why is that?)
• On cap sets and the group-theoretic approach to matrix multiplication

Cited In (25)

• Near-sunflowers and focal families
• Exponential bounds for the Erdős-Ginzburg-Ziv constant
• A gap in the slice rank of \(k\)-tensors
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• Subrank and optimal reduction of scalar multiplications to generic tensors
• Title not available (Why is that?)
• LONELY RUNNERS IN FUNCTION FIELDS
• Multicolour sunflowers
• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• Monochromatic equilateral triangles in the unit distance graph
• A Gap in the Subrank of Tensors
• Title not available (Why is that?)
• Bounds on the higher degree Erdős-Ginzburg-Ziv constants over \({\mathbb{F}}_q^n\)
• An improved upper bound for the size of a sunflower-free family
• Coding for Sunflowers
• Improved bounds for the sunflower lemma
• Geometric rank and linear determinantal varieties
• On sunflowers and matrix multiplication
• The analytic rank of tensors and its applications
• Sunflowers in set systems of bounded dimension
• Sunflowers of convex open sets
• Odd-sunflowers
• On restricted intersections and the sunflower problem
• Turán numbers of sunflowers
• Tensor slice rank and Cayley's first hyperdeterminant

This page was built for publication: UPPER BOUNDS FOR SUNFLOWER-FREE SETS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280253)