# Chapter 9Distributive Lattices

## 9.1 INTRODUCTION

Recall that a lattice is distributive if

**9.1**

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

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