UPPER BOUNDS FOR SUNFLOWER-FREE SETS
UPPER BOUNDS FOR SUNFLOWER-FREE SETS
复制标题
无向日葵组的上限
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
W. Sawin
中科院分区：
文献类型：
--
作者：
Eric Naslund;W. Sawin
如果集合中的任意两个集合的交集相同，则称$k$集合构成$k$-向日葵或$\unicode[STIX]{x1D6E5}$-系统，如果不包含$3$-向日葵，我们称集合${\mathcal{F}}$向日葵为自由的。在Ellenberg和Gijswjt(“关于不含三项算术级数的$\mathbb{F}_{q}^{n}$的大子集”)最近取得突破之后，Ann，数学的一部分。(2)185(2017)，339-343)；($\mathbb{Z}_{4}^{n}$中的无级进集是指数小的‘，AN.数学的一部分。(2)185(2017)，331-337)我们将多项式方法直接应用于ErdőS-Szemerédi向日葵问题(ErdőS和Szemerédi，《集合系的组合性质》，J.Combin)。理论系列。A24(1978)，308-313)，并证明了任何由$1，2，ldots的子集构成的无葵花族，N$的大小至多$$\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}$$我们说一个集合$A\subset(\mathbb{Z}/D\mathbb{Z})^{n}=\{1，2，\ldots，$D>；如果对于A$中的每个不同的三元组x，y，z，存在一个坐标$i$，其中$x_{i}，y_{i}，z_{i}$中的两个恰好相等，则2$是无向日葵的。用特征标为$\unicode[STIX]{x1D712}：\mathbb{Z}/D\mathbb{Z}\rightarrow\mathbb{C}$而不是多项式的多项式方法证明了任何向日葵自由集$A\subset(\mathbb{Z}/D\mathbb{Z})^{n}$的大小为$$\Begin{eqnarray}|A|\leqslant c_{D}^{n}\end{eqnarray}$$其中$c_{D}=\frac{3}{2^{2/3}}(D-1)^{2/3}$.这可以被看作是在证明ERDőS和Rado向日葵猜想(J·Lond的集合系统的交集定理)的可能方法上取得了进一步的进展。数学课。SoC。(2)35(1960)，85-90)，这是由Alon等人的工作。(《关于向日葵和矩阵乘法》，Comput。复杂性22(2013)，219-243；定理2.6)等价于证明了对于某个不依赖于$D$的常数$C$，$c_(D)是倾斜的C$。
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$ .