组合数学真是太棒了

偏序关系

关系：

集合$X$上的关系是$X$与$X$的笛卡尔积$X \times X$的子集$R$
即$X$的元素的有序对集合的一个子集
属于$X \times X$的有序对$(a,b)$记为$aRb$

$R$的一些概念:
自反$:\ \forall x \in X,\ xRx$
对称$:\ \forall x,y \in X,\ xRy \rightarrow yRx$
传递$:\ \forall x,y,z \in X,\ xRy,yRz \rightarrow xRz$

偏序$Partial order$：

偏序关系：自反，反对称且传递，符号$<$
严格偏序：反自反，反对称且传递，符号$\le$
偏序集：$(X,<)$
可比$:\ \forall x,y \in X,\ xRy \lor yRx=true$
全序$:\ $每一对元素都可比

链$chain:\ X$的一个子集，每一对元素都可比
反链$antichain:\ X$的一个子集，任意两个元素都不可比
偏序集的极小元集合和极大元集合都是反链
链与反链有对偶性；$A \bigcap C \le 1$

$Dilworth$定理：

$1.\ $最少反链个数等于最长链大小
$2.\ $最少链个数等于最长反链大小

证明：
只证明$1$,$2$太长了
设最长链长度$r$
首先反链个数不可能更少是显然的，因为最长链里每一个元素必须在不同的反链里；
现在证明可以划分成$r$个反链,通过不停的在$X$中删除最小元集合，后删除的集合中的每个元素一定比先删除的集合中的某个元素大，这样形成一条链。设一共删除$p$次，容易得到$p \le r \land p \ge r$，因此$p=r.$

[偏序关系与CDQ分治]【学习笔记】[更新中]

原文：http://www.cnblogs.com/candy99/p/6434997.html