拉姆塞理論[拉姆塞(Ramsey)理論]

拉姆塞理論可以用通常的語言來表述。在一個集會上，兩個人或者彼此認識，或者彼此不認識，拉姆塞得出結果是說，當集會人數大於或等於6時，則必定有3個人，他們或者彼此認識或者彼此都不認識。

拉姆塞是位天才的英國科學家，只活了26歲。在他去世的1930年，他發表了一篇學術論文，其副產物就是所謂拉姆塞理論。

拉姆塞理論可以用通常的語言來表述。在一個集會上，兩個人或者彼此認識，或者彼此不認識，拉姆塞得出結果是說，當集會人數大於或等於6時，則必定有3個人，他們或者彼此者認識或者彼此都不認識。6稱為拉姆塞數，記r（3,3）。進一步當集會人數大於或等於18時，則必定有4個人，他們或者彼此都認識或者彼此都不認識，用記號表示就是r（4,4）=18。可是集會有多少人，才能有5個人都彼此認識或都不認識呢？時至今日，r（5,5）的精確數目我們還不知道，至於其他的r(n,n）當然就更不清楚了。不過，我們的確證明r(n,n）是一個有限數，的確存在，甚至有精確的上界和下界。只是其中究竟哪一個是拉姆塞數，就不得而知了。因此，求r(n,n）的精確值是一個難題。

拉姆塞理論還有進一步的推廣，一個最簡單的推廣是r(s,t），也就是集會至少有多少人，才能有s個人互相都認識或者t個人互相都不認識。可以證明r(s,t)=r(t,s），因此，我們不妨假定s≤t。現在知道的精確的r(s,t）的值極少，只有如下的9種情形：r（3,3）=6 r（3,4）=9 r（3,5）=14 r（3,6）=18 r（3,7）=23 r（3,8）=28 r（3,9）=36 r（4,4）=18 r（4,5）=25;

在這裡值得提一下，這9個非平凡Ramsey數中，僅僅 r（3,8）=28 有我們中國的學者的身影，該數是由南京大學張克民教授和澳大利亞國立大學麥凱用計算機作為輔助工具共同得到的，其計算量為10的14次方機器指令，這在當時是非常大的計算量，因此也成為當時圖論中用計算機作為輔助工具解決組合問題繼四色問題之後一個比較典型的問題 。

而且我們還知道r（3,t）的一個上界：

r（3,t）≤ (t^2+3）/2

r（3,3,3）=17