Friday, July 11, 2008

Approximating the graph by empty graphs

今天下午跟 BarrosH 討論,對於 papers 裡常提到的底下這一句話,有一點小心得。

Note that the Regularity Lemma is only meaningful for dense graphs, because for sparse graphs, the density of edges between the pieces of the partition tends to 0.

因為一個 sparse graph 的邊不多,所以一旦把邊都集中在 partition 裡的 blocks 裡面,那 block 與 block 之間的邊就會非常少。把 block 用點來代表,如果一個 block-pair 為 dense (ε-)regular,則兩個對應的點就連上一條邊,這樣得到的圖形就是所謂的 regularity graph。如下圖所示, V = {a, b, c, d, e, f, g, h, i, j, k, l},可以 partition 成 3 個 blocks。




因為絕大部分的邊都集中在 blocks 裡面,所以 block-pairs 之間的 density 很低,所以形成的 regularity graph 非常有可能擁有極少的邊,當然 density 為 0 也滿足 regular pair 的條件 (非常低或非常高都很容易滿足 regular pair 的條件)。因此,我們很容易可以得到一個滿足 regularity 的 partition,以及一個對應的 regularity graph,亦即一個 (幾乎是) empty graph。Regularity lemma 重視的是 block pairs 之間的邊,所以一旦圖形不是 dense graph,威力就大打折扣。

另外,假設有 k 個 blocks,當然令它為一個 constant。每個 block 裡面會有 n/k 左右的點,所以去算一個 block pair 的 density,大概會有底下的結果:



所以說,當 n 夠大時,造出來的 regularity graph 是 empty graph,應該是沒有問題。果然,有討論真的有差。感謝 B 大的分享。

No comments: