色數的集中（concentration of the chromatic number）

色數的集中是這樣一個令人驚訝的事實：隨機圖的色數 chi(G) 儘管是個全域且組合上精細的量，卻異常緊密地聚集在其（通常未知的）平均值附近——有時集中在僅僅幾個值上。色數是把頂點著色使相鄰頂點異色所需的最少顏色數；它以錯綜複雜的方式依賴整個圖。人們也許預期它會在不同隨機圖間大幅波動，事實卻相反，這是組合學中鞅集中最乾淨的例證之一。

第一個結果由 Shamir 與 Spencer 給出，使用頂點曝露鞅：由於增加一個頂點至多使 chi 改變 1，有界差 Azuma 不等式給出 sqrt(n) 尺度的集中，P(|chi - E[chi]| > t sqrt(n)) <= 2 e^(-t^2/2)。驚人的精化來自 Bollobas 等人：對稠密隨機圖 G(n, 1/2)，色數以趨於 1 的機率集中在寬度 O(sqrt(n)/log n) 的區間上，且事實上漸近為 chi(G) ~ n / (2 log_2 n)。更驚人的是稀疏範圍：Shamir 與 Spencer 證明，對 G(n, p)、p = n^(-alpha) 且 alpha > 1/2，色數以趨於 1 的機率集中在恰好兩個連續整數上——這現象稱為兩點集中。證明結合曝露鞅（證明無論 chi 取何值都是銳利集中的）與一個獨立的計數論證（證明它能取的少數值是聚集的），因為單憑 Azuma 從不告訴你平均在何處。

其重要性與它所警示者：它是一個里程碑，展示有界差鞅集中可遠比天真的變異數估計所暗示的更銳利，而兩點集中是一種非凡的剛性。但誠實的微妙之處正是集中與定位之間的鴻溝。鞅論證證明 chi 集中在其平均 E[chi] 附近，卻從未計算 E[chi]；釘住實際區間（那兩點，或 n/(2 log n) 的漸近）需要完全獨立的組合工作來界定實際所需的顏色數。也有一個已知的極限：對非常稀疏的圖（p 約 1/n），兩點集中可能失敗，而確定所有密度下集中的確切寬度仍部分未解。集中並不意味我們能算出色數——只意味它幾乎不變動。