Lattice Representations of Order Ideals of Posets July 17, 2009Posted by Martin Camacho in combinatorics.
Tags: combinatorics, lattices, posets
In this post I’ll talk about the representation of order ideals of posets as distributive lattices. You can get a very good description of posets from Stanley’s Enumerative Combinatorics, Vol 1.
First, a couple definitions:
Definition 1 An order ideal of a poset is a set of elements such that if and then
Thus ideals can be finitely generated by selecting a set of generators from . We can represent these order ideals visually by drawing lattices.
Definition 2 A chain decomposition of a poset is a partition of the elements of into sets such that the subposet is identical to a chain of size .
These chain decomopositions actually end up in a 1-1 correspondence with distributive lattices of posets:
Definition 3 A distributive lattice representation of a chain decomposition of some poset is a -dimensional lattice which satisfies the property that iff there is an order ideal of such that .
It turns out that the number of paths in these lattices from to in is equal to the number of linear extensions of . This is an extremely useful tool for computing the number of linear extensions of a complex poset.