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


%additional newcommands
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{cor}{Corollary}
\newtheorem{conj}{Conjecture}
\newtheorem{slog}{Slogan}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{setup}{Setup}
\newtheorem{ques}{Question}
\newtheorem{ex}{Example}
\newtheorem{sit}{Situation}
\newtheorem{notn}{Notation}
\newtheorem{rem}{Remark}
\newtheorem{warn}{Warning}
%\numberwithin{equation}{section}


%additional defs
\def\0{\mathbf{0}}
\newcommand{\bba}{\mathbf{a}}
\newcommand{\bbb}{\mathbf{b}}
\newcommand{\bbd}{\mathbf{d}}
\newcommand{\bbc}{\mathbf{c}}
\newcommand{\bbe}{\mathbf{e}}
\newcommand{\bbf}{\mathbf{f}}
\newcommand{\bbg}{\mathbf{g}}
\newcommand{\bbh}{\mathbf{h}}
\newcommand{\bbi}{\mathbf{i}}
\newcommand{\bbj}{\mathbf{j}}
\newcommand{\bbl}{\mathbf{\ell}}
\newcommand{\bbm}{\mathbf{m}}
\newcommand{\bbt}{\mathbf{t}}
\newcommand{\bbu}{\mathbf{u}}
\newcommand{\bbv}{\mathbf{v}}
\newcommand{\bbw}{\mathbf{w}}
\newcommand{\bbx}{\mathbf{x}}
\newcommand{\bby}{\mathbf{y}}
\newcommand{\bbz}{\mathbf{z}}
\newcommand{\bbal}{\mathbf{\alpha}}
\newcommand{\bbbet}{\mathbf{\beta}}
\newcommand{\bbor}{\mathbf{ord}}

\newcommand{\des}{\mathrm{des}}
\newcommand{\asc}{\mathrm{asc}}
\newcommand{\od}{\mathrm{out}}
\newcommand{\innt}{\mathrm{int}}
\newcommand{\rnk}{\mathrm{rnk}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\vertx}{\mathrm{Vert}}
\newcommand{\cone}{\mathrm{co}}
\newcommand{\brnk}{\mathbf{rnk}}
\newcommand{\bod}{\mathbf{out}}
\newcommand{\rint}{\mathrm{rint}}
\newcommand{\tcone}{\mathrm{tcone}}
\newcommand{\spann}{\mathrm{span}}
\newcommand{\vol}{\mathrm{vol}}
\newcommand{\fcone}{\mathrm{fcone}}
\newcommand{\ncone}{\mathrm{ncone}}
\def\co{\operatorname{cone}}
\def\stellar{\operatorname{st}}
\def\trunc{\operatorname{tr}}
\newcommand{\perm}{\mathrm{Perm}}
\newcommand{\sep}{\mathrm{Sep}}
\newcommand{\adt}{\mathbf{Ad}(\bbt)}
\newcommand{\pfp}{\mathrm{PSep}}
\newcommand{\pf}{\mathrm{PF}}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\D}{\mathbb D}
\newcommand{\bH}{\mathbb H}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\U}{\mathbb U}
\newcommand\cov{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise0.0ex\hbox{$\cdot\mkern0.9mu$}\cr}}}
\def\P{\mathbb P}

\newcommand{\Algebra}{\mathcal{A}}
\newcommand{\scrF}{\mathscr{F}}
\newcommand{\scrG}{\mathscr{G}}
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calW}{\mathcal{W}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}
\newcommand{\rr}{\mathbb{R}}
\newcommand{\ssigma}{\Tilde{\sigma}}

\newcommand{\fS}{\mathfrak S}

% misc notations for this paper
\def\MD{\operatorname{MD}}
\def\bwp{\mathcal{SBP}}
\def\Pord{\mathrm{Pord}}

% operators

\newcommand\commentout[1]{}
\def\type{\operatorname{type}}

%% define your title in the usual way
\title[Faces of Parking Function Polytopes]{Faces of Parking Function 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[F. Liu and W. Thawinrak]{\texorpdfstring{Fu Liu\thanks{\href{mailto:fuliu@ucdavis.edu}{fuliu@ucdavis.edu}{Fu}.  Fu Liu was partially supported by NSF grant \#2153897-0.}\addressmark{1} 
\and Warut Thawinrak \thanks{\href{mailto:wthawinrak@ucdavis.edu}{wthawinrak@ucdavis.edu}.  Warut Thawinrak was partially supported by NSF grant \#2153897-0.}\addressmark{1}}{Fu Liu 
and Warut Thawinrak }}

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

%% put the date of submission here
\received{November 14, 2024}

%% leave this blank until submitting a revised version
\revised{June 17, 2025}

%% 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 extended the notion of parking function polytopes and explored their normal fans, face posets, and $h$-polynomials. To capture their combinatorial properties, we introduced generalizations of ordered set partitions, which we refer to as binary partitions and skewed binary paritions. Using properties of preorder cones, we developed tools to characterize the family of skewed binary partitions that bijectively corresponds  to the normal fan of a parking function polytope. Additionally, we gave a formula for the $h$-polynomials of simple parking function polytopes in terms of generalized Eulerian polynomials.}

%% 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{parking function, polytope, normal fan, face poset, $h$-polynomial}

%% 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{sample.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}

Suppose that $\bbu \in \R^n$ is a vector satisfying $0 \leq u_1 \leq \cdots \leq u_n.$ Let $\bba = (a_1, \dots, a_n) \in \R^n_{\geq 0}$ and $b_1 \leq b_2 \leq \dots \leq b_n$ be the non-decreasing rearrangement of $a_1, \dots, a_n.$ We say that $\bba$ is a $\bbu$-\emph{parking function} if $b_i \leq u_i$ for all $i = 1, \dots, n.$ The \emph{parking function polytope} associated to $\bbu$, denoted by $\pf(\bbu)$, is defined to be the convex hull of all $\bbu$-parking functions. For non-triviality, we will always assume that $\bbu$ is a nonzero vector. Since $\mathbf{0}, (u_n,0, 0, \dots, 0), (0, u_n, 0, \dots, 0), \dots, (0, 0, \dots, 0, u_n)$ are $n+1$ affinely independent points in $\pf(\bbu),$ the polytope $\pf(\bbu)$ is $n$-dimensional for all $\bbu\neq\0.$
\begin{center}
    \begin{figure}[ht]
        \centering
        \includegraphics[scale = 0.2]{Pf.png}
        \caption{Three examples of parking function polytopes}
        \label{fig:enter-label}
    \end{figure}
\end{center}

We note that a parking function (of length $n$) was originally defined as a sequence of positive integers $(a_1, \dots, a_n)$ such that its non-decreasing rearrangement $b_1 \leq \cdots \leq b_n$ satisfies $b_i \leq i$ for all $i \in [n].$ It is a fascinating combinatorial object closely connected to other combinatorial models such as labeled trees \cite{Chassaing2001}, hyperplane arrangement, and non-crossing partitions \cite{Stanley1997, Stanley1998}. The name "parking function" originates from Konheim and Weiss \cite{Konheim1966AnOD}, who introduced it as a way to choose $n$ spots for parking $n$ cars. Stanley later defined parking function polytopes to be the convex hull of all such parking functions in \cite[Problem 12191]{stanley2020question}, which corresponds, in our notation, to $\pf(0, 1, \dots, n-1)$. He also posed questions regarding their faces, volume, and number of lattice points, which were subsequently studied by Amanbayeva and Wang \cite{Amanbayeva_2021}. Recently, Hanada, et al. \cite{hanada2024}, and Bayer, et al. \cite{bayer2024parkingfunctionpolytopes} examined a bigger class of parking function polytopes $\pf(\bbu)$ where $u_1, \dots, u_n$ are integers satisfying $0 \leq u_1 < \dots < u_n$. Their work focused on the combinatorial properties of these polytopes, providing formulas for volume and  $h$-polynomials, and exploring connections to other polytopes. One sees that our definition of parking function polytopes further generalizes this notion by allowing $0 \leq u_1 \le \dots \le u_n$ to be any non-decreasing real numbers, rather than strictly increasing integers. This expands the family of parking function polytopes to include more combinatorial types. To understand their face structure, we introduced skewed binary partitions to describe their normal fans, thereby revealing that the combinatorial types are determined entirely by their multiplicity vectors. Furthermore, we provide a formula for the $h$-polynomials of simple parking function polytopes in terms of generalized Eulerian polynomials.

\textbf{Connection to other polytopes}:
Let $\fS_n(\bbu) := \conv(\tau(\bbu)\,|\, \tau \text{ is a permutation in } \fS_n)$ be the $\fS_n$-permutohedron generated by $\bbu,$ where $\tau(\bbu) := (u_{\tau(1)}, \dots,u_{\tau(n)})$. The parking function polytope $\pf(\bbu)$ can equivalently be defined as 
\[\pf(\bbu) := \{\bbx \in \R^n_{\geq 0}\, |\, \exists\, \bbw \in \fS_n(\bbu) \text{ such that } \bbw - \bbx \in \R^n_{\geq 0}\} = (\R^n_{\leq 0} + \fS_n(\bbu))\cap \R^n_{\geq 0}.\]
This description allows us to see that every $\pf(\bbu)$ is a polymatroid introduced by Edmonds in \cite{edmonds1970}. Thus, by the construction of polymatroid, we have that $\pf(\bbu)$ consists of all $(x_1, \dots, x_n)$ satisfying $x_i \geq 0$ for all $i \in [n]$ and for every nonempty subset $I \subseteq [n]$
    \[\sum_{i \in I}x_i \leq \sum^{|I|-1}_{i = 0} u_{n-i}.\]


When $\bbu = (1,2, \dots, n)$ or any strictly increasing sequence of positive real numbers, the polytope $\pf(\bbu)$ becomes a stellahedron, which is the graph associahedron of a star graph originally introduced by Carr and Devadoss \cite{carr2005coxetercomplexes}. It follows from \Cref{cor: combinatorialType} and \Cref{prop: type-characterization} that the normal fan of every parking function polytope $\pf(\bbu)$ is a coarsening of the normal fan of $\pf(1, 2, \dots, n)$, meaning $\pf(\bbu)$ can be viewed as a deformation of $\pf(1, 2, \dots, n)$. 
Recent work by Eur, Huh, and Larson \cite{EurHuhLar2023} leverages the geometry of the stellahedral toric variety to study matroids and explore the connections between deformations of $\pf(1, 2, \dots, n)$ and polymatroids.

Moreover, each $\pf(\bbu)$ is a signed (type-$B$) generalized permutohedra (see \cite{Euretall2024}) and can be viewed as a projection of a generalized permutohedra. Thus, properties of these generalized permutohedra apply to parking function polytopes as well. In particular, one can compute the volume and the Ehrhart polynomials of parking function polytopes using existing formulas for generalized permutohedra. Due to space constraints, we will omit further discussion of generalized permutohedra in this extended abstract.

\textbf{Paper organization}: In this extended abstract, we aim to describe the normal fans, face posets, and $h$-polynomials of parking function polytopes, and present related findings. We begin with an overview of fundamental concepts related to polyhedra, preposets, and preorder cones, introducing binary partitions and skewed binary partitions to describe the normal fans of these polytopes. Following this, we develop tools to characterize the family of skewed binary partitions that corresponds bijectively to the normal fan of a parking function polytope, and express the $h$-polynomials of simple parking function polytopes in terms of generalized Eulerian polynomials.

\section{Preliminaries}

\subsection{Polyhedra}

A \emph{polyhedron} $P$ in $\R^d$ is the solution to a finite set of linear inequalities. A subset $F$ of $P$ is said to be a \emph{face} of $P$ if there exists $\bbh \in \R^d$ such that
\[F = \{\bbx \in P\,|\, \bbh\cdot \bbx \geq \bbh\cdot \bby, \text{ for all } \bby \in P\}.\] 
  A face of dimension $\dim(P) - 1$ is called a \emph{facet}, a face of dimension $1$ is called an \emph{edge}, and a face of dimension zero is called a \emph{vertex}. The partially ordered set $\calF(P)$ of all nonempty faces of $P$ ordered by inclusion is called the \emph{face poset} of $P$.
  
A \emph{cone} is a polyhedron defined by a system of linear inequalities of the form $\bba\cdot \bbx \leq 0$. Let $F$ be a nonempty face of $P$. The \emph{normal cone} of $P$ at $F$ is the set
\[\ncone(F,P) := \{\bbw \in \R^d \,|\, \bbw\cdot \bbx \geq \bbw \cdot \bby \text{ for all } \bbx \in F \text{ and all } \bby \in P\},\]
that is, $\ncone(F,P)$ is the set of all $\bbw \in \R^d$ such that $\bbw \cdot \bbx$ attains maximum value at $F$ over all points in $P$. The \emph{normal fan} of $P$, denoted by $\Sigma(P)$, is the set of normal cones of $P$ at all of its nonempty faces. 

A bounded polyhedron is called a \emph{polytope} and can alternatively be defined as a convex hull of finitely many points in $\R^d$. A $d$-dimensional polytope is said to be \emph{simple} if all its vertices are incident to exactly $d$ edges. For a $d$-dimensional simple polytope $P$, we let $f_i(P)$ be the number of its $i$-dimensional faces and define its \emph{$f$-polynomial} to be $f_P(t):= f_0(P) +f_1(P)t +\dots + f_d(P)t^d$. The \emph{$h$-polynomial} and the \emph{$h$-vector} of $P$ are then defined to be $h_P(t) = h_0(P) + h_1(P)t\cdots + h_d(P)t^d$ and $(h_0(P), \dots, h_d(P))$, respectively, satisfying the relation $f_P(t) = h_P(t+1)$.

\subsection{Preposets and preorder cones}
%    We introduce preposets, which is in a sense a generalization of posets, and their associated preorder cones. 
We assume readers are familiar with basic poset notations, as presented, for example, in \cite[Section 3.1]{Stanley2011EC1}. 
Here, we introduce a generalized concept: "preposet".
    
    
A binary operator $\preceq$ on a finite set $A$ is called a \emph{preorder} if it is reflexive and transitive on $A$. A \emph{preposet} is an ordered pair $(A,\preceq)$ of a finite set $A$ and a preorder $\preceq$ on it. We write $i \equiv j$ if $i \preceq j$ and $j \preceq i$. Thus, the relation $\equiv$ is an equivalence relation on $A$ and partitions $A$ into equivalence classes. We denote by $A/_\equiv$ the set of equivalence classes of $A$ and $\Bar{i}$ the equivalence class of $i$. One sees we recover the definition of a poset if we require a preposet $(A, \preceq)$ to satisfy $i \equiv j$ if and only if $i = j$, i.e. the relation $\equiv$ is antisymmetric. 

Note that the preorder $\preceq$ on $A$ induces a partial order on $A/_\equiv$ by letting $\Bar{i} \preceq \Bar{j}$ if $i \preceq j$ in $A$, and thus defines a poset $(A/_\equiv, \preceq)$.
%which is closely related to the preposet $(A, \preceq)$. This allows us to define concepts for the preposet $(A, \preceq)$ from concepts for the poset $(A/_\equiv, \preceq)$:
We say that $i$ is a \emph{cover} of $j$ in the preposet $(A, \preceq)$, denoted $i \lessdot j$, if $\Bar{i}$ is a cover of $\Bar{j}$ in the poset $(A/_\equiv, \preceq).$ 
The \emph{Hasse diagram} of a preposet $(A, \preceq)$ is the Hasse diagram of the poset $(A/_\equiv,\preceq)$ except that, when labeling each node by equivalence classes $\Bar{i}$, we remove the parentheses around the set. A preoder $\preceq_1$ is said to be a \emph{contraction} of another preorder $\preceq_2$ if the Hasse diagram of $(A, \preceq_1)$ can be obtained by a sequence of edge contractions of the Hasse diagram of $(A, \preceq_2)$. 



\begin{ex}
\Cref{fig:preposets} displays the Hasse diagrams of three different preposets on $[0,8]$, among which the preposet on the left is a poset. The preorder on the right is a contraction of the preorder in the middle (by contracting the edge $0$---$7$). 
\end{ex}

\begin{figure}
    \centering
    \includegraphics[scale=0.26]{3porders.png}
    \caption{Hasse diagrams of three preorders on \texorpdfstring{$[0,8]$}{[0,8]}}
    \label{fig:preposets}
\end{figure}

In \cite[Section 3]{Postnikov2006}, Postnikov, Reiner, and Williams introduced a natural correspondence between certain cones in the quotient space $\R^n/(1, \dots, 1)\R$ and preorders of the set $[n]$ in their study of faces of generalized permutahedra. Later, Castillo and the first author \cite{CastilloFu2023permutoassociahedron} called these cones \emph{preorder cones}, indicating that they arise from some preposets. In this paper, we will start with a preposet on $[0,n]$ and consider preorder cones without quotienting out $(1,\dots,1)\R$. More precisely, given a preposet $([0,n],\preceq)$, we define its associated \emph{preorder cone} to be the cone $\sigma_\preceq := \{(c_0,c_1, \dots, c_n) \in \R^{n+1}  \ | \ c_i \le c_j \text{ if } i \preceq j, \text{ for } i,j \in [0,n]\}.$ We will use preorder cones to describe the normal fans of parking function polytopes. However, it turns out that the slice of $\sigma_\preceq$ at $c_0 = 0$ will mostly play an important role. This leads us to introduce the following definition. 

\begin{defn}\label{defn:preordcone}
    Let $\preceq$ be a preorder on $[0,n]$. The \emph{sliced preorder cone} $\ssigma_\preceq$ associated to $\preceq$ is given by
  %  \begin{align}\label{eq:preordcone}
    $\ssigma_\preceq := \{(c_1, \dots, c_n) \in \R^{n}  \ | \ c_0 = 0 \text{ and } c_i \le c_j \text{ if } i \preceq j, \text{ for } i,j \in [0,n]\}.$
   % \end{align}
\end{defn}

\begin{ex}\label{ex:preorder-cone}
Let $\preceq$ be the preorder in the middle of \Cref{fig:preposets}. Then
\[    \ssigma_{\preceq} = \{(c_1, \dots, c_8) \in \R^{8}  \ | \ 0, c_2, c_5 \leq  c_6, c_7 \leq c_1 = c_3 = c_4 = c_8\}.
  \]
\end{ex}


\section{Binary partition and contraction}
In this section, we consider a special family of preorders on $[0,n]$ that can be represented by what we call \emph{binary partitions} of $[0,n]$. We will then characterize the contractions of these preorders in terms of binary partitions. In the next section, we will consider special cases of these partitions that will be useful for describing the normal cones of parking function polytopes.

Recall that an ordered partition of a nonempty set $S$ is a tuple $\calB=(B_1, \dots, B_k)$ of nonempty disjoint subsets of $S$ such that $B_1 \sqcup \cdots \sqcup B_k = S.$ Each subset $B_i$ is called a \emph{block}. To represent preorders on $[0,n]$, we introduce an analogue of ordered partition called "binary partition" of the set $S = [0,n]$ by separating blocks into two different kinds: \emph{homogeneous}, and \emph{non-homogeneous}. We will differentiate homogeneous block by adding $\star$ as a superscript to the set. E.g., $\{1, 3\}^\star$ is a homogeneous block. We can apply set-operations, such as union and intersection, to homogeneous and non-homogeneous blocks as we normally do to usual sets. Thus, readers should think of being homogeneous (resp. non-homogeneous) simply as a way of labeling blocks.


\begin{defn}\label{defn: partition} Let $k \in \P.$ A \emph{binary partition} of $[0,n]$ into $k$ blocks is an ordered tuple $(B_1, \dots, B_k)$ of nonempty disjoint subsets of $[0,n]$ such that $B_1 \sqcup \cdots \sqcup B_k = [0,n]$ and satisfies the following additional properties.
\begin{enumerate}
    \item Every block is either homogeneous or non-homogeneous.
    \item Every singleton block is non-homogeneous.
\end{enumerate}
\end{defn}

\begin{defn}\label{defn: preord-partition}
For each binary partition $\calB = (B_1, \dots, B_k)$ of $[0,n]$, we associate the preorder $\preceq_\calB$ on the set $[0,n]$ by letting
\begin{align*}
    p &\preceq_\calB  q & &\text{ if } p \in B_i \text{ and } q \in B_j \text{ and } i < j\\
    p &\equiv_\calB q & &\text{ if $p, q \in B_i$ for some homogeneous block $B_i$. }    
\end{align*}
We also say that a binary partition $\calC$ is a contraction of another binary partition $\calB$, denoted by $\calC \leq \calB$, if $\preceq_\calC$ is a contraction of $\preceq_\calB.$
\end{defn}

\begin{ex}\label{ex:binarypartition}
$\calB = (\{0,2,5\},\{6,7\}, \{1,3,4,8\}^\star)$ and $\calC = (\{2,5\}, \{0,7\}^\star, \{6\}, \{1,3,4,8\}^\star)$ are two binary partitions of $[0,8]$ for which $\preceq_\calB$ and $\preceq_\calC$ are the preorders in the middle and on the right, respectively, of \Cref{fig:preposets}.
\end{ex}


For two binary partitions $\calB = (B_1,\dots, B_p)$ and $\calC= (C_1, \dots, C_q)$ of $[0,n]$, we associate the bipatite graph $G(\calB,\calC)$ in the following way: the blocks in $\calB$ are vertices on the left and the blocks in $\calC$ are vertices on the right. A left vertex $B_i$ is adjacent to a right vertex $C_j$ if $B_i\cap C_j \neq \emptyset$. A vertex of $G(\calB,\calC)$ is \emph{non-homogeneous} (resp. \emph{homogeneous}) if it corresponds to a non-homogeneous (resp. \emph{homogeneous}) block. Additionally, we say that $G(\calB,\calC)$ is \emph{non-crossing} if its edges do not cross.

\begin{ex}\label{ex:bipatite}
Let $\calA = (\{0,2\}, \{3,4\}^\star, \{1,5,6,7\},\{8\})$, $\calB = (\{0,2,5\},\{6,7\}, \{1,3,4,8\}^*)$, and $\calC = (\{2,5\}, \{0,7\}^\star, \{6\}, \{1,3,4,8\}^\star)$ be three binary partitions of $[0,8]$. Then, as shown in \Cref{fig:bipatites}, one sees that $G(\calA, \calB)$ is crossing while $G(\calB, \calC)$ is non-crossing .

\begin{figure}
    \centering
    \includegraphics[scale=1]{Bipatites.pdf}
    \caption{\texorpdfstring{$G(\calA, \calB)$}{G(A,B)} is crossing while \texorpdfstring{$G(\calB, \calC)$}{G(B,C)} is non-crossing}
    \label{fig:bipatites}
\end{figure}
\end{ex}

By applying a characterization of preorder contractions given by Postnikov, Reiner, and Williams \cite[Proposition 3.5]{Postnikov2006}, we obtain a description of binary partition contractions in terms of their corresponding sliced preorder cones, as stated in the next lemma.

\begin{lem}\label{lem: binaryPartitionContraction}
    Let $\calB$ be a binary partition of $[0,n]$. Then a set $F$ is a face of the sliced preorder cone $\ssigma_\calB:= \ssigma_{\preceq_\calB}$ if and only if $F = \ssigma_\calC$ for some binary partition $\calC$ that is a contraction of $\calB.$
\end{lem}

The next theorem gives another characterization of binary partition contractions in terms of bipartite graphs.

\begin{thm}\label{thm: graph-characterization}
    We have that $\calC \leq \calB$ if and only if $G(\calB,\calC)$ satisfies all of the following conditions.
\begin{enumerate}[label=(\arabic*)]
    \item \label{itm: noncrossing} It is a non-crossing bipatite graph.  
    \item \label{itm: left-nonhomog2} Every left non-homogeneous vertex is adjacent to at most one non-homogeneous vertex.
    \item \label{itm: right-nonhomog2} Every right non-homogeneous vertex has degree one and is adjacent to a non-homogeneous vertex.
    \item \label{itm: left-homog2} Every left homogeneous vertex has degree one and is adjacent to a homogeneous vertex.
    \item \label{itm: right-homog2} If a right homogeneous vertex has degree one, then it is adjacent to a homogeneous vertex.
\end{enumerate}
\end{thm}


\section{Skewed binary partition and composition}

We now introduce "skewed binary partition" which is a special case of binary partition, and "skewed binary composition". We will later use them to describe the normal cones of parking function polytopes. Similarly to how a composition records the sizes of blocks in an ordered partition, a skewed binary composition will be used for storing information of the blocks of a skewed binary partition. We begin by describing the skewed binary composition notation. First, the entries of our composition are nonzero integers (as opposed to being positive integers). Additionally, we allow two different variations of entries: $i^\circ$ and $i^\star$. We consider these two variations to have the same numerical values as $i,$ and use the absolute value sign to take their numerical values. Hence, $|i^\circ| = |i^\star| = i= |i|.$ 

For convenience, we let $\N^\circ := \{ i^\circ \ | \ i \in \N\}$,
$\P := \N_{>0}$ and $\P_{\ge 2}^\star :=\{ i^\star \ | \ i \in \P, i \ge 2\}.$

\begin{defn}
Let $n \in \P$ and $k \in \N.$ A \emph{skewed binary composition} of $n$ into $k+2$ parts is an ordered tuple $\bbb = (b_{-1}, b_0, b_1, \dots, b_k)$ %$ \in \N \times (\N^\circ \cup \{0\})\times (\P \cup \P^\star)$ 
such that $\sum^k_{i = -1} |b_i| = n$ and satisfy
\begin{align*}
    (b_{-1}, b_0) \in & \ (\N \times \N^\circ) \cup (\P \times \{0\}) \text{ and } b_i \in \P \cup \P_{\ge 2}^\star \text{ for all } 1 \le i \le k.
\end{align*}
\end{defn}

\begin{defn}\label{defn:bwp}
    Let $n \in \P$ and $k \in \N.$ An \emph{(ordered) skewed binary partition} of $[0,n]$ into $k+2$ blocks is an ordered tuple $(B_{-1}, B_0, \dots, B_k)$ of disjoint subsets of $[0,n]$ such that \linebreak $B_{-1}\sqcup B_0 \sqcup B_1 \sqcup \cdots \sqcup B_k = [0,n]$ satisfying the following conditions:
    \begin{enumerate}
    \item\label{itm:firsttwo} $B_0$ is homogeneous, provided $|B_{0}| \geq 2$, and $B_{-1}$ is non-homogeneous.
    \item\label{itm:zerobelong} $0 \in B_{-1}$ or $ 0 \in B_0$. If $0 \in B_{-1}$, then $B_{-1}$ contains at least another element and $B_0 = \emptyset$. Hence, if $ 0 \in B_{-1},$ then $|B_{-1}| \geq 2$ and $|B_0| = 0.$ 
    \item \label{itm:singleton} For each $0 \le i \le k$, if $B_i$ is a singleton, then it is non-homogeneous.
    \item $B_i \neq \emptyset$ for all $1 \le i \leq k.$
    \end{enumerate}
%blocks is either homogeneous or non-homogeneous (not both).  
\end{defn}

See the first column of Table \ref{tab:ex-BWP} for examples of skewed binary partitions of $[0,8]$. Comparing \Cref{defn:bwp} to \Cref{defn: partition}, one sees that a skewed binary partition is simply a binary partition with extra requirements (conditions \ref{itm:firsttwo}. and \ref{itm:zerobelong}.).  In fact, removing empty blocks from a skewed binary partition yields a binary partition. For instance, removing the empty block from the skewed binary partition shown at the top of Table \ref{tab:ex-BWP} gives a binary partition in \Cref{ex:binarypartition}. Thus, properties of binary partitions extend naturally to skewed binary partitions when regarded in this way.

\begin{defn}
For a skewed binary partition $\calB$ of $[0,n]$, let $\hat{\calB}$ be the binary partition obtained by removing the empty blocks from $\calB.$ We define the associate preorder $\preceq_\calB$ on the set $[0,n]$ to be the preorder $\preceq_{\hat{\calB}}.$ We also say that a skewed binary partition $\calC$ is a contraction of another skewed binary partition $\calB$ if $\preceq_\calC$ is a contraction of $\preceq_\calB.$
\end{defn}

One notices that we also include a column of "$\type(\calB)$" on the right of Table \ref{tab:ex-BWP}. We introduce this concept in the definition below.

\begin{table}
\centering
\begin{tabular}{r|l}
skewed binary partition $\calB$  & $\type(\calB)$   \\ \hline 
$(\{0,2,5\}, \emptyset, \{6,7\},\{1,3,4,8\}^\star)$ &  $(2, 0, 2, 4^\star)$ \\ \hline
$(\{2,5\}, \{0,7\}^\star, \{6\},\{1,3,4,8\}^\star)$ &  $(2, 1^\circ, 1, 4^\star)$ \\ \hline
$(\{1,3,4,5,8\}, \{0\}, \{2\}, \{6,7\})$ &  $(5, 0^\circ, 1,2)$ \\ \hline
$(\emptyset, \{0\}, \{2,3,8\}, \{1,6,7\}^\star,\{4,5\})$ &  $(0, 0^\circ, 3,3^\star,2)$ \\ \hline
$(\{5,7\}, \{0,1,3\}^\star, \{2,4\}^\star, \{6,8\}^\star)$ & $(2, 2^\circ, 2^\star, 2^\star)$\\ \hline
$(\emptyset, \{0,1,2,3,4,5,6,7,8\}^\star)$ &  $(0, 8^\circ)$
\end{tabular}
\caption{Examples of skewed binary partitions of \texorpdfstring{$[0,8]$}{[0,8]} and their types}
\label{tab:ex-BWP}
\end{table}

\begin{defn}\label{defn:type}
Let $\calB= (B_{-1}, B_0, \dots, B_k)$ be a skewed binary partition of $[0,n]$. We associate a skewed binary composition $\bbb =(b_{-1}, b_0, \dots, b_k)$ of $n$ to $\calB$ as followings:
\begin{enumerate}
    \item For $1 \le i \le k$, let $b_i = |B_i|$ if $B_i$ is non-homogeneous, and $b_i = |B_i|^\star$ if $B_i$ is homogenous.
    \item If $0 \in B_0$, then let $b_0 = h^\circ$, where $h = |B_0|-1$, and let $b_{-1} = |B_{-1}|.$
    \item If $0 \in B_{-1}$, then let $b_0 = |B_0| = 0$ and let $b_{-1} = |B_{-1}|-1.$
\end{enumerate}
We say that this vector $\bbb$ is the \emph{type} of $\calB$ and denote it by $\type(\calB)$.
\end{defn}



\begin{prop}\label{prop: dim-preordcone}
Suppose that $\calB = (B_{-1}, B_0, B_1, \dots, B_k)$ is a skewed binary partitions of $[0,n]$
with $\type(\calB) = (b_{-1}, b_0, \dots, b_k)$. Then the co-dimension of $\ssigma_\calB$ (with respect to the space $\R^n$) is
    \[|b_0| + \sum_{b_i \in \P_{\ge 2}^\star}(|b_i|-1).\]
\end{prop}


\section{Face Structure}

\subsection{Face Poset and Normal Fan}

It is well-known that, for every polytope $P$, the dual poset of $\calF(P)$ is isomorphic to the poset $\calF(\Sigma(P)).$ Therefore, rather than describing the face poset of parking function polytopes, we can alternatively describe their normal fans. It turns out that these fans only depend on the \emph{multiplicity vector} of $\bbu.$

\begin{defn}\label{defn:multiplicity}
Suppose that there are $\ell$ positive integers appearing in $\bbu$: $d_1 < d_2< \cdots < d_\ell.$ We define $m_0(\bbu)$ to be the number of $0$'s in $\bbu$, and $m_i(\bbu)$ be the number of $d_i$'s in $\bbu$ for each $1 \le i \le \ell$. The \emph{multiplicity vector} and the \emph{data vector} of $\bbu$ are defined respectively to be $\bbm(\bbu)=(m_0(\bbu), m_1(\bbu), \dots, m_\ell(\bbu))$ and $\bbd(\bbu)=(d_1, d_2, \dots, d_\ell).$ We refer to $(\bbm, \bbd)$ as the \emph{MD pair} for $\bbu$.
\end{defn}

For example, if $\bbu=(0,0,4,4,4,6,8,8)$, then $\bbm(\bbu)=(2,3,1,2)$ and $\bbd(\bbu)=(4,6,8).$ With the notion of MD pair, we now can interchangeably write $\pf(\bbu)$ as $\pf(\bbm, \bbd).$

\begin{defn}\label{def: vertex-type}
    Suppose $\bbm = (m_0, m_1, \dots, m_\ell)$ is a multiplicity vector of a vector in $\R^n$. Let $r=n-m_0= m_1 + \cdots m_\ell$. We let $\bbb_0, \dots, \bbb_r$ be the following $r+1$ skewed binary compositions of $n$:
\begin{enumerate}
    \item We let \begin{align*}
        \bbb_0 := \begin{cases}
            (m_0, 0, m_1, \dots, m_\ell) &\text{ if } m_0 > 0\\
            (0, 0^\circ, m_1, \dots, m_\ell) &\text{ if } m_0 = 0
        \end{cases}.
    \end{align*}
    \item Suppose $1 \le k \le r$. Let $j$ be the unique integer in which $m_1 + \cdots + m_{j-1} < k \leq m_1 + \cdots + m_j.$ We define $\bbb_k := (m_0 + k, 0^\circ, m_1 + \cdots + m_j - k, m_{j+1}, \dots, m_\ell).$
\end{enumerate}
We denote by $\Omega_{\bbm}$ the set of these $r+1$ skewed binary compositions of $n$.
\end{defn} 

\begin{ex}
Let $\bbm=(2, 3, 1, 2)$ and $\bbm'= (0, 3, 5)$ be two multiplicity vectors of vectors in $\R^8$. Then $\Omega_\bbm = \{(2, 0, 3, 1, 2), (3, 0^\circ,2,1,2), (4, 0^\circ ,1,1,2), (5,0^\circ,1,2), (6,0^\circ,2),$ $ (7,0^\circ,1), (8,0^\circ)\}$ and $\Omega_{\bbm'} = \{(0, 0^\circ, 3,5), (1, 0^\circ, 2,5), (2, 0^\circ, 1, 5), (3, 0^\circ, 5), (4, 0^\circ, 4),$ \\$ (5, 0^\circ, 3), (6,0^\circ, 2), (7, 0^\circ, 1), (8, 0^\circ)\}.$
\end{ex}

It can be shown that $\bbv = (v_1, \dots, v_n)$ is a vertex of $\pf(\bbu)$ if and only if $\bbv$ is a permutation of a point of the form $(0,\dots, 0, u_{i+1}, \dots, u_n)$ for some $0 \leq i \leq n.$ The next theorem describes the normal cones at vertices of parking function polytopes.

\begin{thm}\label{thm: fulldimcones}
    Let $(\bbm, \bbd)$ be an MD pair. Then there is a bijection between the vertices of $\pf(\bbm,\bbd)$ and the skewed binary partitions in $\{\calB\,|\, \type(\calB) \in \Omega_\bbm\}$ such that if $\bbv_\calB$ is the vertex of $\pf(\bbm,\bbd)$ corresponding to the skewed binary partition $\calB$, then $\ncone(\bbv_\calB,\pf(\bbm,\bbd)) = \ssigma_\calB.$
\end{thm}

 Let $\calB = (B_{-1}, B_0, 
\dots, B_k)$ be a skewed binary partition whose type satisfies $\type(\calB) = (b_{-1}, b_0, \dots, b_k)$ $ \in \Omega_\bbm.$ Then the bijection in \Cref{thm: fulldimcones} maps $\calB$ to the vertex $\bbv_\calB = (v_1, \dots, v_n)$ that is the permutation of the point $(w_1, \dots, w_n)$ $ = (0,\dots, 0, u_{b_{-1}+1}, \dots, u_n)$ satisfying $v_i = w_t$ if $i \in B_j$ where $t = |b_{-1}| + \cdots + |b_{j}|.$


\Cref{thm: fulldimcones} also allows us to determine when $\pf(\bbm, \bbd)$ is a simple polytope.

\begin{cor}\label{cor: simple}
    Let $(\bbm, \bbd)$ be an MD pair where $\bbm = (m_0, m_1, \dots, m_\ell)$. Then $\pf(\bbm,\bbd)$ is simple if and only if either $\bbm = (0,n)$ or $(n-1, 1)$ or $m_1 = \cdots = m_{\ell-1} = 1$ for some $\ell \geq 2.$
\end{cor}

\begin{defn}
    Let $\bbm$ be a multiplicity vector. We define $\bwp(\bbm)$ to be the poset of all skewed binary partitions $\calB$ such that $\type(\calB) \in \Omega_\bbm$ and their contractions, ordered by contraction, i.e. $\calC, \calB \in \bwp(\bbm)$ satisfy $\calC \leq \calB$ if $\calC$ is a contraction of $\calB$.
\end{defn}

Applying \Cref{lem: binaryPartitionContraction} to skewed binary partitions, we obtain the following result as a consequence of \Cref{thm: fulldimcones}.

\begin{cor}\label{cor: combinatorialType}
    Let $(\bbm,\bbd)$ be an MD pair. Then the posets $\Sigma(\pf(\bbm,\bbd))$ and $\bwp(\bbm)$ are isomorphic. Moreover, If $F_\calB$ is the face of $\pf(\bbm,\bbd)$ in which $\ncone(F_\calB,\pf(\bbm,\bbd))$ corresponds to the skewed binary partition $\calB$, then $\ncone(F_\calB,\pf(\bbm,\bbd)) = \ssigma_\calB.$
\end{cor}

Thus, the combinatorial types of parking function polytopes depend solely on the multiplicity vector, i.e. two parking functions polytopes $\pf(\bbu_1)$ and $\pf(\bbu_2)$ have isomorphic face posets (hence normal fans) if $\bbm(\bbu_1) = \bbm(\bbu_2).$

Since $\Sigma(\pf(\bbm,\bbd))$ and $\bwp(\bbm)$ are isomorphic as posets, it is then natural to ask how can we describe all the skewed binary partitions $\calB$ in $\bwp(\bbm)$. Due to the symmetry of parking function polytope, we have that if $\calB$ corresponds to a normal cone in $\Sigma(\pf(\bbm,\bbd))$, then every skewed binary partition of the same type also corresponds to a normal cone in $\Sigma(\pf(\bbm,\bbd))$. Thus, we can describe these skewed binary partitions by their types. \Cref{thm: graph-characterization} allows us to characterize them, as stated in the next proposition.

\begin{prop}\label{prop: type-characterization}
    Suppose that $\bbm = (m_0, \dots, m_\ell)$ is a multiplicity vector of of a vector in $\R^n$, and $\calB$ is a skewed binary partition of $[0,n]$. Then $\calB$ is in $\bwp(\bbm)$ if and only if $\type(\calB) = (b_{-1}, b_0, \dots, b_p)$ is a skewed binary composition satisfying the following conditions.
    \begin{enumerate}[label=(\arabic*)]
        \item\label{itm: firsttwoblocks} $0 < |b_{-1}|+|b_0| \leq m_0$ if and only if $b_0 = 0$.
        \item\label{itm: positiveblocks} $m_0 < |b_{-1}| + |b_0| + |b_1|$ \footnote{If \texorpdfstring{$\calB = (B_{-1}, B_0)$}{condition 2}, then the inequality becomes \texorpdfstring{$m_0 < |b_{-1}| + |b_0|$}{new inequality}.} and for every positive integer $i \leq \ell$, there exists at most one positive integer $j$ such that
        \begin{align}
            \label{eq:partialsumcondition} 
            m_0 + \cdots + m_{i-1} \leq |b_{-1}| + \cdots + |b_{j-1}| < |b_{-1}| + \cdots + |b_{j}| \leq  m_0 + \cdots + m_{i}.
        \end{align}
        \item\label{itm: blocktypes} If $j$ is a positive integer such that there exists a positive integer $i$ satisfying \eqref{eq:partialsumcondition}, then $b_j \in \P.$ Otherwise, $b_j \in \P^\star$ for $1 \leq j \leq p.$
    \end{enumerate}
\end{prop}



\section{\texorpdfstring{$h$-vectors}{h-vectors}}

Given a poset $(Q,\leq_Q)$ where $Q \subset \N,$ we say that the ordered pair $(i,j)$ is a \textit{descent} of $(Q,\leq_Q)$ if $i \lessdot_Q j$ and $j < i$, and say that $(i,j)$ is an \textit{ascent} if $i \lessdot_Q j$ and $j > i$.

As noted in \Cref{cor: simple}, $\pf(\bbm, \bbd)$ is simple if and only if either $\bbm = (0,n)$ or $(n-1, 1)$ or $m_1 = \cdots = m_{\ell-1} = 1$ for some $\ell \geq 2.$ This implies that for every $\calB \in \Omega_\bbm$, the preorder $\leq_\calB$ is a poset and its Hasse diagram is a tree. We will denote the number of descents and ascents of the poset $([0,n], \leq_\calB)$ by $\des(\calB)$ and $\asc(\calB)$, respectively. The following lemma, which is a slight variation of \cite[Theorem 4.2]{Postnikov2006}, expresses the $h$-polynomials of simple parking function polytopes in terms of descents and ascents.

\begin{lem}\label{lem: hpoly-descents}
    If $\pf(\bbm, \bbd)$ is an $n$-dimensional simple polytope, then its $h$-polynomial equals $$h(t) = \sum_{\type(\calB) \in \Omega_\bbm}t^{\des(\calB)} = \sum_{\type(\calB) \in \Omega_\bbm}t^{\asc(\calB)}.$$
\end{lem}

For $p,q \in \N,$ let $T(p,q)$ be the poset on $[p+q]$ defined by the covering relations $j \lessdot j+1$ for all $j \in [p-1]$ and $p \lessdot k$ for all $k \in [p+1, q].$ Let $\fS_n(T(p,q)) := \{\sigma (T(p,q))\,|\, \sigma \in \fS_n\}$ be the set of all posets on $[p+q]$ having the same Hasse diagram as $T(p,q)$. 

\begin{defn}\label{def: genEulerianPolynomial}
    Given a poset $(T(p,q), \leq_T)$ on $[p+q]$, we define its \emph{generalized Eulerian polynomial} to be 
    \[A(T(p,q),t) := \sum_{T \in \fS_n(T(p,q))} t^{\des(T)} \]
    where $\des(T)$ is the number of descents of the poset $T.$
\end{defn}

The generalized Eulerian polynomial $A(T(p,q),t)$ has degree $p+q-1$ and is palindromic. The usual Eulerian polynomial $A_{p+1}(t)$ of degree $p$ is equal to $A(T(p,1),t)$.

Note that $\pf(0,n)$ is an $n$-cube and $\pf(n-1,1)$ is an $n$-simplex, and that their $h$-polynomials are known to be $(1+t)^n$ and $1+t + \cdots t^n$, respectively. The next theorem gives a formula for the $h$-polynomials of all other simple ones.

\begin{thm}\label{thm: h-polynomial} Let $(\bbm, \bbd)$ be an MD pair where $\bbm = (m_0, m_1, \dots, m_\ell)$ for some $\ell \geq 2.$ Suppose that $\pf(\bbm, \bbd)$ is $n$-dimensional and simple. Then its $h$-polynomial is given by 
    \begin{align*}\label{eq: h-explicit-thm}
    h(t) &=
        \begin{cases}
          \left(\sum^{m_\ell}_{j = 0}\binom{n}{j}t^j\right) + t\sum^{\ell - 1}_{i = 1}\binom{n}{i+m_\ell}A(T(i,m_\ell),t)  &\text{ if } m_0 = 0\\
         g(t) +  \left(\sum^{m_\ell}_{j = 0}\binom{n}{j}t^j\right) + t\sum^{\ell - 2}_{i = 1}\binom{n}{i+m_\ell}A(T(i,m_\ell),t)   &\text{ otherwise }
        \end{cases}
    \end{align*}
where $g(t)= \left[\sum^{z}_{i = 0}\binom{n}{i}\left(\sum^{n-i}_{j = i+1}t^j\right)\right] + \sum^{\ell - 2}_{i = 1}\binom{n}{i+m_\ell}\left(\sum^{n-i-m_\ell}_{j = 2}t^j\right)A(T(i,m_\ell),t),$ and $z = \min\left(m_\ell, n-m_\ell -1\right).$
\end{thm}

We can also express $A(T(p,q),t)$ in terms of Eulerian polynomials. This leads to the following result as a consequence of \Cref{thm: h-polynomial}.

\begin{cor}
Suppose that $\pf(\bbu)$ is $n$-dimensional and simple. Then its $h$-polynomial has the form $h(t) = r_0(t) + \sum^n_{k = 1}r_k(t)A_k(t)$ where $A_d(t)$ is the Eulerian polynomial of degree $d-1$ and $r_d(t)$ is a polynomial with nonnegative coefficients of degree $\leq n.$   
\end{cor}

For instance, the $h$-polynomials of $\pf(1, \dots, n)$ and $\pf(0, \dots, n-1)$ equal
\[1+ \sum^{n}_{k = 1}\binom{n}{k}t A_k(t) \text{ and } 1+ tA_n(t) + \sum^{n-2}_{k = 1}\binom{n}{k}t A_k(t), \text{ respectively}.\]

%\acknowledgements{}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\newpage
\printbibliography
\end{document}
