0
$\begingroup$

I'm wondering if anybody has an easy way to compute the number of subintervals in weak order of $S_n$ (considered as a Coxeter group of type $A_{n-1}$) that are isomorphic to Boolean algebras. I know $[u,v]$ is such a subinterval if and only if $u\leq v$ and $vu^{-1}$ is a product of adjacent transpositions that pairwise commute with each other. Any insight is appreciated.

$\endgroup$
3
$\begingroup$

This is Exercise 3.185(h) in my book Enumerative Combinatorics, vol. 1, second ed. If $f(n,i)$ denotes the number of intervals in the weak order of $S_n$ that are isomorphic to boolean algebras of rank $i$, then $$ \sum_{n\geq 0}\sum_{i\geq 0}f(n,i)q^i\frac{x^n}{n!} = \frac{1}{1-x-\frac 12 qx^2}. $$ Putting $q=1$ shows that the total number $f(n)$ of boolean intervals satisfies $$ f(n+1)=(n+1)f(n)+{n+1\choose 2}f(n-1). $$ Unfortunately no solution is included.

$\endgroup$
3
  • $\begingroup$ Thanks. I've expressed the number of commutation classes of reduced words for the longest element as a determinant, and I think I could organize this into a bound with Hsdamard's inequality. I'm thinking the bound will probably be trivial, but we'll see. $\endgroup$ – Matt Samuel Nov 2 '16 at 23:51
  • $\begingroup$ @MattSamuel: What is the determinant? This could be interesting for its own sake if it isn't too big or complicated. $\endgroup$ – Richard Stanley Nov 3 '16 at 0:22
  • $\begingroup$ The element $C$ of the incidence algebra such that $C(u,v)$ is the number of commutation classes of $vu^{-1}$ is the inverse of a very simple element of the incidence algebra, namely $C^{-1}(u,v)=0$ unless $[u,v]$ is a Boolean algebra, in which case $C^{-1}(u,v)=(-1)^{\ell(u,v)}$. $\endgroup$ – Matt Samuel Nov 3 '16 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.