Computing the Size of Intervals in the Weak Bruhat Order

MaRDI QIDQ6263212zbMATH OpenFDO

Authors Joshua Cooper, Anna Kirkpatrick

Publication date 1 July 2015

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The weak Bruhat order on ${mathcalS}_n$ is the partial order $prec$ so that $sigmaprecau$ whenever the set of inversions of $sigma$ is a subset of the set of inversions of $au$. 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 $[sigm{a}_1,sigm{a}_2]$ can be computed in polynomial time whenever $sigm{a}_1^{-1}sigm{a}_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 $sigma$ in ${mathcalS}_n$ give rise to intervals $[id,sigma]$ 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.

This page was built for publication: Computing the Size of Intervals in the Weak Bruhat Order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6263212)