% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{10}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}


% -------------------------------------------------------------------

%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{paralist}
\usepackage{xcolor}
%\usepackage[colorlinks,cite color=blue,pagebackref=true,pdftex]{hyperref}

\usepackage{float}
\usepackage{wrapfig}

\usepackage{graphicx}

\usepackage{cleveref}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conjecture}[thm]{Conjecture}
                                                                                                                
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{problem}[thm]{Problem}


%\newcommand\note[1]{\textbf{\color{red}#1}}

\newcommand{\Def}[1]{\textbf{#1}} 
\newcommand\ov[1]{\overline{#1}}%

\newcommand{\1}{\mathbf{1}}%
\newcommand{\eps}{\varepsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rnn}{\R_{\ge 0}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Znn}{\Z_{\ge 0}}

\newcommand\wt{w}%

\newcommand\colpat{\widetilde{\arb}}%

\newcommand\SymGrp{\mathfrak{S}}%

\newcommand\PP{\Pi}%
\newcommand\PPGKZ{\psi}%

\renewcommand\L{\mathcal{L}}%
\renewcommand{\emptyset}{\varnothing}
\renewcommand\AA{\mathbb{A}}%

\DeclareMathOperator{\argmax}{argmax}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\conv}{conv}

\newcommand\PS[1][m-1,n-1]{P_{#1}}%
\newcommand\PSV{V_{m,n}}%
\newcommand\PSVo{V^\circ_{m,n}}%

\newcommand\inner[1]{\langle {#1} \rangle}%
\newcommand\arb{\mathcal{A}}%
\newcommand\vopt{v_{\mathrm{opt}}}%
\newcommand\Ass[1][n-2]{\mathrm{Asso}_{#1}}%

\newcommand\Simp[1][n-1]{\Delta_{#1}}%
\newcommand\arbA{\arb_1}%
\newcommand\arbAA{\arb_2}%
\newcommand\br{\mathcal{B}}%

% -------------------------------------------------------------------


%% define your title in the usual way
\title{From linear programming to colliding particles}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[A.~Black, N.~L\"utjeharms \and R.~Sanyal]{\texorpdfstring{%
Alexander E. Black%
\thanks{\href{mailto:alexander.black@math.ethz.ch}{alexander.black@math.ethz.ch}. Alexander E.
Black was supported by the NSF GRFP and NSF DMS-1818969.}%
\addressmark{1},
Niklas L\"utjeharms\addressmark{2}, \and 
Raman Sanyal\thanks{\href{mailto:sanyal@math.uni-frankfurt.de}{sanyal@math.uni-frankfurt.de}}\addressmark{2}
}{%
Alexander E. Black%
%
,
Niklas L\"utjeharms, and 
Raman Sanyal
}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1} Institute for Mathematical Research, ETH Z\"{u}rich, Switzerland\\ 
\addressmark{2} Institut f\"ur Mathematik,
Goethe-Universit\"at Frankfurt, Frankfurt am Main, Germany}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Although simplices may appear trivial in the context of linear optimization, the
simplex algorithm, guided by a pivot rule, can exhibit remarkably intricate
dynamics on them when solving linear programs. In this paper we study the
behavior of max-slope pivot rules on (products of) simplices and describe the
associated pivot rule polytopes. For simplices, the pivot rule polytopes are
combinatorially isomorphic to associahedra. To prove this correspondence, we
interpret max-slope pivot rules in terms of the combinatorics of colliding
particles on a line. For prisms over simplices, we recover Stasheff's
multiplihedra. For products of two simplices we get new realizations of
constrainahedra, that capture the combinatorics of certain particle systems in
the plane.
}


%% put your keywords here, or comment this out if you don't have them yet
\keywords{linear programming, geometry of pivot rules, particle collisions,
associahedra, multiplihedra, constrainahedra} % 3-6 keywords

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{short.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{sec:intro}

A linear program (LP) is an optimization problem of the form
\[
    \begin{array}{lr@{\,+\,}c@{\,+\,}r@{\,}l}
    \text{maximize}  &  c_1x_1 & \cdots & c_nx_n  \\
    \text{subject to}  &  a_{i1} x_1 & \cdots & a_{in} x_n & \ \le \ b_i \quad
    \text{ for } i=1,\dots,N \, .
\end{array}
\]
Geometrically, the set $P \subset \R^n$ of feasible solutions is a polyhedron
and a generic objective function $c = (c_1,\dots,c_n)$ induces an orientation on
the vertex-edge graph $G(P)$ of $P$. The orientation is acyclic with a unique
sink at the optimal vertex $\vopt$. The simplex algorithm starts at a given
vertex $v$ of $P$ and proceeds along directed edges to $\vopt$.  The choice of
which edges to pursue is governed by a pivot rule.

A polytope $P \subset \R^n$ is a \emph{simplex} if its vertices are affinely
independent. Simplices are trivial from an optimization viewpoint as any two
vertices of $P$ are adjacent. However, sophisticated algorithms such as the
simplex algorithm can exhibit complex and interesting dynamics on trivial
instances. In this paper, we describe a beautiful and unexpected connection
between the behavior of certain pivot rules on (products of) simplices and the
combinatorics of colliding particles.

A pivot rule is memory-less if the decisions it makes on a linear program
$(P,c)$ are captured by an arborescence (or rooted tree) on $G(P)$; see, for
example, beginning of \Cref{sec:simplices}. With De Loera, in~\cite{PivPoly} we
studied families of memory-less pivot rules that are parametrized by weight
vectors $\wt$. We showed that for any linear program $(P,c)$ there is a polytope
$\PP(P,c)$, the \emph{pivot rule polytope}, whose vertices correspond to the
arborescences of $(P,c)$ induced by the family of pivot rules.  The facial
structure of $\PP(P,c)$ reflects the relation between the different rules on
$(P,c)$.  For the \emph{max-slope} pivot rule, a generalization of the shadow
vertex algorithm of Gass and Saaty~\cite{GassSaaty} that we introduced
in~\cite{PivPoly}, we were surprised to observe that the numbers of max-slope
arborescences for simplices are given by the Catalan numbers.  Much of the
combinatorics surrounding the Catalan numbers is famously embodied by the
\Def{associahedron} $\Ass[n-2]$, a certain partially ordered set that is
ubiquitous in geometric and algebraic combinatorics. There are many different
realizations of $\Ass[n-2]$ as the face lattice of a simple $(n-2)$-dimensional
polytope (see \cite{CeballosSantosZiegler}) and the present paper adds a new
construction to the list.

\begin{thm}\label{thm:main_asso}
    Let $P$ be an $(n-1)$-dimensional simplex and $c$ a generic objective
    function. Then the max-slope pivot rule polytope $\PP(P,c)$ is
    combinatorially isomorphic to the $(n-2)$-dimen\-sional associahedron
    $\Ass$.
\end{thm}

Associahedra describe the combinatorics of colliding particles. Consider $n$
distinct and ordered particles on the real line.  Particles move, collide, and
merge until there is a single particle left. The various collisions can be
time-independently recorded by a \emph{bracketing}. For example $(12)(345)$
states that at some point particles $1$ and $2$ collided and, before or after,
$3,4$, and $5$ simultaneously collided. Eventually, the two remaining particles
collided. The associahedron $\Ass$ is the set of bracketings of $123\dots n$
partially ordered by refinement. In order to prove \Cref{thm:main_asso}, we
describe a geometric correspondence between max-slope arborescences and
bracketings. For that, the objective function $c$ gives rise to velocities for
the $n$ particles and the weights $\wt$ give each particle a location at time
$t=0$. For $t >0$, the particles start to move from their locations at constant
velocity. If two particles collide, the slower particle is absorbed by the
faster one, which continues at its original velocity.  For $t \gg 0$, only
particle $n$ is left. We record the particle $\arb(i)$ that absorbs the particle
$i$.  Towards a proof of \Cref{thm:main_asso}, we show that these maps $\arb$,
called \emph{collision patterns}, are in bijection with bracketings and are
precisely the max-slope arborescences of an $(n-1)$-simplex with objective
function~$c$.


Bottman and Poliakova~\cite{BottmanPoliakova} studied a more general setup for
particle collisions. For $m,n \ge 1$, they consider $m \cdot n$ particles
sitting at the intersections of $m$ horizontal and $n$ vertical lines in the
plane.  The particles are allowed to move horizontally or vertically but they
must retain their colinearities. The collisions can be recorded by
\emph{rectangular brackets} or, equivalently, by a partially ordered set on
the (spaces between) the horizontal and vertical lines. The resulting poset of
rectangular bracketings is called the \Def{constrainahedron} $C(m,n)$. For
$m=1$, this is the associahedron. For $m=2$, $C(2,n)$ is isomorphic to the
\emph{multiplihedron}, a poset first described by
Stasheff~\cite{Stasheff-book} and realized as a polytope by
Forcey~\cite{Forcey}. It is shown in~\cite{BottmanPoliakova}, that $C(m,n)$ is
the face poset of a generalized permutahedron~\cite{GenPermOrig}. Chapoton and
Pilaud~\cite{ChapotonPilaud} introduced a remarkable operation on products of
generalized permutahedra, called \emph{shuffle products}, and gave a different
realization of $C(m,n)$ as the shuffle product of Loday associahedra.  We give
new realizations of constrainahedra that, in particular, are not generalized
permutahedra.

\begin{thm}\label{thm:constrainahedron}
    Let $\PS$ be the product of an $(m-1)$-simplex and an $(n-1)$-simplex and
    let $c$ be a generic objective function. Then the max-slope pivot rule
    polytope $\PP(\PS,c)$ is combinatorially isomorphic to the
    $(m,n)$-constrainahedron $C(m,n)$.
\end{thm}

The combinatorial construction of constrainahedra was motivated by questions in
homotopical algebra~\cite{poliakova-thesis} as well as Gromov compactifications
of configuration spaces. More precisely, Bottman~\cite{bottman} constructed
\emph{$2$-associahedra} as posets capturing the behavior of ordered particles on
parallel lines in the plane without colinearities. Bottman asked in Section 1.3
of \cite{bottman} whether $2$-associahedra are face posets of convex polytopes
and notes in particular that a connection to fiber polytopes would be especially
interesting and could lead to an interpretation in terms of Fukaya categories.
In~\cite{PivPoly} it is highlighted that max-slope pivot rule polytopes are
generalizations of monotone path polytopes, which are fiber polytopes.  We hope
that our results provide a new point of view on the realizability of
$2$-associahedra.

Our techniques generalize to higher products of simplices. 

\begin{thm}\label{thm:multi_multiplihedron}
    Let $(\AA,\cdot)$ be a non-associative monoid and let $f_1,\dots, f_k : \AA
    \to \AA$ be morphisms. The vertices of the max-slope pivot polytope of the
    Cartesian product of an $(n-1)$-dimensional simplex and a $k$-dimensional
    cube are in bijection with the possible ways of evaluating 
    \[
        (f_{\sigma(1)} \circ f_{\sigma(2)} \circ \cdots \circ
        f_{\sigma(k)})(a_1 \cdot a_2 \cdots a_n)\, ,
    \]
    where $a_1,\dots,a_n \in \AA$ and $\sigma \in \SymGrp_k$ is a permutation.
\end{thm}

These are the vertices of the $(m,n)$-multiplihedra of~\cite{ChapotonPilaud}.
Pilaud and Poullot~\cite{germain_vincent} show that max-slope pivot rule
polytopes of higher products of simplices are isomorphic to shuffle products of
associahedra.

\acknowledgements{
We would like to thank Aenne Benjes, Jes\'{u}s De Loera, Vincent Pilaud, Dasha
Poliakova, Alex Postnikov, Germain Poullot, and Hugh Thomas for insightful
conversations. The last author would like to thank the organizers of the
workshop \emph{Combinatorics and Geometry of Convex Polyhedra}, held at the
Simons Center for Geometry and Physics, where he first learned about
constrainahedra. Many of our results would not have been discovered without the
\textsc{OEIS}~\cite{oeis} and \textsc{SageMath}~\cite{sage}. 
}

\section{Max-slope pivot rule polytopes}\label{sec:max-slope}
We recall max-slope pivot rules and pivot rule polytopes in \Cref{sec:max-slope}
and refer to~\cite{PivPoly, PivotAsso} for proofs.  Let $P \subset \R^n$ be a
convex polytope with vertices $V(P)$ and edges $E(P)$.  We call $c \in \R^n$
\Def{edge-generic} if $\inner{c,u} \neq \inner{c,v}$ for all $uv \in E$. The
vector $c$ defines an objective function $x \mapsto \inner{c,x}$ and $(P,c)$ is
a \Def{linear program} (LP).

Let $\vopt \in V(P)$ be the unique maximizer of $c$ over $P$.  A \Def{$c$-arborescence}
is a map $\arb : V(P) \setminus \vopt \to V(P)$ such that $\arb(v)$ is a
$c$-improving neighbor of $v \neq \vopt$. If $c$ is clear from the context, we
simply call $\arb$ an arborescence. Arborescences encode the behavior of
memory-less pivot rules on the linear program $(P,c)$: From a starting vertex $v
\in V(P)$, the simplex algorithm constructs a monotonically increasing path $v =
v_0v_1\dots v_m = \vopt$ in the graph of $P$ that satisfies $v_i =
\arb(v_{i-1})$ for all $i=1,\dots,m$.

The max-slope pivot rule introduced in~\cite{PivPoly} generalizes the well-known
shadow-vertex simplex algorithm. For generic $\wt \in \R^n$ we define the
\Def{max-slope} arborescence $\arb^w$ of $(P,c)$ by
\begin{equation}\label{eqn:max_slope}
    \arb^w(v) \ := \ \argmax \left\{ 
        \frac{\inner{\wt,u - v}}{\inner{c,u - v}} : uv \in E(P),  \inner{c,u} >
        \inner{c,v} \right\} \, .
\end{equation}
As the notation suggests, $\argmax$ returns the improving neighbor of $v$ that
maximizes the given quantity. In particular \emph{genericity} here means that the
maximum is attained at a unique neighbor $u$ for every vertex $v$.
A geometric interpretation for a max-slope arborescence can be given as
follows. Define the linear projection $\pi : \R^n \to \R^2$ by $\pi(x) =
(\inner{c,x},\inner{\wt,x})$. The projection of an edge $uv \in E$ to the
plane has a well-defined slope with respect to the $x$-axis and $\arb^\wt(v)$
selects the edge with maximal slope.

For a $c$-arborescence $\arb$ we define
\begin{equation}\label{eqn:GKZ}
    \PPGKZ(\arb) \ := \ \sum_{v \neq \vopt} \frac{\arb(v) - v}{\inner{c,\arb(v)
    - v}} \, .
\end{equation}
and the \Def{max-slope pivot rule polytope} of $(P,c)$ 
\[
    \PP(P,c) \ := \ \conv \big\{ \PPGKZ(\arb) : \arb \text{ $c$-arborescence
    of } (P,c) \big\} \, .
\]

This is a $(\dim(P)-1)$-dimensional polytope, that geometrically encodes the
various max-slope arborescences of $(P,c)$. For $\wt \in \R^n$ we write $Q^\wt$
for the face of $Q$ that maximizes $x \mapsto \inner{\wt,x}$.

\begin{thm}[{\cite[Theorem~1.4]{PivPoly}}]\label{thm:PP}
    Let $P$ be a polytope and $c$ an edge-generic objective function. Then $
    \PP(P,c)^\wt  =  \{ \PPGKZ(\arb^w) \}$ for every generic $\wt$.  In
    particular, the vertices of $\PP(P,c)$ are in bijection with max-slope
    arborescences of $(P,c)$.
\end{thm}


We record the following properties of max-slope pivot rule polytopes.
\begin{cor} \label{cor:PP_inv}
    Let $P \subset \R^n$ be a polytope and $c$ an edge-generic objective
    function.
    \begin{compactenum}[\rm (i)]
        \item Let $\wt \in \R^n$ be generic and $\alpha \in \R$. Then $\arb^{\wt
            + \alpha c} = \arb^\wt$.
        \item If $h \in \R^n$ such that $x \mapsto \inner{h,x}$ is constant on
            $P$, then $\PP(P, c + h) = \PP(P,c)$.
        \item For any $b \in \R^n$, $\PP(P + b, c) = \PP(P,c)$.
        \item If $T$ is an invertible linear transformation, then
            $\Pi(TP,(T^{-1})^tc)  \ = \ T\Pi(P,c)$.
    \end{compactenum}
\end{cor}


\section{Max-slope pivot rules on simplices}\label{sec:simplices}

Let $P$ be an $(n-1)$-dimensional simplex and $c$ an edge-generic objective
function. By \Cref{cor:PP_inv} we can assume that $P$ is the standard simplex
$\Simp  :=  \conv( e_1, \dots, e_n )$ in $\R^n$ and that $c_1 < c_2 < \cdots
< c_n$. 


For $n \ge 1$, we write $[n] := \{1,2,\dots,n\}$. Since $\Simp$ has a complete
graph, every vertex $e_j$ with $j > i$ is a $c$-improving neighbor of $e_i$.
Thus, arborescences of $(\Simp,c)$ bijectively correspond to maps $\arb : [n-1]
\to [n]$ such that $\arb(i) > i$ for all $i$. Since every vertex can choose an
improving neighbor independently, there are exactly $(n-1)!$ arborescences of
$(\Simp,c)$. For the tetrahedron, it turns out that of the six arborescences
only five are max-slope arborescences and the figure prompts the following
definition:

\begin{center}
    \includegraphics[width=\textwidth]{imgs/tetrahedron.pdf}
\end{center}

\begin{defn}[Noncrossing arborescence]
    An arborescence $\arb : [n-1] \to [n]$ is \Def{noncrossing} if  $\arb(j) \le
    \arb(i)$ for all $1 \le i < j < n$ with $j < \arb(i)$.
\end{defn}

\begin{thm}\label{thm:noncross}
    Let $\arb : [n-1] \to [n]$ be an arborescence. Then $\arb$ is a max-slope
    arborescence for $(\Simp,c)$ if and only if $\arb$ is noncrossing.
\end{thm}

For the proof, we use a canonical decomposition of noncrossing arborescences;
see \Cref{fig:noncross}.

\begin{figure}[ht]
    \begin{center}
    \includegraphics[height=1.5cm]{imgs/noncross-ex2.pdf}
    \end{center}
    \caption{A noncrossing arborescence on $7$ nodes. $r=4$ is minimal with
    $\arb(r) = 7$. The decomposition into $\arbA,\arbAA$ is obtained by
    restricting to $1,\dots,4$ and $5,\dots,7$.  The nodes $1,3,5$ are
    leaves and they are all immediate leaves.}
    \label{fig:noncross}
\end{figure}

\begin{lem}\label{lem:decomp}
    Let $\arb : [n-1] \to [n]$ be a noncrossing arborescence on $n \ge 2$
    nodes.  Let $r$ be minimal with $\arb(r) = n$. Then $\arbA : [r-1] \to
    [r]$ given by $\arbA(i) := \arb(i)$ for $i < r$ and $\arbAA : [n-r-1] \to
    [n-r]$ given by $\arbAA(i) := \arb(r+i) - r$ are noncrossing
    arborescences.  Moreover, $\arb$ is uniquely determined by
    $(\arbA,\arbAA)$.
\end{lem}

It follows from \Cref{lem:decomp} that the number of vertices is the Catalan
number $C_n$: there is a bijection taking a noncrossing arborescence $\arb$ on
$n$ nodes to a pair of noncrossing arborescences $(\arb_1,\arb_2)$ of sizes $r$
and $n-r$, respectively, for $r = 1,\dots,n-1$.  Since $\arb_1,\arb_2$ are
arbitrary, the number of noncrossing arborescences satisfies the famous Catalan
recurrence; see~\cite{catalan}.  We call $k < n$ a \Def{leaf} of $\arb$ if there
is no $i$ with $\arb(i) = k$. Induction on $n$ yields

\begin{lem}\label{lem:immediate}
    Let $\arb$ be a noncrossing arborescence on $n \ge 2$ nodes. Then there is
    a leaf $k$ with $\arb(k) = k+1$, called an \Def{immediate leaf}.
\end{lem}

\section{Particles with locations and velocities}\label{sec:particles}

Consider $n \ge 2$ labelled particles on the real line. Every particle $i =
1,2,\dots,n$ has a constant velocity $-c_i < 0$. We assume that the velocities
satisfy $0 < c_1 < c_2 < \cdots < c_n$.  At time $t = 0$, the particles are at
locations $-\wt_1 \le -\wt_2 \le \cdots \le -\wt_n$. For example
\begin{center}
    \includegraphics[height=1.2cm]{imgs/particles.pdf}
\end{center}


Once the particles start moving from their initial locations $-\wt =
(-\wt_1,\dots,-\wt_n)$ with velocities $-c = (-c_1,\dots,-c_n)$, they will
eventually collide and merge. If particles $i < j$ collide, then particle $i$ is
absorbed  by the faster particle $j$, which continues at velocity $-c_j$.  For
$t \gg 0$, the only remaining particle is $n$. For example
\begin{center}
    \includegraphics[height=3.5cm]{imgs/particle_ev.pdf}
\end{center}


For now we assume that the locations $-\wt$ are chosen generically, so that at
most two particles collide at any given point in time. We record the collisions
by a map $\colpat^{-\wt} : [n-1] \to [n]$ that we call a \Def{collision
pattern}: If particle $i$ gets absorbed by particle $j$ for the initial
locations $-\wt$, then we set $\colpat^{-\wt}(i) := j$. Note that any $\wt \in
\R^n$ and $\alpha \gg 0$, $-(\wt - \alpha c)$ is strictly increasing and the
associated collision pattern is independent of the choice of $\alpha$. The
connection to max-slope arborescences of simplices is as follows.

\begin{thm}\label{thm:cs_max_arb}
    Let $n \ge 2$ and $c \in \R^n$ with $0 < c_1 < \cdots < c_n$. For $\arb :
    [n-1] \to [n]$ and $\wt \in \R^n$, the following are equivalent.
    \begin{compactenum}[\rm i)]
        \item $\arb = \colpat^{-(\wt - \alpha c)}$ is a collision pattern for
            $n$ particles with given velocities $-c$ and locations $-(\wt - \alpha
            c)$ for some $\alpha \ge 0$.
        \item $\arb = \arb^\wt$ is a max-slope arborescence of $(\Simp,c)$
            with respect to weight $\wt$.
    \end{compactenum}
\end{thm}
\begin{proof}
    We can assume that $-\wt_1 < \cdots < -\wt_n$. If we fix $j > i$ and
    disregard all other particles for the moment, then the time $t_{ij}$ of
    collision of $i$ and $j$ satisfies $-\wt_i - t_{ij} c_i = -\wt_j - t_{ij}
    c_j$, that is, $t_{ij} \ = \ \frac{-(\wt_j - \wt_i)}{c_j - c_i} $. By
    construction, $i$ will be absorbed by particle $j$ if $t_{ij}$ is minimal
    among all $t_{ik}$ with $k > i$. Thus, for $i < n$, we observe
    \[
        \colpat^{-\wt}(i) \ = \
        \argmin \left\{ 
        \frac{-(\wt_{j} - \wt_i)}{c_{j} - c_i} : j > i \right \}
        \ = \ 
        \argmax \left\{ 
        \frac{\wt_{j} - \wt_i}{c_{j} - c_i} : j > i \right \} \ = \
        \arb^\wt(i)
        \, ,
    \]
    where the last equation is the definition of $\arb^\wt$
    in~\eqref{eqn:max_slope}. 
\end{proof}
We use noncrossing arborescence and collision patterns interchangeably and write
$\arb^\wt$. 

In the language of collision patterns, we can also interpret the decomposition
of \Cref{lem:decomp}. If $\arb^\wt$ is the collision pattern obtained from
locations $-\wt$, then there is a time $t_1$ at which there are only two
particles left.  One of these two particles is clearly $n$, the other is the
last particle that is absorbed by $n$, that is, the minimal $r \ge 1$ with
$\arb^\wt(r) = n$. In the time between $t=0$ and $t=t_1$, the particles
$1,\dots,r-1$ get absorbed by $r$ and the particles $r+1,\dots,n-1$ get absorbed
by $n$. The corresponding collision patterns are precisely $\arbA$ and $\arbAA$,
respectively.

Collisions of particles can be encoded in terms of \emph{bracketings}.  A
\Def{bracket} is a subset of $[n]$ of the form $[i,j] := \{i, i+1,\dots,j\}$
for $i \le j$. A \Def{bracketing} $\br$ is a collection of distinct brackets
$B_1,\dots,B_m$ such that for every $1 \le r < s \le m$, $B_r \subset B_s$ or
$B_s \subset B_r$ or $B_s \cap B_r = \emptyset$.  A bracket represents
particles that have collided with each other at some point in time.  If $B_r
\subset B_s$ are contained in a bracketing $\br$, then this means at some
point all the particles in $B_r$ have collided and later all the particles in
$B_s$ will have collided. As there is ultimately only a single particle
left, every bracketing has to contain $[1,n]$. The
\Def{associahedron} $\Ass[n-2]$ is the set of bracketings of $[n]$ ordered by
\emph{reverse} inclusion. The unique \emph{maximal} element is $\{[1,n]\}$.
The minimal elements are the complete bracketings of $[n]$, that is,
bracketings with $n-1$ brackets. 


\begin{thm}\label{thm:arb_to_cs}
    Collision patterns on $n$ particles are in bijection with complete bracketings.
\end{thm}
The proof is by induction on $n$ as illustrated here
    \begin{center}
    \includegraphics[height=2cm]{imgs/bracket.pdf}
    \end{center}

The proof of \Cref{thm:main_asso} proceeds by showing that $\Ass[n-2]$ and
$\PP(\Simp,c)$ have the same vertices-in-facets incidences. To that end, we need
to determine the facets of $\PP(\Simp,c)$, which correspond to the coarsest
non-trivial bracketings.

\begin{prop}\label{prop:rs_loc}
    Let $1 \le r < s \le n$ with $(r,s) \neq (1,n)$.  The bracketing $\br = \{
        [r,s], [1,n]\}$ is obtained from locations $-\wt$ if and only if 
    \[
        -\mu \wt + \gamma \1 - \alpha c \ = \ -\wt^{r,s} \ := \
        (c_1,\dots,c_{r-1},c_s,\dots,c_s,c_{s+1},\dots,c_n) 
    \]
    for some $\gamma, \alpha, \mu \in \R$ with $\alpha \ge 0$ and $\mu > 0$.
\end{prop}
With the locations $-\wt^{r,s}$, the particles $r,r+1,\dots,s$ have already
collided at time $t=0$. The remaining particles collide at time $t=1$.

\section{Products of simplices and constrainahedra}
\label{sec:products}

For $m,n \ge 1$ consider the Cartesian product $\PS = \Simp[m-1] \times
\Simp[n-1] \subset \R^m \times \R^n$. This is a simple $(m+n-2)$-dimensional
polytope whose graph is on nodes $\PSV = [m] \times [n]$ visually arranged in an
$m \times n$-grid. An edge-generic objective function $c = (c',c'') \in \R^m
\times \R^n$ with $0 < c'_1 < c'_2 < \cdots < c'_m$ and $0 < c''_1 < c''_2 <
\cdots < c''_n$ induces an orientation on the graph with oriented vertical edges
$ri \to rj$ for $1 \le i < j \ne n$ and horizontal edges $ri \to si$ for $1 \le
r < s \le m$.  The unique sink is the node $mn$ and we write $\PSVo := \PSV
\setminus \{ mn \}$.

Arborescences of $(\PS,c)$ can be identified with maps $\arb : \PSVo \to \PSV$
with the property that if $\arb(ri) = sj$ then $r < s$ and $i=j$ or $r = s$ and
$i < j$. $\arb$ determines an arborescence $\arb'$ of $(\Simp[m-1],c')$ by
$\arb'(r) := s$ if $\arb(rn) = sn$ and, analogously, an arborescence $\arb''$
for $(\Simp[n-1],c'')$.

Every generic $\wt = (\wt',\wt'') \in \R^m \times \R^n$ determines a max-slope
arborescence of $\PS$ such as the following for $(m,n) = (4,4)$:
\begin{center}
    \includegraphics[height=4cm]{imgs/grid_noncross.pdf}
\end{center}
Inspired from this way of illustrating arborescences of $\PS$, we call $\arb$
\Def{consistent} if $\arb(ri) = si$ implies $\arb'(r)=s$ and $\arb(ri) = rj$
implies $\arb''(i)=j$ for all $ri \in \PSVo$.  We call $\arb$
\Def{grid-noncrossing} if $\arb'$ and $\arb''$ are noncrossing and there are no
$1 \le r \le s < t \le m$ and $1 \le i \le j < k \le n$ with $(r,i) \neq (s,j)$
and with $\arb(si) = sk$ and $\arb(rj) = tj$.  

A node $ri \in \PSV$ is an \Def{immediate leaf} of $\arb$ if it has no incoming
edges and $\arb(ri) = (r+1)i$ or $\arb(ri)=r(i+1)$. 
\begin{defn}
    An arborescence $\arb : \PSVo \to \PSV$ is \Def{reducible}
    if $m=n=1$ or
    \begin{compactitem}[$\circ$]
        \item there exists $r \in [m]$ such that $ri$ is a immediate leaf
            for every $i$ and the restriction of $\arb$ to $\PSVo
            \setminus (r \times [n])$ is reducible, or
        \item there exists $i \in [n]$ such that $ri$ is a immediate leaf
            for every $r$ and the restriction of $\arb$ to $\PSVo
            \setminus ([m] \times i)$ is reducible.
    \end{compactitem}
\end{defn}
The above example is reducible as is illustrated here
\begin{center}
    \includegraphics[width=\textwidth]{imgs/grid_noncross_reduce.pdf}
\end{center}

Reducibility implies that $\arb$ is consistent and grid-noncrossing but the
converse does not hold.  For $m=1$ or $n=1$, reducible arborescences are
precisely the noncrossing arborescences.  

\begin{thm}
    An arborescence $\arb : \PSVo \to \PSV$ is a max-slope arborescence of
    $(\PS,c)$ if and only if $\arb$ is reducible.
\end{thm}

To view max-slope arborescences of $\PS$ as particle collisions, we use the
following generalization of particles on a line due to Bottman and
Poliakova~\cite{BottmanPoliakova}. We consider $m$ vertical lines
$L'_1,\dots,L'_m$ and $n$ horizontal lines $L''_1,\dots,L''_n$. The lines are
labelled left-to-right and bottom-to-top.  We place a particle $ri$ at the point
of intersection of $L'_r$ and $L''_i$.  The particle movements are induced by
parallel displacements of the $m+n$ lines. In this scenario parallel lines
collide and particles contained in the colliding lines merge.

We equip every line $L'_r$ and $L''_i$ with a location $-\wt'_r$ and $-\wt''_i$
at time $t=0$ and we assume that $-\wt'_1 \le -\wt'_2 \le \cdots \le -\wt'_m$
and $-\wt''_1 \le -\wt''_2 \le \cdots \le -\wt''_n$.  For $t > 0$, the lines
$L'_r$ move to the left with constant velocity $-c'_r$, the lines $L''_i$ move
down with constant velocity $-c''_i$. As before we assume that $0 < c'_1 < c'_2
< \cdots < c'_m$ and $0 < c''_1 < c''_2 < \cdots < c''_n$. If two or more lines
collide, they are absorbed by the line with the largest index and this line
continues at its original speed. With this setup, we can interpret $\arb^{-\wt}$
as a collision pattern akin to \Cref{thm:cs_max_arb}. For example
\begin{center}
    \includegraphics[height=5cm]{imgs/particle_grid.pdf}
\end{center}

The combinatorics of collisions of $m\cdot n$ particles sitting on $m$ vertical
and $n$ horizontal lines was modelled in~\cite{BottmanPoliakova} by certain
preorders on $\L = \{L'_1, \dots, L'_{m-1}, L''_1, \dots, L''_{n-1}\}$. Recall
that a \Def{preorder} on $\L$ is a reflexive and transitive relation $\preceq$.
For $x \in \L$, the equivalence class $[x]$ is the collection of elements $y \in
\L$ with $x \preceq y$ and $y \preceq x$. On the collection of equivalence
classes $\preceq$ yields a partial order.  Bottman and Poliakova define a
preorder $\preceq$ on $\L$ to be a \Def{good rectangular}
preorder~\cite[Definition~2.1]{BottmanPoliakova} if 
\begin{compactitem}[$\circ$]
    \item $L'_r$ and $L''_i$ are comparable for all $r,i$ 
        \hfill(orthogonal comparability)
\end{compactitem}
and $L'_o \preceq L'_q$ (respectively $L''_o \preceq L''_q$) if and only if
\begin{compactitem}[$\circ$]
    \item $L'_o \preceq L''_p \preceq L'_q$ (respectively $L''_o \preceq L'_p
        \preceq L''_q$) for some $p$, or \hfill (orthogonal link)
    \item there is no $\min(o,q) < p < \max(o,q)$ with $L'_o \prec L'_p \succ
        L'_q$ (respectively $L''_o \prec L''_p \succ L''_q$).  \hfill (no
        gaps)
\end{compactitem}

A good rectangular preorder $\preceq_2$ is \Def{refined} by $\preceq_1$ if $x
\preceq_1 y$ implies $x \preceq_2 y$ for all $x,y \in \L$. 

\begin{thm}[{\cite[Theorem~4.1]{BottmanPoliakova}}]\label{thm:def_constrainahedron}
    The good rectangular preorders on the set $\L$ of $m+n-2$ lines partially
    ordered by refinement is the face poset of an $(m+n-3)$-dimensional
    polytope,  called the \Def{$(m,n)$-constrainahedron} $C(m,n)$.
\end{thm}

In contrast to the case of a single line for which the constrainahedron is the
associahedron, constrainahedra are in general not simple polytopes. Facets
correspond to \Def{elementary collisions}, which are simultaneous collision of
horizontal and vertical lines that are not the result of at least two
simultaneous and disjoint collisions of sets of lines. There are three distinct
types of elementary collisions. Locations for elementary collisions can be given
similar to \Cref{prop:rs_loc}.  The proof of \Cref{thm:constrainahedron} follows
a similar strategy as that of \Cref{thm:main_asso} but is significantly more
complicated.

\section{Higher products and multiplihedra}
\label{sec:higher}


In this last section, we focus on the max-slope pivot rule polytopes of the product $Q_{n,k}
= \Simp[n-1] \times [0,1]^k  \subset \R^n \times \R^k$ together with an
objective function $(c,r)$ with $c = (c_1 < c_2 < \cdots < c_n)$
and $r = (r_1,\dots,r_k) \in \R^{k}$ with $r_i > 0$ for all $i$. 

For $k = 1$ the max-slope pivot polytope $\PP(Q_{n,k},(c,r))$ is the
constrainahedron $C(2,n)$, which is Stasheff's \Def{multiplihedron}; see
\cite{Stasheff-book}.  For $n=k=2$ the polytope $\PP(Q_{n,k},(c,r))$ is as
follows with a vertex labelling that illustrates \Cref{thm:multi_multiplihedron}
\begin{center}
    \includegraphics[height=2cm]{imgs/multi.pdf}
\end{center}

Consider an evaluation of $(f_{\sigma(1)} \circ f_{\sigma(2)} \circ \cdots \circ
f_{\sigma(k)})(a_1 \cdot a_2 \cdots a_n)$ as in \Cref{thm:multi_multiplihedron}
with $\sigma$ fixed. Disregarding the morphisms for a moment, the order in which
the \mbox{$n-1$} multiplications have to be carried out is encoded by a partial order
$\preceq_T$ on $[n-1]$ whose Hasse diagram is well-known to be a tree $T$ rooted
at the maximum (i.e., the last multiplication to be carried out). Every node in
the tree has at most two children. With the labelling given by $[n-1]$, the
possible posets are precisely the binary search trees on $n-1$ nodes. Now, for
the $j$-th multiplication, we record the number $\phi(j)$ of morphisms that have
to be applied before the multiplication can take place. The poset
$([n-1],\preceq_T)$ together with the map $\phi : [n-1] \to \{0,1,\dots,k\}$
completely determines the evaluation. Note that if $i \prec j$, then $\phi(i)
\le \phi(j)$ and hence $\phi$ is an \Def{order-preserving map}. A max-slope
arborescence of $(Q_{n,k},c)$ determines a noncrossing arborescence $\arb :
[n-1] \to [n]$ and thus a bracketing, which is another representation of
$\preceq_T$. The map $\phi$ comes from the additional information provided by
the arborescence. 

The \Def{order polynomial} $\Omega_P(l)$ of a partially ordered set
$(P,\preceq)$ is a polynomial of degree $|P|$ such that $\Omega_P(l)$ is the
number of order-preserving maps $P \to [l]$; see~\cite{CRT,EC1}. For fixed $n
\ge 2$, we define $V_{n}(k)  :=  \sum_T \Omega_T(k+1)$, where the sum is over
all binary search trees $T$ on $[n-1]$. Our encoding of an evaluation of
$f_{\sigma(1)} \circ f_{\sigma(2)} \circ \cdots \circ f_{\sigma(k)}$ on $a_1 \cdot
a_2 \cdots a_n$ by a binary search tree and an order-preserving map into
$\{0,1,\dots,k\}$ yields the following.

\begin{cor}\label{cor:n_vertices}
    The number of evaluations of $(f_{\sigma(1)} \circ f_{\sigma(2)} \circ
    \cdots \circ f_{\sigma(k)})(a_1 \cdot a_2 \cdots a_n)$ is $V_n(k)$. In
    particular, the number of vertices of $\PP(Q_{n,k},(c,r))$ is $k!V_n(k)$.
\end{cor}

The number of vertices of the $(k,n)$-multiplihedron is given by Proposition 126
of~\cite{ChapotonPilaud} in terms of generating functions.  It is remarkable
that the number of vertices for varying $k$ is essentially given by a
polynomial. It can be shown that the leading coefficient of $V_n(k)$ is $1$ and
the constant coefficient is the $n$-th Catalan number $C_n$.  Experiments show
that all coefficients are non-negative and, of course, we tested if the
polynomials are real-rooted. This seems to be true for $n \le 10$ but unknown
beyond. 

% \todo{clean up references,}
%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography


\end{document}
