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$ 。

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

$t(K_{1,i},G)=\frac{\sum_{v\in V(G)}\text{deg}(v)^i}{n^{i+1}}\geq \frac{1}{n^i}(\frac{\sum_{v\in V(G)}\text{deg}(v)}{n})^i=(\frac{2m}{n^2})^i=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_0)+\mathbb{P}(A_1)+\dots\leq r.$

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

$\frac{1}{1-t(K_2,G)}=1+t(K_2,G)+t(K_2,G)^2+\dots\leq r.$

就得證了。實際上這個證明味道類似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)$ ，則我們有

$\log_2(2m)=H(X,Y)\leq 2H(X)+\log_2(1-\frac{1}{r})\leq 2\log_2 n+\log_2(1-\frac{1}{r}).$

我們前面用過一個算兩次，我們會需要如下的引理取代它，這個引理的弱化版本在我們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的方法我們知道

$H(T_1)=H(X_1,X_2,X_3,X_4)+H(X_3\mid X_1,X_2)=5H(X_1)+\log_2(x_1x_2^2x_3),$

$H(T_2)=H(X_1,X_2,X_3,X_4)+H(X_1\mid X_2,X_3,X_4)=5H(X_1)+\log_2(x_1^2x_2x_3),$

$H(T)=H(X_1,X_2,X_3,X_4)+H(W\mid X_1,X_2,X_3,X_4)\leq H(X_1,X_2,X_3,X_4)+H(W\mid X_2).$

注意到 $(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$ 。