Weak order of permutations

From Wikipedia, the free encyclopedia

In mathematics, the symmetric group, S_n, has a poset structure given by the weak order of permutations, given by u≤v if Inv(u) is a subset of Inv(v). Here Inv(u) is the set of inversions of u, defined as the set of ordered pairs (i, j) with

1 ≤ i < j ≤ n

and

u(i) > u(j).

The edges of the Hasse diagram of the order are given by permutations u and v such that

u < v

and v is obtained from u by interchanging two consecutive values of u.

The identity permutation is the minimum element of S_n.

Moreover, S_n is a lattice with this order.