4.2. Dilworth's theorem for partial ordered sets
A partial order on a set is a transitive and irreflexive relation defined on some
ordered pairs of elements.
(Let we remind the
readaer that a realation is transitive if and
, and is irreflexive if either
or
holds but not both.)
The relation expresses the fact that either
or else
.
A set with a partial order on it is a partial ordered set (poset).
A subset of of a poset P is totally ordered or is a chain if there is some
permutation
of the
subscripts
such that
.
Any two elements and
are called
comparable if they belong to some chain and are incomparable
otherwise.
Any set of pairwise incomparable elements is called an antichain.
A collection of chains (antichains) is called a chain
(antichain) partition of P if the
s are
mutually disjoint and their union is P.
Fact. Any partially ordered set can be represented as a union of disjoint
chains: we consider the one-element chains which is a
trivial partition.
What is the the smallest cardinality chain partition?
The cardinality of an antichain cannot exceed .
What is the largest cardinality of an antichain in P?
Since no two elements
of an antichain can belong to the same chain, we need at least as many chains
as the minimal size of an antichain.
Theorem 4.4. (Dilworth's theorem): In any finite poset the cardinality of any largest antichain equals to the cardinality of any smallest chain partition.
Proof.
What is the connection between the Dilworth's Theorem and the König's Theorem?
The two theorems are equivalent to each other.
We will prove the Dilwort'h Theorem assuming König's Theorem to true. (The converse is housework.)
Let be a poset.
Build a bipartite graph
where
and
and
iff
.
We need two lemmas.
Lemma 4.5.
Let M be a set of independent edges in G. Then there is a
chain partition P of P such that .
Proof.
Suppose .
So and among the distinct elements of these
's we have a set
of chains each
of length at least two and they are pairwise disjoint since M is
independet.
We extend to a chain partition P of P
in a trivial way: we append all one-element chains not already presented in
.
Now let the number of
elements in the jth chain of P . We then have:
since there are precisely edges in the jth chain of P .
Lemma 4.6. If is a minimum
vertex cover of the bipartite graph
of poset P,
then there is an antichain U contained in P with
.
Proof.
Let be a minimum
vertex cover of G.
corresponds
to a subset
of P
with
.
Let .
Then the elements of U are pairwise unrelated in P
since is a cover in G.
So, by construction
Now, we are prepared to prove Dilworth's Theorem:
Let P be any poset and , the bipartite graph correspond-ing to P. Let
-
be a maximum independent set of edges in G and
-
, a minimum cardinality vertex covering of G.
By Lemma 4.5 there is a chain
partition P such that .
By Lemma
4.6 there is an antichain with
.
By the
König's Theorem and so
.
On the other hand, for any arbitrary chain partition of P and any arbitrary antichain
of P, we
must have
since no two elements of can lie in the same chain of
.
From and
we get that
and hence it follows that P is a minimum chain partition of P, and
U is a maximum antichain.