%% 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]{FPSAC2023}
\articlenumber{4}
%% 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}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

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

\usepackage{tikz}
\usepackage{marvosym}
\usepackage{mathtools}
\usepackage{mathscinet}
\usepackage{wasysym}

\usepackage{subcaption}
%\captionsetup[subfloat]{labelfont=normalfont}
%\captionsetup[figure]{position=t}
%\renewcommand{\thesubfigure}{\alph{subfigure}}

\usetikzlibrary{positioning}
\usetikzlibrary{calc}

\theoremstyle{definition}
\newtheorem{defi}{Definition}
\newtheorem{exam}{Example}
\newtheorem{con}{Convention}

\newcommand{\nonconsec}[2]{\mathsf{int}_{#2}(#1)}
\newcommand{\derset}[2]{{\tilde{\mathbf{I}}_{#1}^{#2}}}
\newcommand{\walk}{\dashrightarrow}

\newcommand{\st}{\,\middle\vert\,} % For `such that' in sets
\newcommand{\set}[1]{\left\{\,#1\,\right\}} % For making a set with a condition. (To get the spacing right)
\newcommand{\onevec}{\mathbf{1}} % A vector of ones
\newcommand{\ivec}{E_{i}} % Vector with 1 in the i-th coordinate and zero elsewhere
\newcommand{\rvec}{r\ivec} % For adding r to the i-th coordinate etc.
\newcommand{\sv}[1]{sE_{#1}} % For one you want to change the subscript
\newcommand{\svec}{s\ivec}

\newcommand{\qdn}{Q(d, n)}

\newcommand{\shift}{\sigma}

\newcommand{\seg}[2]{\overline{#1#2}} % Line segment between two points

\newcommand{\darcs}[1]{d\text{-}\mathsf{simp}(#1)} % Set of d-arcs of a triangulation

\newcommand{\swr}{\taurus} % Symmetric intertwining

\DeclareMathOperator{\conv}{conv} % Convex hull

\newcommand{\nw}[1]{\textcolor{blue}{#1}}

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

%% define your title in the usual way
\title{Studying triangulations of even-dimensional cyclic polytopes via directed graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Nicholas J. Williams\thanks{\href{mailto:nicholas.williams@lancaster.ac.uk}{nicholas.williams@lancaster.ac.uk}. Nicholas J. Williams was supported by EPSRC grant EP/V050524/1.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, Fylde College, Lancaster University, Lancaster, LA1 4YF, United Kingdom}

%% 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 prove two results on triangulations of even-dimensional cyclic polytopes using the directed graphs (digraphs) implicitly associated to them by Oppermann and Thomas. First, we show that the digraph of a $2d$-dimensional triangulation encodes whether or not the triangulation has an interior $(d + 1)$-simplex, and we describe the digraphs of such triangulations. Secondly, we show that the digraph of the triangulation allows one to identify the internal $d$-simplices which admit bistellar flips. This also allows one to easily compute the outcome of a bistellar flip.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Cyclic polytopes, triangulations, bistellar flips}

%% 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{fpsacbiblio.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\DeclareFieldFormat{postnote}{#1}

\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}

Cyclic polytopes are a very special family of polytopes. Perhaps their most famous property is that they attain equality in the Upper Bound Theorem \cite{mcmullen}: they have the largest possible number of faces of every single dimension out of all polytopes with a given dimension and number of vertices. This result was generalised by Stanley \cite{stanley_upper}, which gave birth to what is now called `Stanley--Reisner theory'. Another remarkable property of cyclic polytopes is that for every $n$ and for every sufficiently large collection of points in $\mathbb{R}^{m}$ in general position, there exists a subset of $n$ points which form the vertices of a polytope combinatorially equivalent to a cyclic polytope \cite{cd}. In fact, cyclic polytopes are precisely the polytopes which have this property \cite[Proposition~9.4.7]{blswz}. This is a higher-dimensional version of the Erd\H{o}s--Szekeres Theorem, and is related to Ramsey theory.

Triangulations of cyclic polytopes are particularly interesting, and for several reasons. For one thing, they are relatively well-understood amongst triangulations of high-dimensional polytopes \cite[Section~6.1]{lrs}, admitting elegant combinatorial descriptions \cite{ot,njw-hst}. However, there are yet many unresolved problems, such as finding a formula for the number of triangulations of a cyclic polytope. This has been solved in certain cases \cite{as_triang_num}, but is even still an open problem for three-dimensional cyclic polytopes. But the principal reason triangulations of cyclic polytopes are interesting is that their combinatorial structure describes many phenomena in other areas of mathematics, including representation theory \cite{ot,njw-hst}, higher category theory \cite{kv-poly,dk-segal}, integrable systems \cite{dm-h,njw-hbo}, and scattering amplitudes \cite{amplituhedron}. In many of these cases, the poset structure on triangulations of cyclic polytopes appears. Two such poset structures were introduced in \cite{kv-poly} and \cite{er}, but these were proven to be the same in \cite{njw-equal}.

In this paper, which is an extended abstract of \cite{njw-apr}, we study triangulations of even-dimensional cyclic polytopes. Even- and odd-dimensional cyclic polytopes behave quite differently, and it is the even-dimensional cyclic polytopes which behave analogously to convex polygons. In particular, we study triangulations of even-dimensional cyclic polytopes by associating digraphs to them, in a way that was done implicitly in \cite{ot}. Results aside, this provides a visual tool for studying complex high-dimensional objects which are otherwise impossible to visualise. The digraph $Q(\mathcal{T})$ of a triangulation $\mathcal{T}$ of a $2d$-dimensional cyclic polytope has the internal $d$-simplices of $\mathcal{T}$ as its vertices. The arrows of the digraph connect simplices which are adjacent to each other in the triangulation, in a precise sense.

Our first result shows that the digraph $Q(\mathcal{T})$ of a triangulation $\mathcal{T}$ of the cyclic polytope $C(n + 2d + 1, 2d)$ tells whether or not the triangulation contains interior $(d + 1)$-simplices, that is, $(d + 1)$-simplices whose facets do not lie in the boundary of the polytope.

\begin{thm}[{\cite{njw-apr}}]
A triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$ contains no interior $(d + 1)$-simplices if and only if $Q(\mathcal{T})$ is a cut digraph and this is the case if and only if $Q(\mathcal{T})$ does not contain an oriented cycle.
\end{thm}

We define cut digraphs in \cref{sect:back:cut}. They are the higher-dimensional analogues of orientations of the type~$A$ Dynkin diagram.

As an application of this theorem, we prove that the triangulations of $C(n + 2d + 1, 2d)$ without interior $(d + 1)$-simplices form a connected subgraph of the flip graph of triangulations of $C(n + 2d + 1, 2d)$. The flip graph of a polytope is the graph whose vertices are triangulations of the polytope, with edges between triangulations related by a bistellar flip. Here bistellar flips are the higher-dimensional analogues of flipping a diagonal inside a quadrilateral.

Our second result studies bistellar flips of triangulations of even-dimensional cyclic polytopes. It is obvious that every internal edge of a polygon triangulation can be flipped, but the corresponding statement does not hold in higher dimensions. Indeed, Oppermann and Thomas show that bistellar flips of triangulations of $2d$-dimensional cyclic polytopes correspond to replacing one internal $d$-simplex in a triangulation with another. However, not every internal $d$-simplex in a triangulation of a $2d$-dimensional cyclic polytope is replaceable in this way. We call an internal $d$-simplex \emph{mutable} if it can be replaced in a bistellar flip.

We show that the digraph of a triangulation encodes the mutability of internal $d$-simplices. We show how the digraph can be decomposed into certain paths, which we call `retrograde paths', such that the following result holds.

\begin{thm}[{\cite{njw-apr}}]
An internal $d$-simplex is mutable if and only if it does not lie in the middle of a retrograde path in the digraph of the triangulation.
\end{thm}

One can then, in fact, read off the outcome of the bistellar flip from the digraph.

This paper is structured as follows. We start in \cref{sect:back} by giving background, primarily on cyclic polytopes and their triangulations. In \cref{sect:simp}, we define the digraph of a triangulation and describe the digraphs of $2d$-dimensional triangulations without interior $(d + 1)$-simplices. In \cref{sect:mut}, we present the second main result of the paper, which shows how the digraphs of triangulations can be used to identify mutable internal $d$-simplices.

\section{Background}\label{sect:back}

\subsection{Cyclic polytopes}\label{sect:back:cyc}

An introduction to cyclic polytopes, as well as historical background, can be found in \cite[4.7]{gruenbaum}. In this paper, we are only interested in even-dimensional cyclic polytopes, which can be realised in the following way. Let $n \geqslant 0$ and $d \geqslant 1$ and consider the curve defined by $q \colon (0, 2\pi] \to \mathbb{R}^{2d}$, \[q(t) = (\cos t, \sin t, \cos 2t, \sin 2t, \dots, \cos dt, \sin dt)\] which is known as the \emph{Carath\'eodory curve}, after \cite{car1907,car1911}. The (\emph{regular}) \emph{cyclic polytope} $C(n + 2d + 1, 2d)$ is the convex hull \[\conv\left\{q\left(\frac{1}{n + 2d + 1}2\pi\right), q\left(\frac{2}{n + 2d + 1}2\pi\right), \dots , q\left(2\pi\right) \right\}.\] The vertices of $C(n + 2d + 1, 2d)$ are labelled by $[n + 2d + 1] := \{1, 2, \dots, n + 2d + 1\}$, such that $q(2\pi i/(n + 2d + 1))$ is vertex $i$.

A \emph{triangulation} of a cyclic polytope $C(n + 2d + 1, 2d)$ is a set of $2d$-simplices whose vertices are vertices of $C(n + 2d + 1, 2d)$, whose interiors are pairwise disjoint and whose union is $C(n + 2d + 1, 2d)$.

\begin{con}
In this paper we specify $k$-simplices by their vertex tuples, for instance, $A = (a_{0}, a_{1}, \dots, a_{k}) \in [n + 2d + 1]^{k + 1}$, where $a_{0} < a_{1} < \dots < a_{k}$. We always follow the convention that simplices are denoted by upper case letters, with their vertices denoted by the corresponding lower case letters with subscripts.

Furthermore, we allow vertex tuples to be reordered using cyclically shifted orderings. The \emph{cyclically shifted order} $<_{i}$ is the order \[i <_{i} i + 1 <_{i} \dots <_{i} n + 2d + 1 <_{i} 1 <_{i} 2 <_{i} \dots <_{i} i - 1.\] Hence $<_{1}$ is the usual order. For example, by changing the order on $[n + 2d + 1]$, we allow the simplex $(1, 3, 5)$ to be represented by $(5, 1, 3)$ or $(3, 5, 1)$ as well.

We say that $a_{0}, a_{1}, \dots, a_{k}$ are \emph{cyclically ordered} if $a_{0} <_{i} < a_{1} <_{i} \dots <_{i} a_{k}$ for some $i$.
\end{con}

Triangulations of even-dimensional cyclic polytopes were given an elegant combinatorial description in \cite{ot}, which we now explain. A $d$-simplex of a triangulation of $C(n + 2d + 1, 2d)$ is \emph{internal} if it does not lie within a facet of $C(n + 2d + 1, 2d)$, recalling that a \emph{facet} is a face of codimension one. It is clear that a triangulation of a convex polygon is determined by the internal edges of the triangulation; similarly, a triangulation of any $2d$-dimensional convex polytope is determined by the internal $d$-simplices of the triangulation, by a theorem of Dey \cite{dey}. We write $\darcs{\mathcal{T}}$ for the set of internal $d$-simplices of $\mathcal{T}$. We say that a $(d + 1)$-simplex of $\mathcal{T}$ is \emph{interior} if all of its facets are internal $d$-simplices.

There exist combinatorial criteria for when $d$-simplices in $C(n + 2d + 1, 2d)$ are internal $d$-simplices and for when internal $d$-simplices intersect in their interiors. Indeed, a $d$-simplex $A \in [n + 2d + 1]^{d + 1}$ is an internal $d$-simplex in $C(n + 2d + 1, 2d)$ if and only if $A$ contains no consecutive elements in the cyclic ordering of $[n + 2d + 1]$. A $d$-simplex $A$ and a $d$-simplex $B$ are \emph{intertwining} if \[ a_{0} < b_{0} < a_{1} < b_{1} < \dots < a_{d} < b_{d}\] is a cyclic ordering, in which case we write $A \swr B$. Two internal $d$-simplices intersect in their interiors if and only if they intertwine, as can easily be seen in the $d = 1$ case. A collection of $d$-simplices is called \emph{non-intertwining} if no pair of its elements are intertwining.

\begin{thm}[{\cite[Theorem 2.3, Theorem 2.4]{ot}}]
There is a bijection between triangulations of $C(n + 2d + 1, 2d)$ and non-intertwining sets of $\binom{n + d - 1}{d}$ $d$-simplices in $\nonconsec{n + 2d + 1}{d}$, via sending \[\mathcal{T} \mapsto \darcs{\mathcal{T}}.\]
\end{thm}

The corresponding description for triangulations of odd-dimensional cyclic polytopes was found in \cite[Section~4]{njw-hst}.

Triangulations of cyclic polytopes can be \emph{mutated} by operations known as \emph{bistellar flips} \cite[Section~2.4]{lrs}. The following theorem can be taken as a definition of this operation in the case of triangulations of $C(n + 2d + 1, 2d)$.

\begin{thm}[{\cite[Theorem~4.1]{ot}}]\label{thm:flip}
Triangulations $\mathcal{T}$ and $\mathcal{T}'$ of $C(n + 2d + 1,2d)$ are bistellar flips of each other if and only if $\darcs{\mathcal{T}}$ and $\darcs{\mathcal{T}'}$ have all but one element in common.
\end{thm}

Therefore, given a triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$, we call an internal $d$-simplex $A \in \darcs{\mathcal{T}}$ \emph{mutable} if there exists a triangulation $\mathcal{T}'$ such that \[\darcs{\mathcal{T}'} = (\darcs{\mathcal{T}} \setminus \{A\}) \cup \{B\},\] where $A \neq B$.

\subsection{Cuts}\label{sect:back:cut}

We will associate digraphs to triangulations of even-dimensional cyclic polytopes and show what properties of the triangulation are encoded in the digraph. Indeed, we now define the digraphs which are higher analogues of orientations of the $A_{n}$ Dynkin diagram, following \cite{io}. The main result of the first part of this paper is that these digraphs tell that a triangulation of $C(n + 2d + 1, 2d)$ has no interior $(d + 1)$-simplices.

Let $\qdn$ be the digraph with vertices \[Q_{0}(d,n) := \set{(a_{0}, \dots, a_{d}) \in \mathbb{Z}_{\geqslant 0}^{d + 1} \st \sum_{i = 0}^{d}a_{i} = n - 1}\] and arrows $Q_{1}(d, n) := \set{A \to A + F_{i} \st A, A + F_{i} \in Q_{0}(d, n)}$, where $F_{i} = (\dots, 0, \overset{i}{-1}, \overset{i + 1}{1},$ $0, \dots)$, with $F_{d} = (1, 0, \dots, 0, -1)$. See \cref{fig:qdn_ex} for pictures of these digraphs.

A subset $C \subseteq Q_{1}(d, n)$ is called \emph{cut} if it contains exactly one arrow from each $(d + 1)$-cycle in $Q(d, n)$. Given a cut $C$, we write $Q_{C}(d, n)$ for the digraph with arrows $Q_{1}(d, n) \setminus C$ and refer to this as the \emph{cut digraph}. Examples of cut digraphs can be seen in \cref{fig:qdn_cuts}. Note that the cut digraphs of $Q(1, n)$ are precisely the orientations of the $A_{n}$ Dynkin diagram.

\begin{figure}
\caption{Examples of the digraphs $\qdn$}\label{fig:qdn_ex}
\[
\begin{tikzpicture}

%%%%%%%%%%%%%%%%%%%%%%%%
% A_4
%%%%%%%%%%%%%%%%%%%%%%%%

\begin{scope}[shift={(-3,1)},xscale=1.5]

\node(30) at (0,0) {30};
\node(21) at (1,0) {21};
\node(12) at (2,0) {12};
\node(03) at (3,0) {03};

\draw[transform canvas={yshift=1mm},->] (30) -- (21);
\draw[transform canvas={yshift=-1mm},->] (21) -- (30);

\draw[transform canvas={yshift=1mm},->] (21) -- (12);
\draw[transform canvas={yshift=-1mm},->] (12) -- (21);

\draw[transform canvas={yshift=1mm},->] (12) -- (03);
\draw[transform canvas={yshift=-1mm},->] (03) -- (12);

\node at (1.5,-2) {$Q(1,4)$};

\end{scope}

%%%%%%%%%%%%%%%%%%%%%%%%%%
% A_3^2
%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{scope}[shift={(3,0)}]

\node(200) at (0,0) {200};
\node(110) at (1,1) {110};
\node(020) at (2,2) {020};
\node(011) at (3,1) {011};
\node(002) at (4,0) {002};
\node(101) at (2,0) {101};

\draw[->] (200) -- (110);
\draw[->] (110) -- (020);
\draw[->] (020) -- (011);
\draw[->] (011) -- (002);
\draw[->] (002) -- (101);
\draw[->] (101) -- (200);
\draw[->] (110) -- (101);
\draw[->] (101) -- (011);
\draw[->] (011) -- (110);

\node at (2,-1) {$Q(2,3)$};

\end{scope}

\end{tikzpicture}
\]
\end{figure}

\begin{figure}
\caption{Cuts of the digraphs $\qdn$}\label{fig:qdn_cuts}
\[
\begin{tikzpicture}

%%%%%%%%%%%%%%%%%%%%%%%%
% A_4
%%%%%%%%%%%%%%%%%%%%%%%%

\begin{scope}[shift={(-3,1)},xscale=1.5]

\node(30) at (0,0) {30};
\node(21) at (1,0) {21};
\node(12) at (2,0) {12};
\node(03) at (3,0) {03};

\draw[transform canvas={yshift=1mm},->] (30) -- (21);
\draw[transform canvas={yshift=-1mm},->,dotted] (21) -- (30);

\draw[transform canvas={yshift=1mm},->,dotted] (21) -- (12);
\draw[transform canvas={yshift=-1mm},->] (12) -- (21);

\draw[transform canvas={yshift=1mm},->,dotted] (12) -- (03);
\draw[transform canvas={yshift=-1mm},->] (03) -- (12);

\node at (1.5,-2) {$Q_{C}(1,4)$};

\end{scope}

%%%%%%%%%%%%%%%%%%%%%%%%%%
% A_3^2
%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{scope}[shift={(3,0)}]

\node(200) at (0,0) {200};
\node(110) at (1,1) {110};
\node(020) at (2,2) {020};
\node(011) at (3,1) {011};
\node(002) at (4,0) {002};
\node(101) at (2,0) {101};

\draw[->] (200) -- (110);
\draw[->,dotted] (110) -- (020);
\draw[->] (020) -- (011);
\draw[->] (011) -- (002);
\draw[->] (002) -- (101);
\draw[->,dotted] (101) -- (200);
\draw[->] (110) -- (101);
\draw[->,dotted] (101) -- (011);
\draw[->] (011) -- (110);

\node at (2,-1) {$Q_{C}(2,3)$};

\end{scope}

\end{tikzpicture}
\]
\end{figure}

\section{Triangulations without interior \texorpdfstring{$(d + 1)$}{d + 1}-simplices}\label{sect:simp}

In this section, we introduce the digraph of a triangulation of a $2d$-dimensional cyclic polytope, following \cite{ot}. We give the first main result, which states that the digraph detects when the triangulation has no interior $(d + 1)$-simplices and describes such digraphs. We outline how this result is proved.

The digraph of a polygon triangulation was implicitly introduced in \cite{fz1}. The vertices of the digraph are given by internal edges of the triangulation, with an arrow from one internal edge to another if the one precedes the other in the clockwise ordering of the edges of one of the triangles. The key tool used to study triangulations in this paper is the following generalisation of this notion to triangulations of arbitrary even-dimensional cyclic polytopes.

\begin{defi}\label{def:digraph}
Given a triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$, we define the \emph{digraph} $Q(\mathcal{T})$ of $\mathcal{T}$ to be the following directed graph. The vertices are \[Q_{0}(\mathcal{T}) = \darcs{\mathcal{T}}.\]

The arrows of $Q(\mathcal{T})$ are \[Q_{1}(\mathcal{T}) = \set{A \rightarrow A + \rvec \st \parbox{7.2cm}{\centering $A, A + \rvec \in \nonconsec{n + 2d + 1}{d}$, \\ $\nexists s \in [r - 1] \text{ such that } A + \svec \in Q_{0}(\mathcal{T})$}},\] where \[E_{i} := (\dots, 0, \overset{i}{1}, 0, \dots).\]
\end{defi}

This was implicitly introduced in \cite{ot}, but some work is required to show that the digraph which arises in \cite{ot} coincides with the one from the definition above. The details can be found in \cite{njw-apr}. Note that in \cite{njw-apr} and other related literature, digraphs are known as `quivers'.

\begin{exam}\label{ex:quiv}
Consider the triangulation $\mathcal{T}$ of $C(8, 4)$ with the set of $4$-simplices \[\{12345, 12356, 12367, 12378, 13456, 13467, 13478, 14567, 14578, 15678\}.\] Here we write $12345$ for the $4$-simplex $(1, 2, 3, 4, 5)$, and so on. One can compute the internal $d$-simplices of $\mathcal{T}$ by finding the internal $d$-simplices which are faces of these $4$-simplices, obtaining \[\darcs{\mathcal{T}} = \{135, 136, 137, 146, 147, 157\}.\] These form the vertices of $Q(\mathcal{T})$. Using the definition of the arrows of $Q(\mathcal{T})$, one obtains that $Q(\mathcal{T})$ is the digraph \[
\begin{tikzpicture}

\node(135) at (0,0) {$135$};
\node(136) at (1,1) {$136$};
\node(137) at (2,2) {$137$};
\node(146) at (2,0) {$146$};
\node(147) at (3,1) {$147$};
\node(157) at (4,0) {$157$.};

\draw[->] (135) -- (136);
\draw[->] (136) -- (137);
\draw[->] (137) -- (147);
\draw[->] (147) -- (157);
\draw[->] (146) -- (147);
\draw[->] (136) -- (146);

\end{tikzpicture}
\] This is a more informative picture than simply considering the set of 4-simplices.
\end{exam}

Recall that a $(d + 1)$-simplex of a triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$ is \emph{interior} if all of its facets are internal $d$-simplices. The first main theorem of the paper describes digraphs of $2d$-dimensional triangulations with no $(d + 1)$-simplices.

\begin{thm}\label{thm:interior}
A triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$ has no interior $(d + 1)$-simplices if and only if its digraph $Q(\mathcal{T})$ is a cut of $\qdn$, and this is the case if and only if its digraph has no cycle.
\end{thm}

It was implicit in the relation between the two papers \cite{io} and \cite{ot} that cuts of $\qdn$ corresponded to a particular class of triangulations of $C(n + 2d + 1, 2d)$, but these papers left open what class of triangulations this was. The embedding of $Q(\mathcal{T})$ into $\qdn$ is not unique, even up to symmetries of $\qdn$. However, there are certain canonical embeddings which are unique up to said symmetries.

As an application of \cref{thm:interior}, we prove that the set of triangulations of $C(n + 2d + 1, 2d)$ with no interior $(d + 1)$-simplices forms a connected subgraph of the flip graph of $C(n + 2d + 1, 2d)$. Here, the \emph{flip graph} of $C(n + 2d + 1, 2d)$ is the graph whose vertices are triangulations of $C(n + 2d + 1, 2d)$, with edges connecting triangulations related by a bistellar flip.

\begin{exam}
It is straightforward to illustrate the two-dimensional version of \cref{thm:interior}. In \cref{fig:int_triang}, the triangulation on the left contains the internal triangle 135, and so the digraph has a cycle, whereas the digraph on the right has no internal triangles, and so its digraph is an orientation of the type~$A$ Dynkin diagram.

In four dimensions, one cannot draw the triangulations directly, but one can still draw their digraphs. The triangulation on the left-hand side of \cref{fig:int_simp} has set of $4$-simplices \[\{12347, 12356, 12467, 12378, 13478, 14567, 14578, 15678, 23456, 23467\},\] and has no internal $3$-simplices. The triangulation on the right-hand side of \cref{fig:int_simp} has set of $4$-simplices \[\{12345, 12356, 12367, 12378, 13458, 13567, 13578, 34578, 15678, 34567\},\] with $1357$ forming an internal $3$-simplex. Note that the cycle this internal $3$-simplex gives in the digraph does not exclusively have faces of $1357$ as its vertices: $136$ and $358$ are also present in the cycle, but are not faces of this internal $3$-simplex.
\end{exam}

\begin{figure}
\caption{Triangulations of polygons with and without interior triangles}\label{fig:int_triang}
\[
\begin{tikzpicture}

\begin{scope}[shift={(-3,0)}]

% Internal triangulation
\coordinate(2) at (0:2);
\node at (2) [right = 1mm of 2] {2};
\coordinate(1) at (60:2);
\node at (1) [above right = 1mm of 1] {1};
\coordinate(6) at (120:2);
\node at (6) [above left = 1mm of 6] {6};
\coordinate(5) at (180:2);
\node at (5) [left = 1mm of 5] {5};
\coordinate(4) at (240:2);
\node at (4) [below left = 1mm of 4] {4};
\coordinate(3) at (300:2);
\node at (3) [below right = 1mm of 3] {3};

\node(13) at ($(1)!0.5!(3)$) {};
\node(35) at ($(3)!0.5!(5)$) {};
\node(51) at ($(5)!0.5!(1)$) {};

\draw (1) -- (2);
\draw (2) -- (3);
\draw (3) -- (4);
\draw (4) -- (5);
\draw (5) -- (6);
\draw (6) -- (1);

\draw (1) -- (3);
\draw (3) -- (5);
\draw (1) -- (5);

\draw[->] (13) -- (51);
\draw[->] (51) -- (35);
\draw[->] (35) -- (13);

\end{scope}

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

\begin{scope}[shift={(3,0)}]

% Fan triangulation
\coordinate(2) at (0:2);
\node at (2) [right = 1mm of 2] {2};
\coordinate(1) at (60:2);
\node at (1) [above right = 1mm of 1] {1};
\coordinate(6) at (120:2);
\node at (6) [above left = 1mm of 6] {6};
\coordinate(5) at (180:2);
\node at (5) [left = 1mm of 5] {5};
\coordinate(4) at (240:2);
\node at (4) [below left = 1mm of 4] {4};
\coordinate(3) at (300:2);
\node at (3) [below right = 1mm of 3] {3};

\node(13) at ($(1)!0.5!(3)$) {};
\node(14) at ($(1)!0.5!(4)$) {};
\node(64) at ($(6)!0.5!(4)$) {};

\draw (1) -- (2);
\draw (2) -- (3);
\draw (3) -- (4);
\draw (4) -- (5);
\draw (5) -- (6);
\draw (6) -- (1);

\draw (1) -- (3);
\draw (1) -- (4);
\draw (6) -- (4);

\draw[->] (13) -- (14);
\draw[->] (64) -- (14);

\end{scope}

\end{tikzpicture}
\]
\end{figure}

\begin{figure}
\caption{Triangulations of $C(8, 4)$ with and without interior $3$-simplices}\label{fig:int_simp}
\[
\begin{tikzpicture}

\begin{scope}[shift={(3,0)}]

\node(135) at (0,0) {$135$};
\node(136) at (1,1) {$136$};
\node(137) at (2,2) {$137$};
\node(146) at (2,0) {$358$};
\node(147) at (3,1) {$157$};
\node(157) at (4,0) {$357$};

\draw[->] (135) -- (136);
\draw[->] (136) -- (137);
\draw[->] (137) -- (147);
\draw[->] (147) -- (157);
\draw[->] (157) -- (146);
\draw[->] (146) -- (135);

\end{scope}

\begin{scope}[shift={(-3,0)}]

\node(135) at (0,0) {$246$};
\node(136) at (1,1) {$247$};
\node(137) at (2,2) {$137$};
\node(146) at (2,0) {$146$};
\node(147) at (3,1) {$147$};
\node(157) at (4,0) {$157$};

\draw[->] (135) -- (136);
\draw[->] (147) -- (136);
\draw[->] (137) -- (147);
\draw[->] (147) -- (157);
\draw[->] (146) -- (135);
\draw[->] (146) -- (147);

\end{scope}

\end{tikzpicture}
\]
\end{figure}

\section{Identifying mutable \texorpdfstring{$d$}{d}-simplices}\label{sect:mut}

In this section, we outline our second main result, which allows one to identify the mutable internal $d$-simplices of a triangulation from the digraph of the triangulation. It is clear that every internal edge within a polygon triangulation is contained within a unique quadrilateral, and can therefore be flipped for the other diagonal of this quadrilateral to produce a new triangulation. As given in \cref{thm:flip}, the analogue of flipping an internal edge for a triangulation of a $2d$-dimensional cyclic polytope is exchanging one internal $d$-simplex for another. Recall from \cref{sect:back:cyc} that if an internal $d$-simplex can be exchanged for another internal $d$-simplex then it is called \emph{mutable}. Not every internal $d$-simplex is mutable, as is shown by the following example.

\begin{exam}\label{ex:flip}
Consider the triangulation $\mathcal{T}$ of $C(7, 4)$ with set of 4-simplices \[\mathcal{T} = \{12345, 12356, 12367, 13456, 13467, 14567\}.\] We then have \[\darcs{\mathcal{T}} := \{135, 136, 146\}.\] The internal $2$-simplex 135 can be mutated in this triangulation by replacing it with 246 to obtain the triangulation $\mathcal{T}'$ with \[\darcs{\mathcal{T}'} = \{246, 136, 146\}\] and set of 4-simplices \[\mathcal{T}' = \{12346, 12456, 12367, 13467, 14567, 23456\}.\] Similarly, the internal $2$-simplex 146 can be flipped in $\mathcal{T}$ to obtain the triangulation $\mathcal{T}''$ with \[\darcs{\mathcal{T}''} =\{135, 136, 357\}\] and set of 4-simplices \[\mathcal{T}'' = \{12345, 12356, 12367, 13457, 13567, 34567\}.\] However, one cannot perform a bistellar flip at the internal $2$-simplex 136. There is no triangulation of $C(7, 4)$ which has both the internal $2$-simplices 135 and 146 apart from $\mathcal{T}$. 
\end{exam}

The criterion in terms of the digraph for an internal $d$-simplex to be mutable uses the following notion.

\begin{defi}\label{def:retro}
Given a triangulation $\mathcal{T}$ of $C(n + 2d + 1, 2d)$, a path of length two \[(\dots, a_{i - 1}, a_{i}, a_{i + 1}, \dots) \to (\dots, a_{i - 1}, b_{i}, a_{i + 1}, \dots) \to (\dots, a_{i - 2}, b_{i - 1}, b_{i}, a_{i + 1}, \dots)\] in $Q(\mathcal{T})$ is \emph{retrograde at $(a_{0}, \dots, a_{i - 1}, b_{i}, a_{i + 1}, \dots, a_{d})$} if $b_{i - 1} < a_{i}$.

A path of length $\geqslant 2$ \[A_{0} \rightarrow A_{1} \rightarrow \dots \rightarrow A_{l} \rightarrow A_{l+1}\] is \emph{retrograde} if $A_{i-1} \rightarrow A_{i} \rightarrow A_{i+1}$ is retrograde at $A_{i}$ for all $i \in [l]$. For $i \in [l]$, we say that $A_{i}$ is \emph{in the middle} of this retrograde path. We consider paths of length one to be trivially retrograde.
\end{defi}

It is straightforward to show that every arrow in the digraph is contained in a unique maximal retrograde path. We then obtain the main theorem of the second half of this paper.

\begin{thm}\label{thm:retro}
Let $\mathcal{T}$ be a triangulation of $C(n + 2d + 1, 2d)$. Then an internal $d$-simplex of $\mathcal{T}$ is mutable if and only if it is not in the middle of a retrograde path in $Q(\mathcal{T})$.
\end{thm}

In fact, one can read off which internal $d$-simplex should result from the bistellar flip by comparing the adjacent internal $d$-simplices in the digraph. We do not state this procedure explicitly, but illustrate it in \cref{ex:comb_crit}. This then allows one to determine whether the bistellar flip is increasing or decreasing in the poset structure on the triangulations of $C(n + 2d + 1, 2d)$ mentioned in the introduction.

An interesting related question is how the digraph transforms under a bistellar flip. This should give a higher-dimensional version of the quiver mutation of \cite{fz2}. Presently, we are only able to understand limited cases \cite{njw-apr,io}.

\begin{exam}\label{ex:comb_crit}
We provide examples of how one may use this criterion to identify the mutable internal $d$-simplices of a triangulation. We also illustrate how to compute the internal $d$-simplex obtained from the bistellar flip. We represent maximal retrograde paths using consecutive arrows of the same colour.

We first consider the triangulation of $C(8,4)$ given in \cref{fig:cyc_triang}. The three retrograde paths in this digraph are $136 \to 137 \to 147$, $147 \to 157 \to 357$, and $357 \to 135 \to 136$. Here, the last path is seen to be retrograde by cyclically reordering using $<_{3}$ to $357 \to 351 \to 361$. The path $135 \to 136 \to 137$ is not retrograde since one has increased the same entry twice, instead of increasing the $i$-th entry and then the $(i - 1)$-th entry. Cyclically reordering using $<_{4}$, the path $571 \to 573 \to 513$ is not retrograde, since $1 \not< 1$. The mutable internal $2$-simplices of the triangulation are then 136, 147, and 357, since 137, 157, and 135 are the ones lying in the middle of retrograde paths.

The bistellar flip at the internal $2$-simplex $136$ can be computed as follows. We seek an internal $2$-simplex $abc$ which is intertwining with $136$. Then we must have $a = 2$, since this is the only number between $1$ and $3$. Moreover $b = 5$ since $135$ is adjacent to $136$ and $c = 7$ since $137$ is adjacent to $136$. Hence flipping $136$ yields $257$.

Note that maximal retrograde paths are not always of length $d$ for a triangulation of $C(n + 2d + 1, 2d)$. This is shown by the triangulation of $C(10,6)$ given in \cref{fig:one_short_triang}, where we use `A' to denote 10. We have three retrograde paths of length three, and then the retrograde path $1358 \to 1359 \to 1369$ of length two. The mutable internal $d$-simplices of this triangulation are 357A, 1368, 1479.

We finally illustrate the procedure for computing the outcome of a bistellar flip again, now using $1368$. We seek an internal $3$-simplex $abcd$ which intertwines with $1368$. Then $a = 2$ and $c = 7$ are forced. Looking at the adjacent simplices then gives us $b = 5$ and $d = 9$, yielding $2579$ as the outcome of the bistellar flip.

\begin{figure}
\caption{Triangulations for \cref{ex:comb_crit}}
\begin{subfigure}[t]{0.45\textwidth}
\caption{Triangulation of $C(8,4)$}\label{fig:cyc_triang}
\[
\begin{tikzpicture}[scale=1.1]

\node at (2,3) {};
\node(135) at (0,0) {$135$};
\node(136) at (1,1) {$136$};
\node(137) at (2,2) {$137$};
\node(146) at (2,0) {$357$};
\node(147) at (3,1) {$147$};
\node(157) at (4,0) {$157$};

\draw[red,->] (135) -- (136);
\draw[blue,->] (136) -- (137);
\draw[blue,->] (137) -- (147);
\draw[green,->] (147) -- (157);
\draw[red,->] (146) -- (135);
\draw[green,->] (157) -- (146);

\end{tikzpicture}
\]
\end{subfigure}
\begin{subfigure}[t]{0.45\textwidth}
\caption{Triangulation of $C(10,6)$}\label{fig:one_short_triang}
\[
\begin{tikzpicture}[scale=1.1,xscale=1.2]

\node(1359) at (0,0) {$1359$};
\node(1358) at (-1,-1) {$1358$};
\node(1369) at (1,-1) {$1369$};
\node(1357) at (-2,-2) {$1357$};
\node(1368) at (0,-2) {$1368$};
\node(1379) at (2,-2) {$1379$};
\node(357A) at (-2,-3) {$357A$};
\node(1479) at (2,-3) {$1479$};
\node(3579) at (-1,-4) {$3579$};
\node(1579) at (1,-4) {$1579$};

\draw[->,blue] (1358) -- (1359);
\draw[->,blue] (1359) -- (1369);
\draw[->,red] (357A) -- (1357);
\draw[->,red] (1357) -- (1358);
\draw[->,red] (1358) -- (1368);
\draw[->,green] (1368) -- (1369);
\draw[->,green] (1369) -- (1379);
\draw[->,green] (1379) -- (1479);
\draw[->,gray] (1479) -- (1579);
\draw[->,gray] (1579) -- (3579);
\draw[->,gray] (3579) -- (357A);

\end{tikzpicture}
\]
\end{subfigure}
\end{figure}
\end{exam}

\acknowledgements{I would like to thank the reviewers of my abstract for their helpful comments.}

%% 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}
