將一個稀疏圖平均切分成 k 個子圖的時間複雜度是多少？

01-11

這是個很有趣的問題，實際上和素數的分布問題，Green-Tao定理也息息相關。當然這裡我們考慮一個「好的」等價劃分來描述一個稀疏圖，使得每兩部分之間有一些「random-like」的性質。

對於Dense Graph的情形已經廣為人知了。Szemeredi regularity lemma告訴我們，給定一個任意小的數 $varepsilon$ ，我們可以將稠密圖分成有限的 $K$ 部分，並且 $K$ 只與 $varepsilon$ 有關，使得幾乎每兩部分之間都是quasi-random graph。

演算法上我們也有Frieze-Kannon regularity lemma，可以在O(n)時間內把圖分成K個相等的部分，使得幾乎每兩部分之間"weak" regular。所謂「weak」可以理解成，在cut distance意義下，圖G和一個K部隨機圖「很接近」。

實際上regularity lemma對稀疏圖同樣成立，但是為什麼這麼nice的定理對sparse的情形就不太好用呢？想起了之前和朋友的聊天。

我：雖然我的前女友已經和新男友在一起快半年了，但是我還是覺得她是世界上除了我家人之外最在意我的人。

朋友：可是她也不怎麼在意你啊。

我：對，但是...別人更不在意我。所以我們需要一種比較精細的度量。

對dense的情形，我上面回答的都是，「幾乎」每兩部分。也就是說，除了 $varepsilon K^2$ 對之外，都成立。但是對於sparse的情形，有趣的部分可能發生在除去的部分。下面的例子也許聽起來更舒服一些：你想測一下家裡電腦的元件電壓，是不是在4V到4.5V之間，你用一個最小單位是10V的表肯定什麼都測不出來，即使這個表沒有壞。

也就是說，Szemeredi regularity lemma告訴我們，稠密的圖都長一個樣，稀疏的圖各有各的不同。

最簡單的修正，是在regularity lemma的所有地方乘上相應的圖的密度，用同樣的方法可以證明，新的sparse regularity lemma是正確的。這裡也算回答了一下問題，對於「均勻」的稀疏圖，也就是存在常數C，任意點集A，B，他們之間的邊最多 $C|A||B|p$ 條，其中p是圖的密度。在這種情況下，存在O(n)演算法可以把圖分成 $K$ 部分，使得幾乎每兩部分weak regular，這裡的「幾乎」乘了密度p，所以不存在忽略太多有趣的邊數的情況了。

但是對於稀疏圖的主要難點是....counting lemma用不了了。我們剛才一直在想辦法對圖進行regular劃分，目的就是讓每兩部分之間「random-like」。random graph的好處就是，我們可以數數。比如一個圖G(n,p)，我們可以說他很大概率有 $n^2p/2$ 這麼多邊（Chebyshev不等式直接推論），因此可以用來估計我們感興趣的非隨機圖的邊或者特定子圖的數量。比如圖中的三角形就是長度為3的等差數列。

但是稀疏圖不行。比如G(n,p)，讓 $p=o(n^{1/2})$ ，那麼圖中三角形數量 $n^3p^3ll n^2p$ ，後者是邊的數量。也就是說我們可以移除相當少的邊，讓圖G既保證隨機性，又不包含triangle。對於triangle-free的圖，triangle counting lemma當然不成立。目前的做法是將我們感興趣的圖G稠密的嵌入另一個稀疏圖H中，H滿足一些性質，我們稱H為pseudorandom graph，這樣counting lemma就可以用了。

對於H要滿足的性質，不同的人有不同的方法。其中一種，好像是Gowers和合作者的結果，就是讓H是jumbled graph，也就是他的第二個特徵值的一個約束。

另外一種叫linear form condition，也就是Green-Tao定理用的。假設我們想數G中的三角形數量，那我們就讓H中triangle 的 2 blow-up 以及所有子圖數量正確。下圖就是三角形的blow up。