Introduction to Lattice Theory with Computer Science Applications

List of Figures
Nomenclature
Preface

1 Introduction
1.1 Introduction
1.2 Relations
1.3 Partial Orders
1.4 Join and Meet Operations
1.5 Operations on Posets
1.6 Ideals and Filters
1.7 Special Elements in Posets
1.8 Irreducible Elements
1.9 Dissector Elements
1.10 Applications: Distributed Computations
1.11 Applications: Combinatorics
1.12 Notation and Proof Format
1.13 Problems
1.14 Bibliographic Remarks

2 Representing Posets
2.1 Introduction
2.2 Labeling Elements of The Poset
2.3 Adjacency List Representation
2.4 Vector Clock Representation
2.5 Matrix Representation
2.6 Dimension-Based Representation
2.7 Algorithms to Compute Irreducibles
2.8 Infinite Posets
2.9 Problems
2.10 Bibliographic Remarks

3 Dilworth’s Theorem
3.1 Introduction
3.2 Dilworth’s Theorem
3.3 Appreciation of Dilworth’s Theorem
3.4 Dual of Dilworth’s Theorem
3.5 Generalizations of Dilworth’s Theorem
3.6 Algorithmic Perspective of Dilworth’s Theorem
3.7 Application: Hall’s Marriage Theorem
3.8 Application: Bipartite Matching
3.9 Online Decomposition of Posets
3.10 A Lower Bound on Online Chain Partition
3.11 Problems
3.12 Bibliographic Remarks

4 Merging Algorithms
4.1 Introduction
4.2 Algorithm to Merge Chains in Vector Clock Representation
4.3 An Upper Bound for Detecting an Antichain of Size K
4.4 A Lower Bound for Detecting an Antichain of Size K
4.5 An Incremental Algorithm for Optimal Chain Decomposition
4.6 Problems
4.7 Bibliographic Remarks

5 Lattices
5.1 Introduction
5.2 Sublattices
5.3 Lattices as Algebraic Structures
5.4 Bounding The Size of The Cover Relation of a Lattice
5.5 Join-Irreducible Elements Revisited
5.6 Problems
5.7 Bibliographic Remarks

6 Lattice Completion
6.1 Introduction
6.2 Complete Lattices
6.3 Closure Operators
6.4 Topped ∩-Structures
6.5 Dedekind–Macneille Completion
6.6 Structure of Dedekind--Macneille Completion of a Poset
6.7 An Incremental Algorithm for Lattice Completion
6.8 Breadth First Search Enumeration of Normal Cuts
6.9 Depth First Search Enumeration of Normal Cuts
6.10 Application: Finding the Meet and Join of Events
6.11 Application: Detecting Global Predicates in Distributed Systems
6.12 Application: Data Mining
6.13 Problems
6.14 Bibliographic Remarks

7 Morphisms
7.1 Introduction
7.2 Lattice Homomorphism
7.3 Lattice Isomorphism
7.4 Lattice Congruences
7.5 Quotient Lattice
7.6 Lattice Homomorphism and Congruence
7.7 Properties of Lattice Congruence Blocks
7.8 Application: Model Checking on Reduced Lattices
7.9 Problems
7.10 Bibliographic Remarks

8 Modular Lattices
8.1 Introduction
8.2 Modular Lattice
8.3 Characterization of Modular Lattices
8.4 Problems
8.5 Bibliographic Remarks

9 Distributive Lattices
9.1 Introduction
9.2 Forbidden Sublattices
9.3 Join-Prime Elements
9.4 Birkhoff’s Representation Theorem
9.5 Finitary Distributive Lattices
9.6 Problems
9.7 Bibliographic Remarks

10 Slicing
10.1 Introduction
10.2 Representing Finite Distributive Lattices
10.3 Predicates on Ideals
10.4 Application: Slicing Distributed Computations
10.5 Problems
10.6 Bibliographic Remarks

11 Applications of Slicing to Combinatorics
11.1 Introduction
11.2 Counting Ideals
11.3 Boolean Algebra and Set Families
11.4 Set Families of Size k
11.5 Integer Partitions
11.6 Permutations
11.7 Problems
11.8 Bibliographic Remark

12 Interval Orders
12.1 Introduction
12.2 Weak Order
12.3 Semiorder
12.4 Interval Order
12.5 Problems
12.6 Bibliographic Remarks

13 Tractable Posets
13.1 Introduction
13.2 Series–Parallel Posets
13.3 Two-Dimensional Posets
13.4 Counting Ideals of a Two-Dimensional Poset
13.5 Problems
13.6 Bibliographic Remarks

14 Enumeration Algorithms
14.1 Introduction
14.2 BFS Traversal
14.3 DFS Traversal
14.4 LEX Traversal
14.5 Uniflow Partition of Posets
14.6 Enumerating Tuples of Product Spaces
14.7 Enumerating All Subsets
14.8 Enumerating All Subsets of Size k
14.9 Enumerating Young’s Lattice
14.10 Enumerating Permutations
14.11 Lexical Enumeration of All Order Ideals of a Given Rank
14.12 Problems
14.13 Bibliographic Remarks

15 Lattice of Maximal Antichains
15.1 Introduction
15.2 Maximal Antichain Lattice
15.3 An Incremental Algorithm Based on Union Closure
15.4 An Incremental Algorithm Based on BFS
15.5 Traversal of the Lattice of Maximal Antichains
15.6 Application: Detecting Antichain-Consistent Predicates
15.7 Construction and Enumeration of Width Antichain Lattice
15.8 Lexical Enumeration of Closed Sets
15.9 Construction of Lattices Based on Union Closure
15.10 Problems
15.11 Bibliographic Remarks

16 Dimension Theory
16.1 Introduction
16.2 Chain Realizers
16.3 Standard Examples of Dimension Theory
16.4 Relationship Between the Dimension and the Width of a Poset
16.5 Removal Theorems for Dimension
16.6 Critical Pairs in the Pose
16.7 String Realizers
16.8 Rectangle Realizers
16.9 Order Decomposition Method and Its Applications
16.10 Problems
16.11 Bibliographic Remarks

17 Fixed Point Theory
17.1 Complete Partial Orders
17.2 Knaster–Tarski Theorem
17.3 Application: Defining Recursion Using Fixed Points
17.4 Problems
17.5 Bibliographic Remarks

Bibliography
Index