%% 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{100}
%% 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{lipsum}

%\resumetitle{Resumen}

%% define your title in the usual way
\title{A combinatorial proof of an identity involving Eulerian numbers}

%% 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[J. Valencia Porras]{\texorpdfstring{Jer\'onimo Valencia Porras\addressmark{1}}{Jer\'onimo Valencia Porras}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Combinatorics and Optimization, University of Waterloo, Canada\\}

%% 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 give a combinatorial proof of an identity that involves Eulerian numbers and was obtained algebraically by Brenti and Welker (2009). To do so, we study alcoved triangulations of dilated hypersimplices. As a byproduct, we describe the dual graph of these triangulations for the dilated standard simplex and the hypersimplex in terms of combinatorial objects, and conjecture their structure for dilated hypersimplices.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{
% Presentamos una prueba combinatoria de una identidad que involucra n\'umeros Eulerianos y fue obtenida algebr\'aicamente por Brenti y Welker (2009). Para ello, estudiamos triangualciones alcovadas de hipers\'implices dilatados. Como consecuencias adicionales, describimos el grafo dual de la triangulaci\'on en el caso del s\'implice est\'andar, conjeturamos su estructura en el caso de hipers\'implices generales, y probamos combinatoriamente que los n\'umeros Eulerianos coinciden con el volumen normalizado de los hipers\'implices. 
% }

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Alcoved polytope, Eulerian numbers, Hypersimplex, Dual graphs.}

%% 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}
\usepackage{amsmath,amssymb,subcaption,graphicx,amsthm,enumitem,mathpazo,xcolor,tikz-cd, multicol,comment,lipsum,leftindex}
\addbibresource{EulerianIdentityRefs.bib}
\appto\bibfont{\setlength{\emergencystretch}{1em}}

%% note the \printbibliography command at the end of the file which goes with these biblatex commands

%Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{question}[theorem]{Question}
%\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
%\numberwithin{equation}{section}
\Crefname{defn}{Definition}{Definitions}
\Crefname{theorem}{Theorem}{Theorems}
\Crefname{lemma}{Lemma}{Lemmas}

% New commands

\newcommand{\tcr}[1]{\textcolor{red}{#1}}
\newcommand{\tcb}[1]{\textcolor{blue}{#1}}
\newcommand{\tcg}[1]{\textcolor{gray}{#1}}

\newcommand\marginal[1]{\marginpar[\raggedleft\tiny #1]{\raggedright\tiny #1}}

\newcommand{\JV}[1]{\marginal{\textcolor{blue}{JV: #1}}}
\newcommand{\TODO}[2][To do: ]{{\textcolor{red}{\textbf{#1#2}}}}

% Math Operators

\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\alc}{alc}
\DeclareMathOperator{\lin}{lin}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\word}{word}
\DeclareMathOperator{\words}{words}
\DeclareMathOperator{\comp}{comp}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\pair}{pair}
\DeclareMathOperator{\des}{des}

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

Brenti and Welker \cite{BRENTI2009545} studied how the numerator of a rational formal power series transforms after taking a subsequence of the coefficients and computing its generating series. In order to do so, they study a linear transformation with fixed bases related to the following combinatorial objects. First, we denote by $[r]^d$ the set of \emph{words} of length $d$ in the elements $[r] := \{1,2,\ldots,r\}$. 

\begin{definition}\label{def:composition-set}
    For $d,r,i\in\mathbb{N}$ and $d\geq 1$, let $$\mathfrak{C}(r,d,i) := \left\{ (c_1,c_2,\ldots,c_d)\in\mathbb{N}^d \; \big | \; c_1+c_2+\cdots+c_d = i \; , \; c_j\leq r \text{ for } 1\leq j\leq d \right\}.$$ Denote by $C(r,d,i)$ the size of the set $\mathfrak{C}(r,d,i)$.
\end{definition}

The other set of objects comes from the power series $\sum_{k\geq 0} (k+1)^d z^k = \frac{A_d(z)}{(1-z)^{d+1}}$ that was considered by Euler while studying the Riemann $\zeta$-function \cite{euler-riemman}. The numerators $A_d(z)$ are the \emph{Eulerian polynomials} and it is well-known that $a_{d,k}$ counts the permutations of $d$ elements with $k$ descents. These numbers are commonly called \emph{Eulerian numbers}. For our purposes, and to make notation line-up in \Cref{sec:hypersimplices}, we adopt the following convention. 

\begin{definition}\label{def:Eulerian-numbers}
    Let $d\geq 1$ and $1\leq j \leq d$. Define $$\mathfrak{A}(d,j) := \left\{ \sigma\in \mathfrak{S}_d \; \big | \; \des(\sigma) = j-1 \right\}.$$ We denote the cardinality of this sets by $A(d,j) = |\mathfrak{A}(d,j)|$.
\end{definition}

\begin{remark}\label{rem:eulerian-convention}
    With the previous definition, the Eulerian numbers are given by $a_{d,k} = A(d,k+1)$. We will refer to the numbers $A(d,k)$ as the Eulerian numbers, but there is a necessary word of caution when interpreting them in terms of permutations.
\end{remark} 

By considering a change of basis, Brenti and Welker showed the following identities involving the cardinalities of the previous sets. We point out that these two equations follow from diagonalizing a matrix and computing the image of an eigenvector, so both $C(r,d,i)$ and $A(d,j)$ appear due to algebraic considerations.

\begin{prop}[{\cite[Proposition 2.3]{BRENTI2009545}}]\label{prop:identities}
    Let $d,r \geq 1$. Then 
    \begin{equation}\label{eq:identity-general-i}
        \sum_{j=0}^d C(r-1,d+1,ir-j)A(d,j) = r^d A(d,i)
    \end{equation}
    for $i=1,2,\ldots,d.$ In particular, when $i=1$,
    \begin{equation}\label{eq:identity-i-1}
        \sum_{j=0}^d C(r-1,d+1,r-j)A(d,j) = r^d.
    \end{equation}
\end{prop}

Given the enumerative nature of the quantities involved in the equations, Brenti and Welker asked for a combinatorial proof of these identities. Our main result is to provide one such proof by constructing suitable bijections.
The key idea that allows us connect both sides of the equations is to consider dilations of hypersimplices, in particular their \emph{alcoved triangulations} (see \Cref{sec:alcoved}), since the right-hand side of \Cref{eq:identity-general-i} can be interpreted as the (normalized) volume of these dilated polytopes (see \Cref{sec:hypersimplices}).

\begin{theorem}\label{thm:principal}
    Let $\mathcal{A}(r\Delta_{i,d})$ be the set of alcoves of the $r$-dilated hypersimplex $\Delta_{i,d}$. There exist bijections 
    \begin{align*}
        \words_i \; &:\; \mathcal{A}(r\Delta_{i,d})\longrightarrow [r]^d \times \mathfrak{A}(d,i) \\
        \pair_i\; &: \;\mathcal{A}(r\Delta_{i,d})\longrightarrow \bigcup_{j=1}^d \mathfrak{C}(r-1,d+1,ir-j)\times \mathfrak{A}(d,j)
    \end{align*}
    from which we obtain a combinatorial proof of \Cref{eq:identity-general-i}.
\end{theorem}

This document is organized as follows. In \Cref{sec:alcoved} we review some relevant results about alcoved polytopes. In \Cref{sec:delta-1-d-simplices-labels} we construct the bijection needed to show \Cref{eq:identity-i-1} by considering dilated standard simplices; moreover, we describe the dual graph of the triangulation using the combinatorial objects involved in the bijection. We generalize these ideas in \Cref{sec:delta-i-d-simplices-labels} to build the bijections that prove \Cref{eq:identity-general-i} combinatorially, and describe the dual graph of the alcoved triangulation of a hypersimplex using permutations. We conclude with some further directions in \Cref{sec:final_remarks}.

\begin{remark}
    After completion of this document, we found \cite[Proposition 9.4]{alcoved2} where the authors give a formula for the volume of \emph{thick hypersimplices} and specializes to \Cref{eq:identity-general-i} when $\Phi = A_n$ and the parameters are carefully chosen. We point out that their argument relies on considerations of the alcoved triangulations related to affine Weyl groups and, in contrast, we provide a proof of \Cref{eq:identity-general-i,eq:identity-i-1} by interpreting alcoves in terms of combinatorial objects. Moreover, the equations are related to recent work on slices of prisms (see \cite[Corollaries 1.5 and 1.6]{ferroni2024lattice}).
\end{remark}

\section{Alcoved polytopes}\label{sec:alcoved}

Given a set of vectors in $\mathbb{R}^n$, their \emph{convex hull} is the smallest convex set containing all of them. A \emph{polytope} is the convex hull of finitely many vectors in $\mathbb{R}^n$. The \emph{vertices} of $P$ is the smallest set of vectors such that their convex hull equals $P$. 
A \emph{lattice polytope} is a polytope whose vertices only have integer coordinates. 
We focus on a particular family of lattice polytopes known as \emph{alcoved polytopes}.
There are two ways in which alcoved polytopes usually appear in the literature, depending on the coordinates that are chosen to describe them.

\begin{definition}\label{def:alcoved_polytopes}
    An \emph{alcoved polytope} $P$ is a polytope that has one of the following hyperplane descriptions:
    \begin{itemize}
        \item An $(H,z)$-representation $$P = \left\{ \vec{z}\in\mathbb{R}_z^{n-1}:b_{ij} \leq z_i-z_j \leq c_{ij} \;\; \text{for} \;\; 0\leq i < j \leq n-1 \right\}$$ where $z_0 := 0$ and $b_{ij},c_{ij} \in \mathbb{Z}$ for all $i$ and $j$.

        \item An $(H,x)$-representation $$P = \left\{ \vec{x}\in\mathbb{R}_x^{n} \; : \; 
        \begin{matrix}
            b_{ij} \leq x_{i+1}+\cdots+x_j \leq c_{ij} \;\; \text{for} \;\; 0\leq i < j \leq n \\ 
            x_1+x_2+\cdots+x_n = k
        \end{matrix}
        \right\}$$ where $k\in \mathbb{Z}$ and $b_{ij},c_{ij} \in \mathbb{Z}$ for all $i$ and $j$.
    \end{itemize}
\end{definition}

% \begin{remark}\label{rem:equivalent_defs}
%     Both of these descriptions give rise to affinely equivalent polytopes. Indeed,  consider the maps $\varphi \, : \, \mathbb{R}_x^{n} \to \mathbb{R}_z^{n-1}$ given by $$\varphi(x_1,x_2,\ldots,x_n) = (x_1\,,\,x_1+x_2\,,\,x_1+x_2+x_3\,,\ldots,\,x_1+x_2+\cdots+x_{n-1})$$ and $\psi_k\, : \, \mathbb{R}_z^{n-1} \to \mathbb{R}_x^{n}$ given by $$\psi_k(z_1,z_2,\ldots,z_{n-1}) = (z_1\,,\,z_2-z_1\,,\ldots,\,z_{n-1}-z_{n-2}\,,\,k-z_{n-1}).$$ 
% \end{remark}

\begin{example}\label{ex:alcoved_polytopes}

The alcoved polytope $P = P(b_{ij},c_{ij})$ in $z$-coordinates with parameters $b_{0,1} = -4$, $c_{0,1} = -1$, $b_{0,2} = -3$, $c_{0,2} = -1$, $b_{1,2} = -2$, $c_{1,2} = 1$ is depicted in \Cref{fig:alcoved_example}. The map $\psi_2(z_1,z_2) = (z_1,z_2-z_1,2-z_2)$ is an affine equivalence to a polytope in $x$-coordinates. After translating such polytope by the vector $(1,1,1),$ we obtain a polytope that lays on the hyperplane $x_1+x_2+x_3 = 5$ in $\mathbb{R}^3_x.$

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{alcoved.pdf}
    \caption{On the left, an alcoved polytope with its explicit $(H,z)$-representation; the dotted lines represent the elements of the affine Coxeter arrangement of type $A_2$. On the right, the image of the polytope under the map $\psi_2$ after translation by $(1,1,1)$.}
    \label{fig:alcoved_example}
\end{figure}    
\end{example}

The most important alcoved polytopes for our purposes are the hypersimplices. 

\begin{definition}\label{def:hypersimplices}
    The \emph{$i$-th hypersimplex of dimension $d$}, denoted by $\Delta_{i,d}$, is the polytope with $(H,x)$-representation
    \begin{equation}\label{eq:hypersimplex}
        \Delta_{i,d} = \left\{ (x_1,x_2,\ldots,x_d)\in\mathbb{R}_x^d \; :\; \begin{matrix}
                0 \leq x_{i}\leq 1 \;\; \text{for} \;\; 1\leq i \leq d \\ 
                x_1+x_2+\cdots+x_d = i
        \end{matrix}
        \right\}.
    \end{equation}
    
    The \emph{standard simplex of dimension $d$} is the first hypersimplex of dimension $d$, that is $\Delta_{1,d}$. It can also be described as the convex hull of the standard basis vectors in $\mathbb{R}_x^n$. A \emph{unimodular simplex} is a polytope $S$ that is affinely equivalent to $\Delta_{1,d}$.
\end{definition}

A \emph{subdivision} of a polytope $P$ is a collection of polytopes $\mathfrak{P}$ such that every face of a polytope in $\mathfrak{P}$ is also in $\mathfrak{P}$, any two polytopes in $\mathfrak{P}$ intersect in a common face and the union of all the polytopes in $\mathfrak{P}$ equals $P$. If all the polytopes in the collection are (unimodular) simplices, we call the subdivision a \emph{(unimodular) triangulation}.
From a triangulation, we can encode the adjacency of the maximal simplices in a graph. 
\begin{definition}\label{def:dual_graph}
    Let $\mathcal{T}$ be a triangulation of a polytope $P$. The \emph{dual graph} of the triangulation $G_\mathcal{T}$ has vertex set equal to the maximal simplices of $\mathcal{T}$ and two such simplices $S_1$ and $S_2$ form an edge, which we denote by $S_1 \sim S_2$, whenever the dimension of the polytope $S_1\cap S_2$ is $\dim(P)-1$.  
\end{definition}

One of the many interesting features of alcoved polytopes is that they come equipped with a unimodular triangulation. We refer to it as the \emph{alcoved triangulation}. It is induced by the \emph{affine Coxeter arrangement of type $A_{n-1}$} that subdivides $\mathbb{R}_z^{n-1}$ into unimodular simplices called \emph{alcoves} (see \Cref{fig:alcoved_example} for the case $n=3$). 

\begin{definition}
    For an alcoved polytope $P$, let $\mathcal{A}(P)$ be the set of maximal simplices (with respect to inclusion) in the alcoved triangulation of $P$. We refer to an element $A \in\mathcal{A}(P)$ as an \emph{alcove of $P$,} and usually identify it with the set of its vertices. 
\end{definition}

Lam and Postnikov \cite{lam2007alcoved} gave the following a combinatorial description of the alcoves of an alcoved polytope with $(H,x)$-representation.

\begin{definition}\label{def:sorted-multisets}
    Let $\mathcal{I} = \{I_1,I_2,\ldots,I_k\}$ be a collection of $r$-multisets of $\{1,2,\ldots,n\}$ where for each multiset we assume $I_j = \{I_{j1}\leq I_{j2} \leq \ldots \leq I_{jr}\}$. We say that the collection $\mathcal{I}$ is \emph{sorted} if $$I_{11}\leq I_{21} \leq \ldots I_{k1} \leq I_{21} \leq I_{22} \leq \ldots \leq I_{kr}.$$ 
    Denote by $M_{\mathcal{I}}$ the \emph{matrix associated to the collection of multisets} $\mathcal{I}$  constructed by using the (ordered) multisets as rows. Then $\mathcal{I}$ is sorted if the concatenation of columns of $M_{\mathcal{I}}$ from left to right and top to bottom is weakly increasing. 
\end{definition}

\begin{definition}\label{def:multisets_from_vector}
    For an nonnegative integer vector $\vec{a} \in \mathbb{N}^n$ such that $a_1+a_2+\cdots+a_n = r$, let $I_{\vec{a}}$ be the $r$-multiset of $\{1,2,\ldots,n\}$ with $a_i$ elements ``$i$'' for each $i$. For a collection of vectors $A = \{\vec{a}_1,\vec{a}_2,\ldots,\vec{a}_k\} \subseteq \mathbb{N}^n$ such that the coordinates of all of them sum to $r$, define the \emph{collection of multisets of $A$} as $\mathcal{I}_A = \{I_{\vec{a}_1},I_{\vec{a}_2},\ldots,I_{\vec{a}_k}\}.$
\end{definition}

Suppose $P$ has a $(H,x)$-representation in $\mathbb{R}_x^{n}$ such that all points of $P$ have nonnegative coordinates. If this is not the case, by translating $P$ using the vector $m\vec{1} = (m,m,\ldots,m)\in\mathbb{R}_x^n$ for a sufficiently large $m\in\mathbb{Z}$ we obtain an affinely equivalent alcoved polytope with the desired property. Denote by $Z_P = P \cap \mathbb{Z}^{n} \subseteq \mathbb{N}^n$ the set of lattice points of $P$. 

\begin{theorem}[{\cite[Theorem 3.1]{lam2007alcoved}}]\label{thm:alcoves-sorted-sets}
    Let $P \subseteq \mathbb{R}_x^{n}$ be an alcoved polytope lying in the hyperplane $x_1+x_2+\cdots+x_n = k$ such that all its points have nonnegative coordinates. A simplex with vertices $A = \{\vec{a}_1,\vec{a}_2,\ldots,\vec{a}_n\} \subseteq Z_P$ is an alcove in $\mathcal{A}(P)$ if and only if $\mathcal{I}_A$ is a sorted collection of $k$-multisets. 
\end{theorem}

\section{Alcoved triangulations of dilated hypersimplices}\label{sec:hypersimplices}

For an alcoved polytope, its \emph{normalized volume} is given by $|\mathcal{A}(P)|$ (see \cite[Section 5.4]{beck2007computing} for the general discussion on \emph{relative volume} and \cite[Theorem 3.2]{lam2007alcoved} for the particular case of alcoved polytopes). Thus, in order to compute the normalized volume of an alcoved polytope it is enough to understand the set $\mathcal{A}(P)$.

\begin{definition}
    Let $P$ be an alcoved polytope. A \emph{labeling} of $\mathcal{A}(P)$ using the elements of a finite set $S$ is a bijection $f\,:\,\mathcal{A}(P) \longrightarrow S$.
\end{definition}

A famous result from Laplace \cite{laplace1886oeuvres} states that the normalized volume of $\Delta_{i,d}$ is $A(d,i)$. The first triangulation of the hypersimplex that showed this identity combinatorially was constructed by Stanley \cite{Stanley-triang-hypersimplex}. We give another combinatorial proof of this result in \Cref{sec:delta-i-d-simplices-labels} by constructing a labeling of $\mathcal{A}(\Delta_{i,d})$ with permutations in $\mathfrak{S}_d$ with $i-1$ descents. Now note that the right-hand side of \Cref{eq:identity-general-i} can be rewritten as $$r^d A(d,i) = r^d \vol(\Delta_{i,d}) = \vol(r\Delta_{i,d})$$ where $r\Delta_{i,d}$ is the dilation of the hypersimplex by a factor of $r$:
$$r\Delta_{i,d} = \left\{ \vec{x}\in\mathbb{R}_x^{d+1} \;:\; 0\leq x_1\,,\,x_2\,,\,\ldots\,,\,x_{d+1} \leq r \quad \text{and} \quad x_1+x_2+\cdots+x_{d+1} = ir \right\}.$$
Thus, we want to describe a labelings of the alcoves of $r\Delta_{i,d}$ using suitable objects in order to prove the identity. However, we first consider the case of the standard simplex since it contains important ideas in order to construct the general labelings. 

\subsection{The dilated standard simplex}\label{sec:delta-1-d-simplices-labels}

\subsubsection{Labeling of the alcoves with words}

We start by reinterpreting the sorted sets $\mathcal{I}_A$ from \Cref{thm:alcoves-sorted-sets} using words. 

\begin{definition}
    Let $\mathcal{I} = \{I_1,I_2,\ldots,I_{k}\}$ be a sorted collection of different $r$-multisets of $\{1,2,\ldots,n\}.$ The \emph{decorated matrix} $\widetilde M_\mathcal{I}$ is constructed as follows. Arrange the numbers of $M_\mathcal{I}$ in a $k\times r$ grid and then (using matrix coordinates)
    \begin{itemize}
        \item[(a)] if $I_{ab}<I_{(a+1)b}$ mark the edge between the cells $(a,b)$ and $(a+1,b)$ in the grid, and
        \item[(b)] if $I_{nb}<I_{1(b+1)}$ mark the bottom edge of cell $(n,b)$ in the grid. 
    \end{itemize}
\end{definition}

\begin{example}\label{ex:decorated-matrix}
    Fix $n=8$ and $r = 6$. Consider the set of points 
    \begin{multline*}
    A = \{\vec{a}_1,\vec{a}_2,\vec{a}_3,\vec{a}_4,\vec{a}_5\} = \{(2,1,0,1,1,0,0,1),(2,0,1,1,1,0,0,1),\\(1,1,0,2,0,1,0,1),(1,1,0,1,1,1,0,1),(1,1,0,1,1,0,1,1)\}\subseteq \mathbb{R}^8
    \end{multline*}
    The decorated matrix $\widetilde M_{\mathcal{I}}$ for $\mathcal{I} = \mathcal{I}_A = \{I_{\vec{a}_1},I_{\vec{a}_2},I_{\vec{a}_3},I_{\vec{a}_4},I_{\vec{a}_5}\}$ is 
    \begin{center}
        \begin{tikzpicture}[scale = 0.55]
            \def \w{1}
            \def \h{1}
            \def \r{0.3}
            \def \rows{5}
            \def \cols{6}
            \foreach \i in {0,...,\rows}
            {
            \draw[gray!50] (0,\i*\h)--(\w*\cols,\i*\h);
            }
            \foreach \i in {0,...,\cols}
            {
            \draw[gray!50] (\w*\i,0)--(\w*\i,\rows*\h);
            }
            \foreach \xx\yy\c in {0/4/1,0/3/1,0/2/1,0/1/1,0/0/1,
                                  1/4/1,1/3/1,1/2/2,1/1/2,1/0/2,
                                  2/4/2,2/3/3,2/2/4,2/1/4,2/0/4,
                                  3/4/4,3/3/4,3/2/4,3/1/5,3/0/5,
                                  4/4/5,4/3/5,4/2/6,4/1/6,4/0/7,
                                  5/4/8,5/3/8,5/2/8,5/1/8,5/0/8
                                  }
            {
            \node at (\w*.5+\w*\xx,\h*.5+\h*\yy) {{\c}};
            }
            \foreach \xx\yy in {1/3,2/4,2/3,3/2,4/3,4/1,4/0}
            {
            \draw[red,ultra thick] (\xx,\yy) --  (\xx+1,\yy);
            }
            %\node at (2.5,-5.5) {$(N_0,Q_0)$};
        \end{tikzpicture}
    \end{center}
\end{example}

We now examine the case of sorted sets arising from the alcoves of the dilated standard simplex. 

\begin{lemma}\label{lem:properties-marked-matrix-alcoves-dilated-simplex}
    Let $A = \{\vec{a}_1,\vec{a}_2,\ldots,\vec{a}_{d+1}\}$ be the set of vertices of an alcove of $r\Delta_{1,d}$ and let $\mathcal{I} = \mathcal{I}_A$ be the associated sorted collection of $r$-multisets. Then the decorated matrix $\widetilde M_{\mathcal{I}}$ satisfies that for each $1\leq i\leq d$, there is a unique mark between rows $i$ and $i+1$, and there are no marks in the bottom part of the matrix. 
\end{lemma}

The previous lemma allows us to define a labeling of $\mathcal{A}(r\Delta_{1,d})$ by recording the position of the unique mark in each of the rows. 

\begin{definition}
    Let $\word_1 : \mathcal{A}(r\Delta_{1,d}) \to [r]^d\;$ be the map defined as follows. If $A$ is the set of vertices of an alcove of $r\Delta_{1,d}$ with associated collection of multisets $\mathcal{I} = \mathcal{I}_A$ then $\word_1(A)$ is obtained by reading the column label of the marks of $\widetilde M_\mathcal{I}$ from top to bottom. 
\end{definition}

\begin{theorem}\label{thm:bijection-alcoves-words}
    The map $$\word_1 \; : \; \mathcal{A}(r\Delta_{1,d}) \longrightarrow [r]^d$$ is a bijection. 
\end{theorem}

\begin{example}\label{ex:word-simplex-delta-d}
    Fix $d = 4$ and $r = 6$. The set of points 
    \begin{equation*}
    A = \{(3,1,1,0,1),(2,2,1,0,1),(2,2,0,1,1),(2,1,1,1,1),(2,1,1,0,2)\}
    \end{equation*}
    defines an alcove of $6\Delta_{1,4}\subseteq \mathbb{R}^5_x$. The decorated matrix in this case is 
    \begin{center}
        \begin{tikzpicture}[scale = 0.55]
            \def \w{1}
            \def \h{1}
            \def \r{0.3}
            \def \rows{5}
            \def \cols{6}
            \foreach \i in {0,...,\rows}
            {
            \draw[gray!50] (0,\i*\h)--(\w*\cols,\i*\h);
            }
            \foreach \i in {0,...,\cols}
            {
            \draw[gray!50] (\w*\i,0)--(\w*\i,\rows*\h);
            }
            \foreach \xx\yy\c in {0/4/1,0/3/1,0/2/1,0/1/1,0/0/1,
                                  1/4/1,1/3/1,1/2/1,1/1/1,1/0/1,
                                  2/4/1,2/3/2,2/2/2,2/1/2,2/0/2,
                                  3/4/2,3/3/2,3/2/2,3/1/3,3/0/3,
                                  4/4/3,4/3/3,4/2/4,4/1/4,4/0/5,
                                  5/4/5,5/3/5,5/2/5,5/1/5,5/0/5
                                  }
            {
            \node at (\w*.5+\w*\xx,\h*.5+\h*\yy) {\c};
            }
            \foreach \xx\yy in {2/4,3/2,4/3,4/1}
            {
            \draw[red,ultra thick] (\xx,\yy) --  (\xx+1,\yy);
            }
            %\node at (2.5,-5.5) {$(N_0,Q_0)$};
        \end{tikzpicture}
    \end{center}
    and then $\word_1(A) = 3\,5\,4\,5\in [6]^4.$
\end{example}

\subsubsection{Labeling of the alcoves with pairs of compositions and permutations}\label{sec:labeling_pair_case_1}

We start by associating a composition to each collection of nonnegative integer vectors.

\begin{definition}\label{def:composition-set-of-vectors}
    Let $V=\{\vec{v}_1,\vec{v}_2,\ldots,\vec{v}_{m}\}\subseteq\mathbb{N}^{d+1}$ be a collection of vectors with nonnegative integer coordinates. Define $\comp(V) = (c_1,c_2,\ldots,c_{d+1})$ to be the composition with parts $c_k = \min\left \{(\vec{v}_{j})_{k}\,|\,j\in[m]\right \}$ where $(\vec{v}_j)_k$ denotes the $k$-th entry of the vector $\vec{v}_j.$
\end{definition}

If we restrict to collections of vertices of alcoves of a dilated standard simplex, we can give a description of the composition using decorated matrices. 

\begin{lemma}\label{lem:comp-A-from-decorated-matrix}
    Let $A=\{\vec{a}_1,\vec{a}_2,\ldots,\vec{a}_{k}\}\in\mathcal{A}(r\Delta_{1,d})$. Then $\comp(A) = (c_1,c_2,\ldots,c_{d+1})$ satisfies the following conditions: $c_1 = k$ if the first mark is in column $k+1$ and $c_{d+1} = \ell$ if the last mark is in column $r-\ell$. For $2\leq i \leq d$, suppose the $i$-th mark is in column $b_i$. Then $$c_{i} = \begin{cases}b_{i}-b_{i-1}-1 \quad &\text{if the $i$-th mark is higher than the $(i-1)$-th mark}\\ b_{i}-b_{i-1} \quad & \text{if the $i$-th mark is higher than the $(i-1)$-th mark}\\\end{cases}$$ 
\end{lemma}

Now we associate a permutation to each of the alcoves of the dilated hypersimplices. 

\begin{definition}\label{def:permutation-alcove-dilated-simplex}
    Let $A=\{\vec{a}_1,\vec{a}_2,\ldots,\vec{a}_{d+1}\}\in\mathcal{A}(r\Delta_{1,d})$. Define $\sigma_A \in S_{d}$ to be the permutation such that its one-line notation of is the word obtained from $\widetilde M_{\mathcal{I}_A}$ by recording the position of the marks reading the columns from top to bottom and from left to right in the matrix.
\end{definition}  

\begin{example}\label{ex:comp-permutation-simplex-delta-d}
    For the alcove $A\in\mathcal{A}(6\Delta_{1,4})$ from \Cref{ex:word-simplex-delta-d}, $\comp(A) = 2\,1\,0\,0\,1$, and $\sigma_A = 1\,3\,2\,4$ in one-line notation. 
\end{example}

With these two objects we can construct the second labeling that allows us to prove \Cref{eq:identity-i-1} combinatorially.

\begin{theorem}\label{thm:bijection-alcoves-pairs}
    The map $$\pair_1\,:\,\mathcal{A}(r\Delta_{1,d})\longrightarrow \bigcup_{j=1}^d \mathfrak{C}(r-1,d+1,r-j)\times \mathfrak{A}(d,j)$$ given by $\pair_1(A) = (\comp(A),\sigma_A)$ is a bijection.
\end{theorem}

\subsubsection{Dual graph of the triangulation}

From \Cref{thm:bijection-alcoves-words}, the maximal simplices of the alcoved triangulation of $r\Delta_{1,d}$ are labeled by words in $[r]^d$. The following theorem gives a description of the dual graph of this triangulation in terms of words. We show the graph for $r=2$ and $d=3$ in \Cref{ex:graph_comp}.

\begin{definition}\label{def:G_rd}
    For $r,d \geq 1$, let $G_{r,d}$ be the graph on vertex set $[r]^d$ and edges given by
    \begin{enumerate}
        \item $w_1\,w_2\,\ldots\, w_d \; \sim \; (w_d +1)\, w_1\,w_2\,\ldots\, w_{d-1}\;$ whenever $1\leq w_d < r$, and 
        \item $w_1\,\ldots\,w_i\,w_{i+1}\,\ldots\, w_d \; \sim \; w_1\,\ldots\,w_{i+1}\,w_i\,\ldots\, w_d\;$ for any $1\leq i\leq d-1$ such that $w_i\neq w_{i+1}$.
    \end{enumerate}
\end{definition}

\begin{theorem}\label{thm:dual_graph_alcoved_dilated_standard_simplex}
    Let $\mathcal{T}$ be the alcoved triangulation of $r\Delta_{1,d}$. Then $G_\mathcal{T}$ is isomorphic to $G_{r,d}$.
\end{theorem}

\subsection{The dilated hypersimplex}\label{sec:delta-i-d-simplices-labels}

The map $\sigma_\bullet$ from \Cref{def:permutation-alcove-dilated-simplex} can be defined for alcoves of $\Delta_{i,d}$ in an analogous way. Moreover, this map gives a new combinatorial proof of the fact the Eulerian numbers coincide with the volumes of the hypersimplices. 

\begin{theorem}\label{thm:alcoves-hypersimplex-eulerian}
    For $1\leq i \leq d$, the map $$\sigma^{(i)}_{\bullet}\;:\; \mathcal{A}(\Delta_{i,d}) \longrightarrow \mathfrak{A}(d,i)$$ is a bijection, and then $\vol(\Delta_{i,d}) = A(d,i)$.
\end{theorem}

Let $G_{\mathcal{A},i,d}$ be the dual graph of the alcoved triangulation of $\Delta_{i,d}$. We give a description of this graph using permutations. We illustrate $G_{\mathcal{A},2,3}$ in \Cref{ex:graph_comp}.

\begin{prop}\label{prop:dual_graph_hypersimplex}
    The graph $G_{\mathcal{A},i,d}$ is isomorphic to the graph with vertex set $\mathfrak{A}(d,i)$ where $\{\sigma,\tau\}$ is an edge if and only if the permutations satisfy that
    \begin{enumerate}
        \item $\sigma = s_k \tau$ for some $k=1,2,\dots,d-1$ (where $s_k$ is the $k$th simple transposition), or
        \item if $\sigma = \sigma_1\,\sigma_2\,\ldots\,\sigma_d$ and $\tau = \tau_1\,\tau_2\,\ldots\,\tau_d$ are the one-line notations, and $\ell$ and $m$ are the indices such that $\sigma_\ell = 1$ and $\sigma_m=d$, then either $\tau_\ell = d$ and $\tau_j = \sigma_j+1$ for $j\neq\ell$, or $\tau_m = 1$ and $\tau_j = \sigma_j-1$ for $j\neq m$.
    \end{enumerate}
\end{prop}

\subsubsection{Labeling of the alcoves with pairs of words and permutations}

\Cref{thm:bijection-alcoves-words} can be used to label triangulations of dilated polytopes in general as follows. This construction was considered in \cite[Section 4]{Haase_2021} where the authors study the properties of the resulting triangulations.

\begin{observation}\label{obs:main_idea}
    Let $P$ be a polytope of dimension $d$ that has a unimodular triangulation $\mathcal{T} = \{S_i \;|\; i\in I\}$. Consider the (non-unimodular) triangulation $r\mathcal{T} = \{rS \,|\, S\in\mathcal{T}\}$ of $rP$. Then we can use the map $\word_1$ from \Cref{sec:delta-1-d-simplices-labels} to construct a labeling $f\,:\, \Delta \to I\times [r]^d$ of the unimodular triangulation $\Delta$ that arises from alcove-triangulating each simplex $rS \simeq r\Delta_{1,d}$.
\end{observation}

Using this observation we can give a labeling of the alcoves of a dilated hypersimplex as follows. Consider $A\in\mathcal{A}(r\Delta_{i,d})$. It satisfies $A \subseteq rB$ where $B\in\mathcal{A}(\Delta_{i,d})$. Define the \emph{permutation associated to $A$} to be $\tau_A = \sigma_B^{(i)}$. Moreover, there is an affine equivalence $\varphi_B:B\to\Delta_{1,d}$. Through this map, $\varphi_B(A)$ is an alcove of $r\Delta_{1,d}$, and we can compute its $\word_1$. Define the \emph{word of $A$} to be $\word_i'(A) = \word_1(\varphi_B(A))$. Using these objects, together with \Cref{thm:alcoves-hypersimplex-eulerian}, we obtain the first labeling of $\mathcal{A}(r\Delta_{i,d})$. We show these calculations explicitly in \Cref{ex:final}.

\begin{theorem}\label{thm:bijection-alcoves-words-general-case}
    The map $$\words_i \; : \; \mathcal{A}(r\Delta_{i,d}) \longrightarrow [r]^d\times \mathfrak{A}(d,i)$$ defined by $\words_i(A) = (\word_i'(A),\tau_A)$ is a bijection.  
\end{theorem}

\subsubsection{Labeling of the alcoves with pairs of compositions and permutations}

Now we describe a more direct labeling of $\mathcal{A}(r\Delta_{i,d})$ by extending the maps from \Cref{sec:labeling_pair_case_1}. For alcoves $A\in\mathcal{A}(r\Delta_{i,d})$ we can still construct a composition and a permutation in a similar way as we did for $r\Delta_{1,d}$. We denote by $\comp'(A)$ and $\sigma_A'$ the composition and permutation (respectively) obtained from $\widetilde M_{\mathcal{I}_A}$.

\begin{theorem}\label{thm:bijection-alcoves-pairs-general-case}
    The map $$\pair_i\,:\,\mathcal{A}(r\Delta_{i,d})\longrightarrow \bigcup_{j=1}^d \mathfrak{C}(r-1,d+1,ir-j)\times \mathfrak{A}(d,j)$$ given by $\pair_i(A) = (\comp'(A),\sigma'_A)$ is a bijection.
\end{theorem}

\noindent The maps from \Cref{thm:bijection-alcoves-words-general-case,thm:bijection-alcoves-pairs-general-case} are precisely the bijections mentioned in \Cref{thm:principal}. 

\begin{example}\label{ex:final}
    Fix $d=5$, $r=4$, $i=2$ and $j=3$ as parameters in the previous theorems. The set of points
    \begin{multline*}
    A = \{(2,3,0,1,2,0),(2,2,1,1,2,0),(2,2,0,2,2,0),\\(2,2,0,2,1,1),(1,3,0,2,1,1),(1,3,0,1,2,1)\}\subseteq \mathbb{R}^6_x
    \end{multline*}
    defines an alcove in $\mathcal{A}(4\Delta_{2,5})$. It satisfies $\conv(A) \subseteq 4A^{(2)}_{3\,1\,2\,4\,5}$ where $A^{(2)}_\bullet$ is the inverse of $\sigma_\bullet^{(2)}$ from \Cref{thm:alcoves-hypersimplex-eulerian}; therefore $\tau_A = 3\,1\,2\,4\,5$. Moreover, $A^{(2)}_{3\,1\,2\,4\,5} = \conv(\mathfrak{B})$ with 
    \begin{multline*}
        \mathfrak{B} = \{(1,1,0,0,0,0),(1,0,1,0,0,0),(1,0,0,1,0,0),\\(0,1,0,1,0,0),(0,1,0,0,1,0),(0,1,0,0,0,1)\}.
    \end{multline*}
    Using $\mathfrak{B}$ as a basis for $\mathbb{R}_x^6$, the elements of $A$ can be rewritten as 
    \begin{multline*}
        A \cong \{(1,0,1,0,2,0),(1,1,0,1,1,0),(0,0,2,0,2,0),\\(0,0,2,0,1,1),(0,0,1,1,1,1),(0,0,1,0,2,1)\}
    \end{multline*} 
    where $\cong$ denotes the change of basis from the standard basis to $\mathfrak{B}$. From this description we see that the decorated matrix of $A$ relative to $4A^{(2)}_{3\,1\,2\,4\,5}$ is 
    \begin{center}
        \begin{tikzpicture}[scale = 0.55]
            \def \w{1}
            \def \h{1}
            \def \r{0.3}
            \def \rows{6}
            \def \cols{4}
            \foreach \i in {0,...,\rows}
            {
            \draw[gray!50] (0,\i*\h)--(\w*\cols,\i*\h);
            }
            \foreach \i in {0,...,\cols}
            {
            \draw[gray!50] (\w*\i,0)--(\w*\i,\rows*\h);
            }
            \foreach \xx\yy\c in {0/5/1,0/4/2,0/3/3,0/2/3,0/1/3,0/0/3,
                                  1/5/3,1/4/3,1/3/3,1/2/3,1/1/4,1/0/5,
                                  2/5/5,2/4/5,2/3/5,2/2/5,2/1/5,2/0/5,
                                  3/5/5,3/4/5,3/3/5,3/2/6,3/1/6,3/0/6
                                  }
            {
            \node at (\w*.5+\w*\xx,\h*.5+\h*\yy) {\c};
            }
            \foreach \xx\yy in {0/5,0/4,1/2,1/1,3/3}
            {
            \draw[red,ultra thick] (\xx,\yy) --  (\xx+1,\yy);
            }
        \end{tikzpicture}
    \end{center}
    Hence we obtain $\words_2(A) = (1\,1\,4\,2\,2 \;,\; 3\,1\,2\,4\,5) \in [4]^5 \times \mathfrak{A}(5,2).$ 
    
    To compute $\pair_2(A)$ we consider the decorated matrix of $\mathcal{I}_A$ with respect to the canonical basis of $\mathbb{R}_x^6$. That is,
    \begin{center}
        \begin{tikzpicture}[scale=0.55]
                \def \w{1}
                \def \h{1}
                \def \r{0.3}
                \def \rows{6}
                \def \cols{8}
                \foreach \i in {0,...,\rows}
                {
                \draw[gray!50] (0,\i*\h)--(\w*\cols,\i*\h);
                }
                \foreach \i in {0,...,\cols}
                {
                \draw[gray!50] (\w*\i,0)--(\w*\i,\rows*\h);
                }
                \foreach \xx\yy\c in {0/5/1,0/4/1,0/3/1,0/2/1,0/1/1,0/0/1,
                                      1/5/1,1/4/1,1/3/1,1/2/1,1/1/2,1/0/2,
                                      2/5/2,2/4/2,2/3/2,2/2/2,2/1/2,2/0/2,
                                      3/5/2,3/4/2,3/3/2,3/2/2,3/1/2,3/0/2,
                                      4/5/2,4/4/3,4/3/4,4/2/4,4/1/4,4/0/4,
                                      5/5/4,5/4/4,5/3/4,5/2/4,5/1/4,5/0/5,
                                      6/5/5,6/4/5,6/3/5,6/2/5,6/1/5,6/0/5,
                                      7/5/5,7/4/5,7/3/5,7/2/6,7/1/6,7/0/6
                                      }
                    {
                    \node at (\w*.5+\w*\xx,\h*.5+\h*\yy) {\c};
                    }
                    \foreach \xx\yy in {1/2,4/4,4/5,5/1,7/3}
                    {
                    \draw[red,ultra thick] (\xx,\yy) --  (\xx+1,\yy);
                    }
        \end{tikzpicture}
    \end{center}
    Then $\pair_2(A) = ((1,2,0,1,1,0),\,4\,1\,2\,5\,3) \in \mathfrak{C}(3,6,5) \times \mathfrak{A}(5,3).$
\end{example}


% \subsubsection{Dual graph of the triangulation}\label{sec:dual_graph_hypersimplex_general}

% Let $G_{\mathcal{A},i,d}$ be the dual graph of the alcoved triangulation of $\Delta_{i,d}$. We present a description of this graph using permutations in view of \Cref{thm:alcoves-hypersimplex-eulerian}. The proof of this characterization is analogous to the one from \Cref{thm:dual_graph_alcoved_dilated_standard_simplex}. 

% \begin{prop}\label{prop:dual_graph_hypersimplex}
%     The graph $G_{\mathcal{A},i,d}$ is isomorphic to the graph with vertex set $\mathfrak{A}(d,i)$ where $\{\sigma,\tau\}$ is an edge if and only if the permutations satisfy that
%     \begin{enumerate}
%         \item $\sigma = s_k \tau$ for some $k=1,2,\dots,d-1$ (where $s_k$ is the $k$th simple transposition), or
%         \item if $\sigma = \sigma_1\,\sigma_2\,\ldots\,\sigma_d$ and $\tau = \tau_1\,\tau_2\,\ldots\,\tau_d$ are the one-line notations, and $\ell$ and $m$ are the indices such that $\sigma_\ell = 1$ and $\sigma_m=d$, then either
%         \begin{enumerate}
%             \item $\tau_\ell = d$ and $\tau_j = \sigma_j+1$ for $j\neq\ell$, or
%             \item $\tau_m = 1$ and $\tau_j = \sigma_j-1$ for $j\neq m$.
%         \end{enumerate}
%     \end{enumerate}
% \end{prop}

% \begin{example}
%     \Cref{fig:dual_graph_delta-2-4_ss-perms} shows the alcoved triangulation of $\Delta_{2,4}$ in terms of decorated matrices of sorted sets and also in terms of permutations from $\mathfrak{A}(4,2)$.
%     \begin{figure}[t]
%         \centering
%         \hspace{0.75cm}\includegraphics[width=0.9\linewidth]{hypersimplex-4-2-example-ss-perms.pdf}
%         \hspace{1cm}
%         %\includegraphics[width=0.45\linewidth]{hypersimplex-4-2-example-perms.pdf}
%         \caption{The dual graph of the alcoved triangulation of $\Delta_{2,4}$ in terms of sorted sets on the left; the solid and dotted edges correspond, respectively, to conditions $1.$ and $2.$ from \Cref{prop:dual_graph_hypersimplex}. On the right, the same graph but in terms of permutations in $\mathfrak{A}(4,2)$; the colors of the edges represent the different hyperplanes that separate the corresponding alcoves.}
%         \label{fig:dual_graph_delta-2-4_ss-perms}
%     \end{figure}
%     In the graph with decorated matrices, the solid edges correspond to changing a middle row (i.e. not the first or last) of the matrix, and the dotted edges change a top or bottom row of the matrix. These are the analogous cases from \Cref{thm:dual_graph_alcoved_dilated_standard_simplex} and correspond to conditions 1. and 2. from \Cref{prop:dual_graph_hypersimplex} respectively. In the graph with permutations we show the different hyperplanes that generate the triangulation with different colors. 
% \end{example}

% We would like to describe the dual graph of the alcoved triangulation of $r\Delta_{i,d}$ in the setting of \Cref{obs:main_idea}, that is, as a \emph{composition of dual graphs}. This is equivalent to describing the graph using the labeling of $\mathcal{A}(r\Delta_{i,d})$ from \Cref{thm:bijection-alcoves-words-general-case}. We start by defining the operation on graphs that formalizes this idea.

% % \begin{definition}
% %     Let $G_1 = (V(G_1),E(G_1))$ and $G_2 = (V(G_2),E(G_2))$ be finite nonempty graphs. Let $U_1\subseteq V(G_1)$ and $U_2\subseteq V(G_2)$ and $f: U_1 \to U_2$ a bijection between this sets. The \emph{connection of $G_1$ and $G_2$ through $f$} is the graph with vertex set $V(G_1)\sqcup V(G_2)$ and edges $E(G_1)\sqcup E(G_2)\sqcup\{\{u,f(u)\}:u \in U_1\}$ where $\sqcup$ denotes disjoint union. We denote it by $G_1\otimes_f G_2$ if we want to emphasize its dependence on the map, or $G_1\leftindex_{U_1}\otimes_{U_2}\, G_2$ if the map is clear from context and we want to point out the \emph{connecting sets} explicitly.   
% % \end{definition}

% \begin{definition}\label{def:composition_of_graphs}
%     Let $G=(V(G),E(G))$ and $H$ be finite nonempty graphs. For each vertex $v\in V(G)$ take a copy of $H$ and denote it by $H_v$, and for each edge $e=\{x,y\} \in E(G)$ pick a bijection $f_e:X_e\to Y_e$ for some $X_e\subseteq V(H_x)$ and $Y_e\subseteq V(H_y)$. Define $G\langle H \rangle$ as the graph with vertices $$V\left ( G\langle H \rangle \right ) = \bigsqcup_{v\in V(G)} V(H_v)$$ and edges $$E\left ( G\langle H \rangle \right ) = \bigsqcup_{v\in V(G)} E(H_v) \sqcup \bigsqcup_{e\in E(G)}\left\{ \{x,f_e(x)\} \,:\, x\in X_e \right\}$$ where $\sqcup$ denotes disjoint union.   
% \end{definition}

% Intuitively, the previous construction is as follows. We place a copy of $H$ in each vertex of $G$. Then for each one of the edges $e$ of $G$, we connect the copies corresponding to the endpoints of $e$ by creating edges between the sets $X_e$ and $Y_e$ according to the bijection $f_e$. Because of this, we refer to the sets $X_e$ and $Y_e$ as the \emph{connecting sets}. This notion generalizes the Cartesian product of graphs, which is recovered by setting all the bijections $f_e$ to be the identity on $V(H)$.

% For our purposes, we take $G=G_{\mathcal{A},i,d}$ and $H = G_{r,d}$; for the connecting sets we take the boundary words $W_j^\circ$ from \Cref{def:w_circ_j} and the bijections are the identity maps between them. However, additional conditions on how to pick the order of connection of the boundaries must be taken into consideration, as the next example shows.

% \begin{example}\label{ex:graph-composition}
% Consider the case of $2\Delta_{2,3}$. Then the relevant graphs for the construction are
% \begin{figure}[ht]
%     \centering
%     \includegraphics[width=0.6\linewidth]{graph-comp-example-prep.pdf}
% \end{figure}    

% \noindent In $G_{\mathcal{A},2,3}$ we wrote the one-line notation of the permutations with brackets and commas to avoid confusion to the words in $[2]^3$. As in \Cref{fig:dual_graph_delta-2-4_ss-perms}, the solid edges of $G$ are encoding adjacency of the simplices through the hyperplane $x_2+x_3 = 1$ and the dashed edges through the hyperplane $x_1+x_2 = 1$. Since there are two pairs of edges encoding the same adjacency, the connecting sets from $H_{(1,3,2)}$ to $H_{(2,3,1)}$, and from $H_{(2,1,3)}$ to $H_{(3,1,2)}$ have to coincide. The same happens for the dashed edges. Thus, picking the set $W_1^\circ \subset [2]^3$ for the solid edges and $W_2^\circ\subset [2]^3$ for the dashed edges, we obtain the connections that are shown in \Cref{fig:compo-dual-graphs}. Picking different connecting sets for edges of the same type yields a graph that does not correspond to the alcoved triangulation of the dilated polytope. This can be seen from the existence of the $4$-cycle including the four different instances of the word $1\,1\,1$, and the fact that picking the sets incorrectly does not produce such cycle. 

% \begin{figure}[ht]
%     \centering
%     \includegraphics[width=0.7\linewidth]{graph-comp-example.pdf}
%     \caption{The construction of $G_{\mathcal{A},2,3}\langle G_{2,3} \rangle$ when choosing $W_j^\circ$ as connecting sets according to the specified labels. This graph is isomorphic to the dual graph of the alcoved triangulation of $2\Delta_{2,3}$.}
%     \label{fig:compo-dual-graphs}
% \end{figure}

% \end{example}

% Since there is extra compatibility needed depending on the type of hyperplanes to which the edges of the graph $G = G_{\mathcal{A},i,d}$ correspond, we need to determine the correct connecting sets. From the reasoning in \Cref{ex:graph-composition}, we propose the following candidates. Every edge of $G$ corresponds to a hyperplane from the affine Coxeter arrangement of type $A_{d+1}$. Thus, by identifying the edges with the hyperplanes, we obtain an edge-coloring of $G$ (see \Cref{fig:dual_graph_delta-2-4_ss-perms}) that, we believe, induces a correct choice of connecting sets. 

% \begin{conjecture}\label{conj:dual_graph_alcoved_dilated_hypersimplex}
%     Let $G = G_{\mathcal{A},i,d}$ and $H = G_{r,d}$. The edge-coloring of $G$ determined by the hyperplane types prescribes a choice of connecting sets that make $G\langle H \rangle$ isomorphic to the dual graph of the alcoved triangulation of $r\Delta_{i,d}$. 
% \end{conjecture}

\section{Final Remarks}\label{sec:final_remarks}
We conjecture the structure of the dual graph of the alcoved triangulation of $r\Delta_{i,d}$ based on \Cref{thm:dual_graph_alcoved_dilated_standard_simplex} and \Cref{obs:main_idea} (see \cite[Section 3.2.3]{myself} for the definitions).
\begin{conjecture}\label{conj:dual_graph_alcoved_dilated_hypersimplex}
    Let $G = G_{\mathcal{A},i,d}$ and $H = G_{r,d}$. The edge-coloring of $G$ determined by the hyperplane types prescribes a choice of connecting sets that make $G\langle H \rangle$ isomorphic to the dual graph of the alcoved triangulation of $r\Delta_{i,d}$. 
\end{conjecture}

\begin{example}\label{ex:graph_comp}
    Consider the case $i=2$, $d=3$ and $r=2$. The graphs $G$, $H$, and $G\langle H \rangle$ in \Cref{conj:dual_graph_alcoved_dilated_hypersimplex} are 
    \begin{center}
        \hspace{1cm}\includegraphics[width = 0.85\linewidth]{graph-comp-example-together.pdf}
    \end{center}
    The graph composition, shown on the right, is obtained from the connecting sets labeled by the index $j$ (see \cite[Definition 3.36]{myself} for the relevant definitions).% and is shown in \Cref{fig:graph_comp}.
    % \begin{figure}
    % \centering
    %     \includegraphics[width=0.6\linewidth]{graph-comp-example.pdf}
    %     \caption{The graph $G_{\mathcal{A},2,3}\langle G_{2,3}\rangle$ that we conjecture is isomorphic to the dual graph of the alcoved triangulation of $2\Delta_{2,3}$.}
    %     \label{fig:graph_comp}
    % \end{figure}
\end{example}

Further, we believe that \Cref{obs:main_idea} can lead to combinatorial interpretations of unimodular triangulations of dilation of polytopes arising from combinatorial objects such as order polytopes and special cases of flow polytopes. Indeed, these polytopes admit unimodular triangulations labeled by combinatorial objects, so it is natural to investigate the structure of each individual dilated simplex comprising the triangulation in terms of "folded" combinatorial objects.   

\acknowledgements{This work was partially supported by NSERC grant RGPIN-2021-02568. The author is grateful to Volkmar Welker for pointing out that there was not known combinatorial proof of the identities, to Santiago Estupi\~n\'an Salamanca, Cicely Henderson and Federico Castillo for valuable conversations, and to the anonymous reviewers for the useful comments and suggestions for the document. }

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