大概就是今天看数学书的时候学到了如何证明 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\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}（英文好像是这个）的一个推广。

同样的类似上述的解法 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}。

在一条链中，$|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^+ 所有正因数可分为互不相交的对称链。

设命题对不同素因子个数 $\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。

对 $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：修好了，感谢审日报的人员。