jump to navigation

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

Posted by Martin Camacho in combinatorics.
Tags: , ,
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 ${P}$ is a set of elements ${I}$ such that if ${x\in I}$ and ${y\le x}$ then ${y\in I}$

Thus ideals can be finitely generated by selecting a set of generators from ${P}$. We can represent these order ideals visually by drawing lattices.

Definition 2 A chain decomposition of a poset ${P}$ is a partition of the elements of ${P}$ into sets ${C_i}$ such that the subposet ${C_i\subset P}$ is identical to a chain of size ${|C_i|}$.

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 ${\mathbf{C}=(C_1,C_2,\cdots, C_k)}$ of some poset ${P}$ is a ${k}$-dimensional lattice ${L\subset \mathbb{Z}^k}$ which satisfies the property that ${(x_1,x_2,\cdots,x_k)\in L}$ iff there is an order ideal ${I}$ of ${P}$ such that ${|I\cup C_i|=x_i}$.

It turns out that the number of paths in these lattices from ${\widehat{0}}$ to ${(|C_1|,|C_2|,\cdots,|C_k|)}$ in ${L}$ is equal to the number of linear extensions of ${P}$. This is an extremely useful tool for computing the number of linear extensions of a complex poset.

About these ads

## Comments»

1. Akhil Mathew - July 17, 2009

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

2. Martin Camacho - July 17, 2009

In this case, yes, because after picking an initial set of elements we can only include smaller ones in our ideal.

3. Akhil Mathew - July 17, 2009

So you need to assume $P$ finite, no? Otherwise one could consider, say, $\mathbb{N}$, and have the ideal be the entire space.

4. classy coin - June 29, 2013

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.