Dilworth 学习笔记

大概就是今天看数学书的时候学到了如何证明 Dilworth 反链定理。 然后十分赞赏，开个坑，可能会投个日报。 本文大部分内容来自《数学奥林匹克命题人讲座——集合与对应》。 # 0. 引入与前言 相比各位都学过 最长上升子序列 和 最小的用不上升子序列覆盖 的转化（导弹拦截）。 然后其中用的便是 $\mathcal{Dilworth}$ 定理。 然后本文主要介绍如何证明该定理。 你需要的东西：基本的对于 **集合** 以及其运算的一些认识，对于 **子集族** 有一些认识。 tips：由于内容偏向数学（MO），本文使用 $C_{x}^{y}=\dbinom{x}{y}$ 这种形式表示二项式系数。 # 1. 让我们开始 对于 $\mathcal{Dilworth}$ 定理的一个叙述： 当集族 $\mathfrak{A}=\left\{A_1,A_2,\cdots A_t\right\}$ 分拆为互不相交的 链 时，所需用的 链 的最小条数 $m$ 等于 $\mathfrak{A}$ 中最多的 $\mathcal{Sperner}$ 族 的元数 $s$。 以下将会对 链，以及 $\mathcal{Sperner}$ 族 做一些讨论。 # 2. $\mathcal{Sperner}$ 集 又被称为 $\mathcal{Sperner}$ 族，因为其定义在集族上。 若集族 $\mathfrak{A}$ 中任意两个子集 $A_i,A_j(i\neq j)$ 互不包含，称 $\mathfrak{A}$ 为 **$\mathcal{Sperner}$ 族**。 考虑其性质： - 如果 $n$ 元集 $X=\left\{1,2\cdots n\right\}$ 的子集族 $\mathfrak{A}$ 是 $\mathcal{Sperner}$ 族，证明：$\mathfrak{A}$ 的元素至多为 $C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}$，且 $n=2k$ 时当且仅当所有元为所有 $k$ 元集合时取等；$n=2k+1$ 时所有元为所有 $k$ 元集合或者所有 $k+1$ 元集合时取等。 本性质即 $\mathcal{Sperner}$ 定理。 考虑 $1,2\cdots n$ 的全排列，显然其总数为 $n!$。 另一方面，前 $k$ 个元素恰好组成 $\mathfrak{A}$ 中某个集合 $A_i$ 的有 $k!(n-k)!$，而 $\mathfrak{A}$ 为 $\mathcal{Sperner}$ 族，这种前 $k$ 个元素在 $\mathfrak{A}$ 中全排列互不相同，设 $\mathfrak{A}$ 中有 $f_k$ 个 $A_i$ 使得 $|A_i|=k(k=1,2\cdots n)$，则 $\sum\limits_{k=1}^{n} f_k\times k!(n-k)!\le n!$。 而 $C_{n}^{k}$ 在 $k=\left\lfloor\frac{n}{2}\right\rfloor$ 时能取到最大值，所以可以得到 $|\mathfrak{A}|=\sum\limits_{k=1}^n f_k\le C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}\sum\limits_{k=1}^n f_k\times \dfrac{k!(n-k)!}{n!}\le C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}$ 而 $\mathfrak{A}$ 全部由 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 元子集组成时取等。 $\mathcal{Another\ Solution:}$ 设 $\mathfrak{A}=\left\{A_1,A_2\cdots A_t\right\}$，这些元中元数最小的集合是 $r$ 元集，总共有 $f_r$ 个。尝试添加一个 $X$ 中元素到 $r$ 元集中。对每个 $r$ 元集 $n-r$ 中添加方法，所以添加后至少有 $\dfrac{f_r(n-r)}{r+1}>f_r$ 个 $r+1$ 元集，而由于 $\mathcal{Sperner}$ 集的定义，这些集合与 $A_1,A_2\cdots A_t$ 均不相同。 $r\le \left\lfloor\dfrac{n}{2}\right\rfloor$ 时 $\dfrac{n-r}{r+1}>1$，总子集个数增加。 所以可得 $r\ge \left\lfloor\dfrac{n}{2}\right\rfloor$。 类似的方法，可以得到元数最大值 $s\le \left\lfloor\dfrac{n}{2}\right\rfloor$ 时能取到最大值。 因此可以得到 $s=r=\left\lfloor\dfrac{n}{2}\right\rfloor$ 时能取到最大值 $C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}$。 接下来考虑后半段。 第二种解法可以非常隐晦的告诉我们 $n=2k+1$ 时似乎 $s,r$ 不一定都等于 $\left\lfloor\dfrac{n}{2}\right\rfloor$（因为其中有 $\ge$ 号）。 第一种解法则可以直接了当的告诉我们 $n=2k$ 时的情况。 令 $n=2k+1$，$(C_{n}^{q})_{\max}\Leftrightarrow q=k\operatorname{or} q=k+1$。也就是说 $|\mathfrak{A}|_{\max}\Rightarrow \forall A_i\in \mathfrak{A}$，$A_i$ 为 $k$ 或者 $k+1$ 元集。 令 $A_1=\{1,2\cdots k\}$，对 $\forall l>k$，$\{l,1,2\dots k\}\notin \mathfrak{A}$，全排列 $l,1,2\cdots k\cdots$ 前 $k+1$ 个元组成集合 $\notin \mathfrak{A}$，但是 等号要成立，此全排列前 $k$ 或者前 $k+1$ 元所成集在 $\mathfrak{A}$ 中，所以 $\{l,1,2\cdots k-1\}\in \mathfrak{A}$，也即 $\forall A_i\in \mathfrak{A},|A_i|=k$，将 $A_i$ 中一个元换成其他任意元素所得到的 $k$ 元集 $\in \mathfrak{A}$。 经过这样的替代，$X$ 所有 $k$ 元集均 $\in \mathfrak{A}$，所以 $\mathfrak{A}$ 由 $X$ 所有 $k$ 元集组成（此时 $|\mathfrak{A}|=C_n^k$），或者不含 $X$ 任意一个 $k$ 元子集，即全部由 $k+1$ 元子集构成。 同理可知 $\mathfrak{A}$ 包含了所有 $k+1$ 元子集时也是一个 $\mathcal{Sperner}$ 集，且 $|\mathfrak{A}|=C_n^{k+1}=C_n^k$。 综上，命题即得证。 ## 2.2 $\mathcal{Another\ Problem\ About\ Sperner}$ 据说问题来自 $\text{Bollobas}$（博洛巴什），但似乎网上没有找到相关的名称，如果有神仙找到了可以私信我纠正。 我暂且叫他 $\mathcal{Bollobas\ Lemma}$。 这是 $\mathcal{Sperner\ Lemma}$（英文好像是这个）的一个推广。 - $A_1,A_2\cdots A_k,B_1,B_2\cdots B_k$ 为 $X=\{1,2\cdots n\}$ 的子集，当且仅当 $i=j$ 时 $A_i\cap B_j=\varnothing$，如果 $|A_i|=a_i,|B_i|=b_i$，试证明 $\sum\limits_{i=1}^k\dfrac{1}{C_{a_i+b_i}^{a_i}}\le 1$。 同样的类似上述的解法 1，考虑 $n!$ 个全排列，$A_i$ 元素全在 $B_i$ 元素前面全排列 $C_n^{a_i+b_i}\times a_i!b_i!(n-a_i-b_i)!=\dfrac{n!}{C_{a_i+b_i}^{a_i}}$ 个。 如果在一个全排列中，$A_i$ 的元素全在 $B_i$ 元素前面，$A_j$ 元素也全在 $B_j$ 前面$(i\neq j)$，那么在 $A_i$ 已经过了 $B_j$ 还没有到的时候 $A_i\cap B_j=\varnothing$，$A_i$ 结束 $B_j$ 开始情况中，$A_j\cap B_i=\varnothing$，与已知矛盾！ 所以每一个全排列中，至多一个 $A_i$ 在 $B_i$ 前面，因此对 $i$ 求和，$\sum\limits_{i=1}^k \dfrac{n!}{C_{a_i+b_i}^{a_i}}\le n!$。 得证！ 另：取 $B_i=A_i'$（$A_i'$ 表示 $A_i$ 的补集），$A_i\cap B_j$，$A_i\cap B_j\neq\varnothing$，$A_i\nsubseteq A_j$，此时原式变成 $\sum\limits_{i=1}^k \dfrac{1}{C_{n}^{a_i}}\le 1$，由 $(C_n^{\left\lfloor\frac{n}{2}\right\rfloor})_{\max}$ 得出 $\mathcal{Sperner\ Lemma}$。 # 3. 链 狭义的链：对于 $X$ 子集族 $\mathfrak{A}=\left\{A_1,A_2\cdots A_t\right\}$ 中子集满足 $A_1\subset A_2\subset\cdots \subset A_t$，称 $\mathfrak{A}$ 为一条链，其长度为 $t$。 - 性质：设 $\mathfrak{A}_1,\mathfrak{A}_2,\cdots \mathfrak{A}_m$ 为 $X$ 的 $k$ 条链，每两条之间均没有子集关系，如果每条链长度均为 $k+1$，证明 $m_{\max}=C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$。 令 $m_{\max}=f(n,k)$。 设 $m$ 条链 $A_{i0}\subset A_{i1}\subset\cdots \subset A_{ik}$ 满足题目条件。 对 $\mathcal{Bollobas\ Lemma}$ 取 $A_i=A_{i0},B_i=A_{ik}'$，则 $a_i=|A_{i0}|,b_i=n-|A_{ik}|\le n-(a_i+k)$，因此 $C_{a_i+b_i}^{a_i}\le C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$。 而显然的，$A_i\cap B_i\subseteq A_{ik}\cap A_{ik}'=\varnothing$，若有 $i\neq j$ 使得 $A_i\cap B_j=\varnothing$，则 $A_{i0}\subseteq A_{jk}$，显然矛盾。因此 $A_i,B_i$ 满足 $\mathcal{Bollobas\ Lemma}$ 的条件。因此 $m=\sum\limits_{i=1}^m 1\le \sum\limits_{i=1}^m \dfrac{C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}}{C_{a_i+b_i}^{a_i}}\le C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$ 所以 $f(n,k)\le C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$。 另一方面，设 $M_i$ 为 $\{k+1,k+2\cdots n\}$ 的 $\left\lfloor\frac{n-k}{2}\right\rfloor$ 元子集，这样子集 $C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$ 个，链 $M_i\subset M_i\cup \{1\}\subset M_i\cup \{1,2\}\cdots \subset M_i\cup \{1,2\cdots k\}(i\in[1,C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}],i\in Z)$ 满足条件！ 因此 $f(n,k)=C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$。 $k=0$ 时其即为 $\mathcal{Sperner\ Lemma}$。 在一条链中，$|A_{i+1}|=|A_i|+1,|A_1|+|A_t|=n$，则称此条链为 **对称链**。显然每条对称链含有 $X$ 的一个 $\left\lfloor\frac{n}{2}\right\rfloor$ 元子集。$n=2k$ 时，$t$ 为奇数，最中间的集为 $k$ 元集，$n=2k+1$ 时，$t$ 为偶数，最中间两个集合为 $k,k+1$ 元集。 - 性质：$X=\{1,2\cdots n\}$ 全体子集可以分拆成 $C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}$ 条互不相交的对称链。 对 $n$ 使用归纳法，$n=1$ 时显然，设命题对于 $n-1$ 成立，设 $A_1\subset A_2\subset \cdots \subset A_t\qquad(1)$ 为 $n-1$ 时任意一条链，考虑链 $A_1\subset A_2\subset\cdots \subset A_t\subset A_t\cup\{n\}\qquad(2)$ 或者链 $A_1\cup \{n\}\subset A_2\cup \{n\}\subset\cdots \subset A_{t-1}\cup\{n\}\qquad(3)$，显然上述两条链都是 $X$ 的对称链。 设 $A\subset X$，如果 $n\notin A$，$A$ 必在恰一条形如 $(1)$ 或者 $(2)$ 的链中，不在任意一条 $(3)$ 中。 如果 $n\in A$，$A-\{n\}$ 恰在一条 $(1)$ 中，当他等于 $A_t$ 时恰在一条 $(2)$ 中，否则恰在一条 $(3)$ 中。 所以 $X$ 全部子集被拆成不相交的对称链，每条对称链恰含一个 $\left\lfloor\frac{n}{2}\right\rfloor$ 元子集，所以链条数为 $C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor}$。 ## 3.2 广义的链 广义的链：将 $\subset$ 关系推广到任意一种**偏序**关系，即某种关系 $\succ$，满足对某个集合 $S$ 中的某些元素，这些元素满足 $x\succ y,y\succ z$ 时，$x\succ z$，也即这种关系具有**传递性**。 则 $S$ 中具有以下这种**广义的链**：$x_1\succ x_2\succ \cdots \succ x_t$。 常见的偏序关系：大于/小于，包含，整除，OI 中图论里的的有向边 等。 下面是广义链的应用。 ## 3.3 $\mathcal{Problem\ One}$ 证明 $m\in N^+$ 所有正因数可分为互不相交的对称链。 $m=p^{\alpha}$，$p\in P$（$P$ 为素数集），$\alpha\in N$ 时，$m$ 因数可以组成 $1,p,p^2\dots p^{\alpha}$ 一条对称链。 设命题对不同素因子个数 $\le n$ 的 $m$ 成立，考虑 $m=m_1p^{\alpha}$，$p\nmid m_1$，将 $m_1$ 的因数分解成若干条不相交的对称链。设 $d_1\cdots d_h$ 为其中一条。 作表 $\begin{bmatrix}d_1&d_2&\cdots &d_{h-2}&d_{h-1}&d_{h}\\d_1p&d_2p&\cdots&d_{h-2}p&d_{h-1}p&d_{h}p\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\d_1p^{\alpha}&d_2p^{\alpha}&\cdots&d_{h-2}p^{\alpha}&d_{h-1}p^{\alpha}&d_{h}p^{\alpha}\end{bmatrix}$ 每一层均为一条对称链。 以最外层为例 $d_1,d_2\cdots d_{h-1},d_{h},d_h p,d_h p^2\cdots d_hp^{\alpha}$ 构成对称链。 容易发现 $m$ 每个因数都出现过，因此命题成立！ 由 $\mathcal{de\ Brujin}$ 等人在 1951 年证明的结论。 ## 3.4 分拆链 设 $P_1\cdots P_n$ 均为 $X$ 的分拆，如果 $P_1$ 仅有一个集 $X$，$P_i$ 由 $A_1\cdots A_i$ 组成，其中 $A_1\cdots A_i$ 构成 $X$ 的分拆，而且其中某两个集合合并后可组成 $P_{i-1}$，则将 $P_1\cdots P_n$ 称为长为 $n$ 的**分拆链**。 考虑分拆链计数。 考虑已有 $P_n\cdots P_{k+1}$，则 $P_k$ 有 $C_{k+1}^2$ 种（将任意两个集合合并），则分拆链共有 $\prod\limits_{k=1}^{n-1} C_{k+1}^2=\dfrac{(n-1)!n!}{2^{n-1}}$ 个。 # 4. $\mathcal{Dilworth}$ 回到最开始的叙述： - 当集族 $\mathfrak{A}=\left\{A_1,A_2,\cdots A_t\right\}$ 分拆为互不相交的 链 时，所需用的 链 的最小条数 $m$ 等于 $\mathfrak{A}$ 中最多的 $\mathcal{Sperner}$ 族 的元数 $s$。 $\mathcal{Sperner}$ 族中 $s$ 个元互不包含，因此每条链至多含一个这样的元素，因此 $m\ge s$。 对 $t$ 归纳，$t=1$ 时显然成立。 假设结论对 $<t$ 的情况成立，考虑此时的 $\mathfrak{A}$。 对 $\mathfrak{A}$ 中任一元数 $s$ 的 $\mathcal{Sperner}$ 集 $\mathfrak{B}$，不在 $\mathfrak{B}$ 中的元 $A$ 必与 $\mathfrak{B}$ 中某一 $B$ 有包含关系，否则与 $|\mathfrak{B}|=s$ 的最大性矛盾。 将满足 $A\supset B$ 的 $A$ 归入 $\mathfrak{B}_1$ 一族，满足 $A\subset B$ 的 $A$ 归入 $\mathfrak{B}_2$ 一族。 如果 $\mathfrak{B}_1,\mathfrak{B}_2$ 均非空，令 $\mathfrak{A}_1=\mathfrak{B}\cup\mathfrak{B}_1,\mathfrak{A}_2=\mathfrak{B}\cup\mathfrak{B}_2$，$|\mathfrak{A}_1|,|\mathfrak{A}_2|< t$。 定义，最小元为不包含其他任意元素的一个族。同理定义最大元。 由归纳假设，$\mathfrak{A}_1,\mathfrak{A}_2$ 均可以分拆为 $s$ 条链，而 $\mathfrak{B}$ 为 $\mathcal{Sperner}$ 族，所以在 $\mathfrak{A}_1$ 中，$\mathfrak{B}$ 的元都是最小元，从而 $\mathfrak{A}_1$ 的 $s$ 条链终端正是 $\mathfrak{B}$ 的 $s$ 个元，同理，$\mathfrak{A}_2$ 的 $s$ 条链首端为 $\mathfrak{B}$ 的 $s$ 个元（作为最大元）。 因此可以将 $\mathfrak{A}_1$ 链与 $\mathfrak{A}_2$ 链逐对对接起来形成 $\mathfrak{A}$ 的链，$s\ge m$。 如果对 $\mathfrak{A}$ 中任一元数 $s$ 的 $\mathcal{Sperner}$ 集 $\mathfrak{B}$，$\mathfrak{B}_1,\mathfrak{B}_2$ 至少有一个为空，那么 $\mathfrak{A}$ 至多有两个元数为 $s$ 的 $Sperner$ 族，$\mathfrak{A}$ 的最大元（它不在 $\mathfrak{A}$ 的其他元素中）所成族 $\mathfrak{E}$ 与 $\mathfrak{A}$ 的最小元 （它不包含其他 $\mathfrak{A}$ 中的元素）组成的族 $\mathfrak{F}$。 - 如果仅有 $\mathfrak{E}$ 有 $s$ 个元，从 $\mathfrak{E}$ 中去除一个元 $A$，$\mathfrak{A}$ 剩下 $t-1$ 个元，$\mathfrak{A}$ 最大的 $\mathcal{Sperner}$ 族仅有 $s-1$ 个元。由归纳假设，可以分拆为 $s-1$ 条链，添上 $A$ 自己一条链，共 $s$ 条； - 如果仅有 $\mathfrak{F}$ 有 $s$ 个元，同理得可以分拆为 $s$ 条链。 - $\mathfrak{E},\mathfrak{F}$ 均有 $s$ 个元，任取 $B\in \mathfrak{F}$，必有 $A\in \mathfrak{E},A\supset B$，去除 $A,B$ 后剩余元组成 $s-1$ 条链，添上 $A\supset B$，共 $s$ 条。 综上，$\mathcal{Dilworth}$ 定理得证！ 另：定理中的包含可以改为任何偏序关系 $\succ$，只需将集族改为相应的偏序集即可。 简单的应用： - 证明：任何 $mn+1$ 个自然数中，能找到 $m+1$ 个数，使得每一个数能整除比它大的数，或者找到 $n+1$ 个数，每一个数不能整除其他的数。 - 最长上升子序列的长度 等于 最小的用不上升子序列覆盖序列的子序列个数。 [例题：P4928](https://www.luogu.com.cn/problem/P4298)，更难的应用。 本题描述相当于找某个 DAG 上最长的反链。 偏序关系 $\succ$ 满足：$[x\succ y]\Leftrightarrow [y \text{向}x\text{连边}]$。 所以由 $\mathcal{Dilworth}$ 定理得出所求的即为 用原图上的链覆盖 DAG 的链条数最小值。 然后再用最大流等方法求解。 [例题2：CF590E](https://www.luogu.com.cn/problem/CF590E) 建一个 AC 自动机，求出所有的子串关系。 然后发现本题中的 AC 自动机可以转换成上题中的 DAG（子串关系也是一种偏序关系，与连边类似）。 因此利用上题的解法解决即可。 不愧是黑题啊。 # 5. 结语 $\mathcal{Dilworth}$ 定理在 MO 中主要用于解决证明存在性问题。（似乎常用于反证法？） 在 OI 中更多的是求出最值，构造等。 但其中不变的是对于“覆盖”与“最值”的转换思想。（可能比喻不够具体，先这样吧）。 # 6. 后记 被骂了，typo 一吨，然后等下再交。 upd：修好了，感谢审日报的人员。