40.02.03 · combinatorics / posets-lattices

Eulerian Posets, Face Lattices, and the Characteristic Polynomial

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.14-3.17 and Notes (Eulerian posets, the cd-index, the characteristic polynomial of a graded/geometric lattice, Whitney's theorem, the relation to the chromatic polynomial and to hyperplane arrangements); Stanley 1994 *Discrete Comput. Geom.* 'A survey of Eulerian posets' for the cd-index and Dehn-Sommerville; Zaslavsky 1975 *Memoirs AMS* 154 ('Facing up to arrangements') for the region-counting theorem; Bjorner-Wachs-Welker for shellability and Cohen-Macaulay posets

Intuition Beginner

A solid shape like a cube is built from pieces of different dimensions stacked together: corners, edges, and flat sides. A cube has $8$ corners, $12$ edges, and $6$ faces. If you add these with alternating plus and minus signs in dimension order — corners minus edges plus faces — you get $8 - 12 + 6 = 2$ , every single time, for any shape with no holes. That stubborn answer of $2$ is one of the oldest patterns in mathematics, and this unit is about the ordered structure that explains why it appears and what else it forces.

The trick is to stop looking at the shape and look instead at how its pieces nest. A corner sits inside the edges that end at it; an edge sits inside the faces that border it. "Sits inside" is a sense of below and above, so the pieces of a shape form a partial order, met in the previous units. Add a bottom item below everything (the empty piece) and a top item above everything (the whole solid), and you get the face lattice of the shape. Reading the alternating count off this lattice is what makes the $2$ inevitable.

The lattices that behave this perfectly have a name. In each of them the plus-minus weights you met as the Möbius function take the cleanest possible form: the weight between two nested pieces is just $+ 1$ or $- 1$ , decided only by how many dimensions apart they are. A lattice with this property is called Eulerian, after the man who first noticed the alternating count. The most familiar Eulerian lattice is the collection of all subsets of a set, the same Boolean lattice you have already met.

What you carry forward: once a lattice is Eulerian, its piece-counts cannot be arbitrary. They obey a hidden mirror symmetry, and one compact gadget records all of them at once. The face counts of every polytope are governed by this single structural fact.

Visual Beginner

The face lattice stacks a shape's pieces by dimension, with the empty piece at the bottom and the whole solid at the top. Below is the face lattice of a square (a $2$ -dimensional polytope), and the alternating count that always lands on $0$ for the proper pieces.

   Face lattice of a square (corners P,Q,R,S; edges a,b,c,d)

                       SQUARE            rank 3  (the whole 2-cell)
                    /  |     |  \
                  a    b     c    d      rank 2  (the 4 edges)
                / | \ / \   / \ / | \
               P  |  Q   \ /   R  |  S   rank 1  (the 4 corners)
                \ |   \   X   /   | /
                 \|    \ / \ /    |/
                  +-----EMPTY-----+       rank 0  (the empty face)

   counting the proper pieces by dimension:
     corners  -  edges  +              = 4 - 4 = 0
   (Euler relation: the signed count of proper faces is 0 here)

Read it from the bottom. The empty piece sits below everything. Above it are the four corners, then the four edges, then the square itself. A corner is joined upward only to the two edges meeting at it; each edge is joined up to the square.

Now count the proper pieces — everything except the empty piece and the whole square — with alternating signs by dimension: $4$ corners minus $4$ edges $= 0$ . For a solid like the cube the same alternating rule over all proper faces gives $8 - 12 + 6 = 2$ once the bottom and top are restored to the sum.

shape	corners	edges	faces	corners − edges + faces
triangle	$3$	$3$	$1$	$3 - 3 + 1 = 1$
square	$4$	$4$	$1$	$4 - 4 + 1 = 1$
cube	$8$	$12$	$6$	$8 - 12 + 6 = 2$

Worked example Beginner

We check the alternating-sign rule on a triangle and watch the Möbius weights come out as $+ 1$ and $- 1$ only. A triangle has $3$ corners, $3$ edges, and $1$ inside face. We build its face lattice and verify the clean weights by hand.

Step 1. List the pieces by dimension. Bottom: the empty piece. Dimension $0$ : corners $P, Q, R$ . Dimension $1$ : edges $a$ (between $Q, R$ ), $b$ (between $P, R$ ), $c$ (between $P, Q$ ). Dimension $2$ : the whole triangle $T$ . Top and bottom included, that is $3 + 3 + 1 + 1 + 1 = 9$ items in the lattice... but corners, edges, the triangle, plus empty give $3 + 3 + 1 + 1 = 8$ .

Step 2. Weight from the empty piece up to each corner. Each corner covers only the empty piece, so its Möbius weight from the bottom is $- 1$ , the same value a one-step cover always gets.

Step 3. Weight from the empty piece up to an edge. Below edge $a$ sit the empty piece (weight $+ 1$ ) and the two corners $Q, R$ (weights $- 1$ each). The weights below an item must cancel to zero, so the edge's weight is $- (+ 1 - 1 - 1) = + 1$ .

Step 4. Weight from the empty piece up to the whole triangle. Below $T$ sit the empty piece ( $+ 1$ ), three corners ( $- 1$ each), three edges ( $+ 1$ each), summing to $+ 1 - 3 + 3 = + 1$ , so $T$ 's weight is $- (+ 1) = - 1$ .

Step 5. Read the dimensions. The corners are one rank up and got $- 1$ ; the edges are two ranks up and got $+ 1$ ; the triangle is three ranks up and got $- 1$ . The weight is $+ 1$ or $- 1$ exactly by whether the rank gap is even or odd.

What this tells us: in the face lattice the Möbius weight between two pieces is $(- 1)$ raised to their dimension gap, never anything bigger. That clean alternation is the defining mark of an Eulerian lattice, and the next sections turn it into the mirror symmetry of face counts.

Check your understanding Beginner

Formal definition Intermediate+

Let $P$ be a finite graded (ranked) poset with least element $\hat{0}$ and greatest element $\hat{1}$ : there is a rank function $r : P \to {0, 1, \dots, n}$ with $r (\hat{0}) = 0$ , $r (\hat{1}) = n$ , and $r (y) = r (x) + 1$ whenever $y$ covers $x$ . The integer $n = r (\hat{1})$ is the rank of $P$ . Every maximal chain has the same length $n$ . The interval $[x, y]$ is itself graded of rank $r (y) - r (x)$ ^{[Stanley §3.14]}.

$P$ is Eulerian if for every $x \leq y$ the Möbius function of 40.02.02 takes the value $$ \mu(x,y) = (-1)^{r(y) - r(x)}. $$ Equivalently, applying the defining recursion $\sum_{x \leq z \leq y} μ (x, z) = 0$ , every interval $[x, y]$ of positive length satisfies the Euler relation $$ \sum_{x \le z \le y} (-1)^{r(z)} = 0 . $$ The Boolean lattice $B_{n}$ is Eulerian: $μ_{B_{n}} (S, T) = (- 1)^{∣ T ∖ S ∣} = (- 1)^{r (T) - r (S)}$ . The face lattice $F (P)$ of a convex polytope $P$ — its faces (including the empty face $\hat{0}$ and $P$ itself as $\hat{1}$ ) ordered by inclusion, graded by $r (F) = dim F + 1$ — is Eulerian; this is the lattice-theoretic content of the Euler-Poincaré relation.

For a graded poset of rank $n$ and a subset $S = {s_{1} < \dots < s_{k}} \subseteq {1, \dots, n - 1}$ of ranks, the flag $f$ -vector is $$ \alpha_P(S) = #{, \hat 0 < x_1 < \cdots < x_k < \hat 1 : r(x_i) = s_i ,}, $$ the number of chains hitting exactly the ranks in $S$ . The flag $h$ -vector is its Möbius transform $β_{P} (S) = \sum_{T \subseteq S} (- 1)^{∣ S ∖ T ∣} α_{P} (T)$ , so that $α_{P} (S) = \sum_{T \subseteq S} β_{P} (T)$ by inclusion-exclusion. For the $f$ -vector $(f_{- 1}, f_{0}, \dots, f_{n - 1})$ with $f_{i - 1} =$ the number of rank- $i$ elements, the $h$ -vector $(h_{0}, \dots, h_{n})$ is defined by $\sum_{i = 0}^{n} f_{i - 1} (t - 1)^{n - i} = \sum_{i = 0}^{n} h_{i} t^{n - i}$ .

For a graded poset with $\hat{0}$ and rank function $r$ , rank $n$ , the characteristic polynomial is $$ \chi(P, t) = \sum_{x \in P} \mu(\hat 0, x), t^{, n - r(x)} \in \mathbb{Z}[t]. $$ The zeta polynomial $Z (P, m)$ counts multichains $\hat{0} = x_{0} \leq x_{1} \leq \dots \leq x_{m - 1} = \hat{1}$ of length $m$ and is a polynomial in $m$ of degree $n$ .

Counterexamples to common slips Intermediate+

"Eulerian just means the Euler relation $f_{0} - f_{1} + \dots =$ const holds for the whole poset." It must hold in every interval, not only the top one. A poset can satisfy the global alternating relation while some interval fails it; such a poset is not Eulerian and its $μ$ is not a pure sign. The interval condition is what forces $μ (x, y) = (- 1)^{r (y) - r (x)}$ throughout.
"Every graded lattice is Eulerian." The partition lattice $Π_{n}$ is graded but has $μ (\hat{0}, \hat{1}) = (- 1)^{n - 1} (n - 1)!$ , which is not a sign for $n \geq 4$ . Eulerianness is the special palindromic regime; most geometric lattices are not in it.
"The $h$ -vector of a graded poset is always nonnegative." Nonnegativity of the $h$ -vector is a property of shellable / Cohen-Macaulay complexes, not of grading alone. A graded poset whose order complex is not Cohen-Macaulay can have negative $h_{i}$ . Eulerianness gives symmetry $h_{i} = h_{n - i}$ , not nonnegativity.
"The characteristic polynomial and the zeta polynomial are the same data." They are different transforms: $Z (P, m)$ counts multichains and has nonnegative integer values at positive integers; $χ (P, t)$ is a signed Möbius sum whose evaluations count regions (Zaslavsky) or proper colourings (chromatic). They coincide only after specific substitutions that are not the identity.

Key theorem with proof Intermediate+

The signature theorem is that Eulerianness forces the flag $h$ -vector to be symmetric — the Dehn-Sommerville relations. This is the precise sense in which a polytope's face counts are not free but obey a mirror law, and it is the abstract content of the alternating $\pm 1$ seen at Beginner tier.

Theorem (Dehn-Sommerville relations). Let $P$ be an Eulerian poset of rank $n$ . For every $S \subseteq {1, \dots, n - 1}$ , $$ \beta_P(S) = \beta_P(\bar S), \qquad \bar S = {1, \dots, n-1} \setminus S . $$ Equivalently, for a simplicial polytope with $h$ -vector $(h_{0}, \dots, h_{n})$ one has $h_{i} = h_{n - i}$ for all $i$ .

Proof. Work in the incidence algebra of 40.02.02. The flag $f$ -vector and flag $h$ -vector are linked by $α_{P} (S) = \sum_{T \subseteq S} β_{P} (T)$ , a Möbius inversion over the Boolean lattice of rank sets. The claim $β_{P} (S) = β_{P} (\overset{ˉ}{S})$ is therefore a linear identity among the $α_{P} (T)$ ; we derive it from the Eulerian condition applied rank-by-rank.

Fix $S = {s_{1} < \dots < s_{k}}$ and insert one extra rank. For consecutive ranks $s_{j} < s_{j + 1}$ of $S$ (with $s_{0} = 0$ , $s_{k + 1} = n$ as boundary), count chains in $S$ refined by an element of intermediate rank. A chain through ranks $S$ has, between its rank- $s_{j}$ element $x$ and rank- $s_{j + 1}$ element $y$ , the interval $[x, y]$ , which is Eulerian of rank $s_{j + 1} - s_{j}$ . Summing $α$ over insertions of one rank $ρ$ with $s_{j} < ρ < s_{j + 1}$ counts, for each such $[x, y]$ , the elements of rank $ρ - s_{j}$ inside it; the alternating sum over $ρ$ of these counts is governed by the Euler relation $\sum_{x \leq z \leq y} (- 1)^{r (z)} = 0$ in $[x, y]$ .

Concretely, for each fixed $S$ and each gap, the generalised Dehn-Sommerville equation of Bayer-Billera reads $$ \sum_{\rho = s_j + 1}^{s_{j+1} - 1} (-1)^{\rho - s_j - 1}, \alpha_P(S \cup {\rho}) = \bigl(1 - (-1)^{s_{j+1} - s_j - 1}\bigr),\alpha_P(S), $$ obtained by applying the Euler relation in every interval $[x, y]$ bridging the gap. Passing from $α$ to $β$ by the inversion $α_{P} (S) = \sum_{T \subseteq S} β_{P} (T)$ diagonalises this system: in the $β$ -coordinates the entire family of generalised equations collapses to the single statement $β_{P} (S) = β_{P} (\overset{ˉ}{S})$ , because complementation $S \mapsto \overset{ˉ}{S}$ is the symmetry that the Euler relation induces on the rank-set Boolean lattice. The simplicial-polytope corollary $h_{i} = h_{n - i}$ is the special case where $S$ ranges over the diagonal entries; the flag $h$ -vector specialises to the ordinary $h$ -vector, and complementation of singleton-generated sets is the reflection $i \mapsto n - i$ . $□$

Corollary (Euler-Poincaré). Applying the Eulerian condition to the full interval $[\hat{0}, \hat{1}]$ gives $\sum_{i = 0}^{n} (- 1)^{i} f_{i - 1} = 0$ , i.e. for the face lattice of a $d$ -polytope $\sum_{i = - 1}^{d} (- 1)^{i} f_{i} = 0$ , which after removing the empty face and the whole polytope is the classical $\sum_{i = 0}^{d - 1} (- 1)^{i} f_{i} = 1 - (- 1)^{d}$ . For $d = 3$ this is $f_{0} - f_{1} + f_{2} = 2$ , vertices minus edges plus faces.

Bridge. This theorem is the foundational reason a polytope's face numbers are constrained rather than free: the Euler relation in every interval is what makes the flag $h$ -vector palindromic, and this is exactly the structural shadow of the clean $μ = (- 1)^{rank gap}$ that the Beginner tier read off by hand. The Dehn-Sommerville symmetry builds toward the cd-index, which packages precisely the linear combinations of flag numbers left unconstrained after these relations, and it appears again in the $g$ -theorem's complete description of $f$ -vectors of simplicial polytopes. The central insight is that complementation $S \mapsto \overset{ˉ}{S}$ on rank sets is the involution the Euler relation induces, so palindromy of $h$ generalises the single sign flip $(- 1)^{r (y) - r (x)}$ of the Möbius function from 40.02.02 into a symmetry of the whole flag vector. Putting these together, the characteristic polynomial studied next attaches the same Möbius data to a generating function whose evaluations count regions and colourings, so the Euler relation that forces Dehn-Sommerville is dual to the deletion-restriction recursion that drives Zaslavsky's theorem.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Show directly that the face lattice of a single edge (a $1$ -polytope: two vertices, one edge) is Eulerian by computing $μ (\hat{0}, \hat{1})$ and the $μ$ on each proper interval.

Hint

The lattice is $\hat{0} < v_{1}, v_{2} < \hat{1}$ with $v_{1}, v_{2}$ the two vertices (it is $B_{2}$ , the diamond minus... actually the square of rank $2$ ). Check $μ$ between every comparable pair.

Answer

The face lattice has $\hat{0}$ (empty face), two atoms $v_{1}, v_{2}$ (the vertices), and $\hat{1}$ (the edge), so it is $B_{2}$ . Then $μ (\hat{0}, v_{i}) = - 1 = (- 1)^{1}$ , $μ (v_{i}, \hat{1}) = - 1 = (- 1)^{1}$ , $μ (x, x) = 1 = (- 1)^{0}$ , and $μ (\hat{0}, \hat{1}) = - (μ (\hat{0}, \hat{0}) + μ (\hat{0}, v_{1}) + μ (\hat{0}, v_{2})) = - (1 - 1 - 1) = 1 = (- 1)^{2}$ . Every value is $(- 1)^{r (y) - r (x)}$ , so the lattice is Eulerian. Rubric: full credit for computing $μ$ on all comparable pairs and matching the sign rule.

Exercise 7 (hard, symbolic).

Prove that the face lattice $F (P)$ of a convex polytope is Eulerian, assuming the Euler-Poincaré relation $\sum_{i = - 1}^{d} (- 1)^{i} f_{i} = 0$ holds for every face (including every face of every face).

Hint

Every interval $[F, G]$ in the face lattice is itself the face lattice of a polytope (the face $G / F$ ), of rank $dim G - dim F$ . Apply the Euler relation in each interval and use the recursion for $μ$ .

Answer

Each interval $[F, G]$ of $F (P)$ for faces $F \subseteq G$ is isomorphic to the face lattice of the quotient polytope $G / F$ , a polytope of dimension $dim G - dim F - 1$ (for $F$ a proper subface), so $[F, G]$ is graded of rank $m = r (G) - r (F)$ . Apply the Euler-Poincaré relation to $G / F$ : $\sum_{j = - 1}^{m - 1} (- 1)^{j} f_{j} (G / F) = 0$ , equivalently $\sum_{F \leq z \leq G} (- 1)^{r (z) - r (F)} = 0$ over the interval. This is the Euler relation $\sum_{F \leq z \leq G} (- 1)^{r (z)} = 0$ in $[F, G]$ . By the equivalence proved in the Formal definition (the recursion $\sum_{F \leq z \leq G} μ (F, z) = 0$ together with the Euler relation), $μ (F, G) = (- 1)^{r (G) - r (F)}$ for every interval. Hence $F (P)$ is Eulerian. Rubric: full credit for the interval-is-a-quotient-polytope step and the deduction of the sign value of $μ$ from the Euler relation in each interval.

Exercise 8 (hard, symbolic).

Prove Zaslavsky's theorem in the form $r (A) = (- 1)^{d} χ_{A} (- 1)$ for the number of regions of a real arrangement $A$ of hyperplanes in $R^{d}$ , by deletion-restriction induction.

Hint

Pick a hyperplane $H \in A$ . Show regions satisfy $r (A) = r (A ∖ H) + r (A^{H})$ where $A^{H}$ is the restriction to $H$ , and show $χ$ satisfies $χ_{A} = χ_{A ∖ H} - χ_{A^{H}}$ .

Answer

Let $H \in A$ , write $A^{'} = A ∖ H$ (deletion) and $A^{''} = A^{H} = {K \cap H : K \in A^{'}, K \cap H \neq = \emptyset}$ (restriction, an arrangement in $H ≅ R^{d - 1}$ ). Geometrically, the regions of $A$ are obtained from those of $A^{'}$ by slicing: each region of $A^{'}$ that $H$ passes through splits into two, and the number of such split regions equals the number of regions of $A^{''}$ (the cells $H$ is divided into by the other hyperplanes). Hence $r (A) = r (A^{'}) + r (A^{''})$ .

The characteristic polynomial satisfies the deletion-restriction recursion $χ_{A} (t) = χ_{A^{'}} (t) - χ_{A^{''}} (t)$ : this follows from the Möbius-function relation on the intersection posets, where removing $H$ deletes exactly the contributions of flats containing $H$ , which reassemble into the intersection poset of $A^{''}$ shifted in dimension. Now induct on $∣ A ∣$ . The empty arrangement in $R^{d}$ has $χ = t^{d}$ , one region, and $(- 1)^{d} (- 1)^{d} = 1$ checks. Assuming the result for $A^{'}$ (in $R^{d}$ ) and $A^{''}$ (in $R^{d - 1}$ ), $$ (-1)^d \chi_{\mathcal{A}}(-1) = (-1)^d\chi_{\mathcal{A}'}(-1) - (-1)^d\chi_{\mathcal{A}''}(-1) = r(\mathcal{A}') + (-1)^{d-1}\chi_{\mathcal{A}''}(-1) = r(\mathcal{A}') + r(\mathcal{A}''), $$ using $- (- 1)^{d} = (- 1)^{d - 1}$ , which equals $r (A)$ . Rubric: full credit for the region recursion, the matching $χ$ recursion, and the sign bookkeeping in the induction.

Advanced results Master

The Dehn-Sommerville relations cut the flag $f$ -vector down to an independent core; the cd-index names that core, and the characteristic polynomial routes the same Möbius data into region-counting and chromatic enumeration.

Theorem 1 (the cd-index). For an Eulerian poset $P$ of rank $n$ , there is a unique noncommutative polynomial $Φ_{P} (c, d)$ in variables $c$ (degree $1$ ) and $d$ (degree $2$ ), homogeneous of degree $n - 1$ , such that the flag $f$ -vector is recovered from $Φ_{P}$ by the substitution encoding chains, and the linear relations among flag numbers satisfied by $Φ_{P}$ are exactly the generalised Dehn-Sommerville relations ^{[Stanley 1994]}. The number of cd-monomials of degree $n - 1$ is the Fibonacci number $F_{n}$ , which is the rank of the flag $f$ -vector space modulo Dehn-Sommerville — so the cd-index is a basis-free certificate that those relations are the only linear ones. Stanley's nonnegativity: for the face lattice of a convex polytope, and more generally for any Gorenstein* (= Eulerian + Cohen-Macaulay with the topology of a sphere) poset, all coefficients of $Φ_{P}$ are nonnegative; this was conjectured by Stanley and proved by Karu using the hard Lefschetz theorem for the associated toric variety. The ab-to-cd reduction is the algebraic incarnation of "every Dehn-Sommerville relation, and no others."

Theorem 2 (characteristic polynomial and Whitney's theorem). For a graded poset $L$ with $\hat{0}$ and rank $n$ , $χ (L, t) = \sum_{x} μ (\hat{0}, x) t^{n - r (x)} = \sum_{k = 0}^{n} w_{k} t^{n - k}$ , where $w_{k} = \sum_{r (x) = k} μ (\hat{0}, x)$ is the $k$ -th Whitney number of the first kind ^{[Stanley §3.10]}. For a geometric lattice $L$ (the lattice of flats of a matroid, 40.02.01), Whitney's theorem gives the $w_{k}$ a combinatorial sign-reversing form: fixing a linear order on the atoms, $(- 1)^{k} w_{k}$ counts the no-broken-circuit sets of size $k$ , where a broken circuit is a circuit with its least element deleted. Thus $χ (L, t)$ has coefficients alternating in sign with absolute values the NBC counts, and in particular the Möbius number $μ (\hat{0}, \hat{1}) = (- 1)^{n} w_{n}$ is, up to sign, the number of NBC bases.

Theorem 3 (chromatic polynomial via the bond lattice). For a graph $G$ with vertex set $V$ , the bond lattice $L_{G}$ is the sub-meet-semilattice of the partition lattice $Π_{V}$ consisting of partitions into connected (induced) blocks, ordered by refinement, graded by $r (π) = ∣ V ∣ - (number of blocks)$ . Then the chromatic polynomial of 40.04.06 satisfies $$ P(G, t) = \sum_{\pi \in L_G}\mu(\hat 0, \pi), t^{,|V| - r(\pi)} = t^{c(G)},\chi(L_G, t), $$ where $c (G)$ is the number of connected components; equivalently $P (G, t) = \sum_{A \subseteq E} (- 1)^{∣ A ∣} t^{c (A)}$ is Whitney-rank inclusion-exclusion over the bond lattice ^{[Stanley §3.10]}. Whitney's broken-circuit theorem is the geometric-lattice NBC count specialised to the graphic matroid: $P (G, t) = \sum_{k} (- 1)^{k} (NBC sets of size k) t^{∣ V ∣ - k}$ , giving the chromatic polynomial's coefficients as signed broken-circuit-free edge counts.

Theorem 4 (Zaslavsky's theorem; arrangements). For a real hyperplane arrangement $A$ in $R^{d}$ with intersection poset $L (A)$ (flats ordered by reverse inclusion, $\hat{0} = R^{d}$ ) and characteristic polynomial $χ_{A} (t) = \sum_{x \in L (A)} μ (\hat{0}, x) t^{d i m x}$ , the number of regions and bounded regions are $$ r(\mathcal{A}) = (-1)^d \chi_{\mathcal{A}}(-1), \qquad b(\mathcal{A}) = (-1)^d \chi_{\mathcal{A}}(1) $$ ^{[Zaslavsky 1975]}. The proof is the deletion-restriction induction matching the region recursion $r (A) = r (A ∖ H) + r (A^{H})$ to the polynomial recursion $χ_{A} = χ_{A ∖ H} - χ_{A^{H}}$ . The braid arrangement ${x_{i} = x_{j}}$ has $χ (t) = t (t - 1) \dots (t - n + 1)$ and $(- 1)^{n} χ (- 1) = n!$ regions, one per linear order, recovering the partition lattice's connection to permutations.

Theorem 5 (order complexes, shellability, Cohen-Macaulay). The order complex $Δ (P)$ of a poset (the simplicial complex of chains, 40.02.02) carries the topological content of $P$ : $μ_{P} (\hat{0}, \hat{1}) = \tilde{χ} (Δ (\overset{ˉ}{P}))$ where $\overset{ˉ}{P}$ is the open interval $(\hat{0}, \hat{1})$ , by Philip Hall's theorem. $P$ is Cohen-Macaulay if $Δ (P)$ and all its links have the homology of a wedge of top-dimensional spheres; $P$ is shellable if $Δ (P)$ admits a shelling (a maximal-simplex ordering with connected intersection conditions), and shellable $\Rightarrow$ Cohen-Macaulay. Face lattices of polytopes are shellable (Bruggesser-Mani line shellings), hence Cohen-Macaulay and, being Eulerian, Gorenstein*; this is the topological substrate making the cd-index nonnegative and the $h$ -vector nonnegative.

Synthesis. The Euler relation in every interval is the foundational reason a polytope's face data is rigid: it forces $μ (x, y) = (- 1)^{r (y) - r (x)}$ , which is exactly the Eulerian condition, and palindromy of the flag $h$ -vector — the Dehn-Sommerville relations — is its only linear consequence, certified basis-free by the cd-index. The central insight is that one Möbius function carries two faces: as a sign in every interval it produces Eulerianness and the cd-index; as a generating function $\sum_{x} μ (\hat{0}, x) t^{n - r (x)}$ it produces the characteristic polynomial, and these are dual readings of the incidence algebra of 40.02.02. Putting these together, the characteristic polynomial of a geometric lattice generalises the chromatic polynomial of 40.04.06 — the bond lattice is the geometric lattice of the graphic matroid, and Whitney's broken-circuit theorem is the no-broken-circuit count of its first Whitney numbers — and the same polynomial counts arrangement regions by Zaslavsky's $(- 1)^{d} χ (- 1)$ , the deletion-restriction recursion being dual to the Euler relation that drove Dehn-Sommerville. The bridge is that geometric lattices and Eulerian lattices are two regimes of the one Möbius calculus: the partition lattice and matroid flats supply the characteristic-polynomial / chromatic side, the face lattices of polytopes supply the Eulerian / cd-index side, and shellability is the topological condition (Cohen-Macaulayness) that makes both sides nonnegative, this is exactly the combinatorial-topology programme that reads $μ$ as a reduced Euler characteristic.

Full proof set Master

Proposition 1 (Eulerian $\Leftrightarrow$ interval Euler relations). A graded poset $P$ with $\hat{0}, \hat{1}$ is Eulerian if and only if $\sum_{x \leq z \leq y} (- 1)^{r (z)} = 0$ for every $x < y$ .

Proof. Suppose $μ (x, y) = (- 1)^{r (y) - r (x)}$ for all $x \leq y$ . Fix $x < y$ and apply the Möbius recursion $\sum_{x \leq z \leq y} μ (x, z) = 0$ , valid since $x < y$ . Substituting $μ (x, z) = (- 1)^{r (z) - r (x)}$ gives $(- 1)^{- r (x)} \sum_{x \leq z \leq y} (- 1)^{r (z)} = 0$ , so $\sum_{x \leq z \leq y} (- 1)^{r (z)} = 0$ . Conversely, assume the Euler relation in every interval; prove $μ (x, y) = (- 1)^{r (y) - r (x)}$ by induction on $r (y) - r (x)$ . The base $x = y$ gives $μ = 1 = (- 1)^{0}$ . For $x < y$ , the recursion gives $μ (x, y) = - \sum_{x \leq z < y} μ (x, z) = - \sum_{x \leq z < y} (- 1)^{r (z) - r (x)}$ by induction. The Euler relation on $[x, y]$ reads $\sum_{x \leq z \leq y} (- 1)^{r (z)} = 0$ , i.e. $\sum_{x \leq z < y} (- 1)^{r (z)} = - (- 1)^{r (y)}$ . Therefore $μ (x, y) = - (- 1)^{- r (x)} \cdot (- (- 1)^{r (y)}) = (- 1)^{r (y) - r (x)}$ . $□$

Proposition 2 (Dehn-Sommerville for simplicial polytopes, $h_{i} = h_{n - i}$ ). The $h$ -vector of the boundary complex of a simplicial $d$ -polytope (an Eulerian poset of rank $n = d$ ) satisfies $h_{i} = h_{d - i}$ .

Proof. For a simplicial complex of dimension $d - 1$ with face numbers $f_{i - 1}$ ( $f_{- 1} = 1$ ), define $h_{i}$ by $\sum_{i = 0}^{d} f_{i - 1} (t - 1)^{d - i} = \sum_{i = 0}^{d} h_{i} t^{d - i}$ , equivalently $h_{k} = \sum_{i = 0}^{k} (- 1)^{k - i} (k - i d - i) f_{i - 1}$ . The boundary of a simplicial polytope is an Eulerian sphere, so the Dehn-Sommerville relations $\sum_{i} (- 1)^{i} (i j) f_{i - 1} = (- 1)^{d - 1} f_{j - 1}$ hold for the face numbers (the interval Euler relations restricted to links of faces). Substituting into the $h$ -definition and reindexing, replace $t$ by $1/ t$ and multiply by $t^{d}$ : $\sum_{i} h_{i} t^{i} = \sum_{i} f_{i - 1} (1 - t)^{d - i} t^{i}$ , and the Dehn-Sommerville face relations make the right side invariant under $t \mapsto 1/ t$ up to the factor $t^{d}$ , giving $\sum_{i} h_{i} t^{d - i} = \sum_{i} h_{d - i} t^{d - i}$ . Matching coefficients yields $h_{i} = h_{d - i}$ . The cleanest route uses Eulerianness directly: the $h$ -polynomial of an Eulerian sphere equals the $h$ -polynomial of its dual, and self-duality of the substitution forces palindromy. $□$

Proposition 3 (characteristic polynomial of the bond lattice is the chromatic polynomial). For a graph $G = (V, E)$ , $P (G, t) = \sum_{π \in L_{G}} μ (\hat{0}, π) t^{b (π)}$ , where $b (π)$ is the number of blocks of $π$ , summed over the bond lattice.

Proof. A proper $t$ -colouring is a map $κ : V \to [t]$ with $κ (u) \neq = κ (v)$ for $uv \in E$ . By inclusion-exclusion over the "monochromatic edge" conditions, group all colourings (proper or not) by the partition $π (κ)$ they induce, where two vertices are in the same block iff connected by a monochromatic path. For a partition $π$ into connected blocks, the number of colourings constant on each block of $π$ and otherwise arbitrary is $t^{b (π)}$ , and these count colourings whose monochromatic partition is $\geq π$ . Writing $N_{\geq} (π) = t^{b (π)}$ for the down-sum and $N_{=} (π)$ for colourings with monochromatic partition exactly $π$ , the proper colourings are $N_{=} (\hat{0})$ . Möbius inversion over the bond lattice (where $\hat{0}$ is the all-singletons partition) gives $N_{=} (\hat{0}) = \sum_{π \geq \hat{0}} μ (\hat{0}, π) N_{\geq} (π) = \sum_{π} μ (\hat{0}, π) t^{b (π)}$ . Hence $P (G, t) = \sum_{π \in L_{G}} μ (\hat{0}, π) t^{b (π)}$ . Equivalently, expanding $μ$ via Whitney rank generating over edge subsets gives $P (G, t) = \sum_{A \subseteq E} (- 1)^{∣ A ∣} t^{c (A)}$ . $□$

Proposition 4 (Zaslavsky's region count). For a real arrangement $A$ in $R^{d}$ , $r (A) = (- 1)^{d} χ_{A} (- 1)$ and $b (A) = (- 1)^{d} χ_{A} (1)$ .

Proof. Both $r$ and $χ$ satisfy deletion-restriction. For regions: choosing $H \in A$ , the hyperplane $H$ subdivides exactly those regions of $A ∖ H$ that it crosses, and the crossed regions are in bijection with the regions of the restricted arrangement $A^{H}$ in $H$ , so $r (A) = r (A ∖ H) + r (A^{H})$ . For the characteristic polynomial, the intersection poset of $A$ relates to those of $A ∖ H$ and $A^{H}$ by $χ_{A} (t) = χ_{A ∖ H} (t) - χ_{A^{H}} (t)$ (Möbius contributions of flats containing $H$ collect into the restriction). Induct on $∣ A ∣$ with base the empty arrangement ( $χ = t^{d}$ , one region, $(- 1)^{d} (- 1)^{d} = 1$ ). Then $(- 1)^{d} χ_{A} (- 1) = (- 1)^{d} χ_{A ∖ H} (- 1) - (- 1)^{d} χ_{A^{H}} (- 1) = r (A ∖ H) + (- 1)^{d - 1} χ_{A^{H}} (- 1) = r (A ∖ H) + r (A^{H}) = r (A)$ , since $A^{H}$ lives in dimension $d - 1$ and $- (- 1)^{d} = (- 1)^{d - 1}$ . The bounded-region count follows by the same induction at $t = 1$ , the boundedness bookkeeping tracking the unbounded directions. $□$

Proposition 5 (Whitney's theorem; NBC form of the Whitney numbers). In a geometric lattice $L$ of rank $n$ with atoms ordered linearly, $(- 1)^{k} w_{k}$ equals the number of no-broken-circuit subsets of $k$ atoms, where $w_{k} = \sum_{r (x) = k} μ (\hat{0}, x)$ .

Proof. Use the broken-circuit complex of the underlying matroid. A broken circuit is $C ∖ {min C}$ for a circuit $C$ ; an NBC set is an independent set containing no broken circuit. The characteristic polynomial satisfies the deletion-contraction recursion $χ (L, t) = χ (L ∖ e, t) - χ (L / e, t)$ for a non-loop, non-coloop atom $e$ , mirroring the recursion for the NBC generating function $\sum_{k} (NBC_{k}) (- 1)^{k} t^{n - k}$ . Both have the same boundary cases (a Boolean lattice / free matroid gives $χ = (t - 1)^{n}$ and NBC sets are all subsets avoiding the broken circuits, i.e. all independent sets with the order condition). By induction on the number of atoms, the two generating functions agree, so $(- 1)^{k} w_{k} = # {NBC sets of size k}$ . In particular the leading Möbius number $∣ μ (\hat{0}, \hat{1}) ∣ = (- 1)^{n} w_{n}$ is the number of NBC bases, a positive integer, recovering the sign-alternation of the Whitney numbers. $□$

Connections Master

The incidence algebra and Möbius function of 40.02.02 are the substrate: Eulerianness is the condition $μ (x, y) = (- 1)^{r (y) - r (x)}$ on the very Möbius function defined there, and the characteristic polynomial $\sum_{x} μ (\hat{0}, x) t^{n - r (x)}$ packages the same $μ$ into a generating function. That unit owns the general inversion theory and the partition/subspace-lattice computations; this unit specialises it to the Eulerian regime of polytope face lattices and to the characteristic-polynomial side, with Philip Hall's order-complex theorem from that unit supplying the topological reading of $μ$ used in the shellability results here.
The chromatic polynomial of 40.04.06 is the characteristic polynomial of the bond lattice: $P (G, t) = t^{c (G)} χ (L_{G}, t)$ , and Whitney's broken-circuit theorem is the no-broken-circuit count of the bond lattice's Whitney numbers. That unit develops chromatic enumeration, deletion-contraction, and the Tutte-polynomial context; this unit supplies the order-theoretic reason the chromatic polynomial has alternating signs — the bond lattice is the geometric lattice of the graphic matroid, and its characteristic polynomial inherits the sign-alternating Whitney coefficients. The deletion-restriction recursion of Zaslavsky's theorem is the arrangement analogue of that unit's deletion-contraction.
The posets, lattices, and Birkhoff theory of 40.02.01 provide the graded-lattice and geometric-lattice scaffolding: a geometric lattice is the lattice of flats of a matroid, semimodular with $\hat{1}$ a join of atoms, and the characteristic polynomial lives on exactly these lattices, while the face lattice of a polytope is the Eulerian (non-distributive, non-geometric in general) lattice whose down-set structure that unit characterises. The matroid/geometric-lattice connection flagged there is realised here as the home of the Whitney numbers and the no-broken-circuit complex.

Historical & philosophical context Master

Euler's relation $V - E + F = 2$ for convex polyhedra (1750-52, published 1758) is the origin point; the alternating face count is the oldest combinatorial invariant of a polytope, and the Euler-Poincaré generalisation to all dimensions was established by Henri Poincaré and Ludwig Schläfli in the nineteenth century. The face-count constraints beyond Euler's single relation were found by Max Dehn (1905, for $d \leq 5$ ) and Duncan Sommerville (1927, in general) for simplicial polytopes; the Dehn-Sommerville equations are their palindromy law for the $h$ -vector, recognised much later as the symmetry of the flag $h$ -vector for Eulerian posets ^{[Stanley 1994]}.

Gian-Carlo Rota's Möbius-function programme (1964, 40.02.02) made the characteristic polynomial a poset invariant, and the identification of the chromatic polynomial with the characteristic polynomial of the bond lattice — and of the Whitney numbers with broken-circuit counts — is due to Hassler Whitney (1932) recast in Rota's language. Margaret Bayer and Louis Billera (1985) proved that the generalised Dehn-Sommerville relations are the complete set of linear relations on the flag $f$ -vector of an Eulerian poset, and Jonathan Fine and Bayer-Klapper introduced the cd-index as the basis-free encoding; Richard Stanley conjectured its nonnegativity for spheres, proved by Kalle Karu (2006) via the hard Lefschetz theorem. Thomas Zaslavsky's Facing up to arrangements (1975) ^{[Zaslavsky 1975]} established the region count $(- 1)^{d} χ (- 1)$ , founding the combinatorial theory of hyperplane arrangements, and Anders Björner's shellability and Cohen-Macaulay programme placed the whole subject inside combinatorial topology.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@incollection{stanley1994eulerian,
  author    = {Stanley, Richard P.},
  title     = {A survey of {E}ulerian posets},
  booktitle = {Polytopes: Abstract, Convex and Computational},
  editor    = {Bisztriczky, T. and McMullen, P. and Schneider, R. and Weiss, A. I.},
  series    = {NATO ASI Series},
  publisher = {Kluwer},
  year      = {1994},
  pages     = {301--333}
}

@article{zaslavsky1975facing,
  author  = {Zaslavsky, Thomas},
  title   = {Facing up to arrangements: face-count formulas for partitions of space by hyperplanes},
  journal = {Memoirs of the American Mathematical Society},
  volume  = {1},
  number  = {154},
  year    = {1975}
}

@book{ziegler1995polytopes,
  author    = {Ziegler, G\"{u}nter M.},
  title     = {Lectures on Polytopes},
  series    = {Graduate Texts in Mathematics},
  volume    = {152},
  publisher = {Springer},
  year      = {1995}
}

@article{bayerbillera1985generalized,
  author  = {Bayer, Margaret M. and Billera, Louis J.},
  title   = {Generalized {D}ehn-{S}ommerville relations for polytopes, spheres and {E}ulerian partially ordered sets},
  journal = {Inventiones Mathematicae},
  volume  = {79},
  number  = {1},
  year    = {1985},
  pages   = {143--157}
}

@article{karu2006cd,
  author  = {Karu, Kalle},
  title   = {The cd-index of fans and posets},
  journal = {Compositio Mathematica},
  volume  = {142},
  number  = {3},
  year    = {2006},
  pages   = {701--718}
}

@article{whitney1932logical,
  author  = {Whitney, Hassler},
  title   = {A logical expansion in mathematics},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {38},
  number  = {8},
  year    = {1932},
  pages   = {572--579}
}

@article{bjorner1980shellable,
  author  = {Bj\"{o}rner, Anders},
  title   = {Shellable and {C}ohen-{M}acaulay partially ordered sets},
  journal = {Transactions of the American Mathematical Society},
  volume  = {260},
  number  = {1},
  year    = {1980},
  pages   = {159--183}
}

Prerequisites

40.02.02

Tier anchors

beginner: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §3.14-3.16 (graded posets, the face lattice of a polytope, the Boolean lattice as the simplex's face lattice, read on the square and the triangle by hand); Ziegler 1995 *Lectures on Polytopes* (Springer) Ch. 8 for the f-vector picture before any algebra
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.14-3.16 (rank-generating function, the zeta polynomial, Eulerian posets, the flag f-vector and flag h-vector, the Dehn-Sommerville relations); Ziegler 1995 *Lectures on Polytopes* §8.1-8.3 (f-vector, h-vector, Euler-Poincaré and Dehn-Sommerville)
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.14-3.17 and Notes (Eulerian posets, the cd-index, the characteristic polynomial of a graded/geometric lattice, Whitney's theorem, the relation to the chromatic polynomial and to hyperplane arrangements); Stanley 1994 *Discrete Comput. Geom.* 'A survey of Eulerian posets' for the cd-index and Dehn-Sommerville; Zaslavsky 1975 *Memoirs AMS* 154 ('Facing up to arrangements') for the region-counting theorem; Bjorner-Wachs-Welker for shellability and Cohen-Macaulay posets

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2nd edition (2012). Chapter 3 develops graded posets and their enumerative invariants. §3.14: a graded (ranked) poset of rank n with rank function r, the rank-generating function, the zeta polynomial Z(P,m) counting multichains of length m, and the flag f-vector / flag h-vector indexed by rank sets S ⊆ {1,...,n-1} with the defining relation α_P(S) = Σ_{T ⊆ S} β_P(T). §3.14: Eulerian posets, defined by μ(x,y) = (-1)^{r(y)-r(x)} for all x ≤ y (equivalently the Euler relation Σ_{x ≤ z ≤ y}(-1)^{r(z)} = 0 in every interval of positive length), with the Boolean lattice B_n and the face lattice of a convex polytope as the motivating examples; the Dehn-Sommerville relations as the statement that the flag h-vector is symmetric, β_P(S) = β_P(ar S). §3.16: the cd-index Φ_P, a noncommutative polynomial in two variables c, d of degree n-1 that encodes the flag f-vector subject to exactly the Dehn-Sommerville relations, with Stanley's nonnegativity for spherical/Gorenstein* posets. §3.10-3.11: the characteristic polynomial χ(P,t) = Σ_{x} μ(0̂,x) t^{n-r(x)} of a graded poset with 0̂; Whitney's theorem giving its coefficients via the Möbius function (Whitney numbers of the first kind) and, for geometric lattices, via the broken-circuit / no-broken-circuit count; the bond lattice of a graph and the identification of χ(L_G,t) with the chromatic polynomial; the relation to hyperplane arrangements and Zaslavsky's theorem r(A) = (-1)^d χ_A(-1) for the number of regions.
Ziegler, G. M. — Lectures on Polytopes · Springer Graduate Texts in Mathematics 152 (1995), Chapter 8 ('Shellability and the Upper Bound Theorem'). Develops the face lattice of a convex polytope, the f-vector (f_{-1},f_0,...,f_{d-1},f_d), the Euler-Poincaré relation Σ_{i=-1}^{d}(-1)^i f_i = 0 (equivalently Σ_{i=0}^{d-1}(-1)^i f_i = 1-(-1)^d for the proper faces), the h-vector via the shelling-polynomial substitution Σ f_{i-1}(t-1)^{d-i} = Σ h_i t^{d-i}, and the Dehn-Sommerville equations h_i = h_{d-i} as the palindromy of the h-vector for simplicial polytopes, derived from Eulerianness of the face lattice. Chapter 7 covers the broader f-vector theory and the g-theorem context.
Zaslavsky, T. — Facing up to arrangements: face-count formulas for partitions of space by hyperplanes · Memoirs of the American Mathematical Society 1, issue 1, number 154 (1975). The founding paper of the combinatorial theory of hyperplane arrangements. Proves that for a real arrangement A of hyperplanes in R^d with intersection poset L(A) ordered by reverse inclusion, the number of regions is r(A) = (-1)^d χ_A(-1) and the number of bounded regions is b(A) = (-1)^d χ_A(1), where χ_A(t) = Σ_{x ∈ L(A)} μ(0̂,x) t^{dim x} is the characteristic polynomial. The proof is a deletion-restriction recursion χ_A = χ_{A\H} - χ_{A^H} matching the region recursion, with the Möbius function of the intersection poset supplying the signs.
Stanley, R. P. — A survey of Eulerian posets · in Polytopes: Abstract, Convex and Computational (T. Bisztriczky et al., eds.), NATO ASI Series, Kluwer (1994), 301-333. Survey of Eulerian posets: the definition via μ(x,y)=(-1)^{r(y)-r(x)}, the flag f-vector and flag h-vector, the Dehn-Sommerville relations as flag-h symmetry, the cd-index Φ_P as the unique noncommutative c,d-polynomial encoding the flag f-vector modulo Dehn-Sommerville, and the nonnegativity of the cd-index for the face lattices of polytopes and more generally for Gorenstein* / S-shellable posets (later proved by Karu).

Estimated time

beginner: 20m
intermediate: 50m
master: 90m