Discrete Mathematics & Theoretical Computer Science, Vol 3, No 4 (1999)

Font Size:  Small  Medium  Large

A characterization for all interval doubling schemes of the lattice of permutations

Nathalie Caspard

Abstract


The lattice Sn of all permutations on a n-element set has been shown to be bounded [CAS], which is a strong constructive property characterized by the fact that Sn admits what we call an interval doubling scheme. In this paper we characterize all interval doubling schemes of the lattice Sn, a result that gives a nice precision on the bounded nature of the lattice of permutations. This theorem is a direct corollary of two strong properties that are also given with their proofs.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page