Entropy Turán-當甜點師傅炒菜時

跟眼皮HHH Yu的paper生出來了XD。連結：https://arxiv.org/abs/2412.08075。這次先講故事好了。

去年visit IBS的時候，身邊一群人看起來都很會各種extremal graph尤其是Turán相關的問題跟技巧，但我只會polynomial method跟entropy。我就跟眼皮開玩笑說感覺我跟大家討論就像是在一間中餐館炒菜，有人端出一盤牛肉，有人端出一顆高麗菜，有人端出一碗蝦子，問說能不能放在一起做成一道菜。

此時我端出一碗冰淇淋問說：

於是我就丟給眼皮以下問題：

問題： 假設我告訴你 joints很沒結構，你能改進joints的上界嗎？像是我現在有$\mathbb{R}^3$中$n$條線，任三條在projective space不交，我要用幾個平面才能通過每條線兩次？

然後就被識破了= =。好嘛，不要野心那麼大，我們先看看能不能entropy嘛。那，paper都發了，答案就是可以。心路歷程是這樣的，首先triangle-free有一個簡單的做法可以看出來，但無法推廣到更大的clique-free，於是我想了很久就擱置了。之前做hypergraph joints的時候感覺又學會了一些有趣的entropy招式(雖然後來沒用出來)，就決定revisit這個問題。於是我們先很蠢的發現我們猜測的命題假設已知Turán定理本身的情況下是可以證出來的，但我們想要直接用entropy證明Turán嘛總不能循環論證。然後某天晚上半夜12點我忽然靈光一現(半夜太興奮害我隔天中午recitation超沒精神)，就生出了這篇paper的開端。以下進入數學部分。

首先，通常entropy比較難刻畫一些整數性問題，所以我們目標是證density Turán。在敘述定理之前，我們先介紹一下符號。$G$是一張簡單圖，有$n$個頂點跟$m$條邊，並且我們用$V(G)$與$E(G)$表示$G$的點集合跟邊集合。我們說$G$是$H$-free的如果$G$不包含$H$作為子圖。令$K_{r}$為$r$個頂點的完全圖。

定理： 假設$G$是$K_{r+1}$-free的，則我們有$m\leq(1-\frac{1}{r})\frac{n^2}{2}$。

這個定理之所以被稱為density Turán是因為他可以改寫為關於邊密度的不等式，其中我們這篇提到的所有密度都是指homomorphism density。對於一個函數$f:V(H)\rightarrow V(G)$，我們說他是$G$到$H$的homomorphism如果$f$總是把邊映射到邊。那我們可以定義homomorphism density $t(H,G)$為你均勻隨機的選一個$f:V(H)\rightarrow V(G)$，它是homomorphism的機率。也就是說$t(H,G)$是homomorphism個數除以$n^{|V(H)|}$。則我們知道邊的homomorphism density $t(K_2,G)=\frac{2m}{n^2}$，所以density Turán可以被改寫為

定理： 假設$G$是$K_{r+1}$-free的，則我們有$t(K_2,G)\leq(1-\frac{1}{r})$。

在用entropy證明這件事之前，我們先來看一個不用entropy的證明，但可以從它看出來entropy證明應該要長怎樣。

在證明之前，我們需要以下的關於star有Sidorenko性質的引理。

引理： 對於任何圖$G$，我們總是有$t(K_{1,i},G)\geq t(K_2,G)^i$。

而這個引理的證明基本上就是一個柯西不等式：

有這個引理我們就可以開始證明Turán了。首先隨機sample一串$G$的頂點$v_0,v_1,\dots$(均勻隨機且獨立的選，且可以重複)。令事件$A_i$為$v_i$跟前面所有人都有連邊的事件，其中$A_0$是總是為真的事件。如果有$r+1$個事件同時成立的話，假設下標是$0=i_0\leq i_1\leq\dots\leq i_r$，則我們知道$v_{i_0},\dots,v_{i_r}$之間兩兩有連邊，於是找到一個$K_{r+1}$得到矛盾。所以同時至多只能有$r$個事件發生。根據算兩次我們有

另一方面，根據引理我們知道$\mathbb{P}(A_i)=t(K_{1,i},G)\geq t(K_2,G)^i$。所以我們有

就得證了。實際上這個證明味道類似Caro跟Wei的一個關於independent set大小的定理的證明(他們的定理也可以imply density Turán) 。Fun fact：Wei是台灣人，有一個很代數的Turán證明by Li and Li，兩個李都是台灣人，所以目前Turán的證明出現了五個台灣人了XDD

好啊，那接著講entropy證明。首先我們用到了Sidorenko，所以可以預期的我們要用類似Szegedy證明很多東西是Sidorenko的方法sample這些star。(更一般的情況可以參考Yufei note的section 10.3，我們今天只會用到一些特例)

但在開始證明之前，我們需要先把定理改寫一下，並且證明個引理。

定理： 假設$G$是$K_{r+1}$-free的。令$X,Y$是$G$上的兩個隨機頂點使得$\{X,Y\}$總是一條邊，且$(X,Y)$的分佈是對稱的(也就是$(X,Y)$跟$(Y,X)$分佈一樣)。則我們有$H(X,Y)\leq 2H(X)+\log_2(1-\frac{1}{r})$。

不難看出這個定理imply density Turán：如果我們均勻隨機的從所有有序邊中sample $(X,Y)$，則我們有

我們前面用過一個算兩次，我們會需要如下的引理取代它，這個引理的弱化版本在我們Kruskal–Katona定理的entropy證明中出現過。

複習一下，一個隨機變數$X$的support $\text{supp}(X)$是所有使得$\mathbb{P}(X=x)>0$的$x$所成的集合。

定義： 我們說一些隨機變數$X_1,\dots,X_k$有$(a+1)$-wise disjoint supports若對於任何$x$，它至多出現在$a$個$\text{supp}(X_i)$中。

定義： 我們說$Z$是一些隨機變數$X_1,\dots,X_k$的mixture若$Z$是透過以下過程得到的。先丟一個跟其他隨機變數都獨立的骰子(機率可以不均勻)決定一個下標$\mathbf{i}$，然後令$Z=X_{\mathbf{i}}$。

引理： 假設隨機變數$X_1,\dots,X_k$有$(a+1)$-wise disjoint supports，則存在一個它們的mixture $Z$使得$2^{H(X_1)}+\dots+2^{H(X_k)}\leq a2^{H(Z)}$。

證明基本上就是好好的選mixture用到的骰子的機率，然後用$H(\mathbf{i}\mid Z)\leq \log_2a$以及一堆entropy的等式就有了，細節可以看我們的paper。

有了這個引理，我們就可以來證明上面的定理了。先固定一個正整數$N$，對於每個$0\leq i\leq N$，我們sample $N+1$個頂點$T_i=(v_0^{(i)},\dots,v_N^{(i)})$如下。我們先用$(X,Y)$的law sample一條邊$(v_0^{(i)},v_i^{(i)})$，然後condition on $v_i^{(i)}$，獨立的resample $i-1$個$v_0^{(i)}$，分別稱為$v_1^{(i)},\dots,v_{i-1}^{(i)}$。剩下的$v_{i+1}^{(i)},\dots,v_N^{(i)}$每個都是獨立的用$X$的law sample出來。(其中$T_0$是$N+1$個點每個都獨立的用$X$的law sample出來)

那我們可以算一下$T_i$的entropy。我們可以想成$v_{i}^{(i)},\dots,v_N^{(i)}$每個都貢獻跟$X$一樣多的entropy，而$v_0^{(i)},\dots,v_{i-1}^{(i)}$每個都貢獻跟$Y\mid X$一樣多的entropy。所以$H(T_i)=iH(Y\mid X)+(N+1-i)H(X)$。

注意到$T_0,\dots,T_N$的supports得是$(r+1)$-wise disjoint的，因為$T_i$總是包含一個從$v_{i}^{(i)}$往前面所有點連的star。

於是我們可以用上面的引理得到一個$T_0,\dots,T_N$的mixture $T=(v_0,\dots,v_N)$，注意到$v_i$的law跟$X$也得一樣。所以有$H(T)\leq (N+1)H(X)$。而引理的不等式告訴我們$\sum_{i=0}^N 2^{H(T_i)}\leq r2^{H(T)}$。如果假設$x=2^{H(Y\mid X)-H(X)}$，我們會有$\sum_{i=0}^N x^i\leq r$。取$N$趨近無限大我們就有$\frac{1}{1-x}\leq r$，也就是$\log_2x=H(Y\mid X)-H(X)=H(X,Y)-2H(X)\leq \log_2(1-\frac{1}{r})$，即得證。

而這個證明有幾個好處，首先$H(X,Y)-2H(X)$的最大值其實是Lagrangian，而$H(X,Y)-H(X)$的最大值會是spectral radius，所以他其實關聯著圖上的一些常見的量。而另一個好處是我們可以推廣到hypergraph並且在上面做些有趣的事情。以下是其中一個例子的特例。

令$H,G$是兩個hypergraph，我們說$G$是$H$-hom-free的如果不存在從$H$打到$G$的homomorphism。

以下我們考慮的都是$4$-uniform hypergraph。令$\Delta_{(2,1,1)}$表示hypergraph with edges $1234,125a,35bc,45de$(總共四條邊使用了$12345abcde$總共$10$個頂點，用英文表示的代表這個頂點只出現在一條邊，所以驗有沒有從$\Delta_{(2,1,1)}$到$G$的homomorphism的時候可以忽略這些點)。則我們有以下定理。

定理： 假設$G$是$\Delta_{(2,1,1)}$-hom-free的。令$X_1,X_2,X_3,X_4$是$G$上的四個隨機頂點使得$\{X_1,X_2,X_3,X_4\}$總是一條邊，且$(X_1,X_2,X_3,X_4)$的分佈是對稱的。則我們有$H(X_1,X_2,X_3,X_4)\leq 4H(X_1)+\log_2(4!/4^4)$。

類似前面的entropy證明，我們可以定義$x_1=2^{H(X_1\mid X_2,X_3,X_4)-H(X_1)}$, $x_2=2^{H(X_1\mid X_2,X_3)-H(X_1)}$, $x_3=2^{H(X_1\mid X_2)-H(X_1)}$, $x_4=2^{H(X_1)-H(X_1)}=1$。由於$x_1x_2x_3x_4=2^{H(X_1,X_2,X_3,X_4)-4H(X_1)}$，我們的目標是要證明$x_1x_2x_3x_4\leq 4!/4^4$。我們可以先證明$x_i+x_j\leq x_{i+j}$。我們以$x_1+x_2\leq x_3$為例，一般情況都類似以下證明。

我們從$X_1,X_2,X_3,X_4$出發。Condition on $X_1,X_2$獨立的 resample $X_3$得到$Y$。Condition on $X_2,X_3,X_4$獨立的 resample $X_1$得到$Z$。令$T_1=(X_1,X_2,X_3,X_4,Y)$, $T_2=(X_1,X_2,X_3,X_4,Z)$。我們有$T_1,T_2$的support是不交的。否則假設$(v_1,v_2,v_3,v_4,w)$在兩個support裡，根據$T_1$我們知道$v_1,v_2,v_3,v_4$是一條邊，$v_1,v_2,w$落在一條邊裡。根據$T_2$我們知道$v_2,v_3,v_4,w$是一條邊。如此的話，把$\Delta_{(2,1,1)}$的頂點$12345$分別映射到$v_1,v_2,v_3,v_4,w$是一個homomorphism，矛盾。

於是我們可以用上面關於mixture的引理，得到$T=(X_1,X_2,X_3,X_4,W)$是$T_1,T_2$的一個mixture使得$2^{H(T_1)}+2^{H(T_2)}\leq 2^{H(T)}$。根據sample的方法我們知道

注意到$(X_2,Y)$跟$(X_2,Z)$的law是一樣的(都跟$(X_1,X_2)$一樣)，所以$(X_2,W)$的也一樣。也就是說$H(W\mid X_2)=H(X_1\mid X_2)$，所以$H(T)\leq 5H(X_1)+\log_2(x_1x_2x_3^2)$。於是$2^{H(T_1)}+2^{H(T_2)}\leq 2^{H(T)}$告訴我們$2^{5H(X_1)}(x_1x_2^2x_3+x_1^2x_2x_3)\leq 2^{H(T)}\leq 2^{5H(X_1)}x_1x_2x_3^2$也就是$x_1+x_2\leq x_3$。

所以剩下的就是一個純粹的競賽不等式了。

引理： 給定非負實數$x_1,\dots,x_{k-1},x_k=1$，滿足$x_i+x_j\leq x_{i+j}$對於所有$i+j\leq k$皆成立。則我們有$x_1x_2\dots x_k\leq k!/k^k$。

想學這個競賽不等式怎麼做嗎？去找吧，都放在我們的paper裡了。