极值集合论

· · 个人记录

极值集合论：

研究带有一定性质的“集合族”的大小

偏序集 Dilworth 定理/Dilworth 对偶定理

极值集合论中的定理：Sperner 定理，Erdos-Ko-Rado 定理

I. Dilworth 定理

偏序集：(S,\leq) 满足以下性质：

  1. 自反性 \forall a\in S: a \leq a；

  2. 传递性 \forall a,b,c\in S \ \text{s.t.}a\leq b,b\leq c:a \leq c；

  3. 反对称性 \forall a,b \ \text{s.t.}a\leq b,b\leq a:a=b；

常见例子：大小关系，整除关系，集合包含关系

因此，极大是一个局部性质

Rmk. 全序集本身是一条链；极大反链大小为 1。

Dilworth 定理：S 最少被 m 条链覆盖，S 的最大反链包含 M 个元素，则 m=M。

接下来直接证明 $m=M$。考虑对集合元素的个数做归纳。 奠基：$|S|=1$ ok 证明过程：先取一个含 $m$ 条链的覆盖。任取其中一条链，扩充其为极大链，记为 $C$。$S - C$ 可以被 $m-1$ 条链覆盖，且这个 $m-1$ 也是最小的。考察 $S-C$ 当中元素个数最多的反链的元素个数 $M'$： 1. $M'\leq M-1$，因为 $|S-C|<|S|$，所以 $m-1\leq M'\leq M-1$，得证； 2. $M'=M$，记 $S-C$ 中最大的反链为 $A=\{a_1,a_2\cdots a_{M}\},S^-=\{x\in S\mid \exists i:x\leq a_i\},S^+=\{x\in S\mid \exists i:a_i\leq x\}$。 性质： 1. $S^-\subsetneq S,S^+\subsetneq S$。 2. 对 $S^-$ 断言：最大链 $C$ 中最大元素 $y$ 不在 $S^-$ 当中（否则可以继续扩充）。 3. 对 $S^+$ 断言：最大链 $C$ 中最小元素 $y$ 不在 $S^+$ 当中（否则可以继续扩充）。 4. $S^-\bigcup S^+ = S$，由 $A$ 的最大性保证。 5. $A$ 是 $S^-,S^+$ 的最大反链。 由归纳假设，可以取出 $M$ 条链覆盖 $S^+,S^-$，则 $a_1,a_2\cdots a_M$ 必然分属这 $M$ 条链之一，且都是最大元/最小元，所以可以把 $S^+,S^-$ 当中的 $M$ 条链从 $A$ 处拼接起来，由此得出 $S$ 的最小链覆盖是 $M$，即 $m=M$。 Rmk. 其实不会出现 $M'=M$ 的情况。 ### Dilworth 对偶定理：$S$ 最少被 $m$ 条反链覆盖，$S$ 的**最大**链包含 $M$ 个元素，则 $m=M$。 $m\geq M$ 是容易的，抽屉原理即可。 要证明 $m\leq M$，只需要证明 $S$ 可以被 $M$ 条反链覆盖。 设 $M_1$ 是 $S$ 的极大元构成的集合，则 $M_1$ 是一条反链。在 $S-M_1$ 中取出极大元集合 $M_2\cdots$ 根据链划分情况，操作将在 $M$ 步后结束。由此 $m\leq M$。 应用： 1. 一个 $mn+1$ 项的实数序列当中必然包含一个长为 $m+1$ 的递增子列或一个长为 $n+1$ 的递减子列。 推广：一个 $mn+1$ 元偏序集必然包含一个长为 $m+1$ 的链或长为 $n+1$ 的反链。 我们需要重新建立一个偏序关系：设序列为 $a_1,a_2,\cdots a_{nm+1}$，定义 $a_i\preceq a_j\Leftrightarrow i\leq j,a_i\leq a_j$。 链：递增子列；反链：严格递减子列。 证明反证法即可。 2. 将 $1$ 到 $100$ 的所有正整数染色，且同色的两个数不能有整除关系，求颜色数量的最小值。 将 $a\preceq b$ 定义为 $a\mid b$，用 Dilworth 对偶定理，并动态规划（归纳）求解最长正链即可。 3. 有 $1001$ 个长方形，边长均是 $1\sim 1000$ 范围内的正整数，证明：从中可以找到 $3$ 个编号不同的长方体 $A,B,C$ 满足 $C$ 覆盖 $B$，$B$ 覆盖 $A$。覆盖指的是两维均大于等于。 把每个长方形描述为 $(a,b),a\leq b$，集合 $S=\{(a_i,b_i)\}$。 则“覆盖”是一种偏序关系。 结论即为 $S$ 包含一条长为 $3$ 的链，则由抽屉原理只需要证明 $S$ 可以由不超过 $500$ 条链覆盖。再由 Dilworth 定理只需要证明 $S$ 中的反链大小不超过 $500$。 任取一个反链 $\{(a_i,b_i)\}$，有 $\forall i\neq j,a_i\neq a_j,b_i\neq b_j$。 不妨设 $\forall i\in[1,n-1]:a_i< a_{i+1}$，根据反链定义有 $\forall i\in[1,n-1]:b_i>b_{i+1}$，所以 $a_1<a_2<\cdots <a_n\leq b_n<b_{n-1}<\cdots <b_1$，所以 $2n-1\leq 1000$，即 $n\leq 500$。 $\square

II. Sperner 定理

设 A 是一个 n 元集合，B 是其中若干子集构成的子集族，并且 B 中集合两两没有包含关系。问 |B| 的最大值是多少。

所有 k 元集满足条件，最多的是 \begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix}，并且这也是所有可能方案中的最大值。

Sperner 定理：设 A 是一个 n 元集合，B 是其中若干子集构成的子集族，并且 B 中集合两两没有包含关系，则 |B| 的最大值是 \begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix}。

不妨设 A=\{1,2,\cdots n\}，考虑 A 的所有子集构成的子集族，称为 A 的幂集 P，包含关系是 P 的一个偏序关系。

此时 B 是 P 的一个反链。于是 Sperner 定理等价于 P 中元素最多的反链含有 \begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix} 个元素。由 Dilworth 定理等于 P 最少可以由 \begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix} 条链覆盖。

对称链划分定理： 可将 $n$ 元集合的幂集 $P$ 划分为 $\begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix}$ 条链，其中每条链形如 $\{k \text{元集},k-1 \text{元集}\cdots n-k \text{元集}\}$，并且大集合包含小集合。 构造方式： 当 $n=1$ 时，可以直接构造出来。 假设已经有 $\{1,2\cdots n\},n\geq 1$ 的幂集 $P$ 的对称链划分，每条链形如 $\{B_k,B_{k+1}\cdots B_{n-k}\}$，且 $B_l\subset B_{l+1}$。 记 $C=\{n+1\}$。 Step 1. 复制 $\{B_k,B_{k+1}\cdots B_{n-k}\}\Rightarrow \{B_k\bigcup C,B_{k+1}\bigcup C\cdots B_{n-k}\bigcup C\}$。 Step 2. 修正 $\{B_k,B_{k+1}\cdots B_{n-k}\}, \{B_k\bigcup C,B_{k+1}\bigcup C\cdots B_{n-k}\bigcup C\}\Rightarrow \{B_{k+1}\cdots B_{n-k}\}, \{B_k,B_k\bigcup C,B_{k+1}\bigcup C\cdots B_{n-k}\bigcup C\}$。 Rmk. 若 $2\mid n$，对于一元集合 $\{B_{n/2}\}$，实际上是合并。 而根据归纳构成出来的链中每条链都含有恰好一个大小为 $\lfloor n/2\rfloor$ 的集合，所以链的个数就是 $\begin{pmatrix}n\\\lfloor n/2\rfloor\end{pmatrix}$。 应用：设 $N=\displaystyle\prod_{i=1}^k p_i$，且 $p_i$ 互不相同，令 $a< b\leq N$。 令 $S_1=\{d\mid d\mid n,a\leq d\leq b,d \text{有偶数个素因子}\},S_2=\{d\mid d\mid n,a\leq d\leq b,d \text{有奇数个素因子}\}$。 证明：$||S_1|-|S_2||\leq \begin{pmatrix}k\\\lfloor k/2\rfloor\end{pmatrix}$。 可以将 $N$ 的所有因子与 $\{1,2\cdots k\}$ 的子集一一对应。由对称链划分定理，后者可划分为 $\begin{pmatrix}k\\\lfloor k/2\rfloor\end{pmatrix}$ 条对称链。 对于每条对称链，其与 $[a,b]$ 的交集一定是若干连续的元素 $B_{c},B_{c+1}\cdots B_d$，并且这些元素交错位于 $S_1,S_2$ 之中，所以这条对称链对差值的贡献至多为 $1$，由此证得结论。 Sperner 定理的算两次证明法： 设 $B$ 是 $A=\{1,2\cdots n\}$ 的幂集 $P$ 的一个反链，则 $P$ 的每条极大链中至多含有 $B$ 中的一个元素。 观察：$P$ 的每条极大链和 $1,2\cdots n$ 的排列一一对应。给定 $P$ 的一个元素，即 $A$ 的一个子集 $\{b_1,b_2\cdots b_k\}$，则有 $k!(n-k)!$ 条极大链包含 $\{b_1,b_2\cdots b_k\}$。 以下对二元组 $(S,C)$，其中 $S$ 是 $B$ 中元素，$C$ 是极大链，$S\in C$ 来计数： 极大链共 $n!$ 个，每条极大链中最多含有 $1$ 个 $B$ 中元素，故满足条件的 $(S,C)$ 个数 $\leq n!\times 1=n!$； 另一方面，$B$ 中每个 $k$ 元集 $S$ 贡献 $k!(n-k)!$ 个二元组 $(S,C)$，设 $B$ 中有 $a_k$ 个 $k$ 元集，则二元组 $(S,C)$ 个数 $=\displaystyle\sum_{k=0}^n a_k\times k!(n-k)!\leq n!\Rightarrow \displaystyle\sum_{k=0}^n \frac{a_k}{\begin{pmatrix}n\\ k\end{pmatrix}}\leq 1\Rightarrow |B|=\displaystyle\sum_{k=0}^n a_k\leq \begin{pmatrix}n\\ \lfloor n/2\rfloor \end{pmatrix}$。 应用：（Sperner 定理推广）Bollobas 定理： 设 $A_1,A_2\cdots A_m,B_1,B_2\cdots B_m$ 是 $\{1,2\cdots n\}$ 的子集，且 $[|A_i\bigcap B_j|>0]=[i\neq j]$。设 $|A_i|=a_i,|B_i|=b_i$，则 $\displaystyle\sum_{i=1}^m \frac{1}{\begin{pmatrix}a_i+b_i\\ a_i\end{pmatrix}}\leq 1$。 证明：任取 $\{1,2\cdots n\}$ 的一个排列。若存在 $i,j$ 使得 $A_i$ 的元素全排在 $B_i$ 之前，且 $A_j$ 的元素全排在 $B_j$ 之前，会出现矛盾。因此至多存在一个下标 $i$ 使得 $A_i$ 的元素全排在 $B_i$ 的元素之前。 计算：对于给定的 $i$，使得"$A_i$ 的元素排在 $B_i$ 的元素之前"的排列共有 $\begin{pmatrix}n\\a_i+b_i\end{pmatrix}\times (n-a_i-b_i)!\times a_i!\times b_i!=\displaystyle\frac{n!}{\begin{pmatrix} a_i+b_i\\a_i\end{pmatrix}}$ 个，由 $\displaystyle\sum_{i=1}^m\displaystyle\frac{n!}{\begin{pmatrix} a_i+b_i\\a_i\end{pmatrix}}\leq n!$ 即得证。 ## III. Erdos-Ko-Rado 定理 设 $B$ 是 $n$ 元集合 $A$ 的一个子集族，$B$ 中集合两两相交非空，称 $B$ 是相交族，且 $B$ 中集合都是 $k(k\leq \lfloor n/2\rfloor)$ 元集，则 $\max |B|=\begin{pmatrix}n-1\\k-1\end{pmatrix}=\displaystyle \frac{k}{n}\begin{pmatrix}n\\k\end{pmatrix}$。 证明：任取 $\{1,2\cdots n\}$ 的圆排列 $a_1,a_2\cdots a_n$。它有顺次排列的 $n$ 个 $k$ 元集合。断言：这些集合中至多取出 $k$ 个满足它们是两两相交的。 断言证明：不妨设 $\{a_n,a_1\cdots a_{k-1}\}$ 被取出。记 $F_s=\{a_s,a_{s+1}\cdots a_{s+k-1}\}$ 下标模 $n$ 理解。与 $F_n$ 相交的集合有 $F_1,F_2,\cdots F_{k-1},F_{-1},F_{-2}\cdots F_{-(k-1)}$，因 $k\leq \lfloor n/2\rfloor$，所以这 $2k-2$ 个集合两两不同。注意到 $F_{-(k-1)}\bigcap F_{1}=\emptyset,F_{-(k-2)}\bigcap F_{2}=\emptyset\cdots F_{-1}\bigcap F_{k-1}=\emptyset$，所以每组最多选出 $1$ 个集合，总共最多 $k$ 个集合，断言成立。 算两次的严格证明与 II 类似，不再赘述。