入一個很重要定理，還是老生常談得廢話一番：

這是大師Szemerédi在研究Ramsey問題所發明得一個方法

首先重要性，很前沿，一般應用正則引理證明得結論都會發一個不錯的文章

其次說一說它得大體上的感覺，由於是極值圖論，Ramsey問題，因此它蘊含得道理和Ramsey問題十分相似

即一個充分大得系統一定存在我們想要的子結構

更具哲學意義的是：一個系統不可能是完全紊亂沒有規律得

圖如此，人如此，自然界亦是如此

言歸正傳下面來介紹本文

（ps由於證明過於深長，因此先講一個應用）

  • Szemerédi s regularity lemma
  • 證明需要用的引理
  • 證明 Erdos & Stone theorm

1.1 Szemeredis regularity lemma

為了引入正則引理我們來引入幾個概念：

Density：

這個概念看起來不難，但是需要解釋一下：

我們通常說的密度是什麼呢，粗略的說是一立方米所含物質得量（原諒我學的十分爛得物理，大概這個意思）

這裡顯然不是，而是兩個點集X，Y之間得連線個數與X，Y所構成的完全二部圖的比例

舉個例子比如：X中有3個點，Y中有4個點， d(X,Y)=0.5 這說明X，Y間有6條邊，因為X，Y間一共可以有12條

（圖明天補）

說了一堆讓我們往下進行：

epsilon-regular ：

這是一個關於邊分布的概念，我們很容易可以看出來，如果這個 epsilon 足夠的小，那麼也就是A，B的任意的子集都會和A，B的密度差不多，不會出現很極端的情況（比如A中只有一個點連B中所有的點，A中其餘點與B無連接）

epsilon-regular partition :

這裡首先需要說明一下這個 V_{0} 很顯然這個 left| V ight| 並不一定能夠被 k 整除，因此我們把餘下的點放在一個集合里也就是V_{0}，所以我們有這樣一個關係： left| V_{0} ight|equivleft| V ight|(mod k)

Regularity Lemma :

由於這個證明特別的深長，因此以後專門單獨寫一個專題

雖然我們在開篇說了一下正則引理，不過在這裡我們細緻的看一下它

首先我們需要輸入兩個數 epsilon、m 然後呢我們會得到一個 M 它是分類的上界，而且我們也會得到一個 k 的頂點分類，將原圖均勻的分成 epsilon-regular 的 k 個部分

這正好說明了，我們如果給了一個充分大的圖，那麼我們一定可以找到一個均勻的分類方法，使得邊均勻的分布在各個點集之間。

1.2重要引理：

我們將會看到接下來要引入的引理在應用正則引理時候往往會優先考慮，二者相輔相成，相映成輝。

還是先引入一個概念：

a regularity graph of G :

Lemma 1 :

我們依舊感知一下這個引理得威力：它的結論是可推出，也就是蘊含於，換句話說，我們想要知道H在G中只需要知道H在G得正則性圖中，這樣大大得簡化了G得複雜性，由於正則性引理保證了這個R得存在性，又由這個引理來保證H在G中的存在性。

我們可以看到這似乎成為了應用正則性引理得一般思路：

  1. 給定正則性引理得參數，得到一個正則性子圖R
  2. 再通過引理中的參數，來保證子結構得存在性

1.3 證明 Erdos & Stone theorm

很顯然這個定理是如下定理得推廣

解決問題之前捋一下思路：我們現在得目標是，用正則性引理說明我們給定的圖G有一個正則性子圖R，我們可以調整生成R得密度，讓R得邊儘可能得多，然後這樣用定理7.1.1我們就有一個包含 K^{r} 得子圖。

這樣我們得 R_{s} 中就包含了一個 K^{r} （這一點是顯然得）這樣自然的我們就可以應用引理1

這樣就完成了證明，我們來看一下其中的係數如何連接。

首先很自然，確定題中得參數，翻譯一遍題目。

首先我們尋找最自由的，最基礎的變數： d varepsilon Delta m 事實上我們再看幾個應用也會發現每次這幾個都是最先確定的，他們自由，而且基礎。

這個n顯然是大於m的（M乘一個大於1的數）

現在我們對於圖G有了一個正則性劃分： left{ V_{0}, V_{1}, V_{2}, ... V_{k} ight} 其中 mleq k leq M

我們讓 left| V_{1} ight|=left| V_{2} ight|=...=left| V_{k} ight|=l ,顯然我們有 ngeq lk 和

我們現在已經有了一個 G 的正則性子圖 R（epsilon ,l,d） 接下來我們只需要說明 K^{r}in R

然後由引理我們可以知道 K^{r}_{s}in R .

很自然的我們希望應用 Turan theorm ,這就需要說明 R 中的邊數足夠的多，我們需要數一下 R 中的邊數，由於 R 中邊是由 G 來的我們來看一下這個過程邊得變化， G 中的邊變成了一下幾類：

  • V_{0} 中的邊
  • V_{0} 和 V_{i} iin {1，2，3...k } 間的邊
  • 非正則對 left( V_{i} ,V_{j} ight) 也就是兩個集合間密度不夠均勻的那些邊.
  • 正則對 left( V_{i} ,V_{j} ight) 但是密度不夠 d 的那些邊.
  • V_{1}, V_{2}, ... V_{k} 每個集合內的邊.
  • 最後，是密度夠大的正則對 left( V_{i} ,V_{j} ight) 的邊，也就是 R 的邊.

分別看一下這些邊的最大值：

第一部分 對於V_{0} 中的邊顯然有：

left| left| V_{0} ight| ight| leq left( ^{V_{0} } _2 ight) leq frac {1}{2}left( epsilon n ight)^{2}

第二部分 V_{0} 和 V_{i} iin {1，2，3...k } 間的邊最多：

left| V_{0} ight| k l leq epsilon n^2

第三部分 非正則對 left( V_{i} ,V_{j} ight) 也就是兩個集合間密度不夠均勻的那些邊：

根據正則引理這部分的集合數最多有 epsilon k^2 對

每對最多 l^2 個邊，所以這部分是

epsilon k^2l^2

第四部分 正則對 left( V_{i} ,V_{j} ight) 但是密度不夠 d 的那些邊.

frac{1}{2}k^2dl^2

第五部分 V_{1}, V_{2}, ... V_{k} 每個集合內的邊.

最多顯然有 left( ^{l } _2 ight)k 個

最後一部分 最後，是密度夠大的正則對 left( V_{i} ,V_{j} ight) 的邊，也就是 R 的邊.

R 中每個邊至多 l^2 個

這部分最多 left| left| R ight| ight|l^2 個

所以說我們來求和：

Gleqfrac {1}{2}left( epsilon n ight)^{2}+epsilon n^2+epsilon k^2l^2+frac{1}{2}k^2dl^2+ left( ^{l } _2 ight)k+left| left| R ight| ight|l^2

因此我們有如下變形：

我們得到了 K^{r}in R .

推薦閱讀：

相关文章