**Dilworth’s Theorem.** If is a finite poset, then the maximum size of an antichain in equals the minimum number of chains needed to cover the elements of .

**Proof.** Induction on . We separate into two cases.

(a) Some maximum antichain omits both a maximal element and a minimal element of . Then neither or contains all of ; the maximality of implies . Both and has width because they contain , and they only intersect in . Apply induction hypothesis on both sets, we obtain chains covering and chains covering ; combining these chains form chains covering .

(b) Every maximum antichain of consists of all maximal elements or all minimal elements. Thus if is a minimal element and is a maximal element below . Apply induction hypothesis on gives us chains; add chain to get a covering of .

**Theorem.** Dilworth’s Theorem is equivalent to Konig-Egervary Theorem.

**Proof.** Dilworth to Konig-Egervary: View an -node bipartite graph as a bipartite poset. The nodes of one part are maximal elements, and nodes of the other part are minimal. Every covering of the poset of size uses chains of size 2, which is actually a matching. Each antichain of size corresponds to an independent set in , and the rest of nodes forms a vertex cover.

Konig-Egervary to Dilworth: Consider an arbitrary poset of size . Define a bipartite graph as follow: For each element , create two nodes and . The two parts of the graph are and . The edge set is .

Every matching in yields a chain-covering in as follow: We start we chain, each contains a unique element. If is in the matching then and are combined in the same chain. Therefore because each node in appears in at most on edge of the matching, a matching of edges forms a covering of chains.

Given a vertex cover in of size , define a corresponding antichain ; this is indeed an antichain because if there is a relation in then edge will be presented, and vertex cover needs to contain at least one of .

Claim. No minimal vertex cover of uses both , because by transitivity the sets and induce a complete bipartite subgraph in . A vertex cover of a complete bipartite graph must use all of one part. Since have all the neighbors in these two sets, we can remove one of that is not in the right part and decrease the size of the vertex cover.

Thus a minimum vertex cover of size yields an antichain of size .

### Like this:

Like Loading...

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.