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.