## 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}$.

Ref:

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}$.