The equational theory of the weak order on finite symmetric groups - Laboratoire d'informatique fondamentale de Marseille Accéder directement au contenu
Article Dans Une Revue Journal of the European Mathematical Society Année : 2018

The equational theory of the weak order on finite symmetric groups

Résumé

It is well-known that the weak Bruhat order on the symmetric group on a finite number n of letters is a lattice, denoted by P(n) and often called the permutohedron on n letters, of which the Tamari lattice A(n) is a lattice retract. The equational theory of a class of lattices is the set of all lattice identities satisfied by all members of that class. We know from earlier work that the equational theory of all P(n) is properly contained in the one of all A(n). We prove the following results. Theorem I. The equational theory of all P(n) and the one of all A(n) are both decidable. Theorem II. There exists a lattice identity that holds in all P(n), but that fails in a certain 3338-element lattice. Theorem III. The equational theory of all extended permutohedra, on arbitrary (possibly infinite) posets, is trivial. In order to prove Theorems I and II, we reduce the satisfaction of a given lattice identity in a Cambrian lattice of type A to a certain tiling problem on a finite chain. Theorem I then follows from Büchi's decidability theorem for the monadic second-order theory MSO of the successor function on the natural numbers. It can be extended to any class of Cambrian lattices of type A with MSO-definable set of orientations.
Fichier principal
Vignette du fichier
N5B32.pdf (1.05 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00986148 , version 1 (05-05-2014)
hal-00986148 , version 2 (24-09-2014)

Identifiants

Citer

Luigi Santocanale, Friedrich Wehrung. The equational theory of the weak order on finite symmetric groups. Journal of the European Mathematical Society, 2018, 20 (8), pp.1959--2003. ⟨10.4171/JEMS/804⟩. ⟨hal-00986148v2⟩
514 Consultations
266 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More