9、概率方法

概率空间

定义：概率空间

$(Ω, P)$ ， $Ω$ 为有限集， $P : 2^{Ω} \to [0, 1]$ ，测度 $P$ 满足

$P (\emptyset) = 0$
$P (Ω) = 1$
$P (A ⊔ B) = P (A) + P (B)$ 。

把 $Ω$ 的每个子集称为事件： $P (A) = \sum_{ω \in A} P ({ω})$ 。

定义：随机变量

函数 $X : Ω \to R$ 称为一个随机变量。

定义：随机变量的期望

$E [x] := \sum_{ω \in Ω} P ({ω}) X (ω) .$

期望具有线性性：

定理：期望的线性性

$X, Y$ 为 $Ω$ 上随机变量，则

E [X + Y] = E [X] + E [Y] .

在组合学中，概率方法常见的用法是：

技术：概率方法

假设我们需要找到一些组合对象，满足某些属性——称为“好属性”。考虑候选项的大集族并从中随机取出，称其为一个随机对象。若取出“好”对象的概率是正的，则必存在好对象。
为了计算“好”对象的概率，我们常计算“坏”对象并论证其严格小于1。

并集的界

定理

若 $n, s$ 满足 $(\binom{n}{s}) 2^{1 - (\binom{s}{2})} < 1$ ，则 $R (s, s) > n$ 。

证明： 只需找一个 $K_{n}$ 的2-染色，其中无 $K_{s}$ 团。

令 $Φ$ 是全体 $K_{n}$ 的 2-染色线成的集合。任取 $c \in Φ$ 。则 $c$ 是一个随机 2-染色。注意各边被染为某色概率为 $\frac{1}{2}$ ，且各边独立。

令事件 $B$ ：该2-染色不包含单色 $K_{s}$ 。希望 $P (B) > 0$ 。为此，考虑补事件 $A = Φ ∖ B$ 及其概率 $P (A)$ 。

对任意子集 $S \in (\binom{[n]}{s})$ ，假设其 $A_{S}$ 为 $S$ 构成一个单色 $K_{s}$ 的概率，则 $P (A_{S}) = 2^{1 - (\binom{s}{2})}$ 。另一方面， $A = ⋃_{S \in (\binom{[n]}{s})} A_{S}$ ，则

P (A) = P (⋃_{S \in (\binom{[n]}{s})} A_{S}) \leq \sum_{S \in (\binom{[n]}{s})} P (A_{S}) = (\binom{n}{s}) 2^{1 - (\binom{s}{2})} < 1.

这就说明了 $P (B) > 0$ 。

推论

$R (s, s) \geq \frac{s}{e \sqrt{2}} 2^{\frac{s}{2}} .$

证明： 令 $n =$ 这一坨。回忆 $(\binom{n}{s}) < \frac{n^{s}}{s!}$ 且 $s! > e {(\frac{s}{e})}^{s}$ ，我们有

(\binom{n}{s}) 2^{1 - (\binom{s}{2})} < \frac{n^{s}}{e (s / e)^{s}} 2^{1 - (\binom{s}{2})} = 1.

因此 $R (s, s) > n = \frac{s}{e \sqrt{2}} 2^{\frac{s}{2}} {(\frac{e}{2})}^{1 / s} = \frac{s}{e \sqrt{2}} 2^{\frac{s}{2}} .$

定义：随机图

随机图 $G (n, p)$ ， $p \in (0, 1)$ 为： $V = [n]$ ，每条边 $e \in (\binom{V}{2})$ 独立地以概率 $p$ 出现。

上面定理的证明中，我们事实上考虑了 $G (n, 1 / 2)$ 。

对性质 $A$ ，我们考察 $G (n, 1 / 2)$ 具有性质 $A$ 的概率。事实上我们有

P (A) = P (G (n, 1 / 2) 具有性质 A) = \frac{满足性质 A 的图数}{2^{(\binom{n}{2})}} .

定义：几乎一定

称 $G (n, 1 / 2)$ 几乎一定满足性质 $A$ ，若 $lim_{n \to \infty} P (A) = 1$ 。
称几乎一定不满足，若 $lim = 0$ 。

定理：随机图几乎不是二分图

$G (n, 1 / 2)$ 几乎一定不是二分图。

证明： 设 $A$ 为事件： $G (n, 1 / 2)$ 不是二分图。对任意 $U \subset [n]$ ，令 $A_{U}$ 为事件： $G$ 的所有边都在 $U$ 和 $[n] ∖ U$ 之间。则我们有 $A = ⋃_{U \subset [n]} A_{U}$ 。因此

P (A_{U}) = \frac{2^{| U | (n - | U |)}}{2^{(\binom{n}{2})}} \leq \frac{2^{\frac{n^{2}}{4}}}{2^{(\binom{n}{2})}} = 2^{- \frac{n^{2}}{4} + \frac{n}{2}} .

因此

P (A) = P (⋃_{U \subset [n]} A_{U}) \leq \sum_{U \subset [n]} P (A_{U}) \leq 2^{n} \cdot 2^{- \frac{n^{2}}{4} + \frac{n}{2}} \to 0.

证毕。

练习

考虑 $[n]$ 的全体不交 $k -$ 元子集对 $(A, B)$ 构成的集族．称一个集合 $Y$ 分离 $(A, B)$ ，若 $A \subset Y$ 且 $B \cap Y = \emptyset$ ．证明存在 $l = 2 k 4^{k} \ln n$ 个集合，使得每个对 $(A, B)$ 均由其中之一分离．

证明： 从 $[n]$ 中选 $l$ 次子集，每一次都是等可能的．由此我们选出一个集族 $F$ ，其中至多有 $l$ 个子集．对每个不交 $k -$ 元子集对 $(A, B)$ ，令 $X_{A B}$ 为事件“不存在 $F$ 中的成员分离 $(A, B)$ ”．由于分离 $(A, B)$ 的子集合数为 $2^{n - 2 k}$ 个，我们有

P (X_{A B}) = {(1 - \frac{2^{n - 2 k}}{2^{n}})}^{l} = (1 - 2^{- 2 k})^{l} < e^{- 2^{- 2 k l}} = n^{- 2 k} .

总共有 $(\binom{n}{k}) (\binom{n - k}{k})$ 个这样的子集对 $(A, B)$ ．由于

(\binom{n}{k}) (\binom{n - k}{k}) \leq n^{k} (n - k)^{k} \leq n^{2 k},

因此至少一个子集合对不被分离的概率为

P (⋃_{A, B} X_{A B}) \leq \sum_{A, B} P (X_{A B}) < n^{2 k} \cdot n^{- 2 k} = 1.

因此，存在这样的情况：每个对 $(A, B)$ 均被分离．

可染色族

定义：

k -

族

设 $F$ 为 $Ω$ 的子集族。称 $F$ 是一个 $k -$ 族，若其中子集均为 $k -$ 元的。

例

2-族是一个图。

定义：可2-染色族

称 $F$ 可2-染色，若存在函数 $f : Ω \to {蓝，红}$ 使得每个子集 $A \in F$ 均非单色。即：每个 $A$ 都至少有一个蓝元素和一个红元素。

定义：

对任意 $k \in Z_{+}$ ，令 $m (k)$ 为使 $k -$ 族 $F$ 不可2-染色的最小数。

因此，我们有 $m (k) \leq t$ 当有仅当存在一个 $k -$ 族 $F$ ，其有 $t$ 个子集且不可 2-染色。反过来， $m (k) > t$ 等价于任一个由 $t$ 个子集构成的 $k -$ 族均可2-染色。

例

$m (2) = 3$ 。。例： $K_{3}$ 。

定理/练习

$m (k) > 2^{k - 1} - 1.$

也就是说，任一包含 $2^{k - 1} - 1$ 个子集的 $k -$ 族可被2染色。

证明： 给定一个 $k -$ 族 $F$ ，包含 $2^{k - 1} - 1$ 个子集。只需找一个染色 $f$ 使得 $F$ 中的任一子集都有红与蓝顶点。称这样的染色是一个好染色。

考虑随机函数 $φ : Ω \to {红，蓝}$ 。令 $S$ 为 $φ$ 好这一事件。令 $T = S^{c}$ ，则必存在一个子集 $A \in F$ ，其在 $φ$ 下单色。对任意 $A \in F$ ，令 $T_{A}$ 为事件： $A$ 在 $φ$ 下单色。则

T = ⋃_{A \in F} T_{A} .

注意 $P (T_{A}) = 2 \cdot \frac{1}{2^{k}} = 2^{1 - k}$ ，故

P (T) = P (⋃_{A \in F} T_{A}) \leq \sum_{A \in F} P (T_{A}) = | F | 2^{1 - k} < 1.

因此 $P (S) = 1 - P (T) > 0$ ，故存在好染色。

练习

证明若存在 $p \in [0, 1]$ 使得

(\binom{n}{k}) p^{(\binom{k}{2})} + (\binom{n}{t}) (1 - p)^{(\binom{t}{2})} < 1,

就有 $R (k, t) > n$ ．以此证明存在 $C > 0$ 使 $R (4, t) \geq C \cdot {(\frac{t}{\ln t})}^{3 / 2}$ ．

证明： 考虑 $K_{n}$ 的一个随机2-染色，染红概率为 $p$ ．对任意 $k$ 顶点集合 $R$ ，令 $A_{R}$ 为事件“ $K_{n} [R]$ 是红色”．同样定义 $B_{R}$ 为 $t$ 顶点集合 $R$ 中， $K_{n} [R]$ 为蓝色的事件．则由于有 $(\binom{k}{2})$ 条边，得

P (A_{R}) = (\binom{n}{k}) p^{(\binom{k}{2})}, P (B_{t}) = (\binom{n}{t}) (1 - p)^{(\binom{k}{2})} .

于是 $P (A_{R}) + P (B_{t}) < 1$ ，故存在一种染色，使得既无红 $K_{k}$ 又无蓝 $K_{t}$ ，故 $R (k, t) > n$ ．

下面，对 $k = 4$ ，我们有

(\binom{n}{4}) p^{(\binom{4}{2})} + (\binom{n}{4}) (1 - p)^{(\binom{t}{2})} \leq \frac{1}{24} n^{4} p^{6} + \frac{n^{t}}{t!} (1 - p)^{(\binom{t}{2})} \leq \frac{1}{24} + n^{t} {(\frac{e}{t})}^{- p \frac{t^{2} - t}{2}} .

令 $p = \frac{12^{1 / 6}}{n^{2 / 3}}$ ， $n = \frac{t^{3 / 2}}{(\ln t)^{3 / 2}}$ ，代入上面不等式即证！傻逼吧！我操！谁爱算谁算去！

练习

令 $k \geq 4$ 为整数， $F \subset (\binom{X}{k})$ 为 $k -$ 族．基集为 $X$ ．证明若 $| F | < \frac{4^{k - 1}}{3^{k}}$ ，则存在一个 $4 -$ 染色，使得4种颜色都在每个子集中被染到．

证明： 考虑随机4-染色．对每个 $e \in F$ ，令 $A_{e}$ 为事件： $e$ 中并不是4种颜色都出现．若 $A_{e}$ 发生，则 $e$ 中最多有三种颜色，故

P (A_{e}) \leq \frac{1}{4^{k}} (\binom{4}{3}) 3^{k} = \frac{3^{k}}{4^{k - 1}} .

由于 $F$ 中子集数目少于 $\frac{4^{k - 1}}{3^{k}}$ ，故所有 $e$ 发生的概率小于 $1$ ，因此存在这样的染色．

锦标赛（Tournament）

定义：独立变量

懒

定义：锦标赛（Tournament）

一个 $n$ 顶点的锦标赛是一个从 $K_{n}$ 得来的有向图：给每条边一个方向。对边 $i \to j$ ，称其为一个弧，称 $i$ 为头， $j$ 为尾。

定义：

S_{k}

（相互吊打）

称一个锦标赛 $T$ 满足条件 $S_{k}$ ，若对任意 $k$ 大小的子集 $A$ ，都存在一个顶点 $u \in V (T) ∖ A$ 使得 $u \to x$ 对任意 $x \in A$ 成立。

定理：相互吊打的一个充要条件

对任意 $k \in Z_{+}$ ，如果

(\binom{n}{k}) {(1 - \frac{1}{2^{k}})}^{n - k} < 1,

就存在一个 $n -$ 顶点锦标塞，满足性质 $S_{k}$ 。

证明： 我们来考虑随机锦标赛，即：对任意 $i j$ ，存在一个弧 $i \to j$ ，方向选取 $\frac{1}{2}$ 概率且独立。令 $B$ 为 $T$ 不满足 $S_{k}$ 的事件。

对任意 $A \in (\binom{[n]}{k})$ ，令 $B_{A}$ 为事件：对任意顶点 $x \in [n] ∖ A$ ，存在 $u \in A$ 使得 $u \in x$ 。则

B = ⋃_{A \in (\binom{[n]}{k})} B_{A} .

令 $x \in [n] ∖ A$ ，令 $B_{A, x}$ 为事件：存在一些 $u \in A$ 使得 $u \to x$ 。则

B_{A} = ⋂_{x \in [n] ∖ A} B_{A, x} .

显然 $P (B_{A, x}) = 1 - \frac{1}{2^{k}}$ ，且 $B_{A, x}$ 对 $x$ 独立。于是

P (B_{A}) = \prod_{x \notin A} P (B_{A, x}) = {(1 - \frac{1}{2^{k}})}^{n - k} .

因此

P (B) \leq \sum_{A \in (\binom{[n]}{k})} P (B_{A}) =\leq (\binom{n}{k}) {(1 - \frac{1}{2^{k}})}^{n - k} < 1.

证毕。

推论

对任意 $k \in Z_{+}$ ，存在一个最小的 $f (k)$ ，使得存在 $f (k)$ 顶点锦标赛满足 $S_{k}$ 。

例

$f (3) < 91$ ，因为

(\binom{91}{3}) {(1 - \frac{1}{2^{3}})}^{91 - 3} < 1.

期望的线性性

关键观察

$P (X \geq E [X]) > 0, P (X \leq E [X]) > 0.$

从“ $P > 0$ ”即存在的观点来看，若问“存在……大于／小于”问题，可以考虑构造随机变量， $E [X]$ 为此值。

定义：指示变量

对事件 $A$ ，定义

1_{A} (x) = {\begin{cases} 1, & x \in A, 即 A 发生; \\ 0, & x \notin A . \end{cases}

我们有： $E [1_{A}] = P (A)$ 。

定义：无和（sum-free）

称集合 $A$ 无和，若对任意 $x, y \in A$ ，则 $x + y \notin A$ 。

例：无和

$[n]$ 的两个无和 $⌈ n / 2 ⌉$ 子集为

${⌊ n / 2 ⌋ + 1, \dots, n}$
${m \in [n] : 2 ∤ n}$ 。

事实上可以证明：无和子集 $A \subset [n]$ 至多为 $⌈ n / 2 ⌉$ 元素。Hint：考虑 $x \in A \Rightarrow 2 x = x + x \notin A$ 。

定理：无和集存在性

对任意非零整数集 $A$ ，其中存在无和子集 $B$ ，且 $| B | \geq \frac{| A |}{3}$ 。

证明： 选取 $p$ 足够大，使得 $p \equiv 2 (\mod 3)$ 且 $p > | a |$ ， $\forall a \in A$ 。注意到我们有一个 $Z_{p} -$ 无和子集

S = {⌈ \frac{p}{3} ⌉ + 1, \dots, ⌈ \frac{2 p}{3} ⌉} .

我们声称：对任意 $x \in Z_{p}^{*}$ ， $A_{x} = {a \in A : a x (\mod p) \in S}$ 在 $Z$ 中无和。这是因为反设存在 $a, b, c \in A_{x}$ 使得 $a + b = c$ ，两边同乘以 $x$ 得 $a x + b x = c x$ 在 $S$ 中，与 $S$ $Z_{p} -$ 无和矛盾。

现在，我们找一些 $x \in Z_{p}^{*}$ 使得 $| A_{x} | \geq \frac{| A |}{3} .$ 任取 $x$ ，我们计算 $E [| A_{x} |]$ 。注意到

E [| A_{x} |] = E [\sum_{a \in A} 1_{a x (\mod p) \in S}] = \sum_{a \in A} E [1_{a x (\mod p) \in S}] = \sum_{a \in A} P (a x (\mod p) \in S) .

注意到 $p$ 为素数， $a$ 在 $Z_{p}^{*}$ 上的左乘作用是自同构，帮 $P (a x (\mod p) \in S) = \frac{| S |}{| Z_{p}^{*} |} \geq \frac{1}{3}$ 。因此 $E [| A_{x} |] \geq \sum_{a \in A} \frac{1}{3} = \frac{| A |}{3}$ ，故存在这样的 $| A_{x} |$ 使得 $| A_{x} | \geq \frac{| A |}{3}$ 。

定义：主导集（Dominating set）

给定图 $G$ ，称 $G$ 的一个主导集 $A$ 是 $V (G)$ 的一个子集，使得 $u \in V (G) ∖ A$ 在 $A$ 中有一个邻点。

定理

设 $G$ 是一个 $n$ 阶图，最小度为 $δ > 1$ ，则 $G$ 有一个主导集 $A$ ，其至多包含 $\frac{1 + \ln (1 + δ)}{1 + δ} n$ 个顶点。

证明： 待定 $p \in (0, 1)$ 。在 $V (G)$ 中任取顶点以概率 $p$ 。令 $A$ 为这些被取的顶点，并令 $B$ 为 $V (G) ∖ A$ 中在 $A$ 中无邻点的点集。则

$A \cup B$ 是一个主导集；
$b \in B$ 当且仅当 $({b} \cup N_{G} (b)) \cap A = \emptyset$ ：即 $b$ 与 $b$ 的邻点都未被选入 $A$ 。

因此，

P (b \in B) = (1 - p)^{1 + d_{G} (b)} \leq (1 - p)^{1 + δ} \leq e^{- p (1 + δ) .}

最后一个不等式是由于 $1 + x \leq e^{x}$ 。因此，我们有

E [| B |] = E [\sum_{b \in V (G)} 1_{b \in B}] = \sum_{b \in V (G)} P (b \in B) \leq n \cdot e^{- p (1 + δ)} .

另一方面，我们有 $E [| A |] = n p$ ，从而

E [| A \cup B |] \leq E [| A | + | B |] = E [| A |] + E [| B |] \leq n (p + e^{- p (1 + δ)}) .

由微积分， $p = \frac{\ln (1 + δ)}{1 + δ}$ 时右边最小，代入得 $E [| A \cup B |] \leq \frac{1 + \ln (1 + δ)}{1 + δ} n$ 。因此存在一种取法使主导集 $| A \cup B | \leq \frac{1 + \ln (1 + δ)}{1 + δ} n$ 。

定义：

α

令 $α (G)$ 为 $G 中最大独立集大小。

定理

对任意图 $G$ ， $α (G) \geq \sum_{v \in V (G)} \frac{1}{d (v) + 1}$ ，这里 $d (v)$ 为 $v$ 的度。

证明： 令 $V (G) = [n]$ ，则对任意 $i \in [n]$ ，令 $N_{i}$ 为 $i$ 在 $G$ 中的邻点集。令 $S_{n}$ 为全体置换 $π : [n] \to [n]$ 的集合。

对给定置换 $π$ ，称 $i \in [n]$ 是 $π -$ 好的，若 $π (i) < π (j)$ 对任意 $j \in N_{i}$ 成立。令 $M_{π}$ 为全体 $π -$ 好顶点。

我们声称 $M_{π}$ 为独立集。这是因为如果 $i, j \in M_{π}$ ， $i j \in E (G)$ ，不妨设 $π (i) < π (j)$ ，则 $j$ 不 $π -$ 好，矛盾。

下面，我们均匀地选取 $π \in S_{n}$ ，并计算 $E [| M_{π} |]$ 。因为 $| M_{π} | = \sum_{i \in [n]} 1_{i : π 好}$ ，我们有 $E [| π_{M} |] = \sum_{i \in [n]} P (i : π 好) = \sum_{i \in [n]} \frac{1}{d (i) + 1}$ 。因此存在一个 $π \in S_{N}$ 使得 $| M_{π} | \geq \sum_{i \in [n]} \frac{1}{d (i) + 1}$ 。由 $α (G)$ 的定义， $α (G) \geq R H S$ 。

推论（练习）

对任意图 $G$ 有 $n$ 顶点及 $m$ 边， $α (G) \geq \frac{n^{2}}{2 m + n}$ 。

推论

图 $G$ 有 $n$ 个点及平均度数（即 $d = \frac{2 m}{n}$ ，则 $α (G) \geq \frac{n}{1 + d}$ 。

定义：Turan 图

Turan $r$ 部图 $T_{r} (n)$ 是一个 $n$ 顶点图 $G$ ，使得 $V (G) = V_{1} \cup V_{2} \cup \dots \cup V_{r}$ ，且 $| V_{1} | \leq | V_{2} | \leq \dots \leq | V_{r} | \leq | V_{1} | + 1$ ，其中 $a b \in E (G)$ 当且仅当 $a \in V_{i}$ ， $b \in V_{j}$ 且 $i \neq j$ 。

$T_{r} (n)$ 是一个平衡完全 $r -$ 部图。

定理（Turan定理，估计形式）

若 $G$ 无 $K_{r + 1}$ ，则 $e (G) \leq \frac{r - 1}{2 r} n^{2}$ 。

定理（Turan定理，精确形式）

若 $n$ 点图 $G$ 无 $K_{r + 1}$ ，则 $e (G) \leq ex (T_{r} (n)) \approx \frac{r - 1}{2 r} n^{2}$ 。

证明： 给定 $n -$ 顶点无 $K_{r + 1}$ 图 $G$ ， $V (G) = [n]$ 。考虑一个函数 $p : [n] \to [0, 1]$ ，使得

\sum_{i \in [n]} p_{i} = 1.

希望找 $f (p) = \sum_{i j \in E (G)} p_{i} p_{j}$ 的最大值，对任意给定的 $p$ 。假设 $p$ 使 $f (p)$ 取最大——为此，使 $p (i) \neq 0$ 的顶点 $i$ 的数量应当最小。

引理

${i : p (i) > 0}$ 是 $G$ 中的一个子图。

证明： 否则，若存在 $p (i), p (j) > 0$ 使 $i j \notin E (G)$ ，令 $S_{i} = \sum_{k \in N_{G} (i)} p_{k}$ 且 $S_{j} = \sum_{k \in N_{G} (j)} p_{k}$ 。令 $S_{i} \geq S_{j}$ 。则我们可以分配一个新函数 $p^{*} : [n] \to [0, 1]$ 使得

p^{*} (i) = p (i) + p (j), p^{*} (j) = 0, p^{*} (k) = p (k), \forall k \in [n] ∖ {i, j} .

现在，我们有

f (p^{*}) = f (p) - (p_{i} S_{i} + p_{j} S_{j}) + (p_{i} + p_{j}) S_{i} = f (p) + (S_{i} - S_{j}) p_{j} \geq f (p) .

由 $p$ 的取法，我们看出 $f (p^{*}) = f (p)$ ，但 $p^{*}$ 有更少的正权顶点数，矛盾！

回到原题： 令 $S = {1, 2, \dots, s} \subset V (G)$ 为正权顶点。由引理，我们有 $G [S] = K_{s}$ ， $s \leq r$ 且 $G$ 不含 $K_{r + 1}$ 。则

\begin{aligned} max_{p} f (p) & = \frac{1}{2} ({(\sum_{1 \leq i \leq s} p (i))}^{2} - \sum_{1 \leq i \leq s} p^{2} (i)) \\ = \frac{1}{2} (1 - \sum_{1 \leq i \leq s} p^{2} (i)) \\ \leq \frac{1}{2} (1 - s {(\frac{1}{s} \sum_{1 \leq i \leq s} p (i))}^{2}) \\ = \frac{1}{2} (1 - \frac{1}{s}) \leq \frac{1}{2} (1 - \frac{1}{r}) . \end{aligned}

另一方面， $max_{p} f (p) \geq \frac{e (G)}{n^{2}}$ ，比较两边即证！

练习

令 $X_{π}$ 为置换 $π$ 的不动点数，求 $E [X_{π}]$ ，这里 $π \in S_{n}$ ．
掷 $n$ 次硬币，求“连续数”的期望：比如 TTTHHHHTT 的连续数是3．

解： (1) 记事件 $A_{i}$ ： $i$ 被固定．令 $X_{i}$ 为 $A_{i}$ 的指示变量，则 $X_{π} = \sum X_{i}$ ．由对称性，

P (π (i) = j) = \frac{1}{n}, \forall j .

于是 $P (A_{i}) = \frac{1}{n}$ ，从而

E [X_{π}] = \sum P (A_{i}) = 1.

(2) 令 $X_{n}$ 为前 $n$ 次投掷的连续数．若 $n + 1$ 次投掷异于第 $n$ 次，则 $X_{n + 1} = X_{n} + 1$ ，否则 $X_{n + 1} = X_{n}$ ，于是

E [X_{n + 1}] = \frac{1}{2} E [X_{n}] + \frac{1}{2} (E [X_{n}] + 1) . = E [X_{n}] + \frac{1}{2} .

由 $X_{1} = 1$ ，故 $E [X_{n}] = \frac{n + 1}{2}$ ．

练习：Sperner定理另证

设 $F$ 为 $[n]$ 中独立系统．令 $π \in S_{n}$ 为 $[n]$ 中的随机排列．通过考虑集合

X = {i : {π (1), π (2), \dots, π (i)} \in F}

来证明 $| F | \leq (\binom{n}{⌊ n / 2 ⌋})$ .

证明： 令 $F = {A_{1}, \dots, A_{| F |}}$ ．由于 $F$ 是独立系统且 $X$ 中元素相互包含， $X$ 中包含至多一个元素．

另一方面，令 $X_{i}$ 为事件

{π (1), \dots, π (| A_{i} |)} = A_{i}

的指示变量，则 $| X | = \sum X_{i}$ . 因为 ${π (1), \dots, π (| A_{i} |)}$ 的取法有 $(\binom{n}{| A_{i} |})$ 种，我们有

E [X_{i}] = P ({π (1), \dots, π (| A_{i} |)} = A_{i}) = \frac{1}{(\binom{n}{| A_{i} |})} .

因此，我们有

1 \geq E [| X |] = \sum_{i = 1}^{| F |} E [X_{i}] = \sum_{i = 1}^{| F |} \frac{1}{(\binom{n}{| A_{i} |})} .

这是 L-Y-M 不等式．取 $(\binom{n}{| A_{i} |}) \leq (\binom{n}{⌊ n / 2 ⌋})$ 即证．

削除方法

先前我们考虑的是经典概率；现在，我们把这种思想延伸出来，考虑随机事件并非总含有想要的性质的情况——有非常少的“瑕疵”。我们的想法是删掉所有的瑕疵，这样就可以得到想要的性质。

定理

令 $G$ 为 $n$ 顶点图，有平均度 $\geq 1$ 。则 $α (G) \geq \frac{n}{2 d}$ 。

证明： 令 $S \subset V (G)$ 为随机子集：对任意 $v \in V (G)$ ， $P (v \in S) = p$ ，这里 $p$ 待定。

令 $X$ 为 $S$ 中的顶点数，令 $Y$ 为 $G$ 中每个端点都在 $S$ 中的边数。则 $E [X] = n p$ ， $E [Y] = e (G) p^{2} = \frac{n d}{2} p^{2}$ 。令 $p = \frac{1}{d}$ ，则

E [X - Y] = E [X] - E [Y] = \frac{n}{d} .

故存在子集 $S \subset V (G)$ 使得

| S | - e (G [S]) \geq E [X - Y] = \frac{n}{2 d} .

现在，从 $G [S]$ 的每条边中删除一个顶点，得到子集 $S^{*} \subset S$ ，其大小至少为 $| S | - e (G [S]) \geq \frac{n}{2 d}$ 。由于这样删除后 $G [S]$ 无边，故 $S^{*}$ 是一个独立集。

回忆

有定理： $(\binom{n}{k}) 2^{1 - (\binom{k}{2})} < 1$ ，则 $R (k, k) > n$ 。特别地： $R (k, k) > \frac{k 2^{k}}{e \sqrt{2}}$ 。

定理

对任意整数 $n$ ， $R (k, k) > n - (\binom{n}{k}) 2^{1 - (\binom{k}{2})}$ 。

证明： 考虑 $K_{n}$ 的随机2-染色，这里每条边染为红或蓝，概率 $1 / 2$ 。对 $A \in (\binom{[n]}{k})$ ，令 $X_{A}$ 为指示变量： $A$ 诱导一个完全单色图 $K_{k}$ 。则 $E [X_{A}] = 2 \cdot \frac{1}{2^{(\binom{k}{2})}}$ .
令 $X = \sum_{A \in (\binom{[n]}{k})} X_{A}$ 为单色 $k -$ 子集的数量。则

E [X] = \sum_{A \in (\binom{[n]}{k})} E [X_{A}] = (\binom{n}{k}) 2^{1 - (\binom{k}{2})} .

故存在一个 $K_{n}$ 的 2-染色，单色 $k -$ 子集数量至多为 $E [X] = (\binom{n}{k}) 2^{1 - (\binom{k}{2})}$ 。接下来，从每个单色子集中移除一个顶点，这至多删除 $X \leq E [X] \leq (\binom{n}{k}) 2^{1 - (\binom{k}{2})}$ 个顶点，但把单色子集全清除了。于是剩余的 $n - (\binom{n}{k}) 2^{1 - (\binom{k}{2})}$ 个顶点中，没有任何单色 $k -$ 子集。

推论（练习）

$R (k, k) > \frac{1}{e} (1 + o (1)) k 2^{k / 2} .$

提示：固定 $k$ ，令 $n - (\binom{n}{k}) 2^{1 - (\binom{k}{2})}$ 最大。

练习

令 $F \subset (\binom{[n]}{3})$ 是 $m$ 个子集的子集族，其中 $m \geq \frac{n}{3}$ ．证明存在子集 $A \subset [n]$ 使得

| A | \geq \frac{2 n^{3 / 2}}{3 \sqrt{3 m}},

且 $F$ 中的集合没有一个被 $A$ 包含．

证明： 令 $B \subset [n]$ 为由 $P (i \in B) = p$ 定义的随机子集，各边相互独立．令 $X = | B |$ ， $Y = | {e \in F : e \subset B} |$ ．对任意 $e \in F$ ，令 $Y_{e}$ 为事件“ $e \subset B$ ”的指示变量，故 $Y = \sum_{e \in F} Y_{e}$ ．显然 $E [Y_{e}] = p^{3}$ （因为 $F$ 的成员是三元集），故 $E [Y] = m p^{3}$ ．显然， $E [X] = n p$ ．于是

E [X - Y] = n p - m p^{3} \overset{p = \sqrt{n / 3 m}}{=} \frac{2 n^{3 / 2}}{3 \sqrt{3 m}} .

存在一个 $B$ 使得 $X - Y \geq E [X - Y] = \frac{2 n^{3 / 2}}{3 \sqrt{3 m}}$ ．再从 $B$ 中移除 $F$ 中含于 $B$ 的成员中任一个顶点，把剩下的集合记为 $A$ 即可．

练习

令 $F$ 为 $n$ 元集的 $r -$ 一致族子集．假设每个元素属于 $F$ 的 $d$ 个成员．证明存在一个元素集合 $S$ ，使得

$S$ 不包含 $F$ 中的成员，且
$| S | \geq (1 - \frac{1}{r}) n d^{- \frac{1}{r - 1}}$ ．

证明： 我们先要知道 $F$ 有多大．令

M = | {(v, e) : e \in F, v \in e} | .

对其双重计数．固定元素：由于每个元素属于 $F$ 中的 $d$ 个成员，我们有 $M = n d$ ．另一方面，固定成员：每个成员中有 $r$ 个元素．因此 $| M | = | F | r$ ，从而 $| F | = \frac{n d}{r}$ ．

下面，令 $A$ 为随机子集， $P (v \in A) = p$ 待定且对各 $v$ 独立．则

E [| A |] = n p .

令 $Y$ 为 $F$ 的元素中位于 $A$ 的元素的数量．由线性性，我们有

E [Y] = | F | p^{r} = \frac{n d}{r} p^{r} .

因此，我们有

E [| A | - Y] = n p - \frac{n d}{r} p^{r} .

取 $p = d^{- \frac{1}{r - 1}}$ ，则 $E [| A | - Y] = (1 - \frac{1}{r}) n d^{- \frac{1}{r - 1}}$ ．存在这样的一个 $A$ ： $| A | - Y \geq E [| A | - Y]$ ．从 $F$ 的每个成员中删除一个位于 $A$ 中的元素可获得一个集合 $S$ ，其中至少有 $| A | - Y$ 个元素，证毕．

Markov 不等式

定理：Markov 不等式

令 $X \geq 0$ 为随机变量， $t > 0$ ,则

P (X \geq t) \leq \frac{E [X]}{t} .

推论

令 $X_{n} \geq 0$ 为整值随机变量。若

E [X_{n}] \to 0, n \to \infty,

则

P (X_{n} = 0) \to 1, n \to \infty .

即 $X_{n} = 0$ 几乎一定成立。

引理

对随机图 $G (n, p)$ ， $p \in (0, 1)$ ,有

P (α (G (n, p)) \leq ⌈ \frac{2 \ln n}{p} ⌉) \to 1, n \to \infty .

注意到 $p$ 可视为 $n$ 的一个函数。

证明： 令 $t = ⌈ \frac{2 \ln n}{p} ⌉$ 。令 $X_{n}$ 为 $G (n, p)$ 中大小为 $t + 1$ 的独立集的数量。对任意 $S \in (\binom{[n]}{t + 1})$ ,令 $X_{S}$ 为指标变量： $S$ 是一个 $G (n, p)$ 中的独立集。则

X_{n} = \sum_{S \in (\binom{[n]}{t + 1})} X_{S} .

及

\begin{aligned} E [X_{n}] & = \sum_{S \in (\binom{[n]}{t + 1})} E [X_{S}] = \sum_{S \in (\binom{[n]}{t + 1})} (1 - p)^{(\binom{t + 1}{2})} = (\binom{n}{t + 1}) (1 - p)^{(\binom{t + 1}{2})} \\ \leq \frac{n^{t + 1}}{(t + 1)!} e^{- p (\binom{t + 1}{2})} = \frac{1}{(t + 1)!} {(n e^{- p t / 2})}^{t + 1} \\ \leq \frac{1}{(t + 1)!} \to 0. \end{aligned}

由上面的推论， $P (α (G (n, p)) \leq t) = P (X_{n} = 0) \to 1$ 。

定义：染色数

对一个图 $G$ ，其染色数 $χ (G)$ 是最小的 $k$ ，使得 $V (G)$ 可被分为 $k$ 个独立集。

事实

$χ (K_{n}) = n$ 。
$χ (C_{2 n + 1}) = 3$ 。
$χ (G) \leq 2$ 当且仅当 $G$ 是二分图。
$χ (G) \cdot α (G) \geq | V (G) |$ 。

定义：围长（girth）

图 $G$ 的围长 $g (G)$ 为 $G$ 中最短圈的长度。

定理（Erdos）

对任一固定的 $k$ ，存在一个图 $G$ ： $χ (G) \geq k$ 且 $g (G) \geq k$ 。

证明： 考虑一个随机图 $G = G (n, p)$ ，这里 $p$ 待定。令 $t = ⌈ \frac{2 \ln n}{p} ⌉$ ，由上面的引理可知 $P (α (G) \leq t) \to 1$ ，当 $n \to \infty$ 。

令 $X_{n}$ 为 $G$ 中长度小于 $k$ 的圈的数量。则

E [X_{n}] = \sum_{i = 3}^{k - 1} \frac{n (n - 1) \dots (n - i + 1)}{2 i} p^{i} .

这里 $\frac{n (n - 1) \dots (n - i + 1)}{2 i}$ 为 $K_{n}$ 中 $C_{i}$ 的个数。则

E [X_{n}] \leq \sum_{i = 3}^{k - 1} (n p)^{i} \leq \frac{(n p)^{k} - 1}{n p - 1} .

由Markov不等式，

P (X_{n} > \frac{n}{2}) \leq \frac{E [X_{n}]}{n / 2} \leq \frac{2 ((n p)^{k} - 1)}{n (n p - 1)} .

令 $p = n^{- \frac{k - 1}{k}}$ ，则 $n p = n^{1 / k}$ 。我们有

P (X_{n} > \frac{n}{2}) \leq \frac{2 (n - 1)}{n (n^{1 / k} - 1)} \to 0.

令 $n$ 足够大，则存在 $n$ 点图 $G$ ，满足 $X_{n} \leq \frac{n}{2}$ 但 $α (G) \leq t = ⌈ \frac{2 \ln n}{p} ⌉ \leq 3 n^{\frac{k - 1}{k}} \ln n$ 。

通过从每个长度至多为 $k - 1$ 的圈中移除一个顶点，我们可以找到一个诱导子图 $G^{*} < G$ ，其含至少 $n / 2$ 个顶点，并且不存在长度最大为 $k - 1$ 的圈。因此 $g (G^{*}) \geq k$ 。由于 $G^{*}$ 为 $G$ 的诱导子图，我们有

α (G^{*}) \leq α (G) \leq 3 n^{\frac{k - 1}{k}} \ln n .

由 $χ \cdot α \geq | V |$ ，得到 $χ (G^{*}) \geq \frac{| V (G^{*} |)}{α (G^{*})} \geq \frac{n / 2}{3 n^{\frac{k - 1}{k}} \ln n} \geq k$ ，故 $G^{*}$ 为所求图，如欲所证。