李安

摘 要：“六人集會(huì)問題”將拉塞姆定理帶入眾人的視線。拉姆塞定理的內(nèi)容為：對于任意的正整數(shù)P、Q大于等于2，總存在正整數(shù)N0，使得任意一個(gè)至少有N0個(gè)點(diǎn)的圖G中或者含有P個(gè)兩兩有邊相連的點(diǎn)，或有含有Q個(gè)兩兩都無邊相連的點(diǎn)，針對上述拉塞姆定理的內(nèi)容，數(shù)學(xué)家們提出了很多其他理論。其中較為突出的是舒爾定理和范德瓦爾登定理。范德瓦爾登定理內(nèi)容為對任意給定的L，K屬于N，存在W屬于N，使得把{1，…，W}任意拆成K個(gè)部分后，其中必有一部分含有L項(xiàng)等差數(shù)列。通過參考舒爾定理有限形式的乘法形式的推廣過程，即利用指數(shù)函數(shù)包裝等差數(shù)列的方法，范德瓦爾登定理也可以進(jìn)行等比數(shù)列的推廣，最終得出結(jié)論：對于任意正整數(shù)L，K，可以找到一個(gè)對應(yīng)的N，使得對任意C：{1，2，3…，N}→K，都可以找到一個(gè)公比不為1，項(xiàng)數(shù)為L的等比數(shù)列。該結(jié)論使拉塞姆定理的推廣內(nèi)容更加完善，以及為進(jìn)一步的推廣提供了思路和方法。

關(guān)鍵詞：拉姆塞定理;舒爾定理;范德瓦爾登定理;等比數(shù)列

中圖分類號(hào)：TB ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ?doi：10.19311/j.cnki.1672-3198.2020.05.101

1 拉姆塞理論

“任意367個(gè)人中，一定有二人生日相同”，類似這樣的結(jié)論，只要稍加思考，便會(huì)點(diǎn)頭稱是。我們把總結(jié)這類問題的原理稱為“抽屜原理”，又稱“鴿籠原理”。“抽屜原理”更概括的說法是：把多于K·N個(gè)東西任意分放進(jìn)N個(gè)空抽屜，那么一定有一個(gè)抽屜中放進(jìn)了至少K+1個(gè)東西。

通過“抽屜原理”我們可以了解到拉姆塞定理的遠(yuǎn)祖，而拉姆塞定理最簡單又不平凡的特例卻是“六人集會(huì)問題”：在任意六個(gè)人的集會(huì)上，或者有三個(gè)人以前彼此認(rèn)識(shí)，或者有三個(gè)人以前彼此不認(rèn)識(shí)。這個(gè)問題簡單標(biāo)準(zhǔn)的證明是：在平面上任意做出A、B、C、D、E、F六個(gè)點(diǎn)代表六個(gè)不同的人，若其中兩人認(rèn)識(shí)則用紅線將這兩人代表的點(diǎn)連接起來，反之則用藍(lán)線連接起來。那么原來問題的證明等價(jià)于證明連線后存在紅邊三角形或藍(lán)邊三角形。觀察其中某一點(diǎn)，設(shè)為F，從F連出五條邊，易知，其中必有三條同色。不防設(shè)FA、FB、FC是紅邊，若AB是一條紅邊，則FAB是紅邊三角形;若AB是一條藍(lán)邊，則ABC是藍(lán)邊三角形（如圖1所示），證畢。通過“六人集會(huì)問題”的簡單證明，可以引出更為科學(xué)的定理—拉姆塞定理。

下面我們介紹經(jīng)典的拉姆塞定理，首先我們需要了解完全圖的概念。一個(gè)圖G由兩部分組成，分別是點(diǎn)集V和邊集E，故可寫成G=（V，E）。而一個(gè)圖G如果滿足點(diǎn)集中的任意兩點(diǎn)都連邊，則稱G為完全圖，另外，若V中有n個(gè)點(diǎn)，則稱G為Kn完全圖2。