Number Theory. II. Triangle Removal Lemma

05-03

如果一個圖(Graph)有一個三角形，那顯然，我們可以移除一條邊，讓這個graph沒有三角形(triangle-free)。

如果一個圖有三個三角形呢？至多移除三條邊，就可以triangle-free了。並且如果我們知道這個graph只有4個點，那我們可以斷言至多移除2條邊就夠了。

我們發現，如果三角形相對於圖點的個數數量很多，那麼他們「重疊」的就相對多，我們就可以移除相對少的邊，讓graph triangle-free。我們有如下定理。

Theorem (Triangle Removal Lemma)
For every $varepsilon>0$ , there exists $delta>0$ such that if a graph $G$ of order $n$ which contains at most $delta n^3$ triangles, then we can remove at most $varepsilon n^2$ edges to make it triangle-free.

解釋一下：如果圖G中沒有特別多的三角形，我們可以移除相當少的邊，讓它triangle-free。

這個定理看起來平凡，顯然，簡直像一個簡單的數數問題，大概數一下平均的三角形個數就好了。然而這個定理其實是高度不平凡的，使用他可以輕鬆的證明Roth 定理：正密度集存在長度為3的等差數列。另外，上述定理中關於 $delta$ 的界也是一個很多人關心的問題，任何進展都可以發在Annals of Math上。下面我嘗試給出一個簡單的定理證明。

關於圖的cut norm，可以參考Yifan：有哪些指標可以描述兩個圖（graph）的相似度？

（一般來說這個專欄是不涉及證明的，但是因為這個定理太經典，所以我還是把證明放上來）

Proof. 假設定理不成立。

定義 $t(H,G)=frac{mathsf{hom}(H,G)}{|V(G)|^{|V(H)|}}$ 為子圖H在G中的密度，其中 $mathsf{hom}(H,G)$ 是從H到G的homomorphisms的數量，通過反證假設，存在 $varepsilon>0$ 和一個圖序列 ${G_i}_{i=1}^infty$ ，其中 $G_i$ 有 $i$ 個點，滿足 $t( riangle,G_n) o0$ 當 $n oinfty$ ，並且對每個 $G_n$ ，移除 $varepsilon n^2$ 個邊後還有三角形。通過選取 $G_n$ 的子列，不妨設對任意 $F$ 我們有 $t(F,G)$ 收斂。那麼 $G_n$ 存在極限 $W$ 。

（註：圖序列的極限 $W:[0,1]^2 o mathbb{R}$ 可測函數）

於是我們有 $t( riangle,W)=0$ 。並且對於每個 $G_n$ ，將點blow-up可以得到 $W_{G_n}$ ，我們有 $Vert W_{G_n}-WVert_{square} o0$ ，其中 $VertcdotVert$ 是cut-norm。設 $S={(x,y)in[0,1]^2mid W(x,y)>0}$ ，

$chi$ 是示性函數，我們有 $intlimits_{ [[0,1]^2}(1-chi_S)W_{G_n} ointlimits_{ [0,1]^2}(1-chi_S)W=0$ 。於是我們可以選取足夠大的 $N$ 使得 $intlimits_{ [[0,1]^2}(1-chi_S)W_{G_N}<varepsilon/4$ 。

記 $J_i=Big[frac{i-1}{N},frac{i}{N}Big]$ ， $R_{ij}=J_i imes J_j$ 。假設 $lambda$ 是Lebesgue測度，當 $lambda(Scap R_{ij})<frac{3}{4N^2}$ 時，移除 $G_N$ 的邊 $i j$ 得到圖 $G_N^prime$ 。

如果 $G_N^prime$ 還有三角形 $i,j,k$ ，則

$intlimits_{[J_I imes J_{j} imes J_k}chi_S(x,y)chi_S(y,z)chi_S(x,z),dxdydzgeqfrac{1}{4N^2}>0$

另一方面 $intlimits_{[J_I imes J_{j} imes J_k}chi_S(x,y)chi_S(y,z)chi_S(x,z),dxdydz=t( riangle,W)=0$ ，矛盾。

假設我們移除的邊超過了 $varepsilon n^2$ 條，有

$intlimits_{[[0,1]^2}(1-chi_S)W_{G_N}geqvarepsilon N^2intlimits_{R_{ij}}(1-chi)W_{G_N}geqfrac{varepsilon}{4}$ ，與 $N$ 的選取矛盾，證畢。

補充說明：我在上面說過，關於 $delta$ 的界的任意進展都是大新聞，比如Jacob Fox讀博士時證了目前最好的界，發了annals還被邀請到ICM做報告。然而，我上面給出的定理證明應該是目前最簡單的證明，由於太簡單了以至於提供不了任意的界！注意到證明中 $delta$ 的大小取決於 $N$ 的大小，然而我們只有 $N$ 的存在性。

Szemeredi的初始證明給出的 $delta^{-1}=f(1/varepsilon^2)$ ，目前關於 $delta^{-1}$ 最好的估計是 $f(log1/varepsilon)$ 。其中 $f(1)=2$ ， $f(n+1)=2^{f(n)}$ 。

Reference:

J. Fox, A new proof of the graph removal lemma. Ann. of Math. (2)174 (2011), no. 1, 561-579.
D. Conlon and J. Fox, Graph removal lemmas. Surveys in combinatorics 2013, 1–49, London Math. Soc. Lecture Note Ser., 409, Cambridge Univ. Press, Cambridge, 2013.