English Version
Order theory
partial order
Partial orders are special binary relations that satisfy :
- a ≤ a (reflexivity) 自反性
- if a ≤ b and b ≤ a then a = b (antisymmetry) 非对称性
- if a ≤ b and b ≤ c then a ≤ c (transitivity). 传递性
partial ordered set
Defined as a set with a partial order.
Also called poset, and ordered set if the intended meaning is clear.
comparable
For some pair of elements $a,b$, if $a \le b\vee b\le a$ holds, then we say $a$ and $b$ are comparable. Otherwise they are incomparable.
connexity
(adj. connex)
If a relation is connex or satisfies the property of connexity, then it relates all pairs of elements in some way (or to say that every pair of elements are comparable).
i.e. $\forall x,y\in X$，either $x\le y$ or $y \le x$ is true, where $\le$ is the relation we defined with partial ordered set.
total order
A connex partial order is called a total order, a linear order or a chain.
Additionally, a subset of a poset in which no two elements are comparable is an anti-chain.
Dilworth’s theorem
statement
Dilworth’s theorem states that, in any finite partially ordered set, the largest anti-chain has the same size (where the size is defined as the number of elements in it) as the smallest chain decomposition (where the size is defined as the number of sets we have decomposited the elements into so that every set forms a chain).
Meanwhile, the width of a partially ordered set is defined as a size, that can be the size of some anti-chain and can also be that of some chain decomposition. And from the statements above, we know that the width of a given partially ordered set is unique.
proof
Here is the proof via Kőnig’s theorem.
For a partial ordered set $S$, construct a bipartite graph $G=(U,V,E)$, where $U=V=S$ and edge $(x,y)$ is in $E$ if $x \le y\wedge x\not=y$ holds (where $\le$ stands for the partial order).
Suppose that one of the maximum matching for $G$ is $M$, and $C$ is one of the smallest vertex cover that every vetex in $C$ has a neighbouring edge in $M$. And we know $|C|=|M|=m$ by Kőnig’s theorem.
Imagine we start from one vertex $x_V$ in $V$ with a neighbouring edge in $M$, then go to its matching vertex $y_U$, then start again from $y_U$’s corresponding vertex on the other side of the graph $y_V$, then to the vertex that matches $y_V$, and so on. Since no two elements in $S$ are the same, we will never return to $x_V$. That is to say, our path never forms a circle. And from the definition of matching we know that the indegree of every element we passed through (e.g. $x$) is at most $1$ and so is outdegree.
So a matching can refer to a set of disjoint paths (also chains by the definition above) , and when the size of the matching is growing, we add more edges to these paths, and the number of paths is decreasing.
This leads to a conclusion that the size of the smallest chain decomposition is equal to $|S|-m$。
On the other hand, we consider a set $A$ of elements in $S$ that do not correspond to any vertices in $C$. Then the size of $A$ is at least $|S|-m$, since there might be two vertices in $C$ from different side of $G$ and corresponding to the same element in $S$. And obviously, $|A|$ is an antichain. But $|A|$ can not be larger than $|S|-m$ since if $|A|$ is larger than the size of the smallest chain decomposition, at least two elements in $A$ will be in the same chain, which meets a contradiction.
中文版本
Order theory
partial order
偏序关系 (partial order) 定义为满足下列条件的二元关系：
- 自反性 (reflexivity)，即$a\le a$
- 非对称性 (antisymmetry)，即$a\le b \wedge b\le a \Rightarrow a=b$
- 传递性 (transitivity)，即$a\le b \wedge b\le c \Rightarrow a\le c$
partial ordered set
偏序集合 (partial ordered set) 定义为配备了偏序关系的集合；或一个二元组$(S,R)$，其中$R$是定义在$S$中的元素上的偏序关系。
comparable
对于某一对元素$a,b$，如果满足$a\le b \vee b\le a$（其中$\le$是一种偏序关系），那么称它们为可比较的 (comparable) ；否则称它们为不可比较的 (incomparable) 。
connexity
如果一个偏序关系满足任意一对元素都是可比较的，则称这个关系满足完全性条件 (connexity) 或者说这个关系是 完全的 (connex) 。
total order
全序关系 (total order) 即满足完全性的偏序关系。
满足全序关系的集合又叫做全序性集合、线性序集合、简单序集合或者链 (chain)。链也常用于描述偏序集合的满足完全性的子集。
此外，偏序集合的任意两个元素都不可比较的子集称为反链 (anti-chain) 。
Dilworth’s theorem
statement
定义一个偏序集合的链划分 (chain decomposition) 为一个由链组成的集合，满足任意两条链没有公共点，且集合中的链的并集为全集；定义其大小为集合中的链的条数。定义反链的大小为其中的元素数量。
Dilworth’s theorem 则是说，一个偏序集合的最小链划分与最长反链的大小相同。这个大小也被称为这个偏序集合的宽度 (width) 。
proof
下面的证明借助于Kőnig’s theorem（即二分图的最大匹配大小等于最小顶点覆盖）。
对于一个偏序集$S$，构造一个二分图$G=(U,V,E)$，使得$U=V=S$，而边$(x,y)$（从$U$的$x$连到$V$的$y$）存在，当且仅当$x\le y\wedge x\not=y$（$\le$代表偏序关系 ）。求出这个图的一个最大匹配$M$和一个最小顶点覆盖$C$，使得$C$中的任意一个点都有一条邻边在$M$中。令$m=|C|=|M|$。
想象现在从某个在$M$中的点$x_V$（表示$V$这一侧的点$x$）开始，走到它匹配的那个点$y_U$，然后到$y_U$所对应的另一侧的点$y_V$，接下来走到$y_V$所匹配的点……由于$S$中的元素互不相同，而偏序关系具有传递性，所以我们不会走回$x_U$，也就是说我们走过的点不成环。将我们走过的点在$S$中对应的元素拿出来：$x\to y\to \cdots $，恰好会对应一条链，因为匹配的定义保证了每个点的入度至多是$1$，每个点的出度也至多是$1$。
进一步地，一个匹配$M’$实际上对应了一个链划分，由于每往匹配中加一条边相当于合并了两条链，所以这个匹配对应的链划分的大小为$|S| - |M’|$。故而$S$的最小链划分的大小为$|S|-m$。
此外，考虑由$S$没有对应到$C$中的任何一个点的元素构成的集合，设为$A$。$A$显然是反链。那么$|A|\ge |S|-|C|=|S|-m$，因为可能会存在一个元素在$U,V$中对应的点都属于$C$。而从另一个角度考虑，$|A|\le |S|-m$，因为如果$|A|$大于了最小链划分的大小，则至少会有两个$A$中的元素属于最小链划分中的同一条链，与定义矛盾。故而我们有$|A|=|S|-m$。