Uniform set systems with small VC-dimension

這次去IBS收穫滿滿，聽Huy證了一遍Kahn–Kalai，跟子超做了個幾何上的Zarankiewicz，還跟被徐子翔翔哥找了一起做extremal set的問題。只能說，extremal set好好玩XD

Paper以一個很快的速度放上了arXiv(至少比我以前所有paper都快XD)，其他三個人感覺都是超hard-working的人OAO，只有我擅長拖延，我道歉。

俗話說的好，道歉就要露出arXiv連結：https://arxiv.org/abs/2501.13850

以下進入數學部分，但這篇blog應該主要是講故事XD。首先我們先介紹VC-dimension的概念。基本上就是問你給你一個set family $\mathcal{F}\subseteq 2^{[n]}$，我能完全切開一個多大的集合？更準確來說，我們定義 $\mathcal{F}$的VC-dim是最大的$k$使得存在一個$[n]$中大小是$k$的子集合$S$使得以下事情發生：考慮$S\cap F,F\in\mathcal{F}$會取滿$S$的任何子集合(包含空集合以及自己)，也就是說對於所有$B\subseteq S$，都存在$F\in\mathcal{F}$使得$S\cap F=B$，而我們稱$S$被$\mathcal{F}$ shatter。這個定義某種程度上刻畫了$\mathcal{F}$有多複雜。有了這個定義，我們可以問一些極值組合常問的問題。

問題： 考慮$\mathcal{F}$是所有你參與過的paper的作者集合所形成的family，請問他的VC-dim是多少(#)

好啦，認真的問題如下。

問題： 假設我知道$\mathcal{F}\subseteq 2^{[n]}$的VC-dim至多是$d$，請問$\mathcal{F}$最大是多大？

Sauer–Shelah定理給出了這個問題的精確答案。

定理： 若$\mathcal{F}\subseteq 2^{[n]}$的VC-dim至多是$d$，則$|\mathcal{F}|\leq \sum_{i=0}^{d}\binom{n}{i}$。

這個定理可以用純組合方法證明，而且不難，推薦有興趣的讀者讀一遍。而這個上界是緊的，因為可以考慮如下構造：令$\mathcal{F}$是所有$[n]$中大小小於$d+1$的集合所成的family，則任何大小是$d$的集合$S$，你都無法找到$F\cap S=S$，所以VC-dim小於$d+1$。

在這個構造中，我們基本上是靠大小取勝的(?)。所以就會問說，那如果我固定$F$的大小呢？首先，這個大小是少得是$d+1$才有意義，不然我可以像上面一樣全取，於是我們可以考慮問題如下。

問題： 假設我知道$\mathcal{F}\binom{[n]}{d+1}$的VC-dim至多是$d$，請問$\mathcal{F}$最大是多大？

首先注意到，如果有個大小是$d+1$的集合$S$被$\mathcal{F}$ shatter，那$S$必須在$\mathcal{F}$裡面。於是實際上條件等價：對於所有$F\in\mathcal{F}$，存在$B_F\subsetneq F$使得對於所有$F'\in\mathcal{F}$都有$F\cap F'\neq B_F$。

那我們可以怎麼構造呢？考慮$\mathcal{F}$是所有包含$1$且大小是$d+1$的集合所成的family，則對於所有$F\in\mathcal{F}$，取$B_F$是任何$F$中不包含$1$的子集，則不存在$F\cap F'=B_F$(因為交集總是有$1$)。我們稱這個$\mathcal{F}$是個star，而我們知道$|\mathcal{F}|\binom{n-1}{d}$，於是我們會問說這個是不是最好的構造。首先，Frankl–Pach證明了一個蠻接近的上界。

定理： 若$\mathcal{F}\subseteq \binom{[n]}{d+1}$的VC-dim至多是$d$，則$|\mathcal{F}|\leq \binom{n}{d}$。

But，就是這個but。Ahlswede–Khachatrian以及Mubayi–Zhao給出了更大的構造，其中$|\mathcal{F}|=\binom{n-1}{d}+\binom{n-4}{d-2}$。所以狀況是：上界跟$\binom{n-1}{d}$差了$\binom{n-1}{d-1}=O(n^{d-1})$，下界跟$\binom{n-1}{d}$差了$\binom{n-4}{d-2}=\Omega(n^{d-2})$。不久前，徐子翔、叶智恺、张盛桐以及其他人證明了上界總是不緊的。原本的Frankl–Pach上界以及這個證明都是base on多項式方法：考慮對於每個$F$，構造一個多項式使得這些多項式線性獨立，那我們就有關於$|\mathcal{F}|$跟多項式空間維度的關係。

於是我去IBS訪問的時候被翔哥推坑了這個問題。然後在大佬們的carry下，有了這篇paper的第一個結果：

定理： 若$\mathcal{F}\subseteq \binom{[n]}{d+1}$的VC-dim至多是$d$，則$|\mathcal{F}|\leq \binom{n-1}{d}+O(n^{d-1-\frac{1}{4d-2}})$。

我們把跟$\binom{n-1}{d}$的差從$n^{d-1}$推進到了$n^{d-1-\frac{1}{4d-2}}$，也提示了可能$n^{d-2}$是正確的大小(指數怎麼可能不是整數嘛(#))。

而我更關心的其實是能不能有個正確版本的猜想使得star真的是最好的。於是我們考慮了以下$B_F$也是uniform的問題。

猜想： 令$n\geq 2d+2, 0\leq s\leq d$。若$\mathcal{F}\subseteq \binom{[n]}{d+1}$，且對於所有$F\in\mathcal{F}$，存在大小是$s$的$B_F\subsetneq F$使得對於所有$F'\in\mathcal{F}$都有$F\cap F'\neq B_F$。則$|\mathcal{F}|\leq \binom{n-1}{d}$。

當$s=0$的時候，條件等價於$\mathcal{F}$中任兩個集合都相交，於是猜想等價於Erdős–Ko–Rado定理。而我們驗證了$s=d$的時候以及當$n$足夠大且$s=1$的時候猜想都是對的。

而我們paper中這兩部分的證明都回歸到純組合方法，其中我們用到一個很重要的觀察：如果有很多$F$的$B_F$是同一個集合的話，那你總是可以在這些$F$中找到一個sunflower，也就是一些$F_1,\dots,F_r$使得這些集合扣掉全部人共同的交集之後兩兩不交。當$r$夠大加上$B_F$的條件後，$\mathcal{F}$的長相就被大幅限制了。