%% 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[submission]{FPSAC2026} %% 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[capitalize,nameinlink,noabbrev,nosort]{cleveref} \usepackage{enumerate} \usepackage{caption} \usepackage{float} \usepackage{manfnt} % \usepackage{tikz} % \usetikzlibrary{shapes.geometric} % \usetikzlibrary{math} % \usetikzlibrary{calc,arrows} % \usepackage{tikz-3dplot} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{observation}[theorem]{Observations} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \newtheorem*{theorem*}{Theorem} %\newcommand \acknowledgements{\paragraph{\textbf{Acknowledgements}}} % #just kt things \newcommand\inner[2]{\langle #1, #2 \rangle} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathcal{F}} \newcommand{\D}{\mathcal{D}} \newcommand{\precdot}{\prec\!\!\!\cdot_{v_0}} \newcommand{\cube}{\text{\mancube}} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\vertex}{vert} \DeclareMathOperator{\des}{des} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\EE}{EE} \DeclareMathOperator{\volu}{vol} \DeclareMathOperator{\cover}{cover} \newcommand{\ts}{\textsuperscript} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\trace}{trace} \newcommand{\hv}{\mathcal{H}_{\mathcal{V}}} \newcommand{\shift}{\overset{\mathrm{shift}}{=\joinrel=}} \renewcommand{\P}{\mathcal{P}} \DeclareMathOperator{\cDes}{cDes} \DeclareMathOperator{\cdes}{cdes} \DeclareMathOperator{\OSP}{OSP} \DeclareMathOperator{\shuf}{shuffle} \newcommand{\dbtilde}[1]{\accentset{\approx}{#1}} \newcommand{\id}{\Delta_0} \newcommand{\fan}{\text{Fan}} \newcommand{\dist}{\text{dist}} \DeclareMathOperator{\wt}{wt} \DeclareMathOperator{\Ehr}{Ehr} \newcommand{\aff}{\mathrm{aff}} %\DeclarePairedDelimiter{\bbracket}{\llbracket}{\rrbracket} %\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor} %% define your title in the usual way \title[The Ehrhart Series of Alcoved Polytopes]{The Ehrhart Series 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[Elisabeth Bullock and Yuhan Jiang]{Elisabeth Bullock\thanks{Elisabeth Bullock was partially supported by NSF Fellowship 2141064.}\addressmark{1} \and Yuhan Jiang\addressmark{2}} %% then use \addressmark to match authors to institutions here \address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology \\ \addressmark{2}Department of Mathematics, University of California, Berkeley} %% 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{Alcoved polytopes are convex polytopes which are the closure of a union of alcoves in an affine Coxeter arrangement. They are rational polytopes, and therefore have Ehrhart quasipolynomials. We describe a method for computing the generating function of the Ehrhart quasipolynomial, or Ehrhart series, of any alcoved polytope via a particular shelling order of its alcoves. We also show a connection between Early's decorated ordered set partitions and this shelling order for the hypersimplex $\Delta_{2,n}$.} %% 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{alcoved polytopes, Ehrhart theory, root systems} %% 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{sample.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \articlenumber{49} \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} Let $\Phi \subset \R^n$ be an irreducible \emph{crystallographic root system} and $W$ be the corresponding Weyl group. Associated to $\Phi$ is an infinite hyperplane arrangement known as the affine Coxeter arrangement. The connected components of this hyperplane arrangement are simplices called \emph{alcoves}. Lam and Postnikov defined a \emph{proper alcoved polytope} to be the closure of a union of alcoves \cite{alcove2}. For any root system, Fomin and Zelevinsky's \emph{generalized associahedra} are examples of polytopes which can be realized as alcoved polytopes \cite{fz03,chapoton}. In the special situation of the root system $\Phi = A_n$, examples of alcoved polytopes include \emph{hypersimplices} and \emph{positroid polytopes}. The vertices of alcoved polytopes have rational coordinates, meaning that alcoved polytopes are rational polytopes. Let $P \subset \R^n$ be a rational convex polytope, with underlying lattice $\Z^n$. Ehrhart theory is about counting lattice points in rational polytopes. In particular, Ehrhart showed that the number of lattice points in the $t$-dilate of a rational polytope $P$ is a \emph{quasipolynomial} in $t$ \cite{ehrhart}. A quasipolynomial with period $d$ is a function $p: \Z \to \Z$ such that there exist periodic functions $p_i: \Z \to \Z$ with period $d$ so $p(z) = \sum_{i=0}^n p_i(z) z^i$. We call $L(P,t) = \#(t\cdot P) \cap \Z^n$ the \emph{Ehrhart quasipolynomial} of $P$. The generating series $\sum_{t=0}^\infty L(P,t) z^t$, called the \emph{Ehrhart series}, is a rational function in $z$. While the Ehrhart theory of lattice polytopes has been widely studied, the Ehrhart theory of rational polytopes is less explored \cite{beck22,BBKV13,linke11}. % Ehrhart theory extends naturally to polytopes with some facets removed. % The Ehrhart series are \emph{additive}, in the sense that if two half-open polytopes are disjoint, then the Ehrhart series of their union is equal to the sum of their Ehrhart series. Our first main result stated imprecisely is the following: \begin{theorem*}[Precise statement in \cref{thm:main}]\label{thm:main-imprecise} Fix an irreducible crystallographic root system $\Phi\subset \R^n$. Let $P$ be an alcoved polytope and let $\Gamma_P=(V,E)$ be the dual graph to the alcove triangulation of $P$. Pick some $v_0\in V$ and orient the edges of $\Gamma_P$ so that for all $\{u,w\}\in E$, $u\to w$ if and only if $u$ appears before $v$ in the breadth-first search algorithm (see Definition \ref{def:partialorder}) starting at $v_0$. There exists a weighting of the edges $E$ and parameters $\ell_1,\cdots,\ell_n$ depending only on $\Phi$ such that the Ehrhart series of $P$ is equal to \begin{equation}\label{thm: meta} \Ehr(P,z) = \frac{\sum_{w \in V} z^{\wt(w)}}{\prod_{i=0}^n (1-z^{\ell_i})}, \end{equation} where $\wt(w) = \sum_{u \to w} \wt((u,w))$ is the sum of the weights of the ingoing edges to $w$. \end{theorem*} We prove this main result using the additivity of Ehrhart series. Specifically, we can decompose each alcoved polytope into disjoint union of half-open alcoves, and then add up all their Ehrhart series. \begin{remark} The authors realized significantly after proving formula \cref{thm: meta} that it is very similar to one given by \cite{valencia2021ehrhart} for so-called ``sliced polytopes'' which generalize alcoved polytopes of Type A. However our formula considers \emph{rational} polytopes, and as we limit to the case of general alcoved polytopes, we directly incorporate the data of the root system. \end{remark} After proving \cref{thm: meta}, we show a relationship in~\cref{thm:hypersimplicial decorated ordered set partition2n} between this formula and another formula for the $h^*$-polynomial of the second hypersimplex $$\Delta_{2,n}=\{(x_1,\dots,x_n)\in[0,1]^n~\mid~\sum_{i=1}^nx_i=2\}$$ which is given in terms of combinatorial objects called decorated ordered set partitions. The only known proofs of the latter formula simply enumerate decorated ordered set partitions and show that the number of these objects gives the $h^*$ coefficients; our proof gives a bijective reason for why decorated ordered set partitions appear in the $h^*$-polynomial of the second hypersimplex. \subsection{Organization} In \cref{sec:prelim}, we cover relevant background materials, including root systems and alcoved polytopes. In \cref{sec:ehr}, we review some general Ehrhart theory of rational polytopes that is relevant to alcoved polytopes and provide some lemmas that are used to show our first main result. We precisely state this main result (\cref{thm:main}) in \cref{sec:proof}. In \cref{sec:2n}, we recall a formula for the $h^*$-polynomial of the hypersimplex $\Delta_{k,n}$ in terms of hypersimplicial decorated ordered set partitions \cite{Kimh*} and show a connection with the formula yielded by \cref{thm:main} in the case $k=2$. \section{Preliminaries}\label{sec:prelim} In this section, we recall the relevant background for \emph{root systems} which will be used to define \emph{alcoved polytopes}. We follow the conventions in \cite{alcove2}. \subsection{Root systems}\label{sec:rootsys} Let $\R^n$ be equipped with a nondegenerate symmetric inner product $(\cdot,\cdot)$. Let $\Phi \subset \R^n$ be an irreducible \emph{crystallographic root system} with a choice of basis of \emph{simple roots} $\alpha_1, \dots, \alpha_n$. Let $\Phi^+ \subset \Phi$ be the corresponding set of \emph{positive roots}. The \emph{coweight lattice} $\Lambda^\vee$ is the integer lattice defined by $\Lambda^\vee = \Lambda^\vee(\Phi) = \{ \lambda \in \R^n \mid (\lambda, \alpha) \in \Z, \text{ for all } \alpha \in \Phi\}$. Let $\omega_1, \dots, \omega_n \subset V$ be the basis dual to the basis of simple roots, i.e., $(\omega_i, \alpha_j) = \delta_{ij}$. The $\omega_i$ are called the \emph{fundamental coweights}. They generate the coweight lattice $\Lambda^\vee$. Let $\rho = \omega_1 + \cdots + \omega_n$. The \emph{height} of a root $\alpha$ is the number $(\rho, \alpha)$ of simple roots that add up to $\alpha$. Since we assumed that $\Phi$ is irreducible, there exists a unique \emph{highest root} $\theta \in \Phi^+$ of maximal possible height. For convenience we set $\alpha_0 = -\theta$. Let $a_0 = 1$ and $a_1, \dots, a_n$ be the positive integers given by $a_i = (\omega_i, \theta)$. %The \emph{dual Coxeter number} is defined as $h^\vee = (\rho, \theta) + 1 = a_0 + a_1 + \cdots + a_n$. \subsection{Alcoved polytopes}\label{sec:alcove} Let $\Phi\subset \R^n$ be a crystallographic root system. The set of affine hyperplanes of the form $H_{\alpha,k} = \{\lambda \in \R^n \mid (\lambda, \alpha) = k \}$, where $\alpha\in\Phi^+,k\in\mathbb{Z}$, divides $\R^n$ into \emph{open alcoves}: \begin{definition} An (open) \emph{alcove} is the set $$ A = \{ \lambda \in \R^n \mid m_\alpha < (\lambda, \alpha) < m_\alpha+1, \text{ for } \alpha \in \Phi^+\} $$ where $m_\alpha$ is a collection of integers associated with the alcove $A$. A \emph{closed alcove} is the closure of an alcove. \end{definition} \begin{definition}\label{def:fundamental} The \emph{fundamental alcove} is the simplex given by \begin{align*} A_* &= \{ \lambda \in \R^n \mid 0 < (\lambda, \alpha) < 1, \text{ for } \alpha \in \Phi^+\} \\ &= \text{Interior of convex Hull of the points } 0, \omega_1/a_1, \dots, \omega_n/a_n. \end{align*} \end{definition} % \begin{lemma}[Lemma 3.4, \cite{alcove2}] % A bounded subset $P \subset V$ is an alcoved polytope if and only if $P$ is the intersection fo several half-spaces of the form $\{\lambda \in V \mid (\lambda, \alpha) \geq k\}$, for $\alpha \in \Phi$ and $k \in \Z$. % \end{lemma} The \emph{affine Weyl group} $W_{\aff}$ associated with the root system $\Phi$ is generated by the reflections $s_{\alpha,k}: \R^n \to \R^n, \alpha \in \Phi, k \in \Z$, with respect to the affine hyperplanes $H_{\alpha,k}$, and acts simply transitively on the collection of all alcoves \cite{humphreys}. In particular, the closure of each alcove has the same Ehrhart series, and we can use alcoves as the building blocks for a family of polytopes with natural triangulations (see Definition \ref{def:subdiv}) in which all top-dimensional simplices have equal volume: \begin{definition} An \textit{alcoved polytope} is a polytope which is the union of some collection of faces of closed alcoves. A \textit{proper alcoved polytope} is a polytope which is a union of closed alcoves, equivalently a top-dimensional alcoved polytope. \end{definition} In other words, every alcoved polytope is of the form $$ P = \{ \lambda \in \R^n \mid k_\alpha \leq (\lambda, \alpha) \leq K_\alpha, \text{ for } \alpha \in \Phi^+ \}, $$ where $k_\alpha, K_\alpha$ are two collections of integers indexed by the positive roots $\alpha \in \Phi^+$. \begin{definition}\label{def:subdiv} A \emph{subdivision} of a polytope $P$ is a finite set of polytopes $\mathcal{C}$ such that \begin{itemize} \item $\bigcup \mathcal{C} = P$, \item for each $P \in \mathcal{C}$, all the faces of $P$ are in $\mathcal{C}$, \item for any $P,Q \in \mathcal{C}$, $P\cap Q$ is a face of both $P$ and $Q$. \end{itemize} A \emph{triangulation} of a polytope is a subdivision such that each polytope in the subdivision is a simplex. \end{definition} An alcoved polytope is equipped with a triangulation such that the maximal faces are closed alcoves. This is called the \emph{alcove triangulation}. \begin{definition}\label{def:graphlabel} Let $P$ be an alcoved polytope. We associate a graph $\Gamma_P = (V,E)$ with labeled edges to the alcove triangulation of $P$. We will abuse notation and also use $\Gamma_P$ to denote the simplicial complex of the alcove triangulation of $P$. The vertex set $V$ consists of closed alcoves in $P$, and the edge set $E$ consists of $(A, A')$ if $A$ and $A'$ share a common facet. Note that the action of $W_{\aff}$ on the alcoves allows us to label the alcoves by elements of $W_{\aff}$ so that two neighboring alcoves differ by a simple reflection. \end{definition} % \subsection{Coxeter Groups} % For a root system $\Phi$, the affine Weyl group $W_\aff$ is an example of a Coxeter group: % \begin{definition} % Let $S$ be a set. A matrix $m: S \times S \to \{1,2,\dots,\infty\}$ is called a \emph{Coxeter matrix} if it satisfies % \begin{align*} % m(s,s') &= m(s',s) \\ % m(s,s') = 1 & \iff s = s'. % \end{align*} % A Coxeter matrix $m$ determines a group $W$ with the presentation % $$ \langle s \in S \mid (ss')^{m(s,s')} = e \text{ for all } m(s,s') \neq \infty \rangle, $$ % where $e$ is the identity element. % The pair $(W,S)$ is called a \emph{Coxeter system} and % the group $W$ is the \emph{Coxeter group}. % \end{definition} % \begin{definition} % Let $(W, S)$ be a Coxeter system. Each element $w \in W$ can be written as a product of generators $w = s_1 s_2 \cdots s_k$ for $s_i \in S$. If $k$ is minimal among all such expressions for $w$, then $k$ is called the \emph{length} of $w$ (written $\ell(w) = k$) and the word $s_1 s_2 \cdots s_k$ is called a \emph{reduced word} for $w$. % \end{definition} % \begin{definition} % Let $(W, S)$ be a Coxeter system, and let $u, v \in W$. Define the \emph{right weak order} as the partial order $\leq$ on $W$ such that $u \leq w$ if and only if $w = u s_1 s_2 \cdots s_k$ for some $s_i \in S$ such that $\ell(u s_1 s_2 \cdots s_i) = \ell(u) + i$ for all $0 \leq i \leq k$. % \end{definition} % \begin{definition}\label{def:descent} % Let $W$ be a Coxeter group. For $w \in W$, define the \emph{descent set} $\D(w) = \{s \in S \mid w s < w\}$. % For $J \subseteq S$, let $W_J$ be the subgroup of $W$ generated by the set $J$. % \end{definition} \subsection{Ehrhart series of half-open rational simplices}\label{sec:ehr} A key ingredient of the proof of \cref{thm:main} is to write an alcoved polytope $P$ as a disjoint union of \emph{half-open} simplices, or simplices with some facets removed. Since the number of lattice points in $P_1\sqcup P_2$ is the sum of the numbers of lattice points in $P_1$ and $P_2$, it suffices to look at the Ehrhart series of these half-open simplices. We may use the following lemma to write its Ehrhart series: \begin{lemma}\label{lem:half-opensimplex} Suppose $A$ is a $k$-simplex in $\R^m$ with rational vertices $\beta_0, \dots, \beta_k$. Let $\ell_i$ be the least positive integer $t$ for which $t\beta_i \in \Z^m$. Let $F_i$ be the facet of $A$ that does not contain the vertex $\beta_i$. Let $\mathcal{F} \subseteq \{0, \dots, k\}$ label a subset of the facets of $A$. Then the Ehrhart series of $A$ with facets $\{F_i \mid i \in \mathcal{F}\}$ removed is $$ \Ehr(A \setminus \bigcup_{i \in \mathcal{F}} F_i, z) = \frac{ \prod_{i \in \mathcal{F}} z^{\ell_i}}{\prod_{i=0}^k (1-z^{\ell_i})}. $$ \end{lemma} We may use the following tool to build a decomposition of a polytope into half-open simplices: \begin{definition}\label{def:shelling} Let $\Delta$ be a triangulation of some polytope $P$. A \emph{shelling} of $\Delta$ is a linear order $A_1, A_2, A_3, \dots$ on the set of maximal dimensional simplices of $\Delta$ such that $A_k \cap (A_1 \cup \cdots \cup A_{k-1})$ is a union of facets of the maximal dimensional simplices for each $k\geq 2$. \end{definition} If we have a shelling order on a triangulation of $P$, it turns out that $$P=\bigsqcup_{k\geq 1} \left(A_k\setminus(A_1 \cup \cdots \cup A_{k-1})\right),$$ and we may apply Lemma \ref{lem:half-opensimplex}. \section{Main result}\label{sec:proof} We can now describe a shelling order of the alcoves of any alcoved polytope $P$, and use this shelling order to compute the Ehrhart series of $P$. \begin{definition}\label{def:partialorder} Let $\Gamma = (V,E)$ be an undirected graph, and let $v_0 \in V$ be an arbitrary vertex of $\Gamma$. Define the \emph{breadth-first search order of $\Gamma$ with root $v_0$} as the partial order $\prec_{v_0}$ on $V$ such that for two distinct vertices $u, v \in V$, $u \prec_{v_0} v$ if and only if there is a shortest path from $v_0$ to $v$ passing through $u$. \end{definition} \begin{lemma}\label{lem:shelling} Let $P$ be an alcoved polytope and let $\Gamma_P = (V, E)$ be the graph of the alcove triangulation of $P$. For any $v_0 \in V$, any linear extension of the partial order $\prec_{v_0}$ is a shelling order of the alcove triangulation of $P$. \end{lemma} Let $(A, A')$ be an edge of $\Gamma_P$, and let $F = A \cap A'$ be the facet it represents. Then $F$ can be transformed to a facet $F_\circ$ of the fundamental alcove $A_*$ under the action of the affine Weyl group. Let $\omega_i/a_i$ be the vertex of $A_*$ that does not belong to $F_\circ$. Then $(A,A')$ has \emph{weight} $\ell_i$, denoted $\wt((A,A')) = \ell_i$, in which $\ell_i$ is the smallest positive integer such that $\ell_i\omega_i/a_i\in \Z^n$ for $i=1,\dots,n$ and $\ell_0 = 1$. We now have all the ingredients we need to compute the Ehrhart series of an arbitrary alcoved polytope: \begin{theorem}\label{thm:main} Let $P$ be an alcoved polytope and let $\Gamma_P = (V, E)$ be the edge-weighted graph of its alcove triangulation (see Definition \ref{def:graphlabel} for details). Given any $v_0 \in V$, let $\prec_{v_0}$ be the breadth-first search order of $\Gamma_P$ with root $v_0$ (see Definition \ref{def:partialorder}). The Ehrhart series of $P$ is equal to $$\Ehr(P,z) = \frac{\sum_{v \in V} z^{\wt(v)}}{\prod_{i=0}^n (1-z^{\ell_i})}$$ where $\wt(v) = \sum_{u \prec\!\cdot_{v_0} v} \wt((u,v))$ is the sum of the weights of the edges between $v$ and the elements it covers. \end{theorem} \begin{proof}[Proof sketch. ] The breadth-first search order gives a decomposition into half-open alcoves, whose Ehrhart series can be computed via Lemma \ref{lem:half-opensimplex}. Since the Ehrhart series is \emph{additive}, we simply get a sum of these terms over the half open alcoves. \end{proof} \begin{example} Consider the $n$-dimensional hypercube $\cube_n=[0,1]^n$. The graph of the alcove triangulation of a hypercube is the weak Bruhat graph of the symmetric group $\mathcal{S}_n$. Therefore, $h^*(\cube_n,z) = \sum_{w \in \mathcal{S}_n} z^{\des(w)}$, where $\des(w)=\#\{i\in[n-1]~:~w(i)>w(i+1)\}$, which is the Eulerian polynomial. This is a well-known result from \cite{hypercube}. \end{example} \section{The hypersimplex $\Delta_{2,n}$}\label{sec:2n} We now relate our shelling order formula and a combinatorial formula for a well-studied polytope. The hypersimplex $\Delta_{k,n}$ is the subset of $[0,1]^n\subset\mathbb{R}^n$ consisting of points $\{(x_1,\dots,x_n) \mid x_1 + \cdots + x_n = k\}$. Under the linear transformation $$ y_i = x_1+ \cdots + x_i, $$ the hypersimplex $\Delta_{k,n}$ can be realized as an alcoved polytope defined by $0 \leq y_i - y_{i-1} \leq 1$ and $y_n = k$ for all $i =1,\dots,n$ with the convention $y_0 = 0$. Let $\Gamma_{2,n}$ be the graph of the alcove triangulation of the hypersimplex $\Delta_{2,n}$ (see Definition \ref{def:graphlabel}). In this section we will appeal to the following characterization of the alcove triangulation of $\Delta_{k,n}$: \begin{theorem}[\cite{alcove1}] \label{thm:alcove perm description} %\begin{enumerate} The alcoves of $\Delta_{k,n}$ are in bijection with permutations $w\in \mathcal{S}_n$ modulo cycle shifts (ie. $[w_1,\ldots ,w_n]\sim [w_n,w_1,\ldots ,w_{n-1}]$) such that if we take the representative of $w$ with $w_n=n$, $\des(w^{-1})=k-1$. We write $(w)=(w_1,\ldots,w_n)$ to denote the corresponding long cycle in $\mathcal{S}_n$, and $\Delta_{(w)}$ to denote the corresponding alcove in $\Delta_{k,n}$. Then $\Delta_{(u)}$ and $\Delta_{(w)}$ are adjacent in $\Gamma_{k,n}$ if and only if there exists $i\in[n]$ such that $u_i-u_{i+1}\neq \pm 1 (\text{mod }n)$ and the cycle $(w)$ is obtained from $(u)$ by switching the positions of $u_i$ and $u_{i+1}$. %\item The vertices of $\Delta_{(w)}$ may be ordered as $v^{(1)},\ldots,v^{(n)}$ so that $v^{(i+1)}=v^{(i)}+e_{w_i+1}-e_{w_i}$ for all $i\in [n]$ with indices considered modulo $n$. This interpretation is called the \emph{circuit triangulation} of $\Delta_{k,n}$. %\end{enumerate} \end{theorem} Katzman computed the Hilbert series of Veronese type algebras in \cite{katzman2005hilbert}, and as part of a special case one can obtain the following formula for the $h^*$-polynomial of $\Delta_{k,n}$: \begin{equation}\label{eq:katzman} h^*(\Delta_{k,n},z)=\sum_{i\geq 0}(-1)^i\binom{n}{i}\left(\sum_{j\geq 0}\binom{i}{j}(z-1)^j\left(\sum_{\ell\geq0}\binom{n-j}{\ell(k-i)}_{k-i}z^\ell\right)\right), \end{equation} \noindent where $\binom{a}{b}_c$ is defined to be the coefficient of $t^b$ in $(1+t+\ldots+t^{c-1})^a$. However, this formula doesn't give an obviously nonnegative formula for the coefficients of the $h^*$-polynomial. A nonnegative interpretation of coefficients of the $h^*$-polynomial of the hypersimplex $\Delta_{k,n}$ was given in \cite{Kimh*}, where the coefficients were proved to enumerate \emph{hypersimplicial decorated ordered set partitions}. \begin{definition}[\cite{early2017conjectures}] A \emph{decorated ordered set partition} (DOSP) $((S_1)_{s_1},\dots,(S_p)_{s_p})$ of type $(k,n)$ consists of an ordered set partition $(S_1, \dots, S_p)$ of $[n]$ and a $p$-tuple of integers $(s_1, \dots, s_p) \in \Z^{p}$ such that $\sum_{i=1}^p s_i = k$ and $s_i \geq 1$. We regard them up to cyclic rotation, so $$((S_1)_{s_1},(S_2)_{s_2},\dots,(S_p)_{s_p})$$ is the same as $$((S_2)_{s_2},\dots,(S_p)_{s_p},(S_1)_{s_1}).$$ A decorated ordered set partition is \emph{hypersimplicial} if $1 \leq s_i \leq |S_i|-1$ for all $i$. We denote the set of hypersimplicial decorated ordered set partitions of type $(k,n)$ by $\OSP(\Delta_{k,n})$. We call each $S_i$ a block and place them on a circle in the clockwise fashion then think of $s_i$ as the clockwise distance between adjacent block $S_i$ and $S_{i+1}$. The \emph{winding vector} of a decorated ordered set partition is an $n$-tuple of integers $(l_1,\dots,l_n)$ such that $l_i$ is the distance of the path starting from the block containing $i$ to the block containing $(i+1)$ moving clockwise. If $i$ and $(i+1)$ are in the same block then $l_i = 0$. If $l_1 + \cdots + l_n = kd$, then we define the \emph{winding number} to be $d$. \end{definition} \begin{figure} \centering \includegraphics[width=.4\textwidth]{DOSPexample.pdf} \caption{The winding vector of $((1,5,6)_2,(3,7,8,11)_3,(4,10,12)_1,(2,9)_1)$ is (6,3,3,2,0,2,0,4,6,4,3,2) and the winding number is 35/7=5. The $i$-th entry of the winding vector is the circular distance between $i$ and $i+1$ in clockwise direction. One can walk from 1 to 2 to \dots $n$ back to 1 in clockwise direction, and the winding number is the number of times that one walks around the circle.} \label{fig:DOSP} \end{figure} \begin{theorem}[\cite{Kimh*}] Let $h^*(\Delta_{k,n},z) = h_0^*(\Delta_{k,n}) + h_1^*(\Delta_{k,n}) z + \cdots + h_{n-1}^*(\Delta_{k,n}) z^{n-1}$ be the $h^*$-polynomial of the hypersimplex $\Delta_{k,n}$. The number of hypersimplicial decorated ordered set partitions of type $(k,n)$ and winding number $d$ is $h_d^*(\Delta_{k,n})$. \end{theorem} \begin{table}[H] \centering \begin{tabular}{|c|c|} \hline winding number & $\OSP(\Delta_{2,4})$ \\ \hline 0 & $((1234)_2)$ \\ \hline 1 & $((12)_1(34)_1)$ \\ \hline 1 & $((14)_1(23)_1)$ \\ \hline 2 & $((13)_1(24)_1)$ \\ \hline \end{tabular} \caption{The $h^*$-polynomial of the octahedron $\Delta_{2,4}$ is $1+2z+z^2$.} \end{table} In \cite{Kimh*} this result is obtained by directly counting the number of hypersimplicial decorated ordered set partitions via inclusion-exclusion and comparing the result to the coefficients in \cref{eq:katzman}. In this section of our paper, we use our formula in \cref{thm:main} to give a bijective proof of this result for the hypersimplex $\Delta_{2,n}$. We associate a hypersimplicial decorated ordered set partition of type $(2,n)$ with winding number one to each edge in $\Gamma_{2,n}$. \begin{definition}\label{def:edgelabels} Let $A,A' \subseteq \Delta_{2,n}$ be two alcoves such that $A$ and $A'$ share a common facet. Then $A \cap A'$ is of the form $y_j - y_i = 1$ for some $i \not\equiv j \pm 1 \pmod n$. We associate the hypersimplicial decorated ordered set partition $([i-1,j]_1,[j-1,i]_1)$ to the edge $(A,A')$ in the graph $\Gamma_{2,n}$. In terms of the permutation characterization of $\Gamma_{2,n}$ given in \cref{thm:alcove perm description}, this edge corresponds to the transposition $ij\to ji$. \end{definition} % \begin{definition}\label{def:newDOSP} % For two hypersimplicial decorated ordered set partitions $\{A, B\}, \{A', B'\}$ of type $(2,n)$ with nonzero winding numbers, we define $\psi(\{A, B\}, \{A', B'\})$ to be a new hypersimplicial decorated ordered set partition $\{A'', B''\}$ of type $(2,n)$ such that $A'' = A \triangle A'$ is the symmetric difference between $A$ and $A'$ and $B'' = [n] \setminus A''$ is the complement of $A''$. % For a collection of $d$ adjacent hypersimplicial decorated ordered set partitions $\{A_1,B_1\},\dots, \{A_d, B_d\}$ of type $(2,n)$ and winding number one, we define $\psi(\{A_1,B_1\},\dots, \{A_d, B_d\})$ recursively to be % $$\psi(\psi(\{A_1,B_1\},\dots, \{A_{d-1}, B_{d-1}\}), \{A_d, B_d\}).$$ % \end{definition} \begin{definition}\label{def:newDOSP} Let $S^C=[n]\setminus S$. A hypersimlicial decorated ordered set partition of type $(2,n)$ has the form $((S)_1,(S^C)_1)$; we will drop the decorations when they are clear from context. For two hypersimplicial decorated ordered set partitions $(S,S^C), (T,T^C)$ of type $(2,n)$ with nonzero winding numbers, we define $$\psi((S,S^C), (T,T^C)) = (S \triangle T, (S \triangle T)^C),$$ where $S \triangle T = (S \setminus T) \cup (T \setminus S)$ is the symmetric difference of the two sets. For a collection of $d$ adjacent hypersimplicial decorated ordered set partitions $\{(S_i,S_i^C)\}_{i=1}^d$ of type $(2,n)$ and winding number one, we define $$\psi((S_i,S_i^C)_{i=1}^d) = (S_1 \triangle \cdots \triangle S_d, [n] \setminus (S_1 \triangle \cdots \triangle S_d)).$$ \end{definition} \begin{remark} If we view the $S_i$'s as binary vectors in $\{0,1\}^n$, then $\triangle$ is the XOR (exclusive or) operator. \end{remark} \begin{example} Consider $((123)_1(456)_1)$, $((234)_1(156)_1)$, and $((345)_1(126)_1)$ of type $(2,6)$ and winding number one, we have \begin{align*} &\psi(((123)_1(456)_1),((234)_1(156)_1),((345)_1(126)_1)) \\ &= \psi(((14)_1(2356)_1), ((345)_1(126)_1)) \\ &= ((135)_1(246)_1), \end{align*} which has winding number 3. \end{example} \noindent We can finally state the main result of this section: \begin{theorem} \label{thm:hypersimplicial decorated ordered set partition2n} For any $n$ and for any alcove $A_0$ in $\Delta_{2,n}$, let $\prec_{A_0}$ be the breadth-first search order of $\Gamma_{2,n}$ with root $A_0$ (see Definition \ref{def:partialorder}). For an alcove $A$ in $\Delta_{2,n}$, let $\cover(A)$ be the number of alcoves $A$ covers in the poset $\prec_{A_0}$. In other words, $\cover(A)$ is the number of incoming edges of $A$ in the directed graph we obtain from the Hasse diagram of $\prec_{A_0}$. Applying the map $\psi$ to the set of incoming edges of an alcove gives a bijection from the set of alcoves $A$ with $\cover(A) = d$ and the set of hypersimplicial decorated ordered set partitions of type $(2,n)$ with winding number $d$. \end{theorem} \begin{figure} \centering \includegraphics[width=0.7\textwidth]{Delta52example.pdf} \caption{$\Delta_{2,5}$ with $A_0$ at the center. The arrows indicate cover relations in $\prec_{A_0}$, pointing in increasing directions. The orange arrows are facets representing the cover relations of the alcove labeled by $((13)_1(245)_1)$.} \label{fig:hypersimplex25} \end{figure} \begin{example} In \cref{fig:hypersimplex25}, we choose $A_0$ to be the simplex in the center of the graph $\Gamma_{2,5}$ and we label it by the unique hypersimplicial decorated ordered set partition of type $(2,5)$ with winding number 0, which is $((12345)_2)$. The arrows are cover relations, and they point in increasing directions in $\prec_{A_0}$. The alcove labeled by $((13)_1(245)_1)$ covers two alcoves in the poset $\prec_{A_0}$, via the orange edges labeled by $((12)_1(345)_1)$ and $((23)_1(145)_1)$, and one can check that the winding number of $((13)_1(245)_1)$ is precisely 2. Following this example, it is easily seen that $h^*(\Delta_{2,5},z)=1+5z+5z^2$, as there are 1, 5, and 5 alcoves with 0, 1, and 2 incoming arrows respectively. \end{example} We begin by giving a necessary condition for two edges $\{i_1,j_1\}$ and $\{i_2,j_2\}$ to appear together as incoming edges of an alcove $A$ in $\prec_{A_0}$. \begin{definition} We say $\{i_1,j_1\}$ and $\{i_2,j_2\}$ are crossing if $i_1w^{-1}(i+1)$ or if $i=n$ and $w^{-1}(1)_i \cDes_L(w_{A}^{(i)})$ in the Gale order on $\binom{[n]}{2}$ with respect to $<_j$ and $<_i$. \end{lemma} \begin{example} Consider $\Delta_{2,15}$. Let $(w_{A_0})=(1,2,3,4,5,10,6,7,11,8,12,9,13,14,15)$ and $E=\{\{3,11\}\}$. We have $\cDes_L(w_{A_0}^{(11)})=\{7,11\}$. Let $(w)$ corresponds to the alcove with incoming edge set $E$. If $(w)=(\ldots,3,11,\ldots)$, then $\cDes_L(w^{(11)})=\{3,11\}$. If $(w)=(\ldots,11,3,\ldots)$, then $\cDes_L(w^{(11)})=\{2,11\}$. Since $2<_{11} 3<_{11} 7$, we have $(w)=(\ldots,11,3,\ldots)$ so that it is ``further'' away from $(w_{A_0})$. \end{example} Finally note that to prove our main result on the second hypersimplex (\cref{thm:hypersimplicial decorated ordered set partition2n}) injectivity is sufficient because previous work by \cite{ocneanu2013} shows that the sets we are mapping between are equal in cardinality (given by the Eulerian numbers). \begin{remark} An obvious future direction would be to try to extend our bijective result for the second hypersimplex to the general hypersimplex $\Delta_{k,n}$. In our attempts to do this we ran into a couple of difficulties. The first is simply assigning facets of alcoves in $\Delta_{k,n}$ to DOSPs of type $(k,n)$ with winding number 1 (or equivalently, a subset $J\in\binom{[n]}{k}$ that is not a cyclic interval). In particular, one idea that was tried is the following: Given an edge in the graph of the alcove triangulation $A\to A'$, there is a unique vertex $v''$ of $A'$ not shared by $A$. There is also a natural ordering (up to cyclic rotations) on the vertices of an alcove according to the circuit definition of the alcoved triangulation \cite{alcove1}. By taking the vertex preceding $v''$ in this order for $A'$, we obtain some other vertex $v'$ which should be the indicator of some $J\in\binom{[n]}{k}$, and we associate the corresponding DOSP with $v'$ to $A'$. This turns out to generalize our edge labelings for the second hypersimplex, but it does not even yield a bijection between alcoves with one incoming edge in $\prec_{A_0}$ and DOSPs of type $(k,n)$ with winding number 1. We remain hopeful that a clever edge labeling exists. \end{remark} \acknowledgements{We thank Alex Postnikov for suggesting this topic. We thank Lauren Williams for the helpful discussions and comments on the manuscript. We thank Nick Early for helpful discussions.} %% 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}