6、相交族

相交族

相交族（Intersecting Family）

称 $F \subset 2^{[n]}$ 为相交族，若对任意 $A, B \in F$ 有 $A \cap B \neq \emptyset$ .

例子：相交族

$F = {A \subset [n] : 1 \in A}$ ;
$F = {A \subset [n] : | A | > \frac{n}{2}}$ ，当 $n$ 为奇。

以上两个是相交族大小为 $2^{n - 1}$ 的例子。

事实上，对相交族的大小，我们有：

事实：相交族的最大大小

对任意相交族 $F \subset 2^{[n]}$ ，有 $| F | \leq 2^{n - 1}$ 。

证明： 对无序对 ${A, A^{c}}$ 计数，这里 $A \subset [n]$ 。这样的对子恰有 $2^{n - 1}$ 个。由于 $F$ 是相交族，其至多包含对子中的一个集合，故

| F | \leq # {A, A^{c}} = 2^{n - 1} .

这一上界是紧的：上面的例子给出了构造。

各集合大小相同的相交族

Erdos-Ko-Rado 定理

有关相交族，我们最关心的一个事情是各集合大小均为某值的相交族的大小：也就是说， $F \subset (\binom{[n]}{k})$ 的大小。事实上，有两个已知事实：

k) 的情形

当 $k > \frac{n}{2}$ 时， $| F | = (\binom{n}{k})$ 。
当 $k \leq \frac{n}{2}$ 时，若添加条件 $1 \in A$ ，则

F = {A \in (\binom{[n]}{k}) : 1 \in A} ⟹ | F | = (\binom{n - 1}{k - 1}) .

但对 $k \leq \frac{n}{2}$ 的情形，相交族的大小是不固定的：显然可以取得足够少，例如，取两个是显然可行的。我们有如下的估计：

定理（Erdos-Ko-Rado）

当 $n \geq 2 k$ 时，最大的相交族 $F \subset (\binom{[n]}{k})$ 的大小为 $(\binom{n - 1}{k - 1})$ 。
当 $n > 2 k$ 时，最大的相交族必是一个星（star）： $F$ 中的每个集合共享一个元素 $t \in [n]$ .

有两种证明。我们先说最简单的一种。

第一种证明：轮换计数

约定：全轮换包含集合

对全轮换 $π \in C ([n]) \subset S ([n])$ ，称 $A$ 被全轮换 $π$ 包含，若 $A$ 中元素在 $π$ 的轮换表示中连续地出现（consecutive）。
对全轮换 $π$ ，记 $F_{π}$ 为 $F$ 中被全轮换 $π$ 包含的集合族。

引理1：被全轮换包含集合的大小估计

对任意全轮换 $π \in C ([n])$ ，我们有 $| F_{π} | \leq k$ .

证明： 若 $F_{π}$ 非空，任取 $A \in F_{π}$ ，存在 $2 k - 2$ 个集合 $B$ 被 $π$ 包含、不同于 $A$ 且与 $A$ 相交。但注意到这些集合 $B$ 可被分为 $k - 1$ 对不交对（由 $n > 2 k$ ）。由于 $F_{π} \subset F$ ， $F_{π}$ 至多包含这些不交对之一，故 $| F_{π} | \leq k - 1 + 1 = k$ .

定理第一部分证明： 对如下集合双重计数：

N = {(π, A) : π 为全轮换， A \in F_{π}} .

固定 $π$ ，由引理1， $| N | = \sum_{π} | F_{π} | \leq k (n - 1)!$ . 另一方面，固定 $A$ ，有

| N | = \sum_{A \in F} \sum_{π} 1_{A 被 π 包含} = \sum_{A \in F} k! (n - k)! = | F | k! (n - k)! .

因此 $| F | \leq \frac{k \cdot (n - 1)!}{k! (n - k)!} = (\binom{n - 1}{k - 1})$ ，证毕。

下面证明第二部分： $n > 2 k$ 时， $F$ 必是星构造。这需要更多引理。

引理2：包含集的连续性

固定全轮换 $π$ 。若 $F_{π} = {A_{1}, \dots, A_{k}}$ ，则必有

F_{π} = {(a_{j + r}, a_{j + r + 1}, \dots, a_{j + r + k - 1}) : 1 \leq j \leq k},

对任意 $r \in [n]$ 成立，这里下标按模 $n$ 理解。

换句话说，若 $A_{1}, A_{k} \in F_{π}$ 且 $| A_{1} \cap A_{k} | = 1$ ，则任意 $B \subset (\binom{A_{1} \cup A_{k}}{k})$ 且包含于 $π$ 中的集合都出现在 $F_{π}$ 中。

证明： 显然。

以下，不失一般性，按 $r = 0$ 理解。

引理3：特定星形元素的构造

若 $B \in (\binom{A_{1} \cup A_{k} ∖ {a_{k}}}{k - 1})$ ，则 $B \cup {a_{k}} \in F$ .

证明： 不妨设 $B = B_{1} \cup B_{2}$ ， $B_{1}$ 在 $A_{1}$ 中， $B_{2}$ 在 $A_{k}$ 中。按如下方式构造全轮换序列：

τ : (A_{1} ∖ (B_{1} \cup {a_{k}}) B_{1} a_{k} B_{2} A_{k} ∖ (B_{2} \cup {a_{k}})) .

这里按矩阵分块理解记号。则 $A_{1}, A_{k} \in F_{τ}$ 。由连续出现引理， $B_{1} \cup {a_{k}} \cup B_{2} \in F_{τ}$ ，即 $B \cup {a_{k}} \in F$ .

引理4：去心星形元素归类到两端之间

若 $A_{0} \in F$ ， $a_{k} \notin A_{0}$ ，则 $A_{0} \subset A_{1} \cup A_{k} ∖ {a_{k}}$ .

证明： 否则， $A_{0} ⊄ A_{1} \cup A_{k}$ 且 $| A_{0} \cap (A_{1} \cup A_{k}) | \leq k - 1$ 。但 $| A_{1} \cup A_{k} | = 2 k - 1$ ，则存在某些 $B \in (\binom{(A_{1} \cup A_{k}) ∖ A_{0}}{k})$ 使得 $a_{k} \in B$ 。由星形构造引理， $B \in F$ ，但 $A_{0} \cap B = \emptyset$ ，矛盾！

引理5：

F

的构造

$F = (\binom{A_{1} \cup A_{k}}{k})$ 。

证明： $\supset$ . 对任意 $i \in A_{0}$ ，令 $B_{i} = ((A_{1} \cup A_{k}) ∖ A_{0}) \cup {i}$ 。由于 $a_{k} \in B$ ，由星形构造引理知 $B \in F$ 。同星形构造引理的证明，可知 $A_{1} \cup A_{k}$ 的包含 $i$ 的任一 $k -$ 子集均属于 $F$ 。因此 $(\binom{A_{1} \cup A_{k}}{k}) \subset F$ 。

$\subset$ . 否则，若存在 $C \in F$ ， $C ⊄ A_{1} \cup A_{k}$ 。则 $| (A_{1} \cup A_{k}) ∖ C | \geq k$ ，故存在 $B \in (\binom{A_{1} \cup A_{k}}{k})$ 使得 $B \cap C = \emptyset$ . 由 $\supset$ 的情形， $B \in F$ 且 $B \cap C \neq \emptyset$ ，矛盾！故 $F \subset (\binom{A_{1} \cup A_{k}}{k})$ .

定理第二部分的证明： 假设存在 $A_{0} \in F$ ， $a_{k} \notin A_{0}$ ，则 $F = (\binom{A_{1} \cup A_{k}}{k})$ 且 $| F | = (\binom{2 k - 1}{k - 1}) < (\binom{n - 1}{k - 1})$ ，矛盾！

练习：推广

设 $k$ 为固定正整数， $A_{1}, \dots, A_{m}$ 为 $[n]$ 的 $m$ 个子集，满足：

对任一个 $i \in [m]$ ， $| A_{i} | \leq k \leq \frac{n}{2}$ ；
对不同的 $i, j \in [m]$ ， $A_{i} ⊄ A_{j}$ ，且 $A_{i} \cap A_{j} \neq \emptyset$ ．

证明： $m \leq (\binom{n - 1}{k - 1})$ ．

证明： 对全轮换 $π \in C ([n])$ ，称 $A_{i}$ 在 $π$ 上，若 $A_{i}$ 的所有元素在 $π$ 中连续地出现．令 $F_{π}$ 为在 $π$ 上的 $A_{i}$ 的集族，我们对 $(A_{i}, F_{π})$ 计数．

首先，令 $π = (a_{1}, \dots, a_{n})$ （下标按模 $n$ 记）．对任意 $A_{i} \in F_{π}$ ，则存在 $j, l$ 使得

A_{i} = {a_{j}, a_{j + 1}, \dots, a_{j + l - 1}}, l = | A_{i} | .

称 $a_{j}$ 为 $A_{i}$ 的首字母．于是对任一 $a_{j}$ ， $F_{π}$ 中至多有一个 $A_{i}$ 使得 $a_{j}$ 为其首字母：否则 $A_{i}$ 中就会出现包含关系了．

不妨设 $a_{k}$ 是一个首字母．因为 $| A_{i} | \leq k$ ，剩下能当首字母的只有 $a_{1}, \dots, a_{2 k - 1}$ ．对任意 $1 \leq i < k$ ， $a_{i}$ 与 $a_{k + i}$ 不能同为首字母，否则就有非相交集了．因此我们有

\begin{matrix} (!) & | F_{π} | \leq k . \end{matrix}

固定 $F_{π}$ ，因此 $N \leq k \cdot (n - 1)!$ ．

另一方面，每个 $F_{π}$ 与 $π$ 一一对应．对固定的 $A_{i}$ ，不妨设其为 ${a_{1}, \dots, a_{s}}$ ，则其对应于置换数目为 $| A_{i} |! (n - | A_{i} |)!$ ——先排 $A$ 的部分，再排剩下的部分．因此

N = \sum_{i = 1}^{m} | A_{i} |! (n - | A_{i} |)! \geq m \cdot k! (n - k)! .

这里注意到 $m! (n - m)!$ 在 $n > 2 k$ 时 $k$ 越大越小．

综上，我们有 $m \leq \frac{N}{k! (n - k!)} \leq \frac{(n - 1)!}{(k - 1)! (n - k)!} = (\binom{n - 1}{k - 1})$ ，证毕！

练习：补集为相交集

令 $n \leq 2 k$ ， $A_{1}, \dots, A_{m}$ 为 $k -$ 元子集，使得 $A_{i} \cup A_{j} \neq [n]$ ．证明 $m \leq (1 - \frac{k}{n}) (\binom{n}{k}) = (\binom{n - 1}{k})$ ．

证明： 考虑 $F = {A_{1}^{C}, \dots, A_{m}^{C}}$ ．注意由题知 $A_{i}^{C} \cap A_{j}^{C} \neq \emptyset$ ，故 $F$ 是 $n - k$ 元相交族．由于 $n \leq 2 k$ ，故 $n \geq 2 (n - k)$ ，从而由 Erdos-Ko-Rado 定理，

m \leq (\binom{n - 1}{n - k - 1}) = (\binom{n - 1}{k}) .

第二种证明：Kneser 图法

定义：Kneser 图

Kneser 图 $K (n, k)$ （ $n \geq 2 k$ ）是满足如下条件的图：

$V = (\binom{[n]}{k})$ ；
对任意两个集合 $A, B \in (\binom{[n]}{k})$ ， $A B$ 在图中相邻当且仅当 $A \cap B = \emptyset$ 。

例如， $K (5, 2)$ 是 Peterson 图。

定义：最大独立集顶点数

对图 $G$ ，记 $α (G)$ 为 $G$ 中最大独立集的顶点数。

定理（Erdos-Ko-Rado）

对任意 $n \geq 2 k$ ，有 $α (K (n, k)) \leq (\binom{n - 1}{k - 1})$ 。

定义：正则图

称 $G$ 为 $d -$ 正则图，若各顶点度数为 $d$ 。

定理：正则图的最大特征值

若 $G$ 为 $d -$ 正则图，则 $G$ 的最大特征值为 $d$ ，对应于特征向量 $(1, 1, \dots, 1)$ 。

定理（Hoffman）

若 $G$ 为 $n$ 阶 $d -$ 正则图，其特征值（邻接矩阵特征值） $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ ，则

α (G) \leq n \cdot \frac{- λ_{n}}{λ_{1} - λ_{n}} .

证明： 设 $V (G) = [n]$ 。令 $v_{1}, \dots, v_{n}$ 为 $G$ 对应于各特征值的标准正交特征向量（由邻接矩阵为对称阵，故存在）。设 $I$ 为 $G$ 的一个最大独立集（从而 $| I | = α (G)$ ）。令 $1_{I} = (1_{j \in I})_{j}$ ，并记

1_{I} = \sum_{i = 1}^{n} α_{i} v_{i}, α_{i} \in R .

故 $| I | = ⟨ 1_{I}, 1_{I} ⟩ = \sum_{i = 1}^{n} α_{i}^{2}$ ， $α_{i} = ⟨ 1_{I}, v_{i} ⟩$ 。

由 $G$ 为 $d -$ 正则图， $λ_{1} = d$ 且 $v_{1} = \frac{1}{\sqrt{n}} (1, 1, \dots, 1)$ . 因此我们有

α_{1} = ⟨ 1_{I}, v_{1} ⟩ = \frac{| I |}{\sqrt{n}} .

因因为 $I$ 是 $G$ 中的独立集， $1_{I}^{⊤} A_{G} 1_{I} = \sum_{1 \leq i, j \leq n} (1_{I}^{⊤})_{i} a_{i j} (1_{I})_{j} = 0$ 。但另一方面，

\begin{aligned} 0 & = 1_{I}^{⊤} A_{G} 1_{I} = {(\sum_{i} α_{i} v_{i})}^{⊤} A_{G} (\sum_{j} α_{j} v_{j}) = {(\sum_{i} α_{i} v_{i})}^{⊤} (\sum_{j} α_{j} λ_{j} v_{j}) \\ = \sum α_{i}^{2} λ_{i} \geq α_{1}^{2} λ_{1} + (α_{2}^{2} + \dots + α_{n}^{2}) λ_{n} \\ = \frac{| I |^{2}}{n} λ_{1} + (| I | - \frac{| I |^{2}}{n}) λ_{n} . \end{aligned}

则我们有

\frac{| I |^{2}}{n} λ_{1} + (| I | - \frac{| I |^{2}}{n}) λ_{n}

故 $α (G) = | I | \leq n \cdot \frac{- λ_{n}}{λ_{1} - λ_{n}}$ .

定理（GTM 207）

Kneser图的特征值为

v_{j} = (- 1)^{j} (\binom{n - k - j}{k - j}), 重数 (\binom{n}{j}) - (\binom{n}{j - 1}) .

对任意 $0 \leq j \leq k$ 。

定理的证明： 记 $K (n, k)$ 的特征值为 $λ_{1} \geq λ_{2} \geq \dots \geq λ_{(\binom{n}{k})}$ ，此时

λ_{1} = (\binom{n - k}{k}), λ_{(\binom{n}{k})} = - (\binom{n - k - 1}{k - 1}) .

由 Hoffman定理，

α (K (n, k)) \leq (\binom{n}{k}) \frac{- λ_{(\binom{n}{k})}}{λ_{1} - λ_{(\binom{n}{k})}} = (\binom{n - 1}{k - 1}) .

证毕！

练习

证明：对任意相交族 $F \subset 2^{[n]}$ ，都存在一个相交族 $F^{'} \subset 2^{[n]}$ ，使得 $| F^{'} | = 2^{n - 1}$ 且 $F \subset F^{'}$ ．

证明： 起初，令 $F^{'} = F$ ．Claim：对任意 $A \subset [n]$ ， $A$ 或 $A^{C}$ 之一与 $F^{'}$ 均有交：否则存在 $A \cap B = \emptyset$ 且 $A^{C} \cap C = \emptyset$ ，于是 $B \subset A^{C}$ 且 $C \subset A$ ，故 $B \cap C = \emptyset$ ，矛盾．故 Claim 得证．

现设 $A$ 与 $F^{'}$ 中所有元素均有交．把 $A$ 放进去，则 $F^{'}$ 仍是相交族．对每一对 $(B, B^{C}) \subset 2^{[n]} \times 2^{[n]}$ ，不停将其中与 $F^{'}$ 均有交的一个放进去，直到所有 $2^{n - 1}$ 个对子都被遍历即可．