Monday, June 30, 2008

Most degrees into a large set are large (the proof is worked out!)

Theorem: Let (A,B) be an ɛ-regular pair with density d. Then for any , we have




這個定理應該是挺直覺的,照理講不難證明才對。在 paper 裡只是一個 "fact"。在稍微思考之後,我自己寫了一個證明如下。
Proof:

Let be a constant. Let


and assume that

. ..................... (*)

Hence we have
......................(1)

But , since (A,B) are ɛ-regular, we have
..........................(2)

(2) contradicts (1), therefore the theorem is then proved.



呃...好像真的不難...

其實直覺上來講,就是說 small degree 的 vertices 一旦太多,就會把邊的密度拉的太低,違反 regularity 的定義。證明的 trick 在於把這些 small degree 的點看成一個 subset,如此便滿足子集合的 size 大於 ɛ|A| 的條件,而形成稀疏的邊集。


定理出處:
J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi: The regularity lemma and its applications in graph theory. Theoretical Aspects of Computer Science, Lecture Notes Comput. Sci., Vol. 2292, pp. 84--112, 2002.


2 comments:

BarrosH said...

可是我覺得一點都不直覺ㄟ.....Orz

我比較笨嗎XD

Joseph, Chuang-Chieh Lin said...

一開始我也這樣想,後來發現我對於 regularity 的定義並沒有真正了解,後來慢慢就清楚了。其實 regularity 的定義同時給了 subsets 的邊集密度 upper bound 和 lower bound。

說穿了,如果 degree 小的點太多了,會使得邊集的密度降得太低,低過 regularity 所保證的 lower bound。

我自己的感覺,會忍不住把 regularity 和 dense 連想在一起。當兩個 vertex subsets 為 regular pair 時,某種程度上來說,它們之間的邊不會太少。