Stasheff polytope as a sublattice of permutohedron

Abstract

An assosiahedron Kn, known also as Stasheff polytope, is a multifaceted combinatorial object, which, in particular, can be realized as a convex hull of certain points in Rn, forming (n − 1)-dimensional polytope1. A permutahedron Pn is a polytope of dimension (n−1) in Rn with vertices forming various permutations of n-element set. There exists well-known orderings of vertices of Pn and Kn that make these objects into lattices: the first known as permutation lattices, and the latter as Tamari lattices. We provide a new proof to the statement that the vertices of Kn can be naturally associated with particular vertices of Pn in such a way that the corresponding lattice operations are preserved. In lattices terms, Tamari lattices are sublattices of permutation lattices. The fact was established in 1997 in paper by Bjorner and Wachs, but escaped the attention of lattice theorists. Our approach to the proof is based on presentation of points of an associahedron Kn via so-called bracketing functions. The new fact that we establish is that the embedding preserves the height of elements