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 O’Reilly online learning.

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