Lattice Representations of Order Ideals of Posets July 17, 2009
Posted by Martin Camacho in combinatorics.Tags: combinatorics, lattices, posets
trackback
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
Definition 2 A chain decomposition of a poset
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
-dimensional lattice
which satisfies the property that
iff there is an order ideal
.
It turns out that the number of paths in these lattices from 
“Thus ideals can be finitely generated by selecting a set of generators from {P}. We can represent these order ideals visually by drawing lattices.”
Are the generators here to be the maximal elements of the poset ideal?
In this case, yes, because after picking an initial set of elements we can only include smaller ones in our ideal.
So you need to assume
finite, no? Otherwise one could consider, say, 
, and have the ideal be the entire space.