這次去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 ，我能完全切開一個多大的集合？更準確來說，我們定義 的VC-dim是最大的使得存在一個中大小是的子集合使得以下事情發生：考慮會取滿的任何子集合(包含空集合以及自己)，也就是說對於所有，都存在使得，而我們稱被 shatter。這個定義某種程度上刻畫了有多複雜。有了這個定義，我們可以問一些極值組合常問的問題。

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

好啦，認真的問題如下。

問題：假設我知道的VC-dim至多是，請問最大是多大？

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

定理：若的VC-dim至多是，則。

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

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

問題：假設我知道的VC-dim至多是，請問最大是多大？

首先注意到，如果有個大小是的集合被 shatter，那必須在裡面。於是實際上條件等價：對於所有，存在使得對於所有都有。

那我們可以怎麼構造呢？考慮是所有包含且大小是的集合所成的family，則對於所有，取是任何中不包含的子集，則不存在(因為交集總是有)。我們稱這個是個star，而我們知道，於是我們會問說這個是不是最好的構造。首先，Frankl–Pach證明了一個蠻接近的上界。

定理：若的VC-dim至多是，則。

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

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

定理：若的VC-dim至多是，則。

我們把跟的差從推進到了，也提示了可能是正確的大小(指數怎麼可能不是整數嘛(#))。

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

猜想：令。若，且對於所有，存在大小是的使得對於所有都有。則。

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

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