Permutation Lattices Revised


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.


Computer Science

Keywords and Phrases

Join-pseudocomplement; lattice; Meet-semidistributive; Permutation

International Standard Serial Number (ISSN)


Document Type

Article - Journal

Document Version


File Type





© 1994 Springer Verlag, All rights reserved.