Algebraic combinatorics Lecture 12: Dehn-Sommerville, flag enumeration and Eulerian posets; the tip of a convex iceberg

Let Q be a convex polytope in {{\mathbb R}^{d+1}}, and let {f_i} be the number of i-dimensional faces. How are the {f_i} related? Of course Euler’s relation states {V - E + F =2 -2g} and for convex polytope, the genus is {g=0}. Thus for {d=2}, we can parametrize all admissible face vector {(f_1,f_2,f_3)} by two coordinates, {f_0} and {f_2}.

Theorem 4 (Steinutz 1905) The admissible set forms a cone anchored at {(4,4)}. One can build all points from {(4,4)} by adding {(1,2)} or {(2,1)}.

The case of {d \ge 4} is completely open. some progress: the polytopes are simplicial, i.e., every face is a simplex if and only if the extreme points are in general position.
From {f}-vector we can get {h}-vector, defined by

\displaystyle  \sum_{i=0}^d h_i x^{d -i} = \sum_{i=0}^d f_{d-i} (x-1)^{d-i}. \ \ \ \ \ (11)

More explicitly,

\displaystyle  h_i = \sum_{j=0}^i (-1)^{i-j} \binom{d-j}{i-j} f_{i-j}. \ \ \ \ \ (12)

Theorem 5 (Billera, Stanley) Reference: G. Ziegler. {h= (h_1, \ldots, h_d)} is an h-vector of {d}-dimensional polytope if and only if

  1. The Dehn-Sommerville condition holds: {h_i = h_{d-i}}.
  2. Set {g_0 = 1}, {g_i = h_i - h_{i-1}}, {1 \le i \le \lfloor \frac{d}{2} \rfloor}, the {g_i \ge 0}.
  3. {g_{i+1} \le g_i^{\langle i \rangle}} (see definition below).

Here given any positive integer {g}, {i}, write {g = \binom{n_1}{i} + \binom{n_2}{i-1} + \ldots + \binom{n_j}{i-j+1}}, for {n_1 > n_2 \ldots > n_j \ge j \ge 1}. Then

\displaystyle  g_i^{\langle j \rangle} = \binom{n_1 + 1}{i+1} + \binom{n_2 +1}{i} + \ldots + \binom{n_j}{i-j+2}. \ \ \ \ \ (13)

For example, if {i=2}, {j =2}, and {g=9}, then {g = \binom{4}{2} + \binom{3}{1}}, and {g_i^{\langle j \rangle} = \binom{5}{3}+ \binom{4}{2} = 16}.

For general polytopes, the Euler relation becomes {\sum_{i=0}^{d-1} (-1)^i f_i = 1- (-1)^d}. Polya tried harder problem: count not only faces, but chains of faces. Given {S \subseteq \{0,1,\ldots, d-1\}} and {Q} convex, let {f_S(Q) = } number of chains of faces of Q with dimensions in {S}. The image of {S \mapsto f_S(Q)} is called a flag-f vector.

  • it specializes to {(f_0)}, {(f_1)}, etc as {\{f_S: |S| =1\}}.
  • There is a natural flag h-vector, and analogue of Dehn-Sommerville condition holds.
  • Some progress has been made in the flag case.

A natural setting to study is when {S \mapsto f_S(Q)} gives the flag vectors of graded posets. Face lattice of Q is a graded poset, obviously. Recall P is graded poset if {0 \le x \le 1} for all {x \in P} and all max chains from {0} to {1} have the same length. It’s the same as ranked poset.

Definition 6 {S \subseteq [n]}, the flag f-vector {S \mapsto f_S(P) = \{y_1 < y_2 < \ldots < y_k\}}, {y_j \in P}, with {\rho(y_j) = s_j} the distance of {y_j} from {0}; {s= \{s_1 < \ldots < s_k\}} is the dimension set.

Try to characterize Dehn-Sommerville relation: for example, for every graded poset of rank {\ge 4}, {f_{\{1,3\}} - f_{\{1\}} + f_{\{2\}} - f_{\{3\}} \ge 0}.
Tool: (Gil Kalai) convolution: for {S \subset [n-1]}, {T \subset [m-1]}, and {P} a ranked poset of rank {n+m}, we have

\displaystyle  (f_S^n * f_T^m) (P) = \sum_{x \in P: \rho(x) = n} f_S^n([0,x]) f_T^m([x,1])\\ = f_{S \cup \{n\} \cup \{T\} \cup \{m\}}^{n+m} (P) \ \ \ \ \ (14)

Theorem 7 If {G_1 = \sum_S \alpha_S f_S^{(n)}} and {G_2 = \sum_S \beta_S f_S^{(m)}}, and {G_1(P), G_2(P) \ge 0}, for every polytope resp. graded poset, then

\displaystyle  G_1 * G_2 (P) \ge 0 \ \ \ \ \ (15)

for every polytope resp graded poset of dimension rank {= n+m}.

Now back to algebra. Recall {QSM(x_1, x_2, \ldots)}. {\{m_\alpha\}_{\alpha \models n}}, {m_\alpha = \sum_{i_1 < \ldots < i_k} x_{i_1}^{\alpha_1} \ldots x_{i_k}^{\alpha_k}}. Given a poset {P}, define

\displaystyle  F(P) = \sum_{0 = u_0 \le \ldots \le u_{k+1} =1} x_1^{\rho(u_0,u_1)} x_2^{\rho(u_1,u_2)} \ldots x_k^{\rho(u_k,u_{k+1})} \ \ \ \ \ (16)

where {u_i \in P}, and {\rho(x,y):=\rho(x) -\rho(y)}.

Theorem 8

  1. {F(P) \in QSYM_n}, {n = \rho(P)}.
  2. {F(P_1 \times P_2) = F(P_1) F(P_2)}.
  3. {F(P) = \sum_\alpha f_\alpha m_\alpha = \sum_\alpha h_\alpha L_\alpha}.


  1. Luke Billera (Cornell) Flag enumerations and polytopes, Eulerian posets, and coxeter groups. 2010 ICM.
  2. Khazdan-Lusztig symmetric polynomials.

Last topic (I am very confused about the end of this part, someone please explain to me how the zeta function is related to the algebra {\hat{I}}: consider {k[x]} which is not only an algebra, but also a cogebra.

\displaystyle  \Delta(P) = P(1 \otimes x + x \otimes 1)\\ \Delta(x^k) = \sum_{i=0}^k \binom{k}{i} x^i \otimes x^{k-i}\\ \epsilon(P) = P(0) \ \ \ \ \ (17)

For {x \in {\mathbb N}_+}, let {1_x = (1 1 \ldots 1 0 0\ldots)}, with {x} 1’s. Then {m_\alpha (1_x) = \binom{k}{x}}, if {x \models k}.
{f = \sum_\alpha a_\alpha m_\alpha} is a quasi-symmetric function, with {f(1_x) \in k[x]}. If {\hat{I}} is the incidence Hopf algebra of a graded poset (i.e., elements are generated by intervals {[x,y]}), {f \mapsto f(1_x)} is a Hopf map, from which one recovers the famous formula

\displaystyle  \binom{x+y}{k} = \sum_{i=0}^k \binom{x}{i} \binom{y}{k-i}\\ \Delta(m_\alpha(1_x)) = \Delta(\binom{x}{k}) = \binom{x \otimes 1 + 1 \otimes x}{k} \\ = \sum_{i=0}^k \binom{x}{i} \otimes \binom{x}{k-i} = \sum_{i=0}^k \Delta(m_{\alpha_1, \ldots, \alpha_i}) \otimes \Delta(m_{\alpha_{i+1}, \ldots, \alpha_k}) \ \ \ \ \ (18)

where {\alpha \models k}. Thus we have a map inducing the zeta function

\displaystyle  \hat{I} \rightarrow QSYM \rightarrow k[x]\\ Z_P(x) = \sum_n c_n x^n \ \ \ \ \ (19)

where {c_n =} the number of multichains of length {n} in {P}.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s