# Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on permutations $S_n$, we say that $\sigma \leq \tau$ if $\mathrm{Inv}(\sigma)\subseteq \mathrm{Inv}(\tau)$. The length of a permutation $l(\sigma):= |\mathrm{Inv}(\sigma)|$ is the total number of inversions of $\sigma$.

Is there a formula (closed or not) for the size of a principal order ideal (principal downset) in this poset?

Computing all elements in a given order ideal of this poset is easy enough for a fixed $\sigma\in S_n$ using the covering relations given by $\pi\in\{(1,2),(2,3),...,(n-1,n)\}$ and selecting permutations $\pi\sigma$ such that $l(\pi\sigma)<l(\sigma)$ (and repeating until reaching the minimal/identity permutation.)

I was just curious if the size of upper or lower intervals $[\sigma,id^c]$ or $[id,\sigma]$ was easy identifiable in terms of the set of inversions $\mathrm{Inv}(\sigma)$, the inversion table, the Rothe diagram, etc.

## 2 Answers

In general, no "reasonable" formula is known. For separable permutations (or 3142 and 2413-avoiding permutations), see the paper of Fan Wei at http://arxiv.org/pdf/1009.5740.pdf.

Just posted on the arXiv a manuscript giving a polynomial-time algorithm for computing the size of principal order ideals in the weak Bruhat order:

http://arxiv.org/abs/1507.00388

More specifically, we show that the enumeration problem is fixed-parameter tractable in the "intrinsic width" of a a permutation (a generalization of longest decreasing subsequence). This implies a subexponential algorithm for all but an exponentially small fraction of permutations in general.