用户: 迷亭/向日葵猜想

我继续来偷偷边看 $\mathbb{UFC}$ 边写文章. 钻石输了, 他被做了一种介于达斯和日本领结的绞技.

向日葵是集族, 其中任取两个集合总给你相同的交.

定义 0.1 (向日葵). 一朵向日葵是一个集族 $\mathcal{S}=\{F_1,F_2,...,F_p\}$,

使得 $\forall 1\le i\ne j,i^{\prime }\ne j^{\prime }\le p,F_i\cap F_j=F_{i^{\prime }}\cap F_{j^{\prime }}.$

其中, $\forall 1\le i\ne j\le p,C:=F_i\cap F_j$ 是它的花心,  $F_i\backslash C$ 是它的花瓣.

$\mathcal{S}$ 有 $p$ 片花瓣.

有时候向日葵也叫 $\Delta$-系统.

定义 0.2 (伤心). 一朵向日葵是伤心的当且仅当它的花心是空集.

例 0.3. $\mathcal{S}=\{\{1\},\{2\},\{3\}\}$ 是伤心向日葵. 它有 3 片花瓣, 且花心是空集.

定义 0.4 ($k$-无花族). 一个集族 $\mathcal{F}$ 是 $\mathbf{k}$-无花的, 当且仅当其任意 $k$ 个成员不构成向日葵.

当 $k=3$ 时, 我们简称 $\mathcal{F}$ 是无花的.

有一个突然想到了这么一个问题: 一个集族得多大, 才能保证它一定包含向日葵. 换句话说, $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{\mathbb{N}}{k}\right)$ 如果没有向日葵, 它至多能多大.

引理 0.5 (Erdős–Rado 向日葵引理). $\forall k\in \mathbb{N},$ 若 $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{\mathbb{N}}{k}\right),|\mathcal{F}|>k!(p-1{)}^k,$ 那 $\mathcal{F}$ 必定包含 $p$ 片花瓣的向日葵.

证明. 对 $k$ 使用归纳法. 我还没看完.

$\square$

在 Erdős 和 Rado 的同一篇文章里, 他们猜想

猜想 0.6 (Erdős-Rado 向日葵猜想). 若 $k\ge 3$, $\mathcal{F}$ 是一个 $k$-无花且 $w$-正则的集族. 那$$|\mathcal{F}|\le C_k^w,$$其中 $C_k>0$ 是一个只依赖 $k$ 的常数.

在 2021 年, Alweiss, Lovett, 吴克文, 和 Zhang 改进了了这个上界, 现在我们知道 $|\mathcal{F}|\lesssim (\log w{)}^w$.

关于向日葵, 还有另一个猜想

猜想 0.7 (Erdős-Szemerédi 向日葵猜想). 若 $\mathcal{F}$ 是 $k$-无花集族, 且其元素都是 $[n]$ 的子集. 那$$|\mathcal{F}|\le c_k^n,$$其中 $c_k<2$ 是一个只依赖 $k$ 的常数.

在 2017 年, Naslund 和 Sawin 使用切片秩和多项式方法解决了三片花瓣, 也就是 $k=3$ 的情况.

我们来写一些定义 (我只写了需要的, 也就是 3 维时候的情况).

定义 0.8 (切片). 一个函数 $f:A^3\mapsto \mathbb{F}$ 被叫做一个切片, 当且仅当$$\exists h:A\mapsto \mathbb{F},\exists g:A^2\mapsto \mathbb{F},\text{s.t.},f(x,y,z)=h(x)g(y,z).$$

定义 0.9 (切片秩). 令 $f:A^3\mapsto \mathbb{F}$ 是一个函数, $f$ 的切片秩是一个最小的数 $r$, 如果 $f$ 能被写成 $r$ 个切片的线性组合.

这里我们记作 $slicerank(f)$.

引理 0.10 (陶). 令 $A$ 是有限集, $\mathbb{F}$ 是域. 若 $T:A\times A\times A\mapsto \mathbb{F}$ 是函数. 那$$(T(x,y,z)\ne 0⟺x=y=z)⟹slicerank(T)=|A|.$$

证明. 陶哲轩写在他的博客里, 我不会证. 直觉上来看, 他这个就是只有对角线才是非零元, 所以秩数是 $|A|$. 这和方阵的秩很像, 方阵如果只有对角线是非零元, 秩数也是行数.

不证了. 请观察其博客.

$\square$

以下是 Naslund 和 Sawin 的工作,

定理 0.11 (Naslund-Sawin). 令 $\mathcal{F}$ 是无花族, 且其元素都是 $[n]$ 的子集. 那$$|\mathcal{F}|\le 3(n+1)\sum _{k\le n/3}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 3(n+1)c^n,\text{其中 }c=(\frac{3}{2}{)}^{\frac{2}{3}}\le \mathrm{1.89.}$$

证明. 注意对任意 $A\in \mathcal{F},A\subset [n]$, 都有一个相关的指标向量 $x\in \{0,1{\}}^n$, 对于任意 $i\in [n]$, 如果 $i\in A$,  我们置 $x_i=1$; 反之, 置 $0$. 我们叫新的集合 $S$.

我声称 $S$ 有如下性质: $$\forall x,y,z\in S,\exists i,\text{s.t.},\{x_i,y_i,z_i\}=\{0,1,1\},$$其中 $x,y,z$ 互异. 这个显然正确, 不然 $\mathcal{F}$ 会出现向日葵 (注意! 花心是空集属于伤心向日葵) .

对 $S$ 里任意向量 $x$, 我把其中 $1$ 的数量叫做重量 (这也对应着 $\mathcal{F}$ 中 $A$ 的基数). 现在, 我们可以把 $S$ 按照重量进行分解, $$S_l:=\{x\in S:重量(x)=l\},S=\bigcup _{l=0}^n{S}_l.$$显然, $S$ 无花蕴含 $S_l$ 一定也无花.

分解后, 我们可以对每一个 $S_l$ 做出如下断言: $$\forall x,y,z\in S_l,x+y+z\in \{0,1,3{\}}^n⟹x=y=z.$$因为如果 $x,y,z$ 有俩不一样, 那 $2$ 必然出现, 注意到 $x,y$ 和 $z$ 一样重. 不失一般性, 我们考虑 $z=x\ne y$, 那么对于 $x$ 和 $y$, 必然存在至少两个位置 $i,j$, 使得 $x_i\ne y_i$ 且 $x_j\ne y_j$. 不失一般性, 不妨考虑 $x_i=1$, 那么 $y_i=0$; 他们两个质量一样, 我们不妨认为位置 $j$ 上相互补齐, 也就是说 $x_j=0$,$y_j=1$. 这样, 因为 $x=z$, 那么 $x_i+y_i+z_i=2\notin \{0,1,3\}$.

现在我们构造一个多项式 $T:S_l^3\mapsto \mathbb{R}$, 这个多项式巧妙且精确地反应了无花这一性质. $$T(x,y,z):=\prod _{i=0}^n(2-(x_i+y_i+z_i)).$$$T$ 输出 $0$ 当且仅当在某个下标 $i$, $x_i,y_i,z_i$ 的和是 $2$, 这也意味着出现了向日葵; 整个多项式就死亡了.

通过第一条性质, 我们有如下推断$$T(x,y,z)\ne 0⟺\forall i,x_i+y_i+z_i\ne 2⟺x=y=z.$$

巧了, 对这种情况我们有引理 0.10 可以用, 于是我们有 $slicerank(T)=|S_l|$.

如果我们能给 $slicerank(T)$ 找到一个上界, 说明我们同样为 $|S_l|$ 找到了一个上界.

我们重新考察之前定义的多项式, 注意到我们可以把它写成三个单项式的积的线性组合, 每项只需要长这样: $$x_1^{i_1}\dots x_n^{i_n}{y}_1^{j_1}\dots y_n^{j_n}{z}_1^{k_1}\dots z_n^{k_n}.$$观察到, $$i_1,i_2,...,i_n,j_1,j_2,j_n,...,k_1,k_2,...,k_n\in \{0,1\}.$$同时, 因为 $T$ 的度数为 $n$. 因此我们有$$i_1+i_2+\cdots +i_n+j_1+j_2+\cdots +j_n+k_1+k_2+\cdots +k_n\le n.$$

注意到以下三个和里面$$i_1+i_2+\cdots +i_n,j_1+j_2+\cdots +j_n,k_1+k_2+\cdots +k_n$$至少有一个是 $\le \frac{n}{3}$ 的. 不失一般性, 设 $i_1+i_2+\cdots +i_n\le \frac{n}{3}$. 现在我们可以把其写成切片的形式了, $$f(x)g(y,z),$$其中 $f(x)=x_1^{i_1}\dots x_n^{i_n}$, 然后 $g(y,z)$ 是其他项, 只依赖 $y$ 和 $z$.

考虑到切片秩最多只能是能切出来切片的数量, 注意 ${\sum }_{a=1}^n{i}_a\le \frac{n}{3}$. 我们从度数 $0$ 数到度数 $n/3$, 因此对 $x$ 我们有

$$\sum _{k=0}^{n/3}\left(\genfrac{}{}{0ex}{}{n}{k}\right).$$当然我们要考虑 $y$ 和 $z$, 乘 $3$ 后拿到$$|S_l|\le 3\sum _{k=0}^{n/3}\left(\genfrac{}{}{0ex}{}{n}{k}\right).$$注意 $|S|={\sum }_{l=0}^n|S_l|,$ $$|S|\le \sum _{l=0}^n|S_l|\le 3(n+1)\sum _{k=0}^{n/3}\left(\genfrac{}{}{0ex}{}{n}{k}\right).$$

我们现在把常数变出来.

观察到对于 $0<x<1$, 根据二项式定理, $$x^{-\frac{n}{3}}(1+x{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{k-\frac{n}{3}}>\sum _{k=0}^{n/3}(\genfrac{}{}{0ex}{}{n}{k})x^{k-\frac{n}{3}}>\sum _{k=0}^{n/3}(\genfrac{}{}{0ex}{}{n}{k}).$$注意到 $x^{-\frac{1}{3}}(1+x)$ 最大值是 $(\frac{3}{2}{)}^{\frac{2}{3}}$, 出现在 $x=\frac{1}{2}$. 因此$$3(n+1)((\frac{3}{2}{)}^{\frac{2}{3}}{)}^n\ge 3(n+1)x^{-\frac{n}{3}}(1+x{)}^n\ge 3(n+1)\sum _{k=0}^{n/3}(\genfrac{}{}{0ex}{}{n}{k})\ge |S|.$$由于 $|S|=|\mathcal{F}|$, 得证.

$\square$

遗憾的是, 这种多项式方法似乎仅能用在三片花瓣的情况, 对于更多花瓣的向日葵就无能为力了.

参考文献

[1]	Alweiss, R., Lovett, S., Wu, K., & Zhang, J. (2021). Improved bounds for the sunflower lemma. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.
[2]	Babai, L., & Frankl, P. (2022). Linear Algebra Methods in Combinatorics. Section 5.4.
[3]	Erdős, P., & Rado, R. (1960). Intersection theorems for systems of sets. Journal of the London Mathematical Society, 35(1), 85-90.
[4]	Naslund, E., & Sawin, W. (2017). Upper bounds for sunflower-free sets. Forum of Mathematics, Sigma, 5, e15. https://doi.org/10.1017/fms.2017.12
[5]	Noel, J. (2020). Sunflower Lemma. MATH 492/529 Extremal Combinatorics, University of Victoria. [Video]. YouTube. https://www.youtube.com/watch?v=kGuUAK1hd0U
[6]	Tao, T. (2016). A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound. https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capsetbound/
[7]	Groenland, C. (2017, June). Sunflower conjecture and slice-rank method. Combinatorics seminar, University of Amsterdam. https://homepages.cwi.nl/ lex/files/ESsunflowerconjectureCarla.pdf
[8]	Deza, M., & Frankl, P. (1981). Every large set of equidistant $(0,+1,–1)$-vectors forms a sunflower. Combinatorica, 1(3), 225–231. https://doi.org/10.1007/BF02579328
[9]	Peter Frankl & Richard M. Wilson (1981). Intersection theorems with geometric consequences. Combinatorica, 1(1981), 357–368. https://api.semanticscholar.org/CorpusID:6768348