💁🏽Algebraic Combinatorics Unit 7 – Partially Ordered Sets & Lattices

Key Concepts and Definitions

• Partially ordered sets (posets) consist of a set together with a binary relation that is reflexive, antisymmetric, and transitive
• The binary relation in a poset is often denoted as $\leq$ and read as "less than or equal to" or "precedes"
• Two elements $a$ and $b$ in a poset are comparable if either $a \leq b$ or $b \leq a$; otherwise, they are incomparable
• A total order is a poset in which every pair of elements is comparable (linear order)
• A strict partial order is irreflexive and transitive, often denoted as $<$
  • Strict partial orders can be obtained from partial orders by removing reflexivity
• An antichain is a subset of a poset in which no two elements are comparable
• A chain is a totally ordered subset of a poset (linearly ordered set)

Fundamental Properties of Posets

• Reflexivity: For all $a$ in the poset, $a \leq a$
• Antisymmetry: If $a \leq b$ and $b \leq a$, then $a = b$
• Transitivity: If $a \leq b$ and $b \leq c$, then $a \leq c$
• Hasse diagrams visually represent posets by drawing elements as vertices and relations as edges, omitting edges implied by transitivity
• The height of a poset is the maximum length of a chain in the poset
• The width of a poset is the maximum size of an antichain in the poset
• A poset is bounded if it has a unique minimal element (bottom) and a unique maximal element (top)

Types of Partially Ordered Sets

• A lattice is a poset in which every pair of elements has a least upper bound (join) and a greatest lower bound (meet)
• A complete lattice is a lattice in which every subset has a least upper bound and a greatest lower bound
• A modular lattice satisfies the modular law: if $a \leq b$, then $(a \vee c) \wedge b = a \vee (c \wedge b)$
• A distributive lattice satisfies the distributive laws: $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ and $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
  • Every distributive lattice is modular, but not every modular lattice is distributive
• A Boolean lattice is a distributive lattice with a complement for each element (power set of a set ordered by inclusion)
• A well-ordered set is a total order in which every non-empty subset has a least element (natural numbers)

Lattice Theory Basics

• A lattice can be defined algebraically as a set with two binary operations, meet $(\wedge)$ and join $(\vee)$, satisfying the lattice axioms
• The meet $(\wedge)$ of two elements is their greatest lower bound, and the join $(\vee)$ is their least upper bound
• Lattice axioms include commutativity, associativity, idempotence, and absorption laws for meet and join
• A sublattice is a subset of a lattice that is closed under meet and join operations
• A lattice homomorphism is a function between lattices that preserves meet and join operations
• The direct product of two lattices $(L_1, \wedge_1, \vee_1)$ and $(L_2, \wedge_2, \vee_2)$ is a lattice on the Cartesian product $L_1 \times L_2$ with operations defined componentwise

Special Elements in Lattices

• The top element $(\top)$ of a lattice is the unique element that is greater than or equal to all other elements
• The bottom element $(\bot)$ of a lattice is the unique element that is less than or equal to all other elements
• An atom is an element that covers the bottom element (directly above $\bot$ in the Hasse diagram)
• A coatom is an element that is covered by the top element (directly below $\top$ in the Hasse diagram)
• A join-irreducible element cannot be expressed as the join of two other elements
• A meet-irreducible element cannot be expressed as the meet of two other elements
• A complement of an element $a$ is an element $b$ such that $a \wedge b = \bot$ and $a \vee b = \top$

Lattice Operations and Identities

• The meet $(\wedge)$ and join $(\vee)$ operations in a lattice are idempotent, commutative, and associative
• Absorption laws: $a \wedge (a \vee b) = a$ and $a \vee (a \wedge b) = a$
• Duality principle: Every identity in a lattice has a dual identity obtained by exchanging meet and join operations and reversing the order
• In a distributive lattice, the meet and join operations distribute over each other
  • $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
  • $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
• De Morgan's laws for lattices: $(a \wedge b)^* = a^* \vee b^*$ and $(a \vee b)^* = a^* \wedge b^*$, where $^*$ denotes the complement operation

Applications in Combinatorics

• The power set of a set, ordered by inclusion, forms a Boolean lattice (hypercube)
• The divisor lattice of a positive integer $n$ consists of all divisors of $n$ ordered by divisibility
• The partition lattice of a set consists of all partitions of the set ordered by refinement
• The subgroup lattice of a group consists of all subgroups ordered by inclusion
• Möbius inversion formula relates the sum of a function over a poset to the sum of another function over the same poset
• The Dedekind number counts the number of monotone Boolean functions or the number of antichains in the power set lattice
• Sperner's theorem bounds the size of a maximum antichain in the Boolean lattice (power set of an $n$-element set)

Advanced Topics and Extensions

• Birkhoff's representation theorem states that every finite distributive lattice is isomorphic to the lattice of down-sets of a finite poset
• Infinite lattices and complete lattices extend lattice theory to infinite structures
• Semilattices are partially ordered sets with only a meet operation (meet-semilattice) or only a join operation (join-semilattice)
• Heyting algebras and Boolean algebras are special types of lattices with additional properties and operations
• Lattice polynomials are expressions built from variables and lattice operations, used to study identities and varieties of lattices
• Lattice congruences are equivalence relations on a lattice that are compatible with meet and join operations
• Modular and distributive lattices can be characterized by the absence of certain forbidden sublattices ($N_5$ and $M_3$)
• Free lattices are lattices generated by a set of elements without any additional relations