# How linearly independent are the obvious combinatorial invariants of a Bruhat interval?

Let $[u, v]$ be a Bruhat interval in some Coxeter group. Let $I$ be the set of all Bruhat intervals. I am interested in functions $I \to \mathbb{Z}$ which are invariant under poset isomorphisms. Some obvious functions of this type include the functions $v_k$, the number of elements of rank $k$ (where the bottom element has rank $0$), and $e_k$, the number of edges between elements of rank $k$ and elements of rank $k+1$. Similarly, the function $n$, the length of the interval, allows us to write down the functions $v_{n-k}$ and $e_{n-k}$ for some fixed $k$.

Question: Are there any linear relationships between these functions other than the "obvious" ones?

The obvious ones include that $e_0 = v_1, e_{n-1} = v_{n-1}$, and $v_0 = v_n = 1$. Somewhat less obviously, the classification of Bruhat intervals of length $2$ implies that $e_1 = 2v_2, e_{n-2} = 2v_{n-2}$. Beyond that, I more or less expect that these functions are linearly independent - in particular I expect that the functions $v_i$ and $v_{n-i}$ are linearly independent. Are there good reasons to expect otherwise?

(Motivation: linear combinations of these functions occur in some formulas for small coefficients of Kazhdan-Lusztig polynomials that I'm working with, and I want to be sure my intuition that I can't simplify them any further is justified.)

Edit: There is one more relation $v_0 - v_1 + v_2 \mp ... = 0$ coming from the fact that Bruhat intervals are Eulerian. But I should say that I'm only interested in the case where $i$ is small compared to $n$, so this relation doesn't affect what I'm looking at.

• Should we say that the functions you are interested in are all parts of the flag f-vector? Can we rephrase your question as: what are defining equations of the subspace of flag f-vectors spanned by Bruhat intervals? Maybe we can then pass to the right family polytopes to think about this? – Alexander Woo Jul 21 '10 at 20:22
• Since Bruhat intervals are Eulerian their flag $f$-vectors satisfy the Bayer-Billera relations. These give many relations of the type you are looking for. For instance, Gil Kalai gives a few examples at gilkalai.wordpress.com/2008/06/22/…. I doubt whether the flag $f$-vectors of Bruhat intervals satisfy any linear relations not already a consequence of the Eulerian property. – Richard Stanley Jul 21 '10 at 21:38
• Thanks for the link! In the notation of that post, I am only looking for relations between the f_i and the f_{i,i+1}, and it doesn't look like the argument described gives many such relations. But I'll have to take a closer look at the Bayer-Billera relations. – Qiaochu Yuan Jul 21 '10 at 22:30