2015/07/01 by Joshua Cooper, Cooper, Joshua, Anna Kirkpatrick +1
Mathematics · #05A05 #06A07 (Primary) #68Q17 (Secondary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #G.2.1 #Graph theory and applications #Markov Chains and Monte Carlo Methods #acm:05A05 #acm:06A07 #acm:68Q17 #math.CO #msc:05A05 #msc:06A07 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1507.00388
arxiv created 2015/07/01 · openalex publication_date 2015/07/01 · arxiv updated 2015/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.