Thursday, June 26, 2008

A version of Szemerédi's theorem

給定兩個數 k (欲得之等差數列的長度) 和 d (density),其中 k 為正整數,d 為 (0, 1/2] 的實數。則存在一個 N = N(k,d),使得 {1, 2, ..., N} 當中每一個大小至少為 dN 的 subset 都會有一個長度為 k 的等差數列。

截至目前為止,N(k,d) 的 upper bound 和 lower bound 如下:



其中 C > 0.


參考資料:Wikipedia

++++++++++++++++++++++++++++++++++++

這個定理怎麼跟 regular partitions of graphs 扯上關係的,我還得再看看。我想這應該是 testing large graphs 的精髓所在。

No comments: