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].

Get Introduction to Lattice Theory with Computer Science Applications now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.