Union-closed猜想

有鑑於我的blog目標應該是推廣有趣的數學(in particular, extremal combinatorics)，我也該發點我不會做但別人會做的數學XD。由於建中/競賽/台大學弟Saintan最近在PhD job market上浮浮沉沉(?)並努力把它跟Shagnik最近的結果趕出來放上arXiv，就來介紹一下他們在幹麻吧！

我們先從經典的問題開始。問題很好敘述，所以就先上問題吧。

問題： 給你$[n]=\{1,\dots, n\}$的子集中的$m$個子集，假設蒐集起來是$\mathcal{F}=\{A_1,\dots, A_m\}$，使得對於任何$A,B\in \mathcal{F}$，$A\cup B$也落在$\mathcal{F}$裡。請問是否存在一個元素$i\in [n]$出現在至少$0.5m$個$\mathcal{F}$中的集合裡？

由於這個set family $\mathcal{F}$在取兩兩union這個操作下是closed的，所以猜測這命題是對的的猜想被稱為union-closed猜想。

而$0.5m$是緊的，因為你可以考慮所有$2^n$個集合，每個元素都出現在$0.5m=2^{n-1}$個集合中。

在大約兩年前的某個月黑風高的夜晚(?)，arXiv上忽然冒出一篇來自google的Justin Gilmer的文章，證明了上面這個問題的弱化版本。他證明了總是有某個元素出現在至少有$0.01m$個集合裡。雖然$0.01m$看起來離$0.5m$還有很大一段距離，但在extremal combinatorics這是一大突破，至少他說明了線性in $m$是對的order。在此之前人類知道的只有更弱的界(存在元素在$\sim \frac{m}{\log_2 m}$個集合裡)或是加強假設(假設固定$n$的時候$m$足夠大)的情況。而令人意外的是，這篇的證明相當的短，而在他的paper中也提到，如果把所有步驟都做到最好，可以得到$\frac{3-\sqrt5}{2}m$。而證明的主要工具還是entropy(還沒看過Alon-Spencer的The Probabilistic Method第14.6章的讀者請點擊右上角資訊欄(#))。假設大家都會entropy的定義的話，就讓我們來看看這個證明的想法吧！

以下是Gilmer的證明(https://arxiv.org/abs/2211.09055)加上Will Sawin的優化(https://arxiv.org/abs/2211.11504)的證明outline。目標是假設每個元素都出現在不到$\frac{3-\sqrt5}{2}m$個集合裡的話，導出矛盾。

首先，最核心的想法就是，如果你均勻隨機且獨立的從$\mathcal{F}$裡面取兩個集合$A,B$，那根據定義$A\cup B$這個隨機的集合也總是落在$\mathcal{F}$中，所以根據uniform bound它的entropy $H(A\cup B)\leq \log_2 m=H(A)$。然而如果每個元素都出現很少次，那它出現在$A$的機率就很低，那取完聯集每個元素出現在$A\cup B$的機率會比起原本更接近$1/2$，而我們都知道一個bit翻到$0$(或是$1$)機率越接近$1/2$的話，entropy會越大，所以有可能可以證明$H(A\cup B)>H(A)$，那就矛盾了！所以以下會專注在證明這條不等式上。

由於我們會用到每個元素出現的機率，我們就會想要考慮把集合$A$ 跟一個長度為$n$的$0,1$向量identify，就是說by abuse of notation，$A$作為向量第$i$紀錄的是$i$在不在集合$A$裡面。然後我們想要一位一位的看第$i$位對entropy的影響，所以我們定義$A_{i}$是$A$的第$i$位，$A_{\leq i}$是$A$的前$i$位，其他類似的符號同理。

那根據entropy的chain rule我們知道$H(A\cup B)-H(A)$可以拆成$H((A\cup B)_i\mid (A\cup B)_{<i})-H(A_i\mid A_{<i})$的和，所以我們只需要證明每一項都是正的即可。我們固定任何一個$i$，由於$i$出現在不到$\frac{3-\sqrt5}{2}m$個集合裡，所以$A_i=1$的機率不到$\frac{3-\sqrt5}{2}$，也就有$\mathbb{E}[A_i]<\frac{3-\sqrt5}{2}$。

我們知道$H((A\cup B)_i\mid (A\cup B)_{<i})\geq H((A\cup B)_i\mid A_{<i},B_{<i})$。而由於$A,B$是獨立的，我們有$H(A_i\mid A_{<i})=H(A_i\mid A_{<i},B_{<i})$。所以我們只需要證明$H((A\cup B)_i\mid A_{<i},B_{<i})-H(A_i\mid A_{<i},B_{<i})>0$。假設在給定$A_{<i},B_{<i}$的時候，$p,q$分別是$A_i,B_i$是$1$的機率。則$p,q$會是取決於$A_{<i},B_{<i}$的取值在$[0,1]$的隨機變數。

令$h(p)=-p\log_2 p-(1-p)\log_2(1-p)$表示機率為$p$的硬幣的entropy。我們知道conditional entropy可以想成是reveal conditional variable的entropy的期望值(對conditional variable取期望值)。我們還知道知道當固定$A_{<i},B_{<i}$的時候$A_i$的分布是一個機率$p$的硬幣，而$(A\cup B)_i$的分布是一個機率$p+q-pq$的硬幣。於是我們可以把$H((A\cup B)_i\mid A_{<i},B_{<i})-H(A_i\mid A_{<i},B_{<i})$寫成$\mathbb{E}[h(p+q-pq)-h(p)]$，其中$\mathbb{E}$是對$A_{<i},B_{<i}$取期望值。然後關於第$i$個元素出現在$A$裡的機率的條件，可以改寫為$\mathbb{E}[p]<\frac{3-\sqrt5}{2}$。

於是呢，我們成功把問題化簡為一個關於機率分布的不等式問題：

問題： 假設$\mu$是$[0,1]$上的一個機率分布。令$p,q$是兩個服從$\mu$且獨立的隨機變數，且$\mathbb{E}_{p\sim \mu}[p]<\frac{3-\sqrt5}{2}$。試證明$\mathbb{E}_{(p,q)\sim \mu\times \mu}[h(p+q-pq)-h(p)]>0$。

證明之前，我們先來看看為什麼是$\frac{3-\sqrt5}{2}$這個數字。假設你前面的bit都沒給你任何資訊(或是$i=1$你再看第一個bit)的話，那$p,q$都是固定的數字，然後期望值取了個寂寞。這時候你會有$p=q$，然後你想要的是$h(2p-p^2)>h(p)$，但我們知道$h(p)=h(1-p)$，而$p>\frac{3-\sqrt5}{2}$的時候$2p-p^2>1-p$，所以union之後entropy反而離最高峰$1/2$更遠了。

我們回到上面那個問題的證明。接下來我們稍微講一下這個證明的關鍵，詳細細節請看Sawin的paper。

注意到我們要證大於零的那項$\mathbb{E}_{(p,q)\sim \mu\times \mu}[h(p+q-pq)-h(p)]$只取決於我一開始給你的分布$\mu$，所以基本上我們就是要問說固定期望值$\mathbb{E}_{p\sim \mu}[p]$之下，哪個$\mu$讓那項最小。

我們假設$\mu$就是讓那項最小的機率分布。其中一個重要的觀察是$\mu$同時也是讓$\mathbb{E}_{q\sim \nu}[\mathbb{E}_{p\sim \mu}[2h(p+q-pq)-h(p)]]$最小的分布among所有$\nu$。我們可以用這件事情刻劃$\mu$該長怎樣。

我們令$F_{\mu}(q)=\mathbb{E}_{p\sim \mu}[2h(p+q-pq)-h(p)]$，則努力對$q$微分可以得到$F_{\mu}(q)$的反曲點至多只有一個。於是用數奧常見的$(n-1)$EV (?)，也就是把凸的部分的分布都往中間挪，凹的部分往外面挪，這樣取值的期望值會更小。所以我們可以假設$\mu$的機率集中在兩個點上，然後再努力一點就可以得到想要的不等式了。

證明大致就是這樣，可以繼續講故事了(?)。到現在為止最好的紀錄稍微比$\frac{3-\sqrt5}{2}m\approx 0.381966m$再更好一點。目前知道的是$\approx 0.3823455m$，離$0.5m$還有一段距離。

那Saintan跟Shagnik做了什麼呢？人們問了最常出現的元素，就會很自然問第二常第三常出現之類的。於是他們給出了以下的敘述的證明，大致上回答了這個問題。(https://arxiv.org/abs/2412.03862 and https://arxiv.org/abs/2412.03863)

定理： 令$k\geq 3$。假設$\mathcal{F}$是union-closed且$|\cup_{A\in\mathcal{F}}A|\geq k$。則第$k$常出現的元素出現在至少$\frac{m}{2^{k-1}+1}$個集合裡。

而這個定理是緊的，構造就留給讀者思考(或是去看他們paper XD)。那好奇的讀者就會問拉，$k=2$呢？Saintan表示他還在努力，剩下一堆finite case。而會剩finite case的原因也很妙，因為他們的bound來自兩邊。當$m$很小的時候，傳統的方法的$\sim \frac{m}{\log_2 m}$反而是會打贏的，而當$m$大的時候，可以用類似上面的entropy方法做。其中需要更改的部分只有，你會有$(k-1)$個bit的entropy貢獻不一定是正的，但實際上也不會負的太多，所以還是可以被其他bit的貢獻蓋過。