# Eulerian poset

A graded poset $P$ is Eulerian if for any $x\leq y$ in $P$, the Möbius function (http://planetmath.org/MoebiusInversionFormula) of the interval $[x,y]$ is given by

 $\mu_{P}(x,y)=(-1)^{\rho(y)-\rho(x)},$

where $\rho$ is the rank function of $P$. If $P$ is finite and graded with strictly positive rank, then we can equivalently and more simply say that $P$ is Eulerian if and only if each nontrivial interval of $P$ has the same number of elements of even rank as odd rank.

For example, the lattice (http://planetmath.org/Lattice) $M_{3}$ is not Eulerian, because it has 3 elements of rank 1 but only 2 elements of ranks 0 or 2.

 $\xymatrix{&\widehat{1}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&\\ a\ar@{-}[dr]&b\ar@{-}[d]&c\ar@{-}[dl]\\ &\widehat{0}&}$

On the other hand, the Boolean lattice $B_{n}$ is always Eulerian.

 $\xymatrix{&\widehat{1}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&\\ ab\ar@{-}[d]\ar@{-}[dr]&ac\ar@{-}[dl]\ar@{-}[dr]&bc\ar@{-}[dl]\ar@{-}[d]\\ a\ar@{-}[dr]&b\ar@{-}[d]&c\ar@{-}[dl]\\ &\widehat{0}&}$

Each interval of $B_{n}$ is isomorphic to a smaller Boolean lattice, so we can give a proof by induction that $B_{n}$ is Eulerian. Now $B_{0}$ is a single point and so there is only one interval, which has Möbius function 1. So to show that $B_{n}$ is Eulerian, we just need to show that the Möbius function of $B_{n}$ is $(-1)^{n}$. Recall that by definition,

 $\mu_{B_{n}}(B_{n})=-\sum_{S\subset\{1,\dots,n\}}\mu(\emptyset,S){}$ (*)

Thus $\sum_{S\subseteq\{1,\dots,n\}}\mu_{B_{n}}(\emptyset,S)=0$. We can apply the binomial theorem to $0$ to see that $0=(-1+1)^{n}=\sum_{k=0}^{n}\binom{n}{k}(-1)^{k}$ and thus

 $\displaystyle(-1)^{n}$ $\displaystyle=-\sum_{k=0}^{n-1}\binom{n}{k}(-1)^{k}$ $\displaystyle=-\sum_{S\subset\{1,\dots,n\}}\mu(\emptyset,S){}$ (**)

It then follows from Equation $(*)$ and Equation $(**)$ that $\mu(B_{n})=(-1)^{n}$.

Eulerian posets are generalizations of certain special posets, such as face lattices of polytopes.

## Eulerian posets of small rank

In this section we classify bounded Eulerian posets of rank less than 4.

For $n<2$, there is exactly one bounded poset of rank $n$, the chain, and it is Eulerian.

A bounded poset of rank $2$ is determined precisely by its number of coatoms. The ab-index of a rank $2$ bounded Eulerian poset with $r$ coatoms is $a+(r-1)b$, which is a cd-index if and only if $r=2$. Since every Eulerian poset has a cd-index, this implies that every rank $2$ bounded Eulerian poset has exactly two coatoms. Thus up to isomorphism $B_{2}$ is the only rank $2$ bounded Eulerian poset.

Let $P$ be a rank $3$ bounded Eulerian poset. Since $P$ has as many elements of odd rank as even rank, it has exactly the same number of atoms as coatoms. Since every rank $2$ interval in $P$ is a copy of $B_{2}$, it follows that $P$ is not a chain and so has $n\geq 2$ 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 $P$ 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 $P$ consisting of the points on a cycle of length $2k$ plus the minimum and maximum elements of $P$ is the face poset of a $k$-gon. Hence $P$ itself is the face poset of the disjoint union of one or more $k$-gons for various $k\geq 2$.

## References

Title Eulerian poset EulerianPoset 2013-03-22 14:08:16 2013-03-22 14:08:16 mps (409) mps (409) 9 mps (409) Definition msc 06A11 msc 06A07 GradedPoset