Bruhat order -- an overview of the Bruhat order for permutations

The (strong) Bruhat order is a partial order on the symmetric group $\mathfrak{S}_n$. See [BB05] for more details on Bruhat order.

i1 : p = permutation {3,5,1,2,4}

o1 = Permutation{3, 5, 1, 2, 4}

o1 : Permutation

i2 : q = permutation {4,5,1,2,3}

o2 = Permutation{4, 5, 1, 2, 3}

o2 : Permutation

i3 : strongBruhatOrder(p, q)

o3 = true

The (right) weak Bruhat order is a partial order on the symmetric group $\mathfrak{S}_n$. For two permutations $p$ and $q$, $w \leq_R v$ if and only if $\ell(w) + \ell(v^{-1} w) = \ell(v)$, where $\ell$ denotes the length(Permutation) of a permutation and $\leq_R$ is the right weak Bruhat order.

i4 : p = permutation {1,3,2}

o4 = Permutation{1, 3, 2}

o4 : Permutation

i5 : q = permutation {3,1,2}

o5 = Permutation{3, 1, 2}

o5 : Permutation

i6 : weakBruhatOrder(p, q)

o6 = true

The optional argument Side can be used to specify which weak Bruhat order to use. The current options are "left" and "right" (default).

i7 : weakBruhatOrder(p, q, Side=>"left")

o7 = false

We can use these orders to construct the poset of $\mathfrak{S}_n$ using the Posets package. The symmetricGroupPoset method constructs the poset of $\mathfrak{S}_n$ with the Bruhat order for convenience.

i8 : P = symmetricGroupPoset(4, strongBruhatOrder)

o8 = P

o8 : Poset

i9 : Q = symmetricGroupPoset(4, weakBruhatOrder)

o9 = Q

o9 : Poset

This allows us to verify, for example, that the weak Bruhat order is rank-symmetric and Sperner [GG20].

i10 : rankPoly = rankGeneratingFunction Q

       6     5     4     3     2
o10 = q  + 3q  + 5q  + 6q  + 5q  + 3q + 1

o10 : ZZ[q]

i11 : coeffs = apply(flatten entries (coefficients rankPoly)#1, k -> sub(k, ZZ))

o11 = {1, 3, 5, 6, 5, 3, 1}

o11 : List

i12 : d = (degree rankPoly)#0

o12 = 6

i13 : all(apply(#coeffs // 2, i -> coeffs#i == coeffs#(d-i)))

o13 = true

i14 : isSperner P

o14 = true

References

[BB05] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005
[GG20] Christian Gaetz and Yibo Gao, The weak Bruhat order on the symmetric group is Sperner, Sém. Lothar. Combin. 82B (2020), Art. 35, 8 pp.

The source of this document is in Permutations/Documentation/packageDocs.m2:344:0.