Term rewriting on nestohedra

Abstract

We define term rewriting systems on the vertices and faces of nestohedra, and show that the former are confluent and terminating. While the associated posets on vertices generalize Barnard--McConville's flip order for graph-associahedra, the preorders on faces generalize the facial weak order for permutahedra and the generalized Tamari order for associahedra. Moreover, we define and study contextual families of nestohedra, whose local confluence diagrams satisfy a certain uniformity condition. Among them are associahedra and operahedra, whose associated proofs of confluence for their rewriting systems reproduce proofs of categorical coherence theorems for monoidal categories and categorified operads.

28 pages, 2 figures, 1 table. New order on vertices of nestohedra which recovers the facial weak order and generalized Tamari order as special cases. Minor corrections and improved exposition, to appear in Proceedings of the CATMI 2023 conference