%% 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{158}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\usepackage{enumerate}
% Useful packages
\usepackage{multirow}
\usepackage{subcaption}
\usepackage{tikz,tikz-cd}
\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{decorations.markings}
\usetikzlibrary{calc,cd}
\usepackage{thmtools}
\declaretheorem[numberwithin=section]{theorem}
\declaretheorem[sibling=theorem]{question}
\declaretheorem[sibling=theorem]{conjecture}
\declaretheorem[sibling=theorem]{proposition}
\declaretheorem[sibling=theorem]{lemma}
\declaretheorem[sibling=theorem]{corollary}
\declaretheorem[sibling=theorem]{problem}
\declaretheorem[sibling=theorem]{definition}
\declaretheorem[sibling=theorem, style=definition]{property}
\declaretheorem[sibling=theorem, style=definition]{exercise}
\declaretheorem[sibling=theorem, style=definition]{example}
\declaretheorem[sibling=theorem, style=definition]{remark}

%\declaretheorem{thevarthm}[sibling=theorem]{\varthmname}
\newenvironment{varthm}[1]{\def\varthmname{#1}\begin{thevarthm}}{\end{thevarthm}\def\varthmname{}}

\newenvironment{varthm*}[1]{\begin{list}{}{\labelwidth=0cm
			\leftmargin=0cm
			\listparindent=\parindent}\item[\hspace{\labelsep}\bfseries
		#1.]\itshape}{\end{list}}


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

%-----------------------------------
%       Blackboard symbols
%
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
 \newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\p}{{\mathbb P}}

%-----------------------------------
%       Mathematical notions
%
\newcommand{\dd}{\operatorname{d}}
\newcommand{\Def}{\operatorname{def}}
\newcommand{\Area}{\operatorname{Area}}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Card}{\operatorname{card}}
\newcommand{\tc}{\operatorname{tc}}
\newcommand{\osp}{\operatorname{OSP}}

\DeclareMathOperator{\op}{op}
\newcommand{\upto}{\raisebox{1.2 mm}{$\curvearrowright$}}
\newcommand{\downto}{\mathbin{\rotatebox[origin=c]{-180}{$\curvearrowleft$}}}

%\DeclareMathOperator{\mod}{mod}
% \newcommand{\Const}{\operatorname{const}}
% \newcommand{\CP}{{\mathbb C}\!\operatorname{P}^1}
%------------------------------------------------
%   Some new lengths

%\newlength{\halfbls}\setlength{\halfbls}{.5\baselineskip}
%-----------------------------------
%   \CX  = draw X calligraphically.
%
% \newcommand{\CC}{{\mathcal C}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cF}{{\mathcal F}}


\newcommand{\E}{{\bf E}}
\newcommand{\W}{{\bf W}}
\newcommand{\T}{{\bf T}}
\newcommand{\s}{{\bf S}}

\newcommand{\ind}{\textbf{\textit{ind}}}

\def \deg{\textup{deg}}
\def \dim{\textup{dim}}
\def \rank{\textup{rank}}
\def \ord{\textup{ord}}
\def \conv{\textup{conv}}
\def \gr{\textup{gr}}
\def \vol{\textup{vol}}
\def \div{\textup{div}}
\def \Lie{\textup{Lie}}
\def \supp{\textup{supp}}
\def \Proj{\textup{Proj}}
\def \Sym{\textup{Sym}}
\def \codim{\textup{codim}}
\def \ker{\textup{ker}}
\def \Gr{\textup{Gr}}
\def \max{\textup{max}}
\def \span{\textup{span}}
\def \Spec{\textup{Spec}}
\def \Pic{\textup{Pic}}
\def \End{\textup{End}}
\def \ratmap{\dashrightarrow}
\def \Re{\textup{Re}}
\def \Im{\textup{Im}}
\def \grad{\textup{grad}}
\def \Crit{\textup{Crit}}
\def \Hom{\textup{Hom}}
\def \mom{\textup{mom}}
\def \Gr{{\rm{Gr}}}
\def \Mat{{\rm{Mat}}}
\def \sgn{{\rm{sgn}}}

%% define your title in the usual way
\title{Minkowski Decompositions of Alcoved Polytopes}

%% 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[Nick Early, Lukas K\"uhne, and Leonid Monin]{\texorpdfstring{Nick Early\thanks{\href{mailto:earlnick@ias.edu}{earlnick@ias.edu}.  N.E. was partially supported by the European Union (ERC, UNIVERSE PLUS, 101118787). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.}\addressmark{1}, Lukas K\"uhne\thanks{\href{mailto:lkuehne@math.uni-bielefeld.de}{lkuehne@math.uni-bielefeld.de}.  L.K. was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -- SFB-TRR 358/1 2023 -- 491392403 and SPP 2458 -- 539866293.}\addressmark{2}, \and Leonid Monin\thanks{\href{mailto:leonid.monin@epfl.ch}{leonid.monin@epfl.ch}.  L.M. was partially supported by Swiss National Science Foundation (SNSF) -- 200021E\_224099}\addressmark{3}}{Nick Early, Lukas K\"uhne, and Leonid Monin}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Institute for Advanced Study, USA \\ \addressmark{2}Universit\"at Bielefeld, Germany and Institute for Advanced Study, USA \\ \addressmark{3}École Polytechnique Fédérale de Lausanne (EPFL), Switzerland}

%% 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{
We develop a systematic theory of Minkowski sum decompositions for alcoved polytopes, a family of convex polytopes whose facet normals are parallel to roots of type A. Our main result establishes that the type fan of alcoved polytopes is two-determined: the Minkowski sum of a collection of alcoved polytopes is alcoved if and only if each pairwise sum is alcoved. We provide a complete characterization of compatibility between alcoved simplices via a graphical criterion on ordered set partitions that remarkably reduces to conditions on subsequences of length at most~six.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{fkfkf}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Alcoved polytopes, Minkowski sums, type fan, associahedron.}

%% 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]{biblatex}
\addbibresource{alcoved_simplices.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}
A polytope in $\cH_n=\{x_1+\dots + x_n=0\}\subset \R^n$  is \emph{alcoved} if all its facet normals are parallel to the roots $e_i-e_j$ for some $i\neq j\in \left[n\right]$.
Equivalently, a polytope is alcoved if it is determined by the parameters  $a_{i,j}\in \R$ for $1\le i,j,\le n$ via the equation $x_1+\dots +x_n=0$ and  the inequalities
\begin{equation}\label{eq:alcoved}
	x_i-x_j\le a_{i,j} \text{ for all }i,j\in \lbrack n \rbrack, i\neq j.
\end{equation}

Alcoved polytopes were introduced by Lam and Postnikov~\cite{lam2007alcoved} and appeared in different fields under different names.
They are known in the literature as \emph{polytropes} as they are tropical polytopes which are convex in the usual sense~\cite{JK10}.
Moreover, they are \emph{Lipschitz polytopes} (for non-symmetric finite metric spaces)~\cite{GP17,lipschitzpolytope}.
The class of alcoved polytopes includes order polytopes, hypersimplices, and the associahedron. In applications, alcoved polytopes play a key role in phylogenetics \cite{yoshida2019tropical}, mechanism design \cite{crowell2016tropical}, algebraic statistics \cite{Wasserstein}, scattering amplitudes  \cite{CEGM2019,Ear22}, positive configuration spaces \cite{arkani2021positive} and amplituhedra \cite{parisi2021m}, and building theory~\cite{JSY07}.

Our starting point is the observation that unlike some other families of polytopes such as generalized permutohedra, alcoved polytopes are not closed under Minkowski sums in general.
This leads to the following natural question.
\begin{problem}\label{prob:sum_alcoved_polytopes}
	Let $P,Q\subseteq \cH_n$ be alcoved polytopes.
	When is the Minkowski sum $P+Q$ alcoved?
	
	We call the alcoved polytopes $P$ and $Q$ \emph{compatible} if their sum $P+Q$ is alcoved.
\end{problem}

    Several prominent alcoved polytopes such as the associahedron and the cyclohedron are Minkowski sums of alcoved simplices, see~\Cref{sec:examples}.
In particular, the associahedron, which maps onto the connected components in the tiling of the configuration space $\mathcal{M}_{0,n}$, appears in recent approaches to quantum field theory \cite{CHY}; it governs the singularity locus of the $\text{tr}(\phi^3)$ amplitude and satisfies certain important physical compatibility constraints on pairs of poles, called the Steinmann relations.  
The study of pairwise compatible collections of alcoved polytopes could therefore generalize the role of the associahedron in the Cachazo--He--Yuan formalism~\cite{CHY} to arbitrary alcoved polytopes, suggesting new connections between polytope theory and scattering amplitudes.   
A more recent such instance is the so-called $\hat{D}$-polytope recently described in the physics literature~\cite{dhat}, see \Cref{thm: assocCycDHat}.


Moreover, \Cref{prob:sum_alcoved_polytopes} is intimately tied to the general study of the \emph{type fan of alcoved polytopes}.
Suppose the parameters $a_{i,j}$ from~\eqref{eq:alcoved} minimally define an alcoved polytope.
Then they satisfy the following triangle inequalities \cite[Theorem~4.3]{polypositroids}:
\[
a_{i,j}+a_{j,k}\geq a_{i,k}, \text{ for all } i,j,k.
\]
The cone in $\mathbb{R}^{(n-1)n}$ defined by these inequalities has an internal fan structure given by the different combinatorial types of alcoved polytopes.
This fan is \emph{type fan of alcoved polytopes} $\cF_n$.
This fan was also studied in the context of tropical geometry and optimization in~\cite{joswig2022parametric,tran2017enumerating}, and is closely related to the so-called \emph{resonance  arrangement} studied in \cite{early2018honeycomb,kuehne23}.
In this setting, two polytopes $P$ and $Q$ are compatible if and only if their corresponding points are part of the same cone in the fan $\cF_n$.
Understanding the compatibility of alcoved polytopes is therefore equivalent to the study of the cone structure of the type fan $\cF$ of alcoved polytopes. 

This is an extended abstract of \cite{early2025alcoved}.



\subsection{Results}
In~\Cref{sec:type_fan} we prove that compatibility of alcoved polytopes can be checked on pairs:
\begin{varthm*}{Theorem A}\label{thm:A}
	Let $P_1,\dots,P_k$ be alcoved polytopes in $\cH_n$.
	Suppose $P_i$ and $P_j$ are pairwise compatible for all $i\neq j\in\left[n\right]$.
	Then the entire collection is compatible, i.e., $P_1+\dots+P_k$ is alcoved.
\end{varthm*}
This in particular means that the combinatorial structure of the type fan is completely determined by its $2$-dimensional cones, see~\Cref{thm:2_determined}.

Next we focus on alcoved simplices in~\Cref{sec:alcoved_simplices}.
As they are Minkowski indecomposable, they are among the rays of the type fan $\cF_n$.
Up to translation and scaling, every alcoved simplex in $\cH_n$ is characterized by an \emph{ordered set partition} of $\left[n\right]$.

In~\Cref{sec:compatibility} we give a characterization for the compatibility of alcoved simplices.
\begin{varthm*}{Theorem B}\label{thm:B}
    Let $\s$ and $\T$ be two ordered set partitions of $[n]$ corresponding to the alcoved simplices $\Delta_\s$ and $\Delta_\T$ in $\cH_n$.
	The simplices $\Delta_\s$ and $\Delta_\T$ are compatible if and only if the simplices corresponding to the restricted partitions $\s|_I$ and $\T|_I$ are compatible for all  $I\subset [n]$ with $|I|\le 6$.
    \end{varthm*}

We prove this theorem in two steps.
First, we construct a graph associated to simplices  $\Delta_\s$ and $\Delta_\T$ of the ordered set partitions $\s$ and $\T$ such that the simplices are compatible if and only if there is no cycle in this graph of a specific type.
Subsequently, we show that if the graph has such a cycle we can already find such a cycle on a subset of $\left[n\right]$ of size at most~$6$.
As an application, we can swiftly confirm that the $\hat{D}_n$-polytope is alcoved in~\Cref{sec:compatibility}.

\subsection{Outlook}
Our characterization of compatibility for alcoved simplices raises several questions.
The reduction to conditions on just 6-element subsequences is remarkably simple, yet its physical meaning remains mysterious. This echoes other ``small $n$'' phenomena in quantum field theory and combinatorics, such as the criterion to check matroidal subdivisions on octahedral faces.


On the other hand, it is known in the context matroids that a matroid polytope is alcoved if and only if the matroid is a \emph{positroid}~\cite{polypositroids}.
The Minkowski indecomposable positroids are the connected positroids~\cite{ARW16}.
It remains therefore a fascinating open question to investigate the compatibility of connected positroids within the type fan of alcoved polytopes.




\section{The type fan of alcoved polytopes}\label{sec:type_fan}
In this section we give (a sketch of) a proof of Theorem~\hyperref[thm:A]{A}. Let us start with definitions.

\begin{definition}
    We call vectors $e_{i,j}:= e_i - e_j \in \cH_n \subset \R^n$ the roots of type $A$. 
    We say that a vector subspace $L\subset \cH_n$ is a \emph{root subspace} if it is spanned by roots.
\end{definition}

We start with a reformulation of alcoved polytopes in terms of their normal fans.
	A polytope $P$ in the hyperplane $\cH_n$ is alcoved if the lineality space $L$ of the normal fan $\Sigma_P$ is a root subspace and the rays of the quotient fan $\Sigma_P/L$ are generated by roots.



The main technical result we need  to prove Theorem~\hyperref[thm:A]{A} is the following proposition. 

\begin{proposition}\label{prop:alcovedspaces}
    Let $L_1, \dots, L_k\subset \cH_n$ be root subspaces, such that $L_s\cap L_t$ a root subspace for all $1\leq s,t\leq k$. Then $L_1\cap\ldots\cap L_k$ is a root subspace.
\end{proposition}

To prove \Cref{prop:alcovedspaces}, we introduce a graph $G_L$ which completely determines the root subspace $L$ (\Cref{def:GL}).
Subsequently, we give a graphical criterion for the compatibility of root subspaces (\Cref{lem:cycles}).
However, let us first present a proof of \hyperref[thm:A]{Theorem A} assuming \Cref{prop:alcovedspaces}.

\begin{proof}[Proof of Theorem~{\hyperref[thm:A]{A}}]
    The goal is to show that $P=P_1+\ldots+P_k$ is alcoved.
    We can assume that $P$ is full-dimensional as we can otherwise restrict to the sum of the root subspaces given by the linear spans of the polytopes $P_1,\dots,P_k$.
    Let $F$ be a facet of $P$. 
    Hence, we can choose faces $\Gamma_s$ of $P_s$ for all $1\le s \le k$ such that $F=\Gamma_1+\ldots+\Gamma_k$. Therefore, the normal ray $\rho_F$ is given as intersection of the normal cones $\sigma_s$ of  $\Gamma_s$. 

    The ray $\rho_F$ is generated by a root if and only if the linear span of $\rho_F$ is generated by a root.
    Therefore we aim to work with linear spaces instead of cones.
    To this end we replace each $\sigma_s$ with the smallest face of $\sigma_s$ containing $\rho_F$.
    Thus, we obtain the equality
    \[
   \span(\rho_F)= \bigcap_{s=1}^k \span(\sigma_{s}).
    \]
     So it is enough to show that $    \bigcap_{s=1}^k \span(\sigma_{s})$ is generated by roots.

    
    But by the assumptions of the theorem we have that $\span(\sigma_{s})$ as well as $\span(\sigma_{s})\cap\span(\sigma_{t})$ is generated by roots for every $1\le s,t,\le k$.
    Indeed, since $P_s$ and $P_s+P_t$ are alcoved, the rays of their normal fans are all in  root directions and hence, every cone (and its linear span) is generated by roots.
    Therefore, by \Cref{prop:alcovedspaces} we get that $ \bigcap_{s=1}^k \span(\sigma_{s})$ is generated by roots, and thus $\rho_F$ is also a multiple of a root.
\end{proof}

To prove \Cref{prop:alcovedspaces} we first need to set up some notation.
\begin{definition}\label{def:GL}
    For a root subspace $L\subset \cH_n$ we define an undirected graph $G_L$ as follows
    \begin{itemize}
        \item[(1)] The vertices of $G_L$ are labeled by $\left[n\right]$.
        \item[(2)] The graph $G_L$ has an edge $\{i,j\}$ if $e_{ij}\in L$ (note that as $L$ is a subspace, it contains the root $e_{ij}$ if and only it contains the root $e_{ji}$.
    \end{itemize}
\end{definition}


\begin{remark}
Since $\cH_n =\{x_1+\dots+x_n=0\}$ is the root subspace of all roots, the graph $G_{\cH_n}$ is the complete graph on $n$ vertices. Similarly, for a general root subspace $L$ we get that each connected component of $G_L$ is a complete graph.
\end{remark}



Any linear combination of roots $\sum_{1\le i<j\le n} w_{ij}e_{ij}$ defines a weighted sum of oriented edges of $G_{\cH_n}$ by assigning the orientation $j\to i$ and weight $w_{ij}$ to every edge $\{i,j\}$.
Two such combinations $\sum_{1\le i<j\le n} w_{ij}e_{ij}$ and $\sum_{1\le i<j\le n} w'_{ij}e_{ij}$ give rise to the same element of~$\cH_n$ if and only if their difference $\sum_{1\le i<j\le n} (w_{ij}-w'_{ij})e_{ij}$ defines a linear combination of oriented cycles in $G_{\cH_n}$ (here we view the edges with a negative weight as $i\to j$).

Now, let $L, M$ be two root subspaces within $\cH_n$.
An element $x$ is in the intersection $L\cap M$ if it can be simultaneously represented by a linear combination of oriented edges from $G_L$ and $G_M$.
The difference of these two representation is thus a linear combination of cycles supported on the edges $G_L\cup G_M$. 
On the other hand, every oriented cycle $C$ supported on  $G_L\cup G_M$ yields an element of  $L\cap M$ via taking the linear combination 
\begin{equation}\label{eq:xc}
x_C=\sum_{\{i,j\}\in C\cap G_L}e_{ij}=-\sum_{\{s,t\}\in C\cap G_M}e_{st}.
\end{equation}
This leads to the following lemma:

\begin{lemma}\label{lem:spaceintersect}
    Let $L, M$ be two root subspaces within $\cH_n$.
    The intersection $L\cap M$ is generated by elements corresponding to oriented cycles in $G_L\cup G_M$ as in~\eqref{eq:xc}.
\end{lemma}

In addition, a little more careful analysis allows to show the following Lemma. 
\begin{lemma}\label{lem:cycles}
    Let $L, M$ be two root subspaces within $\cH_n$.
    The intersection $L\cap M$ is a root subspace if and only if the there is no chordless cycle of length at least four in $G_L\cup G_M$.
\end{lemma}
\begin{proof}
    Key points of the proof are 
    \begin{itemize}
        \item a chordless cycle in $G_L\cup G_M$ has to be alternating (i.e. if an edge in $C$ is in $G_L$ the next one on $C$ must be in $G_M$);
        \item an alternating cycle $C$ produces an element $x_C\in L\cap M$;
        \item if the length of $C$ is at least 4, the element $x_C$ is not a root and can't be written as combination of roots in $L\cap M$ since $C$ is chordless. \qedhere
    \end{itemize}
\end{proof}

Now we are ready to prove \Cref{prop:alcovedspaces}.
\begin{proof}[Proof of \Cref{prop:alcovedspaces}]
    It is enough to show the statement for $k=3$.
    Indeed assuming this case, the general case follows via induction after replacing $L_1,L_2$ by $L_1\cap L_2$.
    In the case $k=3$, let us define $L_{ij}:= L_i\cap L_j$ for $1\le i<j\le3$. Since $L_{ij}$ is a root subspace, we get $G_{L_{ij}} = G_{L_i}\cap G_{L_j}$.
    
    Assume that there is an element $x\in L_1\cap L_2 \cap L_3=L_{12}\cap L_3$ which is not a linear combination of roots in $L_{12}\cap L_3$. By \Cref{lem:cycles}, there is a chordless, strictly alternating cycle $C$ in $G_{L_{12}}\cup G_{L_3}$ of length at least four. 
    On the other hand, since $L_{13}$ is a root subspace, the cycle $C$ has a chord in $G_{L_1}\cup G_{L_3}$. In fact, since $G_{L_1}\cup G_{L_3}$ does not have any chordless cycles of length at least four, the vertices of $C$ belong to the same connected component of $G_{L_1}$.
    Hence $G_{L_1}$ restricted to the vertices of $C$ is a complete graph. 
    
    The same argument also applies to $G_{L_2}$ restricted to the vertices of $C$.
    Therefore, $G_{L_{12}}=G_{L_1}\cap G_{L_2}$ restricted to vertices of $C$ is also a complete graph which contradicts the assumption of $C$ being chordless in $G_{L_{12}}\cup G_3$.
    \end{proof}


Theorem~\hyperref[thm:A]{A} has the following consequence for the type fan of alcoved polytopes. 

\begin{theorem}\label{thm:2_determined}
    The type fan of alcoved polytopes is two-determined, i.e. if in a collection of rays $\rho_1,\ldots , \rho_s$ any pair $\rho_i,\rho_j$ belongs to some cone of $\cF_n$, then there exists a cone containing the whole collection.
\end{theorem}



\section{Alcoved simplices}\label{sec:alcoved_simplices}
An \emph{ordered set partition}  of the set $\left[n\right]$ is an ordered tuple $\T = (B_1,\ldots, B_\ell)$ of pairwise disjoint subsets $B_i\subseteq \left[n\right]$ such that $\cup_{j=1}^\ell B_j = \left[n\right]$.
We denote the set of ordered set partitions of $\left[n\right]$ by $\osp(n)$.

Moreover, we use the shorthand notation $(1,2\: 3,4)$ for the ordered set partition $(\{1\},\{2,3\},\{4\})$ in $\osp(4)$.
An ordered set partition $\T = (B_1,\ldots, B_\ell)$ is called \emph{nondegenerate} if each block $B_i$ is a singleton, i.e.,\ contains exactly one element of $\lbrack n \rbrack$.



\begin{definition}
To each ordered set partition $\T=(B_1,\dots,B_\ell)$ of $\lbrack n \rbrack$ we associate an \emph{alcoved simplex} $\Delta_\T$ in the hyperplane $\cH_n$ defined by the following set of (in)equalities in $\cH$:

\begin{equation*}
\begin{aligned}
x_{i}= x_{j}\quad \text{ for every }& i,j\in B_k \text{ and every }1\le k \le \ell,\\
x_i\leq x_j \quad \text{ for every }& i\in B_k, \, j\in B_{k+1} \text{ and every }1\le k \le \ell-1,\\
x_i\leq x_j+n \quad \text{ for every }& i\in B_\ell, \, j\in B_1.
\end{aligned}
\end{equation*}
We denote by $\Sigma_{\T}$ the normal fan of the simplex $\Delta_\T$.
\end{definition}


\begin{proposition}
For every ordered set partition $\T$ the corresponding simplex $\Delta_\T$ is alcoved. Moreover, every alcoved simplex in $\cH_n$ is realized by $\Delta_\T$ up to shift and dilation.
\end{proposition}

As above, we study the compatibility of alcoved simplices through a graph.

\begin{definition}
    Let $\T=(B_1,\ldots,B_{\ell})$ be an ordered set partition of $[n]$. We define a graph $G_\T$ as a partially directed graph on $n$ vertices which has an undirected clique on the set $B_i$  for every $1\leq i \leq \ell$ and a directed edge $b_i\to b_{i+1}$ for  $1\leq i \leq \ell$ (regarded cyclically) where $b_j\in B_j$ is the smallest element of a block $B_j$.
\end{definition}


\begin{example}\label{ex:osp}
The alcoved simplex $\Delta_{(1,2\: 3, 4)}$ in $\R^4$ of the ordered set partition $(1,2\: 3,4)$ is defined by $x_1+\dots+x_4=0$ and the (in)equalities
$x_1\le x_2=x_3\le x_4\le x_1+4.$
Its vertices are $(0,0,0,0)$, $(-1,-1,-1,3)$ and $(-3,1,1,1)$ and $G_\T$ is depicted in \Cref{fig:graph_gamma_S}.
\end{example}


\begin{figure}[hbt]
	\begin{center}
\begin{tikzpicture}[baseline=0,>=stealth,xscale=1.5]
\foreach \x in {1,...,4}{
	\coordinate (\x) at (\x,0);
}

\draw  (2,-0.1) to (3,-0.1);
\foreach \x in {1,2,3,4}{
	\draw (\x) node[below,fill=white,draw=black,circle,inner sep =2] {} node[below,yshift=-5pt] {$\x$};
}
\begin{scope}[decoration={
	markings,
	mark=at position 0.5 with {\arrow{>}}}
]
\draw[postaction={decorate}] (1) to [in=90,out=90] (2);
\draw[postaction={decorate}] (4) to [in=90,out=90] (1);
\draw[postaction={decorate}] (2) to [in=90,out=90] (4);


\end{scope}
\end{tikzpicture}
\caption{The graph $G_\T$ of the ordered set partition $(1,2\: 3,4)$.}
\label{fig:graph_gamma_S}
\end{center}
\end{figure}


\begin{proposition}
    Let $\T=(B_1,\dots,B_\ell)$ be an ordered set partition and let $\T'=(B_2,\dots,B_\ell,B_1)$ be the ordered set partition where the blocks are cyclically shifted to the right.  Then 
    \[
        \Sigma_{\T}=\Sigma_{\T'}.
    \]
\end{proposition}
As we are mostly interested in the common subdivisions of the normal fans of alcoved simplices, we consider the ordered set partitions up to cyclic shifts.
Thus, we assume that for an ordered set partition $\T=(B_1,\dots,B_\ell)$ of $\lbrack n \rbrack$ we have $n\in B_\ell$.



The normal fan $\Sigma_\T$ of $\Delta_\T$ for a ordered set partition $\T=(B_1,\dots,B_\ell)$ can be described as follows.
Let $I$ be the set indexing ordered edges of the partially directed graph $G_\T$.
Then the cones of $\Sigma_\T$ are in bijection with non-empty subsets of $I$.
More precisely, given a subset $J\subseteq I$ the corresponding normal cone $\sigma_J$ is positively generated by the roots appearing in the the transitive closure of the partially ordered graph 
\[
\Gamma_{\sigma_J} := \tc(G_\T\setminus\{e_j\}_{j\in J}).
\]


\begin{example}
	We continue the discussion of the ordered set partition $(1,2\: 3,4)$.
	It has the directed edges $I=\{1 \to 2,2 \to 4, 4\to 1\}$.
	\Cref{fig:cone_graphs} shows the graphs corresponding to the normal cones of the subsets $J_1,J_2,J_3$ of edges to be removed from~$G_{\T}$.
	
	All three cones have the $1$-dimensional lineality space spanned by the vector $e_{23}$.
	In the quotient space, the cones $\sigma_{J_1}/L_{\sigma_{J_1}}$ and  $\sigma_{J_2}/L_{\sigma_{J_2}}$ are generated by the roots $\{e_{24},e_{41}\}$ and $\{e_{41}\}$, respectively.
	The cone $\sigma_{J_3}$ equals the lineality space $L_{\sigma_{J_3}}$.
\end{example}
\begin{figure}[hbt]
	\begin{center}
		\begin{subfigure}{.3\linewidth}
		\begin{tikzpicture}[baseline=0,>=stealth,xscale=1.5]
		\foreach \x in {1,...,4}{
			\coordinate (\x) at (\x,0);
		}
		
		\foreach \x in {1,2,3,4}{
			\draw (\x) node[below,fill=white,draw=black,circle,inner sep =2] {} node[below,yshift=-5pt] {$\x$};
		}
		\begin{scope}[decoration={
			markings,
			mark=at position 0.5 with {\arrow{>}}}
		]
		\draw[postaction={decorate}] (3) to [in=90,out=90] (2);
		\draw[postaction={decorate}] (2) to [in=90,out=90] (3);
		\draw[postaction={decorate}] (3) to [in=90,out=90] (4);
		\draw[postaction={decorate}] (4) to [in=90,out=90] (1);
		\draw[postaction={decorate}] (2) to [in=90,out=90] (1);
		\draw[postaction={decorate}] (3) to [in=90,out=90] (1);
		\draw[postaction={decorate}] (2) to [in=90,out=90] (4);
		
		\end{scope}
		\end{tikzpicture}
		\caption{$J_1:=\{1\to 2\}$}
	\end{subfigure}
	\hspace{10pt}
	\begin{subfigure}{.3\linewidth}
		\begin{tikzpicture}[baseline=0,>=stealth,xscale=1.5]
		\foreach \x in {1,...,4}{
			\coordinate (\x) at (\x,0);
		}
		
		\foreach \x in {1,2,3,4}{
			\draw (\x) node[below,fill=white,draw=black,circle,inner sep =2] {} node[below,yshift=-5pt] {$\x$};
		}
		\begin{scope}[decoration={
			markings,
			mark=at position 0.5 with {\arrow{>}}}
		]
		\draw[postaction={decorate}] (4) to [in=90,out=90] (1);
		\draw[postaction={decorate}] (2) to [in=90,out=90] (3);
		\draw[postaction={decorate}] (3) to [in=90,out=90] (2);
		
		\end{scope}
		\end{tikzpicture}
		\caption{$J_2:=\{1\to 2,2\to 4\}$}
	\end{subfigure}
	\hspace{10pt}
	\begin{subfigure}{.3\linewidth}
		\begin{tikzpicture}[baseline=0,>=stealth,xscale=1.5]
		\foreach \x in {1,...,4}{
			\coordinate (\x) at (\x,0);
		}
		
		\foreach \x in {1,2,3,4}{
			\draw (\x) node[below,fill=white,draw=black,circle,inner sep =2] {} node[below,yshift=-5pt] {$\x$};
		}
		\begin{scope}[decoration={
			markings,
			mark=at position 0.5 with {\arrow{>}}}
		]
		\draw[postaction={decorate}] (2) to [in=90,out=90] (3);
		\draw[postaction={decorate}] (3) to [in=90,out=90] (2);
		\draw[postaction={decorate},white] (1) to [in=90,out=90] (4);
		
		\end{scope}
		\end{tikzpicture}
		\caption{$J_3:=\{1\! \to \!2,2\! \to \!4, 4\!\to \!1\}$}
	\end{subfigure}
		\caption{Three graphs of the normal cones of the ordered set partition $(1,2\: 3,4)$.}
		\label{fig:cone_graphs}
	\end{center}
\end{figure}


\section{Compatibility of alcoved simplices}\label{sec:compatibility}


\subsection{Graphical criterion}
In this section, we discuss a graphical criterion to detect when the Minkowski sum of two alcoved simplices $\Delta_\s$ and $\Delta_\T$ is again an alcoved polytope.

\begin{definition}
	We call two ordered set partitions $\s$ and $\T$ \emph{compatible} if the Minkowski sum $\Delta_\s+\Delta_\T$ is alcoved.
\end{definition}

We now turn to the graph theoretic side of the story.

\begin{definition}
Let $\s, \T$ be two ordered set partitions on $\left[n\right]$.
Let us define the partially ordered graph $G_{\s,\T}$ to be the union $G_{\s}\cup G_{\T}^{op}$ where in $G_{\T}^{op}$ all directed edges are reversed.
We call edges in $G_\s$ \emph{upper} and those in $G_{\T}^{op}$ \emph{lower}.

Let $C$ be a cycle in $G_{\s,\T}$.
An \emph{upper path segment} of $C$ is a collection of  consecutive upper edges in $C$.
We call a cycle \emph{violating} if it has at least two disjoint upper path segments and visits every vertex of $G_{\s,\T}$ at most once.
\end{definition}

These graphs allow us to prove a graph theoretic criterion of compatible partitions.
\begin{theorem}\label{thm:set_partitions}
	The ordered set partitions $\s, \T$ on $\left[n\right]$ are compatible if and only if $G_{\s,\T}$ does not have a violating cycle.
\end{theorem}

The proof of this result uses similar arguments as the ones we outlined in~\Cref{sec:type_fan}.
As a corollary of \Cref{thm:set_partitions} we obtain Theorem~\hyperref[thm:B]{B}. For the sake of space we will only illustrate this in the case of non-degenerate set partitions, or equivalently full dimensional alcoved simplices.


\subsection{Compatibility of full-dimensional simplices}
For $\s$ in $\osp(n)$ and a subset $I\subset [n]$ we denote the restriction of $\s$ to $I$  by $\s|_I$.

\begin{definition}
    We call $\s,\T \in \osp(n)$ \emph{4-interlaced} if there exist 4 distinct elements $a,b,c,d\in [n]$ such that the ordered set partitions of $\s$ and $\T$ restricts respectively to
    \[
    \s|_{a,b,c,d} =(a,b,c,d)\quad\text{ and } \quad \T|_{a,b,c,d} =(c,b,a,d).
    \]

    We say that $\s$ and $\T$ are \emph{6-interlaced} if there exist 6 distinct elements $a,b,c,d, e, f\in [n]$ such that the ordered set partitions of $\s$ and $\T$ restricts respectively to one of the two pairs
    \[
    \s|_{a,b,c,d,e,f}=(a,b,c,d,e,f) \quad\text{ and } \quad \T|_{a,b,c,d,e,f}=(c,d,a,b,e,f).
    \]
    \[
    \s|_{a,b,c,d,e,f}=(a,b,c,d,e,f) \quad\text{ and } \quad \T|_{a,b,c,d,e,f}=(a,d,e,b,c,f);
    \]
\end{definition}
These three cases completely characterize compatible non-degenerate partitions.
\begin{theorem}\label{thm:interlaced}
	Let $\s$ and $\T$ be two non-degenerate ordered set partitions. 
	Then $\s$ and $\T$ are not compatible if and only if they are $4$- or $6$-interlaced.
	
	In particular, $\s$ and $\T$ are compatible if and only if $\s_I$ and $\T_I$ are compatible for any $I$ of size at most 6.
\end{theorem}

In the case of full-dimensional simplices~\Cref{thm:interlaced} is a refinement of~Theorem~\hyperref[thm:B]{B}.
We begin by proving that interlaced pairs are indeed incompatible.

\begin{proposition}\label{prop:interlacing}
	Let $\s$ and $\T$ be two non-degenerate set partitions. If $\s$ and $\T$ are $4$- or $6$-interlaced, then $\s$ and $\T$ are not compatible.
\end{proposition}
\begin{proof}
The proof proceeds by distinguishing the three types of interlacing above by finding a violating cycle in $G_{\s,\T}$ in each case.
First assume that $\s$ and $\T$ are $4$-interlaced.
W.l.o.g.\ after relabeling we can assume that the elements $a,b,c,d$ are the number $1,2,3,4$ in this order.
Thus, $\s|_{1,2,3,4}=(1,2,3,4)$ and $\T|_{1,2,3,4}=(3,2,1,4)$.
In this case, we find the violating cycle $1 \upto 2 \downto 3 \upto 4 \downto 1$ of length $4$ in $G_{\s, \T}$.

The other two cases are treated analogously.
\end{proof}


The converse of this statement is the missing piece in the proof of ~\Cref{thm:interlaced}.

\begin{proof}[Proof of~\Cref{thm:interlaced}]
To prove the theorem we show that for any pair $\s$ and $\T$ of incompatible non-degenerate set partitions of $[n]$ with $n>6$, there exists a proper subset $I\subset [n]$ such that $\s_I$ and $\T_I$ are not compatible. Therefore, by applying this reduction iteratively, we will obtain a proper subset $I$ of size $\leq 6$ such that $\s_I$ and $\T_I$ are not compatible.
The theorem then follows from an explicit check of compatibility of ordered set partitions for $n\leq 6$.

To prove the existence of $I$, let us assume the following reduction.
By \Cref{thm:set_partitions} compatibility of $\s$ and $\T$ is equivalent to the existence of  a violating cycle $C$ in $G_{\s, \T}$. Therefore the restriction of the set partitions $\s$ and $\T$ to the vertices involved in the cycle of $C$ is still incompatible.
Hence it is enough for us to study the case when the violating cycle $C$ passes through all vertices of  $G_{\s, \T}$.
Moreover, we can assume that all upper and all lower path segments of $C$ are just single edges as we could otherwise restrict to start and end vertices of these segments and obtain a violating cycle on fewer vertices; note that since the cycle is violating the vertices in the middle of such segments are met by the cycle exactly once.
So in total the cycle $C$ visits every vertex exactly once and the edges in $C$ alternate between upper and lower vertices.
Further without loss of generality we can assume that $\s=(1,\ldots,n)$ is the standard cyclic order on $[n]$ and $\T = (j_1,\ldots,j_n)$.

   
For a cyclic order $\T=(j_1,\ldots, j_n)$ we define its $i$-th step $s_i$ to be 
\[
s_i =  j_{i+1}-j_{i} \mod n,
\]
for $i<n$ and the $n$-th step to be $j_1-j_n\mod n$.
Let us assume that there is $i$ such that the $i$-th step in $\T$ is not 1 or 3. We will construct a violating cycle $C'$ strictly shorter than~$C$, i.e., not passing through all vertices of $G_{\s, \T}$.
The existence of $C'$ proves the theorem under the assumption that not all the steps in $\T$ are equal to 1 or 3.
The case that this assumption is not true is dealt with in \Cref{cor:13stepsinterlaced}.

Let $s_i\ne 1,3$ be the $i$-th step in $\T$. 
We can assume that the cycle $C$ contains the edges $j_{i+1}-3 \,\upto\, j_{i+1}-2$ and $j_{i+1}-1 \,\upto\, j_{i+1}$ of $G_\s$. If not, we can consider the complementary cycle to $C$.
Thus, the cycle $C$ consists of the concatenation of the four segments $j_{i+1}-3 \,\upto\, j_{i+1}-2$, $P_1$, $j_{i+1}-1 \,\upto\, j_{i+1}$, and $P_2$ where $P_1$ is an alternating path from $j_{i+1}-2$ to $j_{i+1}-1$ and $P_2$ is an alternating path from $ j_{i+1}$ to $j_{i+1}-3$.
Note that both paths start and end with a lower edge.

Let $C'$ be the cycle comprised of the two segments $j_{i+1}-3 \,\upto\, j_{i+1}-2 \upto j_{i+1}-1 \,\upto\, j_{i+1}$ and~$P_2$.
It is easy to see that $C'$ is still violating.
By removing the vertices $ j_{i+1}-2$ and  $ j_{i+1}-1$ we thus get a shorter violating cycle of the two segments $j_{i+1}-3 \,\upto\, j_{i+1}$ and $P_2$ in the graph corresponding to the restricted set partitions $\s|_{\left[n\right]\setminus\{j_{i+1}-2 \, ,\, j_{i+1}-1\}}$ and $\T|_{\left[n\right]\setminus\{j_{i+1}-2 \, ,\, j_{i+1}-1\}}$.
\end{proof}

\begin{proposition}\label{cor:13stepsinterlaced}
    Assume that $\T=(j_1,\ldots, j_n)$ is a non-degenerate ordered set partitions with all steps $s_i$ equal to either $1$ or $3$. Then there are only four possible cases:
    \begin{itemize}
        \item[(1)] $s_i=1$ for all $1\le i\le n$;
        \item[(2)] $n$ is not divisible by 3 and $s_i=3$ for all $1\le i \le n$;
        \item[(3)] $n=4k+2$ and $s_{2i-1}=1$, $s_{2i}=3$ for all $1\leq i\leq 2k+1$;
        \item[(4)] $n=4k+2$ and $s_{2i-1}=3$, $s_{2i}=1$ for all $1\leq i\leq 2k+1$.
    \end{itemize}
In particular, a nonstandard order $\T$ with all steps equal to either
1 or 3 is $4$- or $6$-interlaced with the standard order on $\left[n\right]$ for $n\ge 7$.
\end{proposition}


\section{Prominent alcoved polytopes}\label{sec:examples}


 In this section we will present three series of  polytopes which can be shown to be alcoved using Theorem~\hyperref[thm:B]{B}: the associahedron $A_{n}$, the cyclohedron $C_n$ and $\hat{D}_n$-polytope.
 The fact that associahedra and cyclohedra are alcoved is well-known, but our techniques give a new proof.
 The conclusion that the $\hat{D}_n$-polytope is alcoved is new to our knowledge.
 

One can show that the cyclohedron is normally equivalent to the Minkowski sum over all coarsenings of the OSP $(1,2,\ldots, n)$ such that at most one block has more than one element. Moreover, the associahedron normally equivalent to the Minkowski sum over all coarsenings of the OSP $(1,2,\ldots, n)$ such that at most one block has more than one element and $n$ is in this largest block. In particular, the associahedron is a Minkowski summand of the cyclohedron.


Finally, we present the $\hat{D}_n$-polytope as follows. For a cyclic interval $I = [s,t]\subset [n-1]$, let  $\s_{I}$ be an ordered set partition of $[n-1]$ which is given as follows
\[
\s_{I} = ([s,t],t+1, t+2, \ldots,s-1).
\]
Now for any partition $\s_{s,t}$ of $[n-1]$ we define the partition $\hat{\s}_{s,t}$ of $[n]$, by joining $n$-th point to the interval $[s,t]$, resulting in
\begin{equation}\label{eq:dhat}
\hat{\s}_{s,t} = ([s,t]\cup n, t+1, \ldots, s-1).
\end{equation}
In total there are $(n-1)^2$ of such partitions and we define $\hat{D}_n$ as
$\displaystyle \sum_{r,t\in [n-1]}\Delta_{\hat{\mathbf{S}}_{r,t}}.
$


The main result of this section is the following.
\begin{theorem}\label{thm: assocCycDHat}
    The associahedron $A_{n}$, the cyclohedron $C_n$ and the $\hat{D}_n$-polytope are alcoved.
\end{theorem}

\begin{proof}
    Since the  associahedron is a Minkowski summand of the cyclohedron, it is enough to show that $C_n$ and $\hat{D}_n$ are alcoved. Using Theorem~\hyperref[thm:A]{A} it is enough to show that any pair of simplices in the corresponding Minkowski sum is compatible.
    
    Let us start with $C_n$ and let $\mathbf{S},\mathbf{S}'$ be two ordered set partitions as above. Notice that for any subset $A\subset [n]$ of size $6$, the restrictions $\mathbf{S}|_A,\mathbf{S}'|_A$ again have the form of as above. Thus by Theorem~\hyperref[thm:B]{B} the compatibility of $\mathbf{S},\mathbf{S}'$ follows from the fact that $C_6$ is alcoved, which can be checked directly.

    The argument for $\hat{D}_n$ is similar. For $\s,\s'$ of the form \eqref{eq:dhat}, their restrictions  $\s|_A,\s'|_A$ to a subset $A\subset [n]$ of size $6$ are of the form of cyclohedron summand if $n\notin A$ and of the form \eqref{eq:dhat} if $n\in A$. So the compatibility of $\s,\s'$ follows from the fact that $C_6$ and $\hat{D}_6$ are alcoved. \qedhere
\end{proof}



\acknowledgements{The authors would like to thank Christian Haase, Thomas Lam, Raman Sanyal and Benjamin Schröter for fruitful discussions.
The main part of this research was carried out while the authors stayed as Oberwolfach Research Fellows at the Oberwolfach Research Institute for Mathematics.
\printbibliography


\end{document}
