格拉汉姆数

设 是最小维度 的 超立方体，使得如果连接所有角对的线被 双色着色，对于任何 ，一个单色 完全图 将会被强制出现，且具有共面顶点。通俗地说，这个定义等价于考虑来自某人数 的每个可能的委员会，并枚举每对委员会。现在将每对委员会分配到两个组中的一个，并找到最小的 ，即最小的 ，它将保证存在四个委员会，其中所有对都属于同一组，并且所有人都属于偶数个委员会（Hoffman 1998, p. 54）。

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

(1)

其中格拉汉姆数 由递归定义为

(2)

和

(3)

这里， 是所谓的 高德纳箭号表示法。 通常被认为是实际应用中用过的最大数字（Exoo 2003）。

在 链式箭号表示法 中， 满足不等式

(4)

Graham 和 Rothschild (1971) 也通过证明 必须至少为 6，从而提供了一个下限。最近，Exoo (2003) 已经证明 必须至少为 11，并提供了实验证据表明它实际上甚至更大。