Chapter 9Distributive Lattices

9.1 INTRODUCTION

Recall that a lattice c09-math-0001 is distributive if

9.1 equation

Distributive lattices form one of the most interesting class of lattices. Many lattices that arise in distributed computing and combinatorics are distributive. The set of all consistent global states in a distributed computation forms a distributive lattice. The set of all subsets of any set forms a distributive lattice under the subset relation.

In this chapter, we discuss some of the crucial properties of distributive lattices. Section 9.2 gives a characterization of distributive lattices using forbidden sublattices. In Section 9.4, we discuss a duality between finite distributive lattices and finite posets. Every finite distributive lattice can be recovered from the poset of its join-irreducible elements. This result due to Birkhoff,is known as the fundamental theorem of finite distributive lattices.

9.2 FORBIDDEN SUBLATTICES

Given a modular lattice, the following theorem is useful in determining if the lattice is distributive.

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.