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$

1 Answer 1

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$
4
  • $\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$ Nov 2, 2016 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$ Nov 3, 2016 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$ Nov 3, 2016 at 0:27
  • $\begingroup$ For further information about this problem, see arxiv.org/abs/2306.14734 $\endgroup$ Oct 18, 2023 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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