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$.

Weak Bruhat Order on Permutations $S_4$

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.

up vote 7 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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