拉姆齊數的機率下界（probabilistic lower bounds for Ramsey numbers）
/ RAM-zee /
拉姆齊數的機率下界是機率方法的奠基性勝利，至今仍是其最驚人的展示之一。拉姆齊數 R(k, k) 是最小的 n，使得完全圖 K_n 的邊的每種二著色都含有 k 個頂點上的單色團——一個所有邊同色的完全子圖。拉姆齊定理保證 R(k, k) 有限；問題是它有多大。下界 R(k, k) > n 意味著存在 K_n 邊的一種二著色，沒有單色 k 團，亦即一種「避開秩序」的著色。明確地展示這樣的著色極為困難；機率方法幾乎免費地產生一個。
Erdos 1947 年的論證：用公平硬幣獨立地把 K_n 的每條邊染紅或藍。對固定的 k 個頂點，其 C(k,2) 條邊全同色的機率為 2 乘以 2^(-C(k,2))（全紅或全藍）。由第一動差法（聯集界），單色 k 團的期望個數至多為 C(n,k) * 2^(1 - C(k,2))。若此期望個數嚴格小於 1，則以正機率沒有單色 k 團，故存在一種好著色，R(k, k) > n。簡短計算表明：只要 n 至多約為 2^(k/2) / e 乘以一個多項式因子，期望便低於 1，給出 R(k, k) > (1 + o(1)) (k / (e sqrt(2))) 2^(k/2)。刪除法藉由容許少數單色團並從每個刪除一個頂點，把常數再略為銳化。
令人驚奇的事實，也是每門課都先講這個例子的原因，是知識與構造之間的鴻溝。機率界 2^(k/2) 在 1947 年兩行內被證明；最佳的明確拉姆齊著色構造卻指數級落後超過六十年，直到最近才透過偽隨機性的深刻工作逼近隨機界。上界 R(k,k) <= 4^k（Erdos-Szekeres）使指數的底數介於 sqrt(2) 與 4 之間仍未確定——這是著名的未解問題——即使改進下界中的常數也很困難。誠實的提醒是：此方法證明沒有大單色團的著色存在卻不指明任何一個：它是純粹的存在性證明，數十年來無人能寫下單一一個與隨機著色所達成者相當的著色。
取 k = 10。一個單色 10 團用掉 C(10,2) = 45 條同色邊，對固定的 10 元集機率為 2 * 2^(-45)。對 C(n,10) 個集合的期望計數約在 n ~ 2^5 = 32（差常數倍）處降到 1 以下，故存在 K_32 邊的一種紅藍著色沒有單色 10 團，證明 R(10,10) > 32——這個界的取得從未展示過該著色。
單色 k 團期望個數 C(n,k) 2^(1 - C(k,2)) < 1 強制存在好著色：R(k,k) > 約 2^(k/2)。
證明給出存在卻無見證者：隨機界 R(k,k) > 約 2^(k/2) 直到六十年後才被明確構造匹配，而指數底數（sqrt(2) 對 4）仍是著名的未解問題。