隨機圖的著色數與獨立數（the chromatic and independence numbers of a random graph）

一張圖最難的兩個組合參數是它的獨立數 alpha(G)（內部無邊的最大頂點集之大小）與著色數 chi(G)（為使相鄰頂點異色所需的最少顏色數）。對一般圖求其一皆為 NP 難，然而對隨機圖 G(n,p) 二者都被驚人精確地釘住——這是機率方法與集中性的勝利。它們回答的問題是：隨機圖有多「可攤開」（有大獨立集嗎？）、有多「凝聚」（需要許多顏色嗎？），又被多麼尖銳地決定？

為具體起見取稠密情形 p = 1/2。獨立數由對給定大小獨立集計數所用的第二動差法支配：大小為 k 的獨立集存在的機率趨於 1 或 0，視 2^k 2^(-C(k,2)) 為大或小而定，這給出 alpha(G) 集中在 2 log_2 n 附近本質上兩個相鄰整數上。同樣的計算施於團（完全子圖）顯示團數也約為 2 log_2 n 且有兩點集中——這是 Bollobas、Erdos 與 Matula 的著名結果。著色數於是由下被 chi >= n/alpha 強迫（每個顏色類是大小至多 alpha 的獨立集），給出 chi(G) >= n/(2 log_2 n)；Bollobas 的深刻定理（用鞅集中、Azuma／頂點揭露不等式）顯示此下界是緊的：chi(G(n,1/2)) 漸近於 n/(2 log_2 n)。對稀疏 G(n, c/n) 著色數集中在有界個數值上，Shamir-Spencer 加 Luczak 證明它 whp 是至多兩個相鄰整數之一——儘管我們往往說不出是哪兩個。

這些結果之所以重要，是因為它們是組合學中測度集中的櫥窗：著色數這個極其複雜的整體泛函，靠鞅論證被集中在寬度 O(1) 或 O(sqrt(n)) 的窗口內，即使其確切值未知。它們也推動圖著色演算法的理論與約束滿足門檻的分析。此處要保持的誠實尤為尖銳：集中並不代表我們知道值。頂點揭露鞅（逐頂點揭露圖）每步最多改變 chi 一，故 Azuma 立即給出 O(sqrt(n)) 內的集中，更細的論證給出兩整數的窗口——但釘住確切常數或確切的值對，數十年來一直是開放的，而對稀疏圖，k 著色性門檻的精確位置是一個深刻、直到近年才（靠帶權第二動差法與統計物理的想法）解決的問題。