組合學/拉姆齊數的界

拉姆齊定理中的數字R(r,s)（以及它們對兩種以上顏色的擴充套件）被稱為拉姆齊數。拉姆齊理論中一個主要的研究問題是找出各種r和s值的拉姆齊數。我們將在本文中推匯出任何一般拉姆齊數R(r,s)的經典邊界。這意味著該R(r,s)的精確值位於兩個界限之間，即下界和上界。

上界

上界實際上是從拉姆齊定理的證明中推匯出來的。由於R(r, s) ≤ R(r − 1, s) + R(r, s − 1)，所以這會自動給出上界，儘管不是我們期望的封閉形式。封閉形式表示式為 $R(r,s)\leq {\binom {r+s-2}{r-1}}$ 。為了推匯出這一點，我們對 r 和 s 進行雙重歸納。基本情況r = s = 2 很容易確定，因為 $R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2$ 。現在假設表示式對於R(r − 1, s) 和 R(r, s − 1) 成立。然後 $R(r,s)\leq R(r-1,s)+R(r,s-1)\leq {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}$ 為我們提供了上界。注意，我們在最後一個等價關係中使用了帕斯卡關係。

如果R(r − 1, s) 和 R(r, s − 1) 都是偶數，那麼可以進行輕微改進。在這種情況下，不等式是嚴格的。

結果： 如果R(r − 1, s) + R(r, s − 1) 都是偶數，那麼R(r, s) < R(r − 1, s) + R(r, s − 1)。

證明： 假設R(r, s) = R(r − 1, s) + R(r, s − 1)，其中R(r − 1, s) 和 R(r, s − 1) 都是偶數。令n = R(r − 1, s) + R(r, s − 1) − 1。現在，根據我們對n的選擇，存在一個在n個頂點上的完全圖，即一個K_n，它既沒有紅色的K_r，也沒有藍色的K_s。在討論中固定此K_n。同時固定K_n 中的一個頂點v。

現在很明顯，如果從v 出發的紅色邊的數量小於R(r − 1, s) − 1，而藍色邊的數量小於R(r, s − 1) − 1，那麼從v 出發的總邊數將小於R(r − 1, s) + R(r, s − 1) − 2，這是一個矛盾，因為v 與恰好R(r − 1, s) + R(r, s − 1) − 2 個頂點相連。因此，從v 出發的紅色邊的數量至少為R(r − 1, s) − 1，或者從v 出發的藍色邊的數量至少為R(r, s − 1) − 1。不失一般性，假設第一個成立。現在我們將證明從v 出發的紅色邊的數量不能超過R(r − 1, s) − 1。假設它們確實超過了。現在，選擇與v 由紅色邊連線的任何R(r − 1, s) 個頂點，並考慮由這些頂點形成的K_{R(r − 1, s)}。根據拉姆齊定理，它應該包含紅色的K_r-1 或者藍色的K_s。根據我們對n 的選擇，它不能包含後者。因此，它包含一個紅色的K_r-1。但是，將此紅色K_r-1 的頂點與v 連線起來會得到一個紅色的K_r，這也是不可能的。因此，紅色邊的數量不能超過R(r − 1, s) − 1。因此，它們必須恰好是R(r − 1, s) − 1。然後，剩餘的藍色邊數為R(r, s − 1) − 1。總之，我們可以說，我們K_n 中的每個頂點都與其他n − 1 個頂點恰好連線了R(r − 1, s) − 1 條紅色邊和R(r, s − 1) − 1 條藍色邊。

因此，K_n 中紅色邊的總數為 ${\frac {n(R(r-1,s)-1)}{2}}$ ，它必須是一個整數。但是，由於R(r − 1, s) 和 R(r, s − 1) 都是偶數，所以這是不可能的。因此，初始的等式是不可能的。所以R(r, s) < R(r − 1, s) + R(r, s − 1)。

下界

由保羅·埃爾德什給出的一個論證得出的經典下界在下面給出。該論證被稱為機率方法。它為R(r,r) 提供了一個下界，縮寫為R(r)。

首先要注意，如果我們在一個隨機著色的K_n中給定一組r個頂點，紅色或藍色，那麼K_r是單色的機率是 $2^{1-{\binom {r}{2}}}$ 。要了解這一點，請注意，有2種方法可以對 ${\binom {r}{2}}$ 條邊中的每一條進行染色，因此染色總數的可能性是 $2^{\binom {r}{2}}$ 。在這些可能性中，只有2種是有利的：紅色K_r或藍色K_r。因此，我們給定的K_r是單色的機率是 $2^{1-{\binom {r}{2}}}$ 。

現在，如果在開始時沒有固定一組r個頂點，那麼出現單色K_r的機率是多少？有 ${\binom {n}{r}}$ 種方法可以從n個頂點中選擇r個頂點。根據機率加法定律，我們可以簡單地取任意r個頂點集，得到其機率如上所述為 $2^{1-{\binom {r}{2}}}$ ，然後移動到另一個r個頂點集，得到其機率為 $2^{1-{\binom {r}{2}}}$ ，依此類推；然後我們可以將所有機率加起來得到得到單色K_r的機率。但這可能發生，我們選擇的兩個r個頂點集都產生了單色K_r。這換句話說，這些事件不一定是互斥的。因此，加法定理不適用，總機率肯定不能保證為 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$ 。但是，根據布林不等式，我們至少可以得出結論，K_n中存在單色K_r的機率不能超過 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$ 。

現在，如果 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}<1$ ，那麼這告訴我們，K_n中存在單色K_r的機率小於1，因此K_n中不存在單色K_r。這只是另一種說法，即 $R(r)>n$ 。

現在固定 *r* 並令 *N* 為滿足以下不等式的 *n* 的最小值： ${\binom {n}{r}}2^{1-{\binom {r}{2}}}\geq 1$ 。由於滿足此不等式的數字集合非空；*R*(*r*) 本身就是一個例子，並且有下界；*r* 和任何小於 *r* 的數字都是不屬於此集合的下界，因此保證存在最小值。

還要注意的是， $R(r)\geq N$ ，因為如果 $R(r)<N$ ，那麼 $R(r)\leq N-1$ 。但這與 $R(r)>N-1$ 相矛盾，因為 ${\binom {N-1}{r}}2^{1-{\binom {r}{2}}}<1$ 。因此 $R(r)\geq N$ 。

所以，

R(r)\geq N=(N^{r})^{\frac {1}{r}}>\left({\binom {N}{r}}r!\right)^{\frac {1}{r}}\geq (2^{{\binom {r}{2}}-1}r!)^{\frac {1}{r}}=2^{{\frac {r}{2}}-{\frac {1}{2}}-{\frac {1}{r}}}(r!)^{\frac {1}{r}}

現在使用斯特林公式對階乘進行近似，該公式適用於 *r* 的較大值；即 $r!\approx {\sqrt {2\pi r}}\,\left({\frac {r}{e}}\right)^{r}$ 。因此對於較大的 *r*，簡化後得到，

R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}(\left({\frac {\pi }{2}}\right)^{\frac {1}{2r}}r^{\frac {1}{2r}})

.

由於右邊的括號內的項始終大於 1，因此我們可以得出結論：對於較大的 *r*， $R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}$ 。

已知的拉姆齊數

下表顯示了 *r* 和 *s* 的值在 10 以內的 *R*(*r*,*s*)。如果精確值未知，則表中列出了已知的最佳邊界。對於小於 3 的 *r* 和 *s* 的值，*R*(*r*,*s*) 由 *R*(*1*,*s*) = *1* 和 *R*(*2*,*s*) = *s* 給出，適用於所有 *s* 的值。拉姆齊數研究進展的標準調查是由斯塔尼斯拉夫·拉德齊斯佐夫斯基編寫的，他還與布倫丹·麥凱一起找到了 *R*(4,5) 的精確值。

r,s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–42
4	1	4	9	18	25	36–41	49–61	59–84	73–115	92–149
5	1	5	14	25	43–48	58–87	80–143	101–216	133–316	149–442
6	1	6	18	36–41	58–87	102–165	115–298	134–495	183–780	204–1171
7	1	7	23	49–61	80–143	115–298	205–540	217–1031	252–1713	292–2826
8	1	8	28	56–84	101–216	134–495	217–1031	282–1870	329–3583	343-6090
9	1	9	36	73–115	133–316	183–780	252–1713	329–3583	565–6588	581–12677
10	1	10	40–42	92–149	149–442	204–1171	292–2826	343-6090	581–12677	798–23556

對角線存在一個微不足道的對稱性。

此表摘自由Stanisław Radziszowski編制的更大的表格。

多色示例：R(3,3,3) = 17

多色Ramsey數是使用3種或更多種顏色的Ramsey數。只有一個非平凡的多色Ramsey數其確切值已知，即R(3,3,3) = 17。

假設你有一個使用3種顏色（紅色、黃色和綠色）對完全圖的邊進行著色。進一步假設邊著色沒有單色三角形。選擇一個頂點v。考慮與頂點v有綠色邊的頂點集。這被稱為v的綠色鄰域。v的綠色鄰域不能包含任何綠色邊，因為否則將存在一個由該綠色邊的兩個端點和頂點v組成的綠色三角形。因此，在v的綠色鄰域上誘導的邊著色只有兩種顏色，即黃色和紅色。由於R(3,3) = 6，v的綠色鄰域最多可以包含5個頂點。類似地，v的紅色和黃色鄰域最多可以包含5個頂點。由於除v本身之外的每個頂點都在v的綠色、紅色或黃色鄰域之一中，整個完全圖最多可以有1 + 5 + 5 + 5 = 16個頂點。因此，我們有R(3,3,3) ≤ 17。

要看到R(3,3,3) ≥ 17，只需在16個頂點的完全圖上繪製一個使用3種顏色對邊進行著色，該著色避免了單色三角形。事實證明，在K₁₆上恰好有兩種這樣的著色，即所謂的非扭曲著色和扭曲著色。兩種著色都在右圖中顯示，頂部的非扭曲著色，底部的扭曲著色。在圖中的兩種著色中，注意頂點都被標記，並且頂點v₁₁到v₁₅在左邊和右邊都繪製了兩次，以便簡化繪圖。

因此，R(3,3,3) = 17。

已知在K₁₅上恰好有兩種使用3種顏色的邊著色，它們避免了單色三角形，這些著色可以透過分別從K₁₆上的非扭曲著色和扭曲著色中刪除任何頂點來構建。

還已知在K₁₄上恰好有115種使用3種顏色的邊著色，它們避免了單色三角形，前提是我們認為顏色排列不同的邊著色是相同的。