The -weak order and -permutahedra I: combinatorics and lattice structure
arXiv:2212.11556 · doi:10.1137/23M1605818
Abstract
This is the first contribution of a sequence of papers introducing the notions of -weak order and -permutahedra, certain discrete objects that are indexed by a sequence of non-negative integers . In this first paper, we concentrate purely on the combinatorics and lattice structure of the -weak order, a partial order on certain decreasing trees which generalizes the classical weak order on permutations. In particular, we show that the -weak order is a semidistributive and congruence uniform lattice, generalizing known results for the classical weak order on permutations. Restricting the -weak order to certain trees gives rise to the -Tamari lattice, a sublattice which generalizes the classical Tamari lattice. We show that the -Tamari lattice can be obtained as a quotient lattice of the -weak order when has no zeros, and show that the -Tamari lattices (for arbitrary ) are isomorphic to the -Tamari lattices of Préville-Ratelle and Viennot. The underlying geometric structure of the -weak order will be studied in a sequel of this paper, where we introduce the notion of -permutahedra.
37 pages, 17 figures