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

Nathalie Caspard, CERMSEM

Résumé. Il a été prouvé que le treillis S_n de toutes les permutations sur un ensemble de cardinalité n est borné [5], ce qui est une propriété constructive forte caractérisée par le fait que S_n possède ce qu'on appelle un schéma de duplication d'intervalle. Dans ce papier, nous caractérisons tous les schémas de duplication d'intervalle du treillis S_n. Ce résultat donne une précision constructive supplémentaire sur la nature bornée du treillis des permutations. Pour démontrer ce théorème, nous utilisons et prouvons une propriété importante de la relation d'ordre entre les éléments sup-irréductibles de S_n.
Mots clés : A-table, extension linéaire, permutation, relations flèche, schéma de duplication d'intervalle, tableaux, treillis, treillis borné.

Abstract. The lattice S_n of all permutations on a n-element set has been shown to be bounded [5], which is a strong constructive property characterized by the fact that S_n admits what we call an interval doubling scheme. In this paper we characterize all interval doubling schemes of the lattice S_n. This result gives a nice precision on the bounded nature of the lattice of permutations. To prove this theorem, we use and prove an important property of the order relation between all join-irreducible elements of S_n.
Keywords : Arrow relations, A-table, interval doubling schemes, lattice, bounded lattice, linear extension, permutation, tableaux.

JEL Classification : C60.