[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

## `combinat::permutations::leequalBruhat` -- Bruhat order on standard permutations

#### Introduction

Functions related to the Bruhat order on permutations.

#### Details

- The Bruhat order is a partial order defined on the elements of a given symmetric group, that is, on the permutations of a given size.

- A permutation p1 is smaller than a permutation p2 if and only if one of the reduced words of p1 is a subsequence (the chosen letters do not have to be consecutive) of one of the reduced word of p2.

- The Bruhat order is the transitive closure of the following relation: p1 is smaller than p2 if p2 is obtained by multiplying p1 to the left or to the right by a transposition in such a way that it increases its number of inversions.

#### Method leequalBruhat: Test of the order relation of two permutations

- `leequalBruhat(standard permutations p1, p2)`

- Returns the boolean answering the question ''Is `p1` smaller than `p2` in the Bruhat order?''

#### Method bruhatInversions: list of inversions in the Bruhat order

- `bruhatInversions(standard permutation p)`

- Returns the list of inversions of `p` such that the application of this inversion to `p` decrements its number of inversions.

- Equivalently, it returns the list of pairs (i,j), i<j such that p(i)>p(j) and such that there exists no k between i and j satisfying p(i)>p(k)>p(j).

#### Method predBruhat: list of the precedessors of a permutation

- `predBruhat(standard permutation p)`

- Returns the list of permutations strictly smaller than `p` in the Bruhat order, such that there is no permutation between one of those and `p`.

#### Method succBruhat: list of the successors of a permutation

- `succBruhat(standard permutation p)`

- Returns the list of permutations strictly greater than `p` in the Bruhat order, such that there is no permutation between `p` and one of those.

#### Method smallerBruhat: list of the permutations smaller than a permutation

- `smallerBruhat(standard permutation p)`

- Returns the list of permutations smaller than or equal to `p` in the Bruhat order.

#### Method greaterBruhat: list of the permutations greater than a permutation

- `greaterBruhat(standard permutation p)`

- Returns the list of permutations greater than or equal to `p` in the Bruhat order.

#### Example 1

To check whether a permutation is smaller than another thanks to the Bruhat order, you can call:

    >> combinat::permutations::leequalBruhat([2,4,3,1],[3,4,2,1]);

                                       TRUE

You can ask for the inversions of a given permutation by:

    >> combinat::permutations::bruhatInversions([6, 1, 4, 5, 2, 3])

             [{1, 2}, {1, 3}, {1, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}]

Applying those inversions to the previous permutation, you exactly get the permutations preceding it as you can check with

    >> combinat::permutations::predBruhat([6, 1, 4, 5, 2, 3])

          [[1, 6, 4, 5, 2, 3], [4, 1, 6, 5, 2, 3], [5, 1, 4, 6, 2, 3],

             [6, 1, 2, 5, 4, 3], [6, 1, 3, 5, 2, 4], [6, 1, 4, 2, 5, 3],

             [6, 1, 4, 3, 2, 5]]

Now, you can compute the transitive ideal generated by the predecessor relation and get (on the previous example, the answer is one page long)

    >> combinat::permutations::smallerBruhat([4, 1, 2, 3])

          [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3],

             [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [4, 1, 2, 3]]

What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:

    >> combinat::permutations::succBruhat([6, 1, 4, 5, 2, 3]);
       combinat::permutations::greaterBruhat([4, 1, 2, 3])

          [[6, 4, 1, 5, 2, 3], [6, 2, 4, 5, 1, 3], [6, 1, 5, 4, 2, 3],

             [6, 1, 4, 5, 3, 2]]

          [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3],

             [4, 1, 3, 2], [4, 1, 2, 3]]

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package