Dilworth 定理
前言
为什么这个定理这么图论又这么数学啊。
相关定义
然后 Dilworth 定理是一个建立在偏序集上的东西，偏序集，即存在偏序关系的集合。
偏序关系的定义要涉及集合论。比较复杂，大概来说只要一些元素满足自己和自己有大小关系，若两元素不相等，且互相有大小关系，它们不能互相大于等于对方，若 $a,b$ 有大小关系，$a,b$ 有大小关系，那么 $a,c$ 有大小关系。
比较典型的例子就是二元组，子集，子序列，DAG 上的可达关系之类的。
在此基础上，定义：
- 可比：$A,B$ 之间存在大小关系。
- 不可比：$A,B$ 之间不存在大小关系。
- 链：二元组集合 $S$ 对于任意 $x,t\in S$ 满足 $x$ 和 $y$ 可比（其实可以视作每个点向比它小的点连边后建的图上的一条链）。
- 反链：二元组集合 $S$ 对于任意 $x,t\in S$ 满足 $x$ 和 $y$ 不可比（补图的链）
定理内容
对一个偏序集建出的 DAG 满足最小链覆盖等于最长反链。
这个其实比较好感性理解，因为考虑你在每条链上选一个连起来连出反链，考虑严谨证明。
证明
设最小链覆盖大小为 $N$，最长反链大小为 $M$。
首先显然 $M\le N$，因为最长反链上不可能有任意两个点在同一条链上。
下面证明 $M\ge N$。为方便叙述，称满足 $M\ge N$ 的偏序集为“是好的偏序集”。
考虑数学归纳法，设偏序集大小为 $k$，当 $k=1$ 时，显然成立。
考虑证明当大小为 $k'=k-1$ 的偏序集是好的，大小为 $k$ 的偏序集必然满足条件。
先随便取走一个没有入度的点，就变成了一个大小为 $k-1$ 的 DAG，设删除这个点后的最小链覆盖和最长反链大小均为为 $n$（根据假设它们相等），最小链覆盖的所有链分别为 $S_1,S_2\dots S_n$。
容易发现每条反链必然会在 $S_1,S_2\dots S_n$ 中各选一个元素，设 $A_i$ 为所有反链在 $S_i$ 中取到过的最大元素（因为每个 $S_i$ 两两可比所以肯定有个最大）。
那么考虑再把这个点加进去，显然至多使最小链划分的个数增加一，即 $n\le N,M\le n+1$。
然后再分这个新点的两种情况：
- 若这个新点和任意 $A_i$ 不可比，那么显然它会使最小链划分至少增加 $1$，即 $N\ge n+1$，所以 $N=n+1$。并且由于它和任意 $A_i$ 不可比，那选上所有 $A_i$ 和它就是一个新的最大反链覆盖，即 $M=n+1$
- 若这个新点大于某个 $A_i$（之前取出来的是没有入度的，不可能比某个小），那么显然 $N=n,M=n$。
两种情况 $M,N$ 均相等，证毕。