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.
$$\text{xymatrix}\mathrm{\&}\widehat{1}\text{ar}\mathrm{@}-[dl]\text{ar}\mathrm{@}-[d]\text{ar}\mathrm{@}-[dr]\mathrm{\&}a\text{ar}\mathrm{@}-[dr]\mathrm{\&}b\text{ar}\mathrm{@}-[d]\mathrm{\&}c\text{ar}\mathrm{@}-[dl]\mathrm{\&}\widehat{0}\mathrm{\&}$$ |
On the other hand, the Boolean lattice ${B}_{n}$ is always Eulerian.
$$\text{xymatrix}\mathrm{\&}\widehat{1}\text{ar}\mathrm{@}-[dl]\text{ar}\mathrm{@}-[d]\text{ar}\mathrm{@}-[dr]\mathrm{\&}ab\text{ar}\mathrm{@}-[d]\text{ar}\mathrm{@}-[dr]\mathrm{\&}ac\text{ar}\mathrm{@}-[dl]\text{ar}\mathrm{@}-[dr]\mathrm{\&}bc\text{ar}\mathrm{@}-[dl]\text{ar}\mathrm{@}-[d]a\text{ar}\mathrm{@}-[dr]\mathrm{\&}b\text{ar}\mathrm{@}-[d]\mathrm{\&}c\text{ar}\mathrm{@}-[dl]\mathrm{\&}\widehat{0}\mathrm{\&}$$ |
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
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$.
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 |