%% 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{111}
%% 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{mathtools}
\usepackage{float}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{math}
\usetikzlibrary{calc}
\usepackage{tikz-3dplot}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rem}[thm]{Remark}

\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\renewcommand{\P}{\mathbf P}
\newcommand{\J}{\mathcal J}
\newcommand{\B}{\mathcal B}
\newcommand{\y}{\mathbf y}
\newcommand{\precdot}{\prec\hspace{-5pt}\cdot ~}

\def\des{\ensuremath{\mathrm{des}}}
\def\cdes{\ensuremath{\mathrm{cdes}}}
\def\cDes{\ensuremath{\mathrm{cDes}}}
\def\Des{\ensuremath{\mathrm{Des}}}
\def\area{\ensuremath{\mathrm{area}}}
\def\cover{\ensuremath{\mathrm{cover}}}

\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\rk}{rank}
\DeclareMathOperator{\conv}{convex}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\vol}{vol}

\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}

\newcommand{\pyramid}{
    \tikz[scale=0.3]{
        % Define the coordinates for the base of the pyramid
    \coordinate (A) at (0,1);
    \coordinate (B) at (2.5,0);
    \coordinate (C) at (4,1);
    \coordinate (D) at (1.5,2);

    % Define the coordinate for the apex of the pyramid
    \coordinate (Apex) at (2,4);

    % Draw the base of the pyramid
    \draw[thick] (A) -- (B) -- (C);
    \draw[thick,dotted] (C) -- (D) --(A);

    % Draw the edges from the apex to the base vertices
    \draw[thick] (Apex) -- (A);
    \draw[thick] (Apex) -- (B);
    \draw[thick] (Apex) -- (C);
    \draw[thick,dotted] (Apex) -- (D);
    }
}

\newcommand{\prism}{
\tikz[baseline=(base),scale=1.5]{
        % Define the vertices of the prism
        \coordinate (A1) at (0,0);        % Bottom-left of the front face
        \coordinate (B1) at (0.5,0);      % Bottom-right of the front face
        \coordinate (C1) at (0.25,0.4);   % Top vertex of the front face (for a triangular face)
        
        \coordinate (A2) at (0.2,0.2);    % Bottom-left of the back face
        \coordinate (B2) at (0.7,0.2);    % Bottom-right of the back face
        \coordinate (C2) at (0.45,0.6);   % Top vertex of the back face

        % Draw the front face (triangle)
        \draw[thick] (A1) -- (B1) -- (C1) -- cycle;

        \draw[thick,dotted] (A1) -- (A2);
        \draw[thick,dotted] (A2) -- (B2);
        \draw[thick,dotted] (A2) -- (C2);
        \draw[thick] (B2) -- (C2);

        % Draw the edges connecting the front and back faces
        \draw[thick] (B1) -- (B2);
        \draw[thick] (C1) -- (C2);

        % Mark the base line for alignment with text
        \path (A1) -- (B1) coordinate [pos=0.5] (base);
    }
}

%% define your title in the usual way
\title{The Ehrhart h*-polynomials of positroid 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{\texorpdfstring{Yuhan Jiang\thanks{\href{mailto:yjiang@math.harvard.edu}{yjiang@math.harvard.edu}.}\addressmark{1}}{Yuhan Jiang}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Harvard University, USA}

%% 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{A positroid is a matroid realized by a matrix such that all maximal minors are non-negative.
Positroid polytopes are matroid polytopes of positroids.
In particular, they are lattice polytopes.
The Ehrhart polynomial of a lattice polytope counts the number of integer points in the dilation of that polytope.
The Ehrhart series is the generating function of the Ehrhart polynomial, which is a rational function with the numerator called the $h^*$-polynomial.
We compute the $h^*$-polynomial of an arbitrary positroid polytope and an arbitrary half-open positroid polytope.
Our result generalizes that of Katzman, Early, Kim, and Li for hypersimplices.}

%% 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{positroids, Ehrhart theory}

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

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

\begin{document}

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

\section{Introduction}\label{intro}

A positroid is a matroid on an ordered set realized by a matrix such that all of its maximal minors are non-negative. 
Postnikov \cite{postnikov2006} showed that positroids are in bijection with several interesting classes of combinatorial objects, including Grassmann necklaces, decorated permutations, $\reflectbox{L}$-diagrams, and equivalence classes of plabic graphs.

If $P \subseteq \Z^n$ is a $d$-dimensional lattice polytope, its \emph{Ehrhart function/polynomial} is defined for every integer $t \ge 0$ by
\[
E(P,t) := \#(t \cdot P) \cap \Z^n
\]
where $t \cdot P$ is the dilation of $P$ by a factor $t$, i.e., $t \cdot P = \{t \cdot v \mid v \in P\}$.
It is well known from Ehrhart \cite{ehrhart} that $E(P,t)$ is a polynomial function in $t$.
The corresponding \emph{Ehrhart series} is defined as
$\sum_{t=0}^\infty E(P,t) z^t = \frac{h^*(P,z)}{(1-z)^{d+1}}$
where $h^*(P,z) = h_0+h_1 z +\cdots + h_d z^d$ is a polynomial of degree at most $d$ with non-negative coefficients \cite{stanley80}, called the \emph{Ehrhart $h^*$-polynomial} of $P$.
Ehrhart theory naturally extends to half-open polytopes, which are polytopes with some facets removed. The Ehrhart $h^*$-polynomial of the whole polytope can then be obtained by inclusion-exclusion on the faces.

In this paper, we give explicit formulas for the $h^*$-polynomials of positroid polytopes and half-open positroid polytopes.
Our work generalizes the work of Katzman \cite{Katzman}, Early \cite{early2017conjectures}, Kim \cite{Kimh*}, and Li \cite{NanLi} on hypersimplices, as the hypersimplex $\Delta_{k,n}$ is the matroid polytope of the uniform matroid $U_{k,n}$, which is also a positroid.
Apart from the special case of the uniform matroid, no prior combinatorial formula for the $h^*$-polynomial of an arbitrary positroid polytope was known.

\begin{thm}\label{thm:main}
Let $P_\J$ be any connected positroid polytope (see \Cref{def:connected}), where $\J$ is the associated Grassmann necklace (see \Cref{def:Grassneck}). 
Let $D_\J \subset S_n$ be the subset of permutations that label the circuit triangulation of $P_\J$ (see \Cref{thm:trian}).
For any $w_0 \in D_\J$, let $(\mathcal{P}_{w_0,\J}, \prec)$ be the corresponding poset on $D_\J$ (see \Cref{def:digraph}).
The cover statistic of $\mathcal{P}_{w_0,\J}$ gives the $h^*$-polynomial of $P_\J$, i.e.,
$$h^*(P_\J,z) = \sum_{w \in D_\J} z^{\cover(w)}$$
where
$\cover(w)$ is the number of elements $w$ covers in the poset $\mathcal{P}_{w_0,\J}$.
\end{thm}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[thick,scale=1, every node/.style={scale=.8}]
    \draw (0,0) node (2413) [draw,circle] {24135};
    \draw (-3,2) node (2143) [draw,circle] {21435};
    \draw (-1,2) node (3241) [draw,circle] {32415};
    \draw (1,2) node (4213) [draw,circle] {42135};
    \draw (3,2) node (2431) [draw,circle] {24315};
    \draw (2413) -- (2143);
    \draw (2413) -- (3241);
    \draw (2413) -- (4213);
    \draw (2413) -- (2431);
    \draw (-2,4) node (3214) [draw,circle] {32145};
    \draw (0,4) node (3421) [draw,circle] {34215};
    \draw (2,4) node (4231) [draw,circle] {42315};
    \draw (2143) -- (3214) -- (3241);
    \draw (3241) -- (3421) -- (4213);
    \draw (4213) -- (4231) -- (2431);
    \end{tikzpicture}
    \caption{We show the graph of the circuit triangulation of the positroid polytope $P_\J$ associated to the positroid with Grassmann necklace $\J = (123,235,345,145,125)$, which coincides with the Hasse diagram of the poset $\mathcal{P}_{24135,\J}$. The $h^*$-polynomial of $P_\J$ is $1+4z+3z^2$.}
    \label{fig:positroid34521}
\end{figure}

\subsection{Organization}
In \Cref{sec:posi}, we introduce positroids and related combinatorial objects. We reduce the problem to \emph{connected positroids}; see \Cref{def:connected}.
In \Cref{sec:trian}, we analyze the \emph{circuit triangulation} of connected positroid polytopes.
In \Cref{sec:shelling}, we give a family of shellings of connected positroid polytopes, which give formulas for the $h^*$-polynomial of an arbitrary connected positroid polytope, proving \Cref{thm:main}.
In \Cref{sec:half-open}, we give a formula for the $h^*$-polynomial of any connected positroid polytope with \emph{upper facets} removed.
In \Cref{sec:tree}, we apply our theorems to the special case of tree positroids and derive \Cref{cor:tree} in terms of the \emph{circular extensions} of \emph{partial cyclic orders}.


\section{Positroids}\label{sec:posi}
In this section, we will start by defining \emph{matroids} and \emph{positroids}.
We also define Postnikov's notion of
\emph{Grassmann necklace}, and explain how each one naturally labels a posi\-troid.
Then we introduce positroid polytopes and the notion of \emph{connected} positroids, and we reduce the problem to connected positroids.

% \begin{definition}
%     A \emph{matroid} is a pair $M = (E,\B)$ consisting of a finite set $E$ and a nonempty collection of subsets $\B = \B(M)$ of $E$, called the \emph{bases} of $M$,
%     which satisfy the \emph{basis exchange axiom}:
% \begin{center}
%     For any $I, J \in \B$ and $i \in I$ there exists $j \in J$ such that $(I \setminus \{i\}) \cup \{j\} \in M$.
% \end{center}
% All the bases $B \in \B$ have the same size, which is called the \emph{rank} of $M$.
% \end{definition}

For a $k \times n$-matrix $A$ of rank $k$ and a $k$-element subset $I \subset [n]$, let $A_I$ denote the $k\times k$-submatrix of $A$ in the column set $I$, and let $\Delta_I(A) := \det(A_I)$ denote the corresponding \emph{maximal minor} of $A$.
The set of $k$-subsets $I \subset [n]$ such that $\Delta_I(A) \neq 0$ form the bases of a rank $k$ matroid $M(A)$.

\begin{definition}
Suppose $A$ is a $k \times n$ matrix of rank $k$ with real entries such that all its maximal minors are nonnegative.
The matroid $M(A)$ associated to $A$ is called a \emph{positroid}.
\end{definition}

\begin{definition}\label{def:Grassneck}
Let $k \leq n$ be a positive integer. A \emph{Grassmann necklace} of type $(k,n)$ is a sequence $(J_1, J_2, \dots, J_n)$ of $k$-subsets $J_i \in \binom{[n]}{k}$ such that for any $i \in [n]$,
\begin{itemize}
    \item if $i \in J_i$ then $J_{i+1} = J_i - \{i\} \cup \{j\}$ for some $j \in [n]$,
    \item if $i \notin J_i$ then $J_{i+1} = J_i$,
\end{itemize}
where $J_{n+1}=J_1$ by convention.
\end{definition}

Towards the bijection between Grassmann necklaces and positroids, we need the notion of \emph{$i$-order}.
The \emph{i-order} $<_i$ on the set $[n]$ is the total order
\[
i <_i i+1 <_i \cdots <_i n <_i 1 <_i \cdots <_i i-2 <_i i-1.
\]

Let $i \in [n]$. The \emph{Gale order} on $\binom{[n]}{d}$ (with respect to $<_i$) is the partial order $\le_i$ defined as follows: for any two $d$-subsets $S = \{s_1 <_i \cdots <_i s_d \} \subseteq [n]$ and $T = \{t_1 <_i \cdots <_i t_d \} \subseteq [n]$, we have $S \le_i T$ if and only if $s_j \le_i t_j$ for all $j \in [d]$.

\begin{lem}[{\cite[Lemma 16.3]{postnikov2006}}]
For a matroid $M \subseteq \binom{[n]}{k}$ of rank $k$ on the set $[n]$, let $\J_M = (J_1, \dots, J_n)$ be the sequence of subsets in $[n]$ such that, for $i \in [n]$, $J_i$ is the minimal basis of $M$ with respect to the Gale order with respect to $<_i$ on $[n]$.
The sequence $\J(M)$ is a Grassmann necklace of type $(k,n)$.
\end{lem}

\begin{thm}[\cite{postnikov2006,oh2017}]\label{thm:basis}
Let $\J = (J_1, \dots, J_n)$ be a Grassmann necklace of type $(k,n)$. Then the collection
$$ \mathcal{B}(\J) := \left\{ B \in \binom{[n]}{k} \mid B \geq_i J_i \text{ for all } i \in [n] \right\} $$
is the collection of bases of a rank $k$ positroid $\mathcal{M}(\J) := ([n], \mathcal{B}(\J))$.
Moreover, for any positroid $M$ we have $\mathcal{M}(\J(M)) = M$.
\end{thm}

\begin{ex}
Let $\J$ be the Grassmann necklace $(12,23,13,14)$. The bases of the positroid associated to $\J$ is $\{12,13,14,23,24\}$.
\end{ex}

\begin{definition}
Given a matroid $M = ([n],\B)$, the (basis) \emph{matroid polytope} 
$$P_M := \conv \{e_B \mid B \in \B\} \subset \R^n$$ of $M$ is the convex hull of the indicator vectors of the bases of $M$, where $e_B = \sum_{i \in B} e_i$ and $\{e_1,\dots,e_n\}$ is the standard basis of $\R^n$.
\end{definition}

\noindent
The next proposition provides inequalities defining the matroid polytope of a positroid.
\begin{prop}[\cite{positroids,polyposi}]\label{prop:posi}
Let $\J = (J_1, J_2, \dots, J_n)$ be a Grassmann necklace of type $(k,n)$. 
For any $i \in [n]$, suppose the elements of $J_i$ are $a_1^i <_i a_2^i <_i \cdots <_i a_k^i$. Then the matroid polytope $P_{\mathcal{I}}$ of the positroid associated to $\J$ can be described by the inequalities $x_i \ge 0$ for all $i \in [n]$ and
\begin{align*}
    x_1+x_2+\cdots+x_n &= k \\
    x_i + x_{i+1} + \cdots + x_{a_{j}^{i}-1} &\le j-1 
\end{align*}
for all $i \in [n]$ and $j \in [k]$, where all the subindices are taken modulo $n$.
\end{prop}

To write the inequalities more concisely, we will use the following notation. Given $i, j \in [n]$, we define the \emph{(cyclic) interval} $[i,j]$ to be the totally ordered set
$$
[i,j] := \left\{ \begin{matrix}
        \{i <_i i+1 <_i \cdots <_i j\} & \text{ if } i \leq j, \\
        \{i <_i i+1 <_i \cdots <_i n <_i 1 <_i \cdots <_i j\} & \text{ if } i > j,
    \end{matrix}
    \right.
$$
and
$ x_{[i,j)} = x_i + \cdots + x_{j-1}$
with all indices modulo $n$.

We reduce the problem to connected positroids.

\begin{definition}\label{def:connected}
A matroid which cannot be written as the direct sum of two nonempty matroids is called \emph{connected}.
\end{definition}

\begin{lem}[{\cite[Lemma 7.3]{positroids}}]
Let $M$ be a positroid on $[n]$ and write it as a direct sum of connected matroids $M = M_1 \oplus \cdots \oplus M_m$. Then each $M_i$ is a positroid.
\end{lem}

\begin{rem}\label{rema:reduce_to_connected}
The matroid polytope of a connected positroid on $[n]$ has dimension $n-1$ \cite[Theorem 8.2]{positroids}.
If a matroid $M$ is equal to the direct sum of matroids $M = M_1 \oplus \cdots \oplus M_m$, then the matroid polytope $P_M$ of $M$ is equal to the direct product $P_M = P_{M_1} \times \cdots \times P_{M_m}$.
The Ehrhart polynomial of $P_M$ is equal to $E(P_M) = E(P_{M_1}) \cdots E(P_{M_m})$.
Thus, to know the $h^*$-polynomial of all positroid polytopes, it suffices to give formulas for all connected positroid polytopes.
From now on, we will focus on connected positroids.
\end{rem}

\section{Circuit triangulation of connected positroid polytopes}
\label{sec:trian}

In this section, we analyze the triangulation of connected positroid polytopes in terms of \emph{$(w)$-simplices}, defined by Parisi, Sherman-Bennett, Tessler, and Williams, and follow their conventions.
We now introduce several
definitions regarding descents/permutations that lead up to the characterization of $(w)$-simplices.

\begin{definition}\label{def:leftcycdes}
Let $w \in S_n$. A letter $i < n$ is a \emph{left descent} of $w$ if $i$ occurs to the right of $i+1$ in $w$. 
In other words, $w^{-1}(i) > w^{-1}(i+1)$. 
We say that $i \in [n]$ is a \emph{cyclic left descent} of $w$ if either $i<n$ is a left descent of $w$ or if $i=n$ and 1 occurs to the left of $n$ in $w$, that is, $w^{-1}(1) < w^{-1}(n)$. We let $\cDes_L(w)$ denote the set of cyclic left descents of $w$ and let $\cdes_L(w) = |\cDes_L(w)|$.
\end{definition}

\begin{definition}\label{Dk+1n}
Choose $0 \leq k \leq n-2$. 
We let $D_n$ be the set of permutations $w \in S_n$ with $w_n=n$, and let  $D_{k+1, n}$ to be the set of permutations $w \in D_n$ with $k+1$ cyclic left descents. 
Let $(w)$ denote the cycle $(w_1, \cdots, w_n)$.
\end{definition}

The definition of cyclic left descent only depends on the total order on $[n]$. That is, given any permutation of any totally ordered set that is not a singleton or empty set, the cyclic left descent of such a permutation can be defined analogously.
This definition coincides with \cite[Definition 6.2]{alcove2} in type A.

\begin{definition}
Let $w = w_1\cdots w_n \in S_n$ and $i, j \in [n]$.
Let $[i,j]$ denote the cyclic interval defined in \Cref{sec:posi}.
Let $w|_{[i,j]}$ be the restriction of $w$ to the totally ordered set $[i,j]$, and let $\cdes_L(w|_{[i,j]})$ be the number of cyclic left descents of $w|_{[i,j]}$.
\end{definition}

\begin{ex}
Let $w = 32415$. Then $w|_{[1,3]} = 321$ and $w|_{[3,1]} = 3415$. Then $\cDes_L(w|_{[1,3]}) = \{1,2\}$ and $\cDes_L(w|_{[3,1]}) = \{5,1\}$.
\end{ex}

\begin{definition}
For $w = w_1 w_2 \cdots w_n \in S_n$, let $w^{(a)}$ denote the cyclic rotation of $w$ ending at $a$. We define
$$ I_r(w) := \cDes_L(w^{(r)}). $$
Note that $I_r$ only depends on the cycle $(w)$, and $|I_1(w)| = \cdots = |I_n(w)|$.

We define the $(w)$-simplex
$\Delta_{(w)}$ to be the convex hull of the points $e_{I_1(w)}, \dots, e_{I_n(w)}$; this is an $(n-1)$-dimensional simplex. We call
\[
I_{w_1} \to I_{w_2} \to \cdots \to I_{w_n} \to I_{w_1}
\]
the \emph{circuit} of $\Delta_{(w)}$.
\end{definition}

Triangulations by $(w)$-simplices are often called \emph{circuit triangulations} \cite{alcove1}.

\begin{ex}
The circuit of $32415$ is $135 \to 235 \to 245 \to 124 \to 125 \to 135$. The vertices of $\Delta_{(32415)}$ are $11001, 10101, 01101, 01011, 11010$.
\end{ex}

We now characterize the set of $(w)$-simplices in a positroid polytope.

\begin{thm}\label{thm:trian}
Let $P_\J$ be any connected positroid polytope, where $\J = (J_1, \dots, J_n)$ is the associated Grassmann necklace. 

For any $i \in [n]$, suppose the elements of $J_i$ are $a_1^i <_i \cdots <_i a_k^i$. Then the positroid polytope associated to $\pi$ is triangulated by $(w)$-simplices for $w$ in the set
\begin{align*}
    D_\J &:= \{ w \in D_{k+1,n} \mid \cdes_L(w|_{[i,a_j^i]}) \leq j-1 \text{ for all } i \in [n], j \in [k] \} \\
    &= \{ w \in D_{k+1,n} \mid I_{w_i} \geq_j J_j \text{ for all } i,j \in [n] \},
\end{align*}
where $I_{w_1} \to I_{w_2} \to \dots \to I_{w_n} \to I_{w_1}$ is the circuit of $w$.
The normalized volume of $P_\J$ is
$\vol(P_\J) = |D_\J|$ the cardinality of $D_\J$.
\end{thm}

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.6]
    % Define the coordinates for the base of the pyramid
    \coordinate (A) at (0,1);
    \coordinate (B) at (2.5,0);
    \coordinate (C) at (4,1);
    \coordinate (D) at (1.5,2);

    % Define the coordinate for the apex of the pyramid
    \coordinate (Apex) at (2,5);

    % Draw the base of the pyramid
    \draw[thick] (A) -- (B) -- (C);
    \draw[thick,dotted] (C) -- (D) --(A);

    % Draw the edges from the apex to the base vertices
    \draw[thick] (Apex) -- (A);
    \draw[thick] (Apex) -- (B);
    \draw[thick] (Apex) -- (C);
    \draw[thick,dotted] (Apex) -- (D);
    \draw[thick,dotted] (B) -- (D);

    % Label the base vertices
    \node[below left] at (A) {0110};
    \node[below right] at (B) {1010};
    \node[above right] at (C) {1001};
    \node[above left] at (D) {0101};

    % Label the apex
    \node[above] at (Apex) {1100};
    \end{tikzpicture}
    \caption{The positroid polytope associated to the Grassmann necklace $(12,23,13,14)$, with bases $\{12,13,14,23,24\}$, consisting of the $(1324)$-simplex on the left and the $(2134)$-simplex on the right.}
    \label{fig:pyramid}
\end{figure}

\begin{ex}
Consider the Grassmann necklace $\J = (12,23,13,14)$. Then $D_\J$ consists of permutations in $S_4$ that end with 4 such that $\cdes_L(w) = 2$ and $\cdes_L(w|_{[3,4]}) \leq 1$, so $D_\J = \{1324, 2134\}$. The positroid polytope $P_\J$ is a pyramid, as in \Cref{fig:pyramid}. The $(1324)$-simplex has vertices $1100,0101,0110,1010$, and the $(2134)$-simplex has vertices $1100,0101,1001,1010$.
\end{ex}

\section{The h*-polynomial of connected positroid polytopes}\label{sec:shelling}

In this section, we prove \Cref{thm:main}, which gives the $h^*$-polynomial of an arbitrary connected positroid polytope.

\begin{definition}
A \emph{shelling} of a simplicial complex $\Gamma$ is a linear order on its maximal faces $G_1, G_2, \dots, G_s$ such that, for each $i \in [2,s]$, the set $G_i \cap (G_1 \cup \cdots \cup G_{i-1})$ is a union of facets of $G_i$.
\end{definition}

\begin{lem}[{\cite[Corollary 2.6]{stanley80}}]\label{lem:stanley}
Let $\Gamma$ be a unimodular triangulation of a polytope $P$ and
let $G_1, \dots, G_s$ be a shelling of $\Gamma$. Then the $h^*$-polynomial of $P$ is equal to
$h^*(P,z) = \sum_{i=1}^{s} z^{\alpha_i}$ where
$\alpha_i$ is the number of facets of $G_i$ in the intersection $G_i \cap (G_1 \cup \cdots \cup G_{i-1})$.
\end{lem}

\begin{definition}\label{def:graph}
Consider a connected positroid polytope $P_\J$ with Grassmann necklace $\J$.
Let $\Gamma_\J$ be the graph whose vertices are $w \in D_\J$ and there is an edge between $w$ and $u$ if and only if $\Delta_{(w)}$ and $\Delta_{(u)}$ share a common facet.
We call $\Gamma_\J$ the \emph{graph of the circuit triangulation of $P_\J$}.
\end{definition}

In the special case of the hypersimplex $\Delta_{k,n}$, the graph $\Gamma_{k,n}$ is defined in \cite[Section 2.5]{alcove1}.
For a generic connected positroid with Grassmann necklace $\J$ of type $(k,n)$, the graph $\Gamma_\J$ is a connected subgraph of $\Gamma_{k,n}$.

\begin{definition}\label{def:digraph}
Let $\Gamma = (V, E)$ be an undirected graph, and let $v_0 \in V$ be an arbitrary vertex of $\Gamma$. 
Define a partial order $(\mathcal{P}_{v_0,\Gamma},\prec)$ on $V$ with minimal element $v_0$ such that, for two distinct vertices $u, v \in V$, $u \prec v$ if and only if there exists a shortest path from $v_0$ to $v$ passing through $u$.
\end{definition}

In particular, the above definition applies to $\Gamma_\J$ and $w_0 \in D_\J$ for any Grassmann necklace $\J$. 
In this case, we will simplify our notation and denote $\mathcal{P}_{w_0, \Gamma_\J}$ by $\mathcal{P}_{w_0,\J}$.
We can embed any connected positroid polytope into an \emph{affine Coxeter arrangement}. The partial order $\mathcal{P}_{w_0,\J}$ is identified with the restriction of the weak order on a subset of the \emph{affine symmetric group} $\tilde{S}_n$.

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=3,every node/.style={draw, circle, inner sep=2pt, scale=.8}]
    % Nodes
    \node (4123) at (0:1) {41235}; 
    \node (1243) at (72:1) {12435}; 
    \node (1324) at (144:1) {13245};
    \node (2134) at (216:1) {21345};
    \node (2341) at (288:1) {23415}; 
    
    \node (1423) at (36:0.6) {14235}; 
    \node (3124) at (108:0.6) {31245}; 
    \node (1342) at (180:0.6) {13425};
    \node (2314) at (252:0.6) {23145};
    \node (3412) at (324:0.6) {34125}; 

    \node (3142) at (0,0) {31425};

    \draw[thick,->] (3142) -- (1423);
    \draw[thick,->] (3142) -- (3124);
    \draw[thick,->] (3142) -- (1342);
    \draw[thick,->] (3142) -- (2314);
    \draw[thick,->] (3142) -- (3412);

    \draw[thick,->] (3124) -- (1324);
    \draw[thick,->] (3124) -- (1243);
    
    \draw[thick,->] (1423) -- (4123);
    \draw[thick,->] (1423) -- (1243);
    
    \draw[thick,->] (3412) -- (4123);
    \draw[thick,->] (3412) -- (2341);
    
    \draw[thick,->] (2314) -- (2134);
    \draw[thick,->] (2314) -- (2341);

    \draw[thick,->] (1342) -- (2134);
    \draw[thick,->] (1342) -- (1324);
\end{tikzpicture}
 \caption{We draw the graph $\Gamma_{2,5}$ of the circuit triangulation of the hypersimplex $\Delta_{2,5}$. The vertices of $\Gamma_{2,5}$ are labeled by permutations in one-line notation. The arrows represent cover relations in the poset $\mathcal{P}_{31425,\J}$ for $\J = (12,23,34,45,51)$, pointing from a smaller element to a bigger element.
We have $h^*(\Delta_{2,5},z) = 1+5z+5z^2$.}
\label{fig:hypersimplex25}
\end{figure}

% \begin{lem}\label{lem:facets}
% Let $P_\J$ be a connected positroid polytope where $\J$ is the associated Grassmann necklace. 
% Let $u, w \in D_\J$. 
% Let $J$ be the minimal set of simple reflections that generate $L_u(w)$ in $\tilde{S}_n$ with $|J| = m$. Then the intersection between $\Delta_{(w)}$ and $\Delta_{(u)}$ is $\Delta_{(w)} \cap \Delta_{(u)} = \conv(e_{I_{w_i}} \mid i \notin J)$ with codimension $m$.
% \end{lem}

Benedetti--Knauer--Valencia-Porras proved the following for general type A alcoved polytopes in \cite[Proposition 2.5]{benedetti2023latticepathmatroidpolytopes}.
In the spirit of \cite[Theorem 2.1]{bjorner}, \Cref{prop:shelling} can be generalized to any other Coxeter group, studied by the author and Bullock in \cite{BJ24}.

\begin{prop}\label{prop:shelling}
Consider a connected positroid polytope $P_\J$ with Grassmann necklace $\J$. 
Let $\Gamma_\J$ be the graph of the circuit triangulation of $P_\J$.
For any $w_0 \in D_\J$,
any linear extension of $\mathcal{P}_{w_0, \J}$ is a shelling of the circuit triangulation of $P_\J$.
\end{prop}

\Cref{thm:main} follows naturally from \Cref{prop:shelling}.

% \begin{figure}
%     \centering
%     \begin{tikzpicture}[every node/.style={draw, circle, inner sep=2pt, scale=.8}]
%     \node at (0,0) (2413) {24135};
%     \node at (-2,2) (4213) {42135};
%     \node at (0,2) (3241) {32415};
%     \node at (2,2) (4132) {41325};
%     \node at (-2,4) (3421) {34215};
%     \draw[thick] (2413) -- (4213);
%     \draw[thick] (4213) -- (3421);
%     \draw[thick] (2413) -- (3241);
%     \draw[thick] (3241) -- (3421);
%     \draw[thick] (2413) -- (4132);
%     \end{tikzpicture}
%     \caption{We show the graph of the circuit triangulation of the positroid polytope associated with the Grassmann necklace $\J = (124, 234, 134, 145, 125)$. 
%     The bases of this positroid are $\{124,125,134,135,145,234,235,245\}$.
%     The vertices of $\Gamma_\J$ are labeled by $D_\J$.}
%     \label{fig:positroid24153}
% \end{figure}

\section{\texorpdfstring{The h*-polynomial of half-open connected positroid \\ polytopes}{The h*-polynomial of half-open connected positroid polytopes}}\label{sec:half-open}

In this section, we give a combinatorial formula for the $h^*$-polynomials of half-open connected positroid polytopes in terms of descents of permutations.
We then compute the $h^*$-polynomial of a whole closed polytope by inclusion-exclusion on its half-open subpolytopes of smaller dimension.
Our result generalizes \cite{NanLi} and \cite{AJR20}.

The facets of these $(w)$-simplices and positroid polytopes are all in the form $x_{[i,j)} = k$ for some $i, j \in [n]$ and $k \in \Z$. We will call a facet of a positroid polytope or $(w)$-simplex \emph{upper} if it is of the form $x_{[i,j)} = k$ such that the polytope satisfies $x_{[i,j)} \leq k$.

\begin{thm}\label{thm:half-open}
Let $P_\J$ be a connected positroid polytope, where $\J$ is the associated Grassmann necklace.
Consider the half-open positroid polytope $\tilde{P}_\J \subset [0,1)^{n-1}$ which is the projection of $P_\J$ onto the first $(n-1)$ coordinates with all upper facets removed.
Then the $h^*$-polynomial of $\tilde{P}_\J$ is equal to
$h^*(\tilde{P}_\J,z) = \sum_{w \in D_\J} z^{\des(w)+1}$.
\end{thm}

To compute the $h^*$-polynomial of a polytope from the $h^*$-polynomials of its facets and the half-open polytope with those facets removed, we use the inclusion-exclusion principle.
Let $P$ be a polytope and let $F_1, \dots, F_\ell$ be a collection of facets of $P$.
Consider the restriction of the face poset of $P$ to have coatoms $F_1, \dots, F_\ell$.
This poset $\mathcal{P}_{F_1, \dots, F_\ell}$ describes all the faces of $P$ in the intersections of $F_1, \dots, F_\ell$.
Let $\mu_{F_1, \dots, F_\ell}$ be the M\"obius function of this poset.

The next proposition follows from inclusion-exclusion on the face poset and additivity of Ehrhart polynomials.
% \begin{prop}\label{prop:from_half-open}
% Let $P$ be a polytope. 
% Let $F_1, \dots, F_\ell$ be a collection of facets of $P$, and 
% let $\tilde{P} = P \setminus (F_1 \cup \cdots \cup F_\ell)$.
% The $h^*$-polynomial of the polytope $P$ is equal to
% $$h^*(P,z) = h^*(\tilde{P},z) - \sum_{F \in \mathcal{P}_{F_1, \dots, F_\ell}(F), F \neq P} \mu_{F_1, \dots, F_\ell}(F,P) (1-z)^{\dim(P) - \dim(F)} h^*(F, z).$$
% \end{prop}

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.7]
    % Define the coordinates for the base of the pyramid
    \coordinate (A) at (0,0);
    \coordinate (B) at (4,0);
    \coordinate (C) at (4,2);
    \coordinate (D) at (0,2);

    % Define the coordinate for the apex of the pyramid
    \coordinate (Apex) at (2,5);

    % Draw the base of the pyramid
    \draw[thick] (A) -- (B) -- (C);
    \draw[thick] (C) -- (D) --(A);

    % Draw the edges from the apex to the base vertices
    \draw[thick] (Apex) -- (A);
    \draw[thick] (Apex) -- (B);
    \draw[thick] (Apex) -- (C);
    \draw[thick] (Apex) -- (D);

    % Label the base vertices
    \node[below left] at (A) {0110};
    \node[below right] at (B) {1010};
    \node[above right] at (C) {1001};
    \node[above left] at (D) {0101};

    \draw[fill=red!80,opacity=0.5] (Apex) -- (B) -- (C) -- cycle;
    \draw[fill=yellow!80,opacity=0.5] (Apex) -- (A) -- (D) -- cycle;
    \draw[fill=blue!80,opacity=0.5] (Apex) -- (A) -- (B) -- cycle;

    % Label the apex
    \node[above] at (Apex) {1100};
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.7]
    \node (P) at (2,7) {\small{\pyramid}};
    \node (F1) at (0,5)  {$\triangle$};
    \node (F3) at (2,5) {$\triangle$};
    \node (F2) at (4,5) {$\triangle$};
    \draw[thick] (P) -- (F1);
    \draw[thick] (P) -- (F2);
    \draw[thick] (P) -- (F3);
    \node (E1) at (1,3) {/};
    \node (E2) at (3,3) {$\backslash$};
    \draw[thick] (F1) -- (E1) -- (F3);
    \draw[thick] (F3) -- (E2) -- (F2);
    \node (Apex) at (2,1) {1100};
    \draw[thick] (E1) -- (Apex) -- (E2);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.7]
    \node (P) at (2,7) {1};
    \node (F1) at (0,5)  {-1};
    \node (F3) at (2,5) {-1};
    \node (F2) at (4,5) {-1};
    \draw[thick] (P) -- (F1);
    \draw[thick] (P) -- (F2);
    \draw[thick] (P) -- (F3);
    \node (E1) at (1,3) {1};
    \node (E2) at (3,3) {1};
    \draw[thick] (F1) -- (E1) -- (F3);
    \draw[thick] (F3) -- (E2) -- (F2);
    \node (Apex) at (2,1) {0};
    \draw[thick] (E1) -- (Apex) -- (E2);
    \end{tikzpicture}
        \caption{The positroid polytope associated to the Grassmann necklace $\J = (12,23,13,14)$ is a pyramid. The red facet corresponds to $F_1: x_1 = 1$; the yellow facet corresponds to $F_2: x_2 = 1$; the blue facet corresponds to $F_3: x_1+x_2+x_3 = 2$. These are all the upper facets of this positroid polytope.
        The poset $\mathcal{P}_{F_1,F_2,F_3}$ and the value of its M\"obius function $\mu_{F_1,F_2,F_3}(-,P_\J)$.}
    \label{fig:2413poset}
\end{figure}

\begin{ex}\label{exem:2413}
Consider the Grassmann necklace $\J = (12,23,13,14)$.
Then $D_\J$ consists of permutations in $S_4$ that end with 4 such that $\cdes_L(w|_{[3,4]}) \leq 1$ so $D_\J = \{1324, 2134\}$.
Now $\des(132)=\des(213) = 1$, so $h^*(\tilde{P}_\J,z) = 2z^2$.
To compute the $h^*$-polynomial of the whole positroid polytope $P$, which is a pyramid, we use inclusion-exclusion.
The upper facets we removed are $F_1: x_1 = 1, F_2: x_2 = 1, F_3: x_1+x_2+x_3 = 2$.
We depict the poset $\mathcal{P}_{F_1, F_2, F_3}$ and the value of its M\"obius function in \Cref{fig:2413poset}.
Therefore, by inclusion-exclusion, the $h^*$-polynomial of $P_\J$ is
$h^*(P_\J,z) = 2z^2 + 3(1-z) - 2(1-z)^2 = 1+z$.
\end{ex}

\section{Tree positroids}\label{sec:tree}
When the plabic graph of a positroid is acyclic, we call it a \emph{tree positroid}. 
In this section, we apply \Cref{thm:main} to the special case of a tree positroid.
To each plabic graph, one can associate a \emph{plabic tiling} \cite{plabictiling}.
Tree positroids are positroids whose plabic tilings are \emph{bicolored subdivision}.
We start with several defintions, following the conventions of \cite{parisi2024magic}.

\begin{definition}
Let $\P_n$ be a convex $n$-gon with vertices labeled from 1 to $n$ in clockwise order. 
A \emph{bicolored subdivision} $\tau$ is a partition of $\P_n$ into black and white polygons such that two polygons sharing an edge have different colors. 
We say that $\tau$ has \emph{type} $(k,n)$ if any triangulation of the black polygons consists of exactly $k$ black triangles.
\end{definition}

\begin{rem}
Given a Grassmann necklace $\J = (J_1,\dots,J_n)$, we can define a graph $G_\J$ on $[n]$ such that $\{i,j\}$ is an edge if and only if $|J_i \setminus J_j| = |J_j \setminus J_i| = 1$.
The positroid $P_\J$ associated with the Grassmann necklace $\J$ is a tree positroid if and only if the graph $G_\J$ is a subdivision of a convex $n$-gon into polygons by diagonals.
\end{rem}

The tree positroid polytopes are triangulated by $(w)$-simplices where $w$ extends a \emph{partial cyclic order} \cite{parisi2024magic}.

\begin{definition}\label{def:cyclic-order}
    A \emph{(partial) cyclic order} on a finite set $X$ is a ternary relation $C \subset \binom{X}{3}$ such that for all $a, b, c, d \in X$:
    \begin{align}
        (a,b,c) \in C &\implies (c, a, b) \in C \tag{cyclicity}\\
        (a,b,c) \in C &\implies (c, b, a) \notin C \tag{asymmetry}\\
        (a,b,c) \in C \text{ and }(a, c, d) \in C &\implies (a,b,d) \in C \tag{transitivity}
    \end{align}
    A cyclic order $C$ is \emph{total} if for all $a, b, c\in X$, either $(a,b,c)\in C$ or $(a, c, b) \in C$.
    A total cyclic order $C'$ is a \emph{circular extension} of $C$ if $C \subseteq C'$.
    The set of total cyclic orders on $[n]$ is in bijection with the set $D_n$ (see \Cref{Dk+1n}).
    We denote the set of all circular extensions of $C$ by $\Ext(C)$.
  \end{definition}

\begin{definition}
Let $x_1,\dots,x_m$ be a sequence of $m$ distinct elements of $[n]$ (for $3 \leq m \leq n$).
We let $C=C_{(x_1, x_2 \dots, x_m)}$ denote the partial cyclic order on $[n]$ in which 
for each triple $1\leq i < j < \ell \leq m$ 
        we have $(x_i,x_j, x_{\ell}) \in C$ (which implies by cyclicity that
        also $(x_j,x_{\ell}, x_i)$ and $(x_{\ell}, x_i, x_j)$ lie in $C$).  
We call this partial cyclic order a \emph{chain}.
\end{definition}

\begin{definition}\label{def:cyclic-from-perm-subdiv}
Let $\tau$ be a bicolored subdivision of $\mathbf{P}_n$ with $q$ polygons $P_1, \dots, P_q$ which are black or white.
If $P_a$ is white (respectively, black), we let $v_1,\dots,v_r$ denote its list of vertices read in clockwise (respectively, counterclockwise) order.  We then associate the chain $C_a = C_{(v_1,\dots,v_r)}$ to $P_a$.  Finally we define the \emph{$\tau$-order}
to be the partial cyclic order which is the union of the partial cyclic orders associated
to the black and white polygons: \\
    \centerline{$C_{\tau}:=C_1 \cup \dots \cup C_q.$}
\end{definition}

\begin{rem}
Not all cyclic orders have a circular extension \cite{Megiddo1976}, that is, 
$\Ext(C)$ could be empty. 
Moreover, the problem of determining
whether a cyclic order has a circular extension is NP-complete
\cite{Megiddo1976}, which implies that it is NP-complete to test if two partial cyclic order $C, C'$ has a common circular extension $\Ext(C \cup C')$, and it is in general hard to tell if two positroid polytopes intersect or not.
\end{rem}

\begin{prop}[{\cite[Corollary 4.8]{parisi2024magic}}]
Let $\sigma$ be a bicolored subdivision of type $(k,n)$. Let $\J_\sigma$ be the Grassmann necklace associated with the tree positroid of $\sigma$.
Then the positroid polytope associated with $\J_\sigma$ is a union of $(w)$-simplices for $(w)$ that cyclically extends $C_\sigma$:
$$P_{\J_\sigma} = \bigcup_{(w) \in \Ext(C_\sigma)} \Delta_{(w)}.$$
\end{prop}

\begin{cor}\label{cor:tree}
Let $\sigma$ be a bicolored subdivision of type $(k,n)$. Let $\J_\sigma$ be the Grassmann necklace associated with the tree positroid of $\sigma$. Then we have $\Ext(C_\sigma) = D_{\J_\sigma}$.
\end{cor}

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.8, dot/.style={circle,inner sep=1pt,fill,label={#1},name=#1},
  extended line/.style={shorten <=-#1},
  extended line/.default=1cm]
    % Define the radius of the pentagon
    \def\radius{2}
    
    % Draw the pentagon
    \foreach \i in {1,2,3,4,5} {
        \coordinate (P\i) at ({90 - 360/5 * (\i - 1)}:\radius);
    }
    
    % Draw the edges of the pentagon
    \foreach \i in {1,2,3,4,5} {
        \pgfmathtruncatemacro{\j}{mod(\i,5) + 1}
        \draw (P\i) -- (P\j);
    }

    % Draw the labels
    \foreach \i in {1,2,3,4,5} {
        \node at ({90 - 360/5 * (\i - 1)}: \radius + 0.5) {\i};
    }
    
    \draw[fill = black, opacity = 0.5] (P1) -- (P2) -- (P3) -- (P1);
    \draw[fill = black, opacity = 0.5] (P1) -- (P4) -- (P5) -- (P1);


    \node[inner sep=0pt, circle, fill=black, minimum size = 7pt] (b1) at (barycentric cs:P1=1,P2=1,P3=1) {};
    \node[inner sep=0pt, circle, fill=black, minimum size = 7pt] (b2) at (barycentric cs:P1=1,P4=1,P5=1) {};
    \node[inner sep=0pt, circle, draw = black, minimum size=7pt] (w) at (barycentric cs:P1=1,P3=1,P4=1) {};

    \def\radius{2.5}
    
    % Draw the pentagon
    \foreach \i in {1,2,3,4,5} {
        \coordinate (Q\i) at ({55-360/5 * (\i - 1)}:\radius);
    }
    \foreach \i in {1,2,3,4,5} {
        \node at ({55-360/5 * (\i - 1)}: \radius + 0.5) {\i};
    }

    \draw[thick] (Q1) -- (b1) -- (Q2);
    \draw[thick] (b1) -- (w) -- (b2);
    \draw[thick] (w) -- (Q3);
    \draw[thick] (Q5) -- (b2) -- (Q4);
\end{tikzpicture}
    \caption{The tree plabic graph and bicolored subdivision associated to the Grassmann necklace $\J = (124, 234, 134, 145, 125)$. We have that $C_\tau$ consists of the chains $(3,2,1), (1,3,4)$ and $(5,4,1)$.}
    \label{fig:tree24153}
\end{figure}

\section{Future work}
The \emph{polypositroid} is a \emph{polymatroid}, or equivalently, \emph{generalized permutohedron}, that is also alcoved \cite{polyposi}.
They are parametrized by \emph{Coxeter necklaces} and \emph{membranes}, as analogies to \emph{Grassmann necklaces} and \emph{plabic graphs}.
How much does the positroid results generalize to polypositroids?

Early gave a formula for the $h^*$-polynomial of any dilated hypersimplices in terms of the \emph{decorated ordered set partitions} \cite{early2017conjectures}. Is there a bijection between his formula and our shelling formula? Bullock and the author conjectured a bijection for $\Delta_{2,n}$ \cite{BJ24}.

Elias--Kim--Supina \cite{EKS} and Clarke--K\"olbl \cite{CK24} studied the equivariant Ehrhart $H^*$ of the hypersimplices and showed that they are related to the $S_n$-representation on the decorated ordered set partitions.
Ardila--Supina--Vindas-Mel\'endez and Ardila--Schindler--Vindas-Mel\'endez \cite{ASV20,ASV21} studied the 
equivariant Ehrhart theory of the regular permutohedron. Is there a relation between the equivariant 
Ehrhart $H^*$ of the permutohedron and decorated ordered set partitions?

\acknowledgements{We thank Lauren Williams for suggesting the problem and helpful conversations and comments on the manuscript. We thank Alex Postnikov, Alejandro Morales, Nick Early, Arvind Ayyer, Elisabeth Bullock, Colin Defant, Theo Douvropoulos, Johnny Gao, Grace O'Brien for helpful discussions.}

\printbibliography

\end{document}
