Computing the Size of Intervals in the Weak Bruhat Order

Abstract

The weak Bruhat order on $ { \mathcal S }_n $ is the partial order $\prec$ so that $σ\prec τ$ whenever the set of inversions of $σ$ is a subset of the set of inversions of $τ$. We investigate the time complexity of computing the size of intervals with respect to $\prec$. Using relationships between two-dimensional posets and the weak Bruhat order, we show that the size of the interval $ [ σ_1, σ_2 ]$ can be computed in polynomial time whenever $σ_1^{-1} σ_2$ has bounded width (length of its longest decreasing subsequence) or bounded intrinsic width (maximum width of any non-monotone permutation in its block decomposition). Since permutations of intrinsic width $1$ are precisely the separable permutations, this greatly extends a result of Wei. Additionally, we show that, for large $n$, all but a vanishing fraction of permutations $ σ$ in $ { \mathcal S }_n$ give rise to intervals $ [ id , σ]$ whose sizes can be computed with a sub-exponential time algorithm. The general question of the difficulty of computing the size of arbitrary intervals remains open.