×

The equational theory of the weak Bruhat order on finite symmetric groups. (English) Zbl 1450.06001

The weak Bruhat order on the symmetric group \(S_n\) is a lattice \(\mathsf{P}(n)\) called the permutohedron on \(n\) letters. The Tamari lattice \(\mathsf{A}(n)\) is a lattice retract of \(\mathsf{P}(n)\). Given a poset \(E\), there is an ‘extended permutahedron’ lattice defined from \(E\) denoted \(\mathsf{R}(E)\).
The main results of this important paper are:
A. The class of all \(\mathsf{P}(n)\) has a decidable equational theory.
B. The class of all \(\mathsf{A}(n)\) has a decidable equational theory.
C. There is a lattice identity that holds in all \(\mathsf{P}(n)\) but fails in some \(3,338\)-element lattice.
D. Any finite meet-semidistributive lattice embeds in \(\mathsf{R}(E)\) for some countable poset \(E\). (The poset \(E\) for this embedding can always be taken to be the directed union of finite dismantlable lattices.) In particular, the class of all \(\mathsf{R}(E)\) generates the variety of all lattices.

MSC:

06B20 Varieties of lattices
03C85 Second- and higher-order model theory
06A07 Combinatorics of partially ordered sets
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B10 Lattice ideals, congruence relations
06B25 Free lattices, projective lattices, word problems
20B30 Symmetric groups
PDF BibTeX XML Cite
Full Text: DOI