The Syntax of Polytopal Projections: From Permutohedra to Associahedra

Miloš Adžić, Filip D. Jevtić · 2026

Read The Syntax of Polytopal Projections: From Permutohedra to Associahedra by Miloš Adžić, Filip D. Jevtić (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25229.txt.

Introduction

Miloš Adžić and Filip Jevtić give a syntactic account of two maps that turn orderings into branching trees. Tonks' projection and the Loday-Ronco map each turn a permutation into a flat binary tree. The pair traces both maps to distinct codes inside one equational calculus. The vertex form of Tonks' map comes from a head-insertion code run on the reversed ordering. The Loday-Ronco map instead comes from a decreasing code. A local proof closes the paper, showing Tonks' vertex map preserves order between two classic orderings.

Catalog record

CREATORMiloš Adžić, Filip D. Jevtić
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52011
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.25229

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Syntax of Polytopal Projections: From Permutohedra to Associahedra Miloš Adžić, Filip D. Jevtić Abstract Tonks’ projection from the permutohedron to the associahedron and the Loday–Ronco map both send permutations to planar binary trees. We give a syntactic account of these maps in the equational calculus of the free non-symmetric, non-unital operad on one binary generator. The vertex restriction of Tonks’ projection is obtained by evaluating the head-insertion encoding on the reversed permutation, while the Loday–Ronco map is obtained by evaluating the decreasing encoding. We also give a local operadic proof that Tonks’ vertex map is order-preserving from the weak Bruhat order to the Tamari order. 1 Introduction The associahedron and the permutohedron are among the central objects of the theory of polytopes, and beyond. In this paper we consider the associahedron \mathcal{K}^{n+1} and the permutohedron \mathcal{P}^{n} , which in our indexing convention both have dimension n-1 . They belong to the broader family of nestohedra, equivalently hypergraph polytopes (see [ 2 ] ). A classical connection between them is given by Tonks’ [ 5 ] cellular quotient map \theta:\mathcal{P}^{n}\longrightarrow\mathcal{K}^{n+1}. Its restriction to vertices yields a map \phi from permutations to (planar) binary trees. A closely related map \psi , again from permutations to binary trees, was introduced by Loday–Ronco [ 3 ] in their study of dendriform algebras: \psi:\mathfrak{S}_{n}\longrightarrow\mathbb{Y}_{n} Figure 1 : The upper hexagon is the right and the lower hexagon is the left weak Bruhat order on \mathfrak{S}_{3} . Tonks’ map \phi collapses the edge 132\text{--}312 , while the Loday–Ronco map \psi collapses 132\text{--}231 to the same binary tree. In both cases, the quotient is the Tamari order on \mathbb{Y}_{3} . Figure 1 shows the smallest nontrivial case of Tonks’ and Loday–Ronco’s maps at the level of vertices. We describe both \phi and \psi in the equational calculus \mathcal{I} of Došen and Petrić [ 1 ] , which axiomatises the free non-symmetric, non-unital operad on one binary generator. The two maps arise from indexed operadic terms: head-insertion for Tonks’ map and decreasing insertion for the Loday–Ronco map. The same syntax also gives a local proof of order preservation for Tonks’ map. 2 Preliminaries In this section we give a rigorous definition of Tonks’ cellular quotient map \theta:\mathcal{P}^{n}\longrightarrow\mathcal{K}^{n+1} , and Loday–Ronco map \psi:\mathfrak{S}_{n}\longrightarrow\mathbb{Y}_{n} . To that end, we set up some conventions and recall some facts of combinatorics. Let [0]=\emptyset and [n]=\{1,\dots,n\} for n\geqslant 1 . Let \mathfrak{S}_{n} denote the symmetric group on [n] , with its elements given in one-line notation; in particular, \mathfrak{S}_{0}=\{\emptyset\} . For n>0 , let \mathbb{Y}_{n} denote the set of binary trees with n internal nodes, equivalently with n+1 leaves, and let \mathbb{Y}_{0}=\{\ast\} , where \ast denotes the trivial tree with a single vertex. Binary trees can be grafted: for T_{1}\in\mathbb{Y}_{p} and T_{2}\in\mathbb{Y}_{q} , let T_{1}\vee T_{2}\in\mathbb{Y}_{p+q+1} be the tree obtained by attaching T_{1} and T_{2} as the left and right subtrees of a new root, respectively. Throughout the paper we use the convention that the (n-1) -dimensional permutohedron \mathcal{P}^{n} has vertex set \mathfrak{S}_{n} , while the (n-1) -dimensional associahedron \mathcal{K}^{n+1} has vertex set \mathbb{Y}_{n} . Thus the shift in the notation for \mathcal{K}^{n+1} reflects the indexing of binary trees by their number of leaves. For a finite word a=a_{1}\cdots a_{k} of distinct integers, its standardization \mathrm{std}(a)\in\mathfrak{S}_{k} is obtained by replacing the smallest letter of a by 1 , the second smallest by 2 , and so on, while preserving relative order. If a=\emptyset , we set \mathrm{std}(\emptyset)=\emptyset\in\mathfrak{S}_{0} . For a word a=a_{1}\cdots a_{k} , let w(a)=a_{k}\cdots a_{1} denote its reversal . For 1\leqslant t\leqslant k , write a_{\leqslant t}=a_{1}\cdots a_{t} for a prefix of the word a of length t . Given a word a=a_{1}\cdots a_{k} of distinct integers and an integer x , let a^{<x} denote the subsequence of entries of a that are strictly less than x , and let a^{>x} denote the subsequence of entries of a that are strictly greater than x . These subsequences are taken in the original left-to-right order and may be empty. For \pi=\pi_{1}\cdots\pi_{n}\in\mathfrak{S}_{n} , an inversion of \pi is a pair (i,j) with 1\leqslant i<j\leqslant n and \pi_{i}>\pi_{j} . We write \ell(\pi) for the number of inversions of \pi . The (right) weak Bruhat order \leqslant_{B} on \mathfrak{S}_{n} is the partial order generated by the covering relations \pi\lessdot_{B}\pi s_{i}, where s_{i}=(i,i+1) is the adjacent transposition and \ell(\pi s_{i})=\ell(\pi)+1 . Equivalently, \pi\lessdot_{B}\pi s_{i}\quad\text{if and only if}\quad\pi_{i}<\pi_{i+1}, since right multiplication by s_{i} swaps the entries in positions i and i+1 . For example, in Figure 1 , the weak Bruhat cover 132\lessdot_{B}312 is collapsed by \phi to a single tree in \mathbb{Y}_{3} . The (left) weak Bruhat order is defined analogously using left multiplication: its covers replace \pi with s_{i}\pi whenever \ell(s_{i}\pi)=\ell(\pi)+1 . In one-line notation this swaps i and i+1 , and the length increases exactly when i appears to the left of i+1 . Thus Figure 1 also shows that the left weak order cover from 132 to 231 is collapsed by the Loday–Ronco map. In the remainder of the paper, we will use “weak order” to mean “right weak order”. The set \mathbb{Y}_{n} has cardinality equal to the n -th Catalan number C_{n}=\frac{1}{n+1}\binom{2n}{n} . It is partially ordered by the Tamari order \leqslant_{T} , generated by the local rotation ((X,Y),Z)\longrightarrow(X,(Y,Z)), where X , Y , and Z are binary trees, and the rotation may occur at any subtree. 2.1 The Loday–Ronco map Definition 2.1 . We define \psi recursively. For the empty permutation \emptyset , let \psi(\emptyset)=\ast\in\mathbb{Y}_{0} . Let \pi=\pi_{1}\cdots\pi_{n}\in\mathfrak{S}_{n} with n>0 , and let k be the unique index such that \pi_{k}=n . Define \pi_{L}=\pi_{1}\cdots\pi_{k-1},\qquad\pi_{R}=\pi_{k+1}\cdots\pi_{n}. Then \psi(\pi)=\psi(\mathrm{std}(\pi_{L}))\vee\psi(\mathrm{std}(\pi_{R})). Example 2.1 . Let \pi=2413 . The maximum entry is 4 , occurring in position 2 . Thus, \pi_{L}=2 and \pi_{R}=13 , so \psi(2413)=\psi(\mathrm{std}(2))\vee\psi(\mathrm{std}(13))=\psi(1)\vee\psi(12). Now \psi(1)=\psi(\emptyset)\vee\psi(\emptyset),\qquad\psi(12)=\psi(1)\vee\psi(\emptyset). Hence \psi(2413) is the binary tree shown below, obtained by grafting the tree \psi(1) to the left of the root and the tree \psi(12) to the right. 2.2 Tonks’ Quotient Map Combinatorially, the faces of \mathcal{P}^{n} are indexed by ordered partitions of [n] , while the faces of \mathcal{K}^{n+1} are indexed by planar rooted trees with n+1 leaves. At the level of vertices, ordered partitions reduce to permutations and planar rooted trees reduce to planar binary trees. Since only this vertex-level restriction is used below, we pass to the induced map \phi:\mathfrak{S}_{n}\longrightarrow\mathbb{Y}_{n} . Definition 2.2 . Let \pi=\pi_{1}\cdots\pi_{n}\in\mathfrak{S}_{n} , and let (\pi_{i},\pi_{i+1})=(a,b) be a pair of entries in adjacent positions. We say that (a,b) is Tonks-independent if there exists an index j>i+1 such that \min(a,b)<\pi_{j}<\max(a,b). Equivalently, (a,b) is Tonks-independent if and only if some entry to the right of the pair has value strictly between a and b . Remark 2.3 . Tonks defines independence more generally for adjacent blocks A_{k-1},A_{k} in an ordered partition (A_{1},\dots,A_{m}) . In that setting, the condition is that some element of a block strictly to the right of A_{k} lie strictly between the minimum and the maximum of A_{k-1}\cup A_{k} . For vertices, where all blocks are singletons, this reduces to Definition 2.2 . Let \sim be the equivalence relation on \mathfrak{S}_{n} generated by the elementary moves that replace a permutation \pi by a permutation \rho obtained from \pi by swapping a

Read the complete text