格拉漢姆數

設 是最小維度 的 超立方體，使得如果連線所有角對的線被 雙色著色，對於任何 ，一個單色 完全圖 將會被強制出現，且具有共面頂點。通俗地說，這個定義等價於考慮來自某人數 的每個可能的委員會，並列舉每對委員會。現在將每對委員會分配到兩個組中的一個，並找到最小的 ，即最小的 ，它將保證存在四個委員會，其中所有對都屬於同一組，並且所有人都屬於偶數個委員會（Hoffman 1998, p. 54）。

Graham 和 Rothschild (1971) 證明了答案存在，他們也提供了已知的最佳上限，由下式給出

(1)

其中格拉漢姆數 由遞迴定義為

(2)

和

(3)

這裡， 是所謂的 高德納箭號表示法。 通常被認為是實際應用中用過的最大數字（Exoo 2003）。

在 鏈式箭號表示法 中， 滿足不等式

(4)

Graham 和 Rothschild (1971) 也透過證明 必須至少為 6，從而提供了一個下限。最近，Exoo (2003) 已經證明 必須至少為 11，並提供了實驗證據表明它實際上甚至更大。