Posets and lattices · Definition

Lattice or order theory

enumerative combinatoricsposets and lattices

Before you start you need to know

Lattices generalize the notions of union and intersection of sets to any order relation. They appear in enumerative combinatorics when studying the inclusion order on partitions and on subspaces.

Definition

A lattice is a partially ordered set (L, ≤) in which every pair of elements x and y has a supremum (x ∨ y) and an infimum (x ∧ y).

\[x \vee y = \sup\{x,y\}, \quad x \wedge y = \inf\{x,y\}\]

If \(L\) is a lattice, the operations \(\vee\) and \(\wedge\) are commutative and associative and satisfy the absorption laws \(x \wedge (x \vee y) = x\) and \(x \vee (x \wedge y) = x\). Moreover, a finite poset with a least element \(\hat{0}\) and a greatest element \(\hat{1}\) is a lattice if and only if every pair has a supremum and an infimum, so it suffices to check existence for pairs.

Consider the poset of divisors of 12 ordered by divisibility. The supremum of 4 and 6 is 12 and the infimum is 2, since 2 is the greatest common divisor of both. This set is therefore a lattice in which \(x \vee y = \operatorname{lcm}(x,y)\) and \(x \wedge y = \gcd(x,y)\).

A common mistake is to claim that every poset with a least and greatest element is a lattice. For example, in the poset \(\hat{0} < a, b < c, d < \hat{1}\), the elements \(a\) and \(b\) have two incomparable minimal upper bounds, \(c\) and \(d\), so they have no supremum and the poset is not a lattice.

Think about it

Why is having a least and a greatest element not enough for a poset to be a lattice?

Because two elements may have several incomparable minimal upper (or maximal lower) bounds, so no unique supremum (or infimum) exists.

Exercises 10

  1. What is the supremum of 4 and 6 in the poset of divisors of 12 ordered by divisibility?
  2. In the poset of divisors of 12 ordered by divisibility, what is \(4 \wedge (4 \vee 6)\)?
  3. In a lattice, what name is given to the operation x ∨ y?
  4. In the poset of subsets of \(\{1,2,3\}\) ordered by inclusion, what is \(\{1,2\} \vee \{2,3\}\)?
  5. What is the supremum of 2 and 3 in the poset of divisors of 6 ordered by divisibility?
  6. In the poset of divisors of 30 ordered by divisibility, compute \(6 \wedge 10\).
  7. In the poset of divisors of 60 ordered by divisibility, compute \(10 \vee 15\).
  8. In the poset \(L=\{\hat{0},a,b,c,\hat{1}\}\) with \(\hat{0}<a,b<c<\hat{1}\), what is \(a \wedge b\)?
  9. Let \(L\) be the poset with elements \(\hat{0}\), \(a\), \(b\), \(c\), \(\hat{1}\) and \(\hat{0} < a, b < c < \hat{1}\) (no relation between \(a\) and \(b\) beyond those stated). How many pairs of elements of \(L\) have no supremum?
  10. How many divisors of 360 have a pair with 12 whose infimum is 4?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.