Introduction to Lattice Theory with Computer Science Applications

Chapter 16Dimension Theory

16.1 Introduction

The notion of dimension of a poset was introduced in a seminal paper by Dushnik and Miller [DM41]. The dimension of a poset, roughly speaking, is the dimension of the Euclidean space in which the poset can be embedded. The dimension of a poset reveals important information about the poset. For example, many problems that are algorithmically hard for general posets, such as counting the number of ideals, are easy for posets of dimension less than or equal to two. As we saw in Chapter 2, the concept of dimension also lets us represent the order relation of a poset in an implicit manner. The dimension theory of ordered sets has been an active area of research and the reader will find a good survey of results in the book by Trotter [Tro92]. In this chapter, we cover only the most basic results and their applications.

We begin with the classical dimension theory based on notion of chain realizers. A chain realizer shows how a poset with elements and dimension can be represented using -dimensional vectors of coordinates from . In Section 16.7 ...