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

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