PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Eulerian poset (Definition)

A graded poset $ P$ is Eulerian if for any $ x\le y$ in $ P$, the Möbius function of the interval $ [x,y]$ is given by

$\displaystyle \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 $ M_3$ is not Eulerian, because it has 3 elements of rank 1 but only 2 elements of ranks 0 or 2.

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & \widehat{1}\ar@{-}[dl]\ar@{-}[... ... \ a\ar@{-}[dr] & b\ar@{-}[d] & c\ar@{-}[dl] \ & \widehat{0} & } } \end{xy}$
On the other hand, the Boolean lattice $ B_n$ is always Eulerian.
$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & \widehat{1}\ar@{-}[dl]\ar@{-}[... ... \ a\ar@{-}[dr] & b\ar@{-}[d] & c\ar@{-}[dl] \ & \widehat{0} & } } \end{xy}$
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,
$\displaystyle \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\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$.

Bibliography

1
Stanley, R., Enumerative Combinatorics, vol. 1, 2nd ed., Cambridge University Press, Cambridge, 1996.



Anyone with an account can edit this entry. Please help improve it!

"Eulerian poset" is owned by mps.
(view preamble)

View style:

See Also: graded poset
Log in to rate this entry.
(view current ratings)

Cross-references: disjoint union, plus, length, nodes, cycles, decomposition, graph, bipartite graph, interior, Hasse diagram, covers, atoms, isomorphism, implies, ab-index, chain, bounded poset, polytopes, face, posets, equation, binomial theorem, Möbius function, point, induction, isomorphic, Boolean lattice, odd, even, number, positive, strictly, finite, rank function, interval, graded poset
There are 2 references to this entry.

This is version 6 of Eulerian poset, born on 2004-02-07, modified 2007-06-16.
Object id is 5552, canonical name is EulerianPoset.
Accessed 2183 times total.

Classification:
AMS MSC: 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets)
 06A11 (Order, lattices, ordered algebraic structures :: Ordered sets :: Algebraic aspects of posets)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)