概率方法

它让我们只需逐一相加各个概率,就能计算出某个计数的平均值,而完全不必关心这些事件之间如何相互影响——这是概率方法中最有用的捷径。

将 $X = \sum_{i=1}^m \mathbb{1}[A_i]$ 记作:若 $A_i$ 发生则 $\mathbb{1}[A_i]$ 取 $1$,否则取 $0$。期望本身被定义为按概率加权对各结果求的和(或积分),而这个和对有限个随机变量总是可加的——无论这些变量是否独立都成立,因为期望的可加性从不依赖独立性,只依赖我们是在同一个概率测度上求和这一事实。

形式上,由有限个随机变量之和的期望可加性,有 $\mathbb{E}[X] = \mathbb{E}\left[\sum_{i=1}^m \mathbb{1}[A_i]\right] = \sum_{i=1}^m \mathbb{E}[\mathbb{1}[A_i]]$。

最后,对任意指示变量都有 $\mathbb{E}[\mathbb{1}[A_i]] = 1 \cdot \Pr[A_i] + 0 \cdot \Pr[\overline{A_i}] = \Pr[A_i]$。代入上式,便恰好得到 $\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i]$,且完全不需要对 $A_i$ 之间的关系做任何假设。

随着 $k$ 增大,$n$ 个顶点的图中 $k$ 元子集的个数只按 $n$ 的多项式增长,但某个特定子集为单色的概率却按 $k$ 的双指数速度缩小。平衡这两种速度就说明,即便 $n$ 相对于 $k$ 呈指数级增长,单色团的期望个数依然低于 $1$——这比任何人手工构造出的结果都要好得多。

令 $n = \lfloor 2^{k/2} \rfloor$。由上面一阶矩的计算,$\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$。若能证明 $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$,那么由于 $X$ 只取非负整数值,必存在某个2染色使得 $X=0$——否则总有 $X \ge 1$,从而迫使 $\mathbb{E}[X]\ge 1$。满足 $X=0$ 的染色完全不含单色 $k$ 元团。

用 $\binom{n}{k} \le n^k/k!$ 估计二项式系数,且由 $n \le 2^{k/2}$ 得 $n^k \le 2^{k^2/2}$。代入期望公式,$\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$。

化简指数:$\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$。于是 $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$,因此只需对所有 $k \ge 3$ 证明 $k! > 2^{1+k/2}$。

对 $k$ 用归纳法验证。基础情形 $k=3$:$3! = 6$,$2^{1+3/2} = 2^{2.5} \approx 5.657$,确实 $6 > 5.657$。归纳步骤:设某个 $k \ge 3$ 时 $k! > 2^{1+k/2}$ 成立。那么 $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$,又因 $k+1 \ge 4 > \sqrt2$,此式超过 $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$,这正是 $k+1$ 时的结论。故 $k! > 2^{1+k/2}$ 对一切 $k \ge 3$ 成立,由此得到所需的 $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$。

因此存在 $K_n$ 的一个不含单色 $k$ 元团的2染色,故 $R(k,k) > n = \lfloor 2^{k/2}\rfloor$。对任意实数 $x$ 都有 $\lfloor x\rfloor + 1 > x$,所以 $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$,这正是 $R(k,k) > 2^{k/2}$。