O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required