Introduction to Lattice Theory with Computer Science Applications

Chapter 3Dilworth's Theorem

3.1 Introduction

Of all the results in lattice theory, perhaps the most famous is Dilworth's Theorem for decomposition of a poset. Dilworth's Theorem belongs to the special class of results, called min–max results, which relate a maximal value in a structure to a minimal value. Dilworth's Theorem states that the minimum number of chains a poset can be partitioned into equals the maximum size of an antichain. In this chapter, we cover this result and associated algorithms.

3.2 Dilworth's Theorem

We first present a proof of Dilworth's Theorem due to Galvin [Gal94].

Theorem 3.1

([Dil50]) [Dilworth's Theorem] Any finite poset of width can be decomposed into chains. Furthermore, chains are necessary for any such decomposition.

Proof:

We begin by proving that chains are necessary and that it is not possible to decompose the poset into less than chains. ...