Eulerian poset
A graded poset is Eulerian if for any in , the Möbius function (http://planetmath.org/MoebiusInversionFormula) of the interval is given by
where is the rank function of . If is finite and graded with strictly positive rank, then we can equivalently and more simply say that is Eulerian if and only if each nontrivial interval of has the same number of elements of even rank as odd rank.
For example, the lattice (http://planetmath.org/Lattice) is not Eulerian, because it
has 3 elements of rank 1 but only 2 elements of ranks 0 or 2.
On the other hand, the Boolean lattice is always Eulerian.
Each interval of is isomorphic to a smaller Boolean lattice, so
we can give a proof by induction that is Eulerian. Now is
a single point and so there is only one interval, which has Möbius
function 1. So to show that is Eulerian, we just need to show
that the Möbius function of is . Recall that by definition,
(*) |
Thus . We can apply
the binomial theorem to to see that
and thus
(**) |
It then follows from Equation and Equation that .
Eulerian posets are generalizations of certain special posets, such as
face lattices of polytopes.
Eulerian posets of small rank
For , there is exactly one bounded poset of rank , the chain, and it is Eulerian.
A bounded poset of rank is determined precisely by its number of
coatoms. The ab-index of a rank bounded Eulerian poset with
coatoms is , which is a cd-index if and only if .
Since every Eulerian poset has a cd-index, this implies that every
rank bounded Eulerian poset has exactly two coatoms. Thus up to
isomorphism is the only rank bounded Eulerian poset.
Let be a rank bounded Eulerian poset. Since has as many
elements of odd rank as even rank, it has exactly the same number of
atoms as coatoms. Since every rank interval in is a copy of
, it follows that is not a chain and so has atoms.
Moreover, every atom is covered by exactly two coatoms, and every
coatom covers exactly two atoms. That is, the Hasse diagram of the
interior of is a 2-regular bipartite graph
. This graph admits a
decomposition into even cycles. In each cycle, half of the nodes are
atoms and half are coatoms. The non-induced subposet of
consisting of the points on a cycle of length plus the minimum
and maximum elements of is the face poset of a -gon. Hence
itself is the face poset of the disjoint union
of one or more -gons
for various .
References
- 1 Stanley, R., Enumerative Combinatorics, vol. 1, 2nd ed., Cambridge University Press, Cambridge, 1996.
Title | Eulerian poset |
---|---|
Canonical name | EulerianPoset |
Date of creation | 2013-03-22 14:08:16 |
Last modified on | 2013-03-22 14:08:16 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 9 |
Author | mps (409) |
Entry type | Definition |
Classification | msc 06A11 |
Classification | msc 06A07 |
Related topic | GradedPoset |