##
Lattice Representations of Order Ideals of Posets *July 17, 2009*

*Posted by Martin Camacho in combinatorics.*

Tags: combinatorics, lattices, posets

trackback

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 1Anorder idealof 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 2Achain decompositionof 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 3Adistributive lattice representationof 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.

“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.

The opposite classy coin players’ looseness combined with fewer quantity of enemy will assist you to participate in more arms, however it is still ideal to keep your own VPIP below 25. Which, folks, is surely an astonishing 93% as well as I’m able to

dwell using those people amounts every time in the year.