Eulerian poset

A graded poset $P$ is Eulerian if for any $x\le 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.

On the other hand, the Boolean lattice $B_n$ is always Eulerian.

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,\mathrm{\dots },n\}}\mu (\mathrm{\varnothing },S)$$ (*)

Thus ${\sum }_{S\subseteq \{1,\mathrm{\dots },n\}}{\mu }_{B_n}(\mathrm{\varnothing },S)=0$. We can apply the binomial theorem to $0$ to see that $0={(-1+1)}^n={\sum }_{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right){(-1)}^k$ and thus

${(-1)}^n$ $=-{\displaystyle \sum _{k=0}^{n-1}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){(-1)}^k$

$=-{\displaystyle \sum _{S\subset \{1,\mathrm{\dots },n\}}}\mu (\mathrm{\varnothing },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 , 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\ge 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\ge 2$.

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