Permutation Lattices Revised
Abstract
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.
Recommended Citation
G. Markowsky, "Permutation Lattices Revised," Mathematical Social Sciences, vol. 27, no. 1, pp. 59 - 72, Springer Verlag, Feb 1994.
The definitive version is available at https://doi.org/10.1016/0165-4896(94)00731-4
Department(s)
Computer Science
Keywords and Phrases
Join-pseudocomplement; lattice; Meet-semidistributive; Permutation
International Standard Serial Number (ISSN)
0165-4896
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 1994 Springer Verlag, All rights reserved.
Publication Date
01 Feb 1994
