To put this in context: I am in the process of developing a package for Macaulay 2 (a commutative algebra software,) called "Permutations", which will add permutations as a type of combinatorial object that M2 will handle, hopefully integrating nicely with the (still in development) Posets package, the (still in development) Graphs package, and various current M2 functions.
One of the first things that I'd wanted to put in was functions which compute the poset of the Bruhat order on $S_n$ and compute when one permutation covers another in the Bruhat order. This was all coded and "working" – but has been producing a poset which is decidedly NOT the desired poset (among other things, the graph of the Hasse diagram isn't regular.) I'd like to ask whether the (probably somewhat naive) algorithm I was using to check covering relations seems reasonable (so the problem is just in the coding of it, not in the theory behind it) or not.
To see if $P\leq R$ in the Bruhat order:
Given a pair of permutations P and R, compute their lengths (the number of simple transpositions in their decomposition, or [as implemented right now] the sum of entries in their inversion vectors.) If length(P)=length(R)+1, then we compute
$(P^{-1})*R$.
If R covers P in the Bruhat order, then length$((P^{-1})*R)=1.$
Am I missing some subtlety of the Bruhat order? I thought one permutation covered enough exactly when they differed by a single, simple transposition. This seemed to capture that – but is giving me an incorrect poset.
Coding error or theory error? I'd love to hear it.
Best Answer
My M2 permutation code is here: http://www.math.cornell.edu/~allenk/permutation.m2 It's got a bunch of specialized stuff about Rothe diagrams and Fulton's essential set, but at the end it's got a BruhatLeq, for strong Bruhat order (so, not what you're computing).
If you want covering relations in strong Bruhat or right weak Bruhat, find the first place F and the last place L that your permutations differ. Weak Bruhat Covering: L=F+1. Strong Bruhat covering: each value w(F+1)...w(L-1) is not in the interval (w(F),w(L)).
If you want all relations in weak Bruhat order, w >= v if l(w) = l(v) + l(v^-1 w).
For all relations in strong Bruhat order, best to compute the corresponding rank matrices, and compare those entrywise. (That's what I do in the above code.)