This paper shows how to compute efficiently meets and joins of permutations. The algorithms presented here have a worst case time of O(N2) and a space requirement of O(N). The paper discusses how to adapt these algorithms for computing the meets and joins in the Newman commutativity lattices of Bennett and Birkhoff (1990).
Every element in the lattice of n-element permutations, Sn, has a complement; see, for example, Bennett and Birkhoff (1990). Since Sn is semidistributive (Duquenne and Cherfouh, 1991), it is also pseudocomplemented. As shown by Chameni-Nembua and Monjardet (1992, 1993) the complements of an element, x, in a complemented and pseudocomplemented lattice form an interval with the top element being the meet-pseudocomplement of x,x,*, while the bottom element is the join-pseudocomplement of x,x†. This paper describes how to compute x* and x†.
The material developed in this paper is used to prove a result of Björner that the automorphism group of Sn for n≥3 consists of exactly 2 elements. The group of automorphisms and dual automorphisms of Sn is the Klein, 4-group. Finally, the poset of irreducibles for Sn is characterized.