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 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 c16-math-0001 elements and dimension c16-math-0002 can be represented using c16-math-0003-dimensional vectors of coordinates from c16-math-0004. In Section 16.7 ...

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