%% 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]{FPSAC2024}
\articlenumber{101}
%% 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}

%Packages:
\usepackage{enumitem}   %<--for nice lists in enumerate
\usepackage{stmaryrd } %<-- for [n] symbol
\usepackage{MnSymbol}  %<-- for cover relation symbol
\usepackage{paralist}  %<-- For compact lists

%Theorems and lemmas:
\newtheorem{Thm}{Theorem}[section]
\newtheorem{Lem}[Thm]{Lemma}
\newtheorem{Cor}[Thm]{Corollary}
\newtheorem{Prop}[Thm]{Proposition}
\theoremstyle{definition}
\newtheorem{Def}[Thm]{Definition}
\newtheorem{remark}[Thm]{Remark}
\newtheorem{Ex}[Thm]{Example}

\usepackage{lipsum}

%Rings, semirings, and fields:
\newcommand{\NN}{{\mathbb{N}}}
\newcommand{\ZZ}{{\mathbb{Z}}}
\newcommand{\QQ}{{\mathbb{Q}}}
\newcommand{\RR}{{\mathbb{R}}}
\newcommand{\CC}{{\mathbb{C}}}

%Extra definitions:
\newcommand{\set}[1]{\left\{ #1 \right\}}
\DeclareMathOperator\supp{supp}
\DeclareMathOperator\rev{rev}
\DeclareMathOperator\revcomp{revcomp}
\DeclareMathOperator\desc{desc}
\DeclareMathOperator\seq{seq}
\newcommand{\cover}{\leqslantdot}
\newcommand{\Flow}{\textbf{Flow}}
\newcommand{\nset}[1]{ [ #1 ]}

%In-text comments:
\newcommand{\wtd}[1]{ {\color{orange}{William: #1}}}
\newcommand{\ahm}[1]{ {\color{red}{Alejo: #1}}}

%% define your title in the usual way
\title[$f$-vectors of flow polytopes]{On the $f$-vectors of flow polytopes \\ for the complete graph}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{William T. Dugan\thanks{\href{wdugan@umass.edu}{wdugan@umass.edu}. This project was partially supported by NSF grants DMS-1855536 and DMS-2154019. }\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, University of Massachusetts Amherst, Amherst MA, 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{The Chan-Robbins-Yuen polytope ($CRY_n$) of order $n$ is a face of the Birkhoff polytope of doubly stochastic matrices that is also a flow polytope of the directed complete graph $K_{n+1}$ with netflow $(1,0,0, \ldots , 0, -1)$. The volume and lattice points of this polytope have been actively studied, however its face structure has received less attention. We give generating functions and explicit formulas for computing the $f$-vector by using Hille's (2003) result bijecting faces of a flow polytope to certain graphs, as well as Andresen-Kjeldsen's (1976) result that enumerates certain subgraphs of the directed complete graph. We extend our results to flow polytopes over the complete graph having arbitrary (non-negative) netflow vectors and recover the $f$-vector of the Tesler polytope of M\'esz\'aros--Morales--Rhoades (2017).}

%% 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{Chan-Robbins-Yuen polytope, flow polytopes, complete graphs, Fishburn matrices}

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

The Chan-Robbins-Yuen polytope ($CRY_n$) of order $n$ is defined as the convex hull of $n$ by $n$ permutation matrices $\pi$ for which $\pi_{i,j} = 0$ for $j \geq i+2$ \cite{Chan_Robbins_Yuen_2000}. This polytope has been the object of much interest in the research community, as it possesses many interesting traits. For example, Zeilberger proved in \cite{zeilberger_proof_1998} using a variation of the Morris constant term identity that $CRY_n$ has normalized volume equal to the product of the first $n-2$ Catalan numbers. A second algebraic proof was provided in \cite{Baldoni_Vernge_2001}, though a combinatorial proof of this fact remains elusive.  $CRY_n$ is also a face of the Birkhoff polytope of doubly stochastic matrices  having dimension $\binom{n}{2}$ and $2^{n-1}$ vertices \cite{Chan_Robbins_Yuen_2000}.

$CRY_n$ is also an example of a more general family of polytopes, namely those which are flow polytopes of the complete (transitively directed) graph $K_{n+1}$ on vertex set $\set{v_1, \ldots , v_{n+1}}$, which include the family of Tesler polytopes \cite{Tesler_polytopes_2015}. 

\begin{Def}
    For $n \in \NN$ and ${\bf a} \in \NN^n$, we denote the flow polytope $\mathcal{F}_{K_{n+1}}({\bf a}, -\sum_{i=1}^{n} a_i)$ as $\Flow_n({\bf a})$.  We will denote the $f$-vector of $\mathcal{F}_{K_{n+1}}({\bf a}, -\sum_{i=1}^{n} a_i)$ by $f^{(n)}({\bf a})$ or ($f^{(n)}({\bf a}; x)$ if written as a Laurent polynomial, where the coefficient of $x^i$ gives the number of $i$-dimensional faces for $i \geq -1$).
\end{Def}

In particular, $CRY_n$ is realized as an instance of $\Flow_n({\bf a})$ by setting ${\bf a} = (1, 0, \ldots , 0)$. $\Flow_n({\bf a})$ has also been  studied by M\'esz\'aros--Morales--Rhoades \cite{Tesler_polytopes_2015} in the context of \textbf{Tesler polytopes}, in which they show that the case of all $a_i > 0$, such as ${\bf a} = (1,1,\ldots, 1)$, is combinatorially equivalent to a product of simplices $\Delta_n \times \Delta_{n-1} \times \ldots \times \Delta_1$. This was later generalized to other graphs by M\'esz\'aros--Simpson--Wellner \cite{Meszaros2017FlowPO}. Part of the difficulty in obtaining the $f$-vector of $\Flow_n({\bf a})$ for more general ${\bf a}$ arises from the fact that $\Flow_n(1,1, \ldots, 1)$ is simple, whereas general instances of $\Flow_n({\bf a})$ (including the case of $CRY_n$) are not.

%In particular, $CRY_n$ is realized as an instance of $\Flow_n({\bf a})$ by setting ${\bf a} = (1, 0, \ldots , 0, -1)$. Other examples of $\Flow_n({\bf a})$ previously studied include the case that all $a_i > 0$ such as ${\bf a} = (1,1,\ldots, 1, -n)$, which is combinatorially equivalent to a product of simplices $\Delta_n \times \Delta_{n-1} \times \ldots \times \Delta_1$. This is originally due to M\'esz\'aros--Morales--Rhoades \cite{Tesler_polytopes_2015}, and later generalized to other graphs by M'esz'aros--Simpson--Wellner \cite{Meszaros2017FlowPO} obtained by setting ${\bf a} = (1,1, \ldots, 1, -n)$ \cite{Meszaros2017FlowPO}. Part of the difficulty in obtaining the $f$-vector of $\Flow_n({\bf a})$ outside of this special case is that $\Flow_n(1,1, \ldots, 1)$ is simple, whereas general instances of $\Flow_n({\bf a})$ (including the case of $CRY_n$) are not.

%$\Flow_n({\bf a})$ was previously studied by M\'esz\'aros--Morales--Rhoades \cite{Tesler_polytopes_2015}, in which they show that $\Flow_n({\bf a})$ is integrally equivalent to the \textbf{Tesler polytope} determined by the same vector ${\bf a}$, as well as characterize the faces of  $\Flow_n({\bf a})$ in terms of certain Tableaux \cite{Tesler_polytopes_2015}. To this end, we will refer to $\Flow_n({\bf a})$ as the Tesler polytope.  

In this manuscript, we give an explicit formula for the $f$-vector of $\Flow_n({\bf a})$ for any non-negative ${\bf a}$ as a sum over certain compositions. Namely, given a netflow vector ${\bf a}$, let $\revcomp({\bf a})$ be the composition obtained by reading the entries of ${\bf a}$ from right to left, inductively creating blocks whenever a new nonzero entry is encountered, and recording the tuple of sizes coming from the list of blocks (see Example~\ref{ex::revcomp_ex}). Furthermore, let $\succeq$ be the partial order of refinement on compositions, and let $\ell(\alpha)$ be the number of parts of composition $\alpha$. 

\begin{Thm} 
\label{thm::main_result}
Given a netflow vector $({\bf a}, -\sum_{i = 1}^n a_i) = (a_1, \ldots a_n, -\sum_{i = 1}^n a_i)$ with $a_i \in \mathbb{N}$, let $\alpha$ be the integer composition of $n$ given by $\alpha = \revcomp({\bf a})$. Then the $f$-vector Laurent polynomial of $\Flow_n({\bf a})$ is given by:
     % \begin{equation}
     %     f({\bf a}; x) = \frac{1}{x} + \frac{1}{x^n}\sum_{\beta \succeq \alpha}  (-1)^{\ell(\beta) - \ell(\alpha)} x^{\ell(\beta)}[\ell(\beta)]_{x+1}! \cdot {\bf x}^{\beta-{\bf 1}}|_{x_i = (x+1)^i - (x+1)}
     % \end{equation}
     \begin{equation}
     \label{eq::f_vec_main_result}
        f({\bf a}; x)  = \frac{1}{x} + \frac{1}{x^n}\sum_{\beta \succeq \alpha}  (-1)^{\ell(\alpha) - \ell(\beta)} \pi_{\ell(\beta)}(x) {\bf x}^{\beta-{\bf 1}}|_{x_i = (x+1)^i - (x+1)}\\
     \end{equation}
     % \begin{equation}
     %    f({\bf a}; x)  =\frac{1}{x} + \frac{1}{x^n}\sum_{\beta \succeq \alpha} (-1)^{\ell(\beta) - \ell(\alpha)}\pi_{\ell(\beta)}(x)M_{\beta - {\bf 1}}(x_1, x_2, \ldots , x_{\ell(\beta)})|_{x_i = (x+1)^i - (x+1)} 
     % \end{equation}
     where $\pi_{n}(x):=x^{n}[n]_{x+1}! = \prod_{i = 1}^{n}((x+1)^i - 1)$.
\end{Thm}

The reader may notice that equation~\eqref{eq::f_vec_main_result} looks almost like an evaluation of a quasisymmetric function. We will discuss this viewpoint in Section~\ref{subsect::formulas_as_evaluations_of_sums_of_quasisymmetric_polynomials}.

Note that in the case of $a_i > 0$ for all $i$, we recover the results of \cite[Thm 1.7]{Tesler_polytopes_2015} that $f({\bf a}; x) = [n]_{x+1}!$, a consequence of $\Flow_n({\bf a})$ being combinatorially equivalent to a product of simplices $\Delta_n \times \Delta_{n-1} \times \ldots \times \Delta_1$ as referenced above. In the case that ${\bf a} = (1, 0, \ldots , 0)$, we obtain a succinct formula for the previously-unknown $f$-vector of $CRY_n$ as a sum over complete homogeneous symmetric functions $h_m({\bf x}) := \sum_{1 \leq i_1 \leq \ldots \leq i_n}x_{i_1}\cdots x_{i_n}$.

\begin{Cor}
\label{cor::CRY_f_vec_formula}
     Let $f^{(n)}(x)$ be the  $f$-vector of $CRY_n = \Flow_n(1,0, \ldots, 0)$ written as a Laurent polynomial. Then for all $n \geq 1$:
     \begin{equation}
        f^{(n)}(x) = \frac{1}{x} +  \frac{1}{x^n}\sum_{m = 0}^{n-2}(-1)^m(1+x)^m\pi_{n-m}(x)\cdot h_m((x+1)^1 - 1, (x+1)^2 - 1, \ldots , (x+1)^{n-m - 1} -1)
    \end{equation}
    %   \begin{equation}
    %     f_n(x) = \frac{1}{x} +  \sum_{m = 0}^{n-2}(-1)^m(1+x)^m x^{-m}[n-m]_{x+1}! \cdot h_m((x+1)^1 - 1, (x+1)^2 - 1, \ldots , (x+1)^{n-m - 1} -1)
    % \end{equation}
    % \begin{equation}
    %     f_n(x) = \frac{1}{x} +  \sum_{m = 0}^{n-2}(-1)^m x^{-m}[n-m]_{x+1}! \cdot h_m(x+1)^2 - (x+1), (x+1)^3 - (x+1), \ldots , (x+1)^{n-m} -(x+1))
    % \end{equation}

    %   \begin{equation}
    %     f_n(x) = \frac{1}{x} +  \sum_{m = 0}^{n-2}(-1)^m x^{-m}[n-m]_{x+1}! \cdot h_m(x_1,\ldots,x_{n-m}) \mid_{x_i = (x+1)^{i+1}-(x+1)}
    % \end{equation}
\end{Cor}
This is a direct generalization of a theorem due to Andresen--Kjeldsen \cite[Prop. 3.3]{andresen_kjeldsen_1976} (which is recovered by setting $x = 1$) enumerating certain subgraphs of $K_{n+1}$. In their paper, the authors of \cite{andresen_kjeldsen_1976} study two families of subgraphs originating from their prior work in automata theory:
\begin{equation*}
    \Omega_n := \set{H \subseteq K_{n+1} \, | \, \text{every $v \in V(H)$ lies along a direct path from $v_1$ to $v_{n+1}$}}
\end{equation*}
and the following set of \textbf{primitive} subgraphs:
\begin{equation*}
    \Omega_n' := \set{H \in \Omega_n \, | \, V(H) = \set{v_1, \ldots, v_{n+1}}}.
\end{equation*}
They then give formulas for the cardinalities $\psi_n := |\Omega_n|$ (c.f. \cite[\href{https://oeis.org/A005016}{A005016}]{oeis})  and $\xi_n := |\Omega_n'|$ (c.f. \cite[\href{https://oeis.org/A005321}{A005321}]{oeis}). For example, they show that:
\begin{equation}
\label{eq::Andresen_Kjeldsen_psi_n}
         \psi_n = \sum_{m = 0}^{n-2}(-2)^m\pi_{n-m}\cdot h_m(2^1 - 1, 2^2 - 1, \ldots , 2^{n-m - 1} -1)
\end{equation}
where $\pi_n := \prod_{i = 1}^n (2^i - 1)$. One may actually recover $\psi_n$ from $\xi_n$ (and vice versa), as shown in \cite[eq. 1]{andresen_kjeldsen_1976}, which is a special case of our Corollary~\ref{cor::CRY_binomial_f_vec_f_primitive_vec_relationship}.

The connection between Corollary~\ref{cor::CRY_f_vec_formula} and equation~\eqref{eq::Andresen_Kjeldsen_psi_n} is made explicit  via the following powerful theorem of Hille \cite{Hille_2003}, originally introduced in the context of quivers. Here a subgraph $H \subseteq G$ is \textbf{${\bf a}$-valid} if $H$ is the support of an ${\bf a}$-flow on $G$, and the \textbf{first Betti number of $H$} is $\beta_1(H) := |E(H)| - |V(H)| + c(H)$, where $c(H)$ is the number of connected components of $H$. See also \cite{PS_vertices}. 

%To be self-contained, we restate these results here.

% \begin{Lem}[{\cite[Prop. 3.2]{andresen_kjeldsen_1976}}]
% \label{lem::andresen_kjeldsen_prop_xi}
%     Let $\pi_n := \prod_{i = 1}^n (2^i - 1)$. Then:
%     \begin{equation}
%         \xi_n = \sum_{m = 0}^{n-1}\pi_{n-m}\cdot h_m(2^1 - 1, 2^2 - 1, \ldots , 2^{n-m} -1)
%     \end{equation}
%     The numbers $\xi_n$ are sequence \cite[\href{https://oeis.org/A005321}{A005321}]{oeis} in OEIS.
% \end{Lem}

% \begin{Lem}[{\cite[Prop. 3.3]{andresen_kjeldsen_1976}}]
% \label{lem::andresen_kjeldsen_prop_psi}
% Let $\pi_n := \prod_{i = 1}^n (2^i - 1)$. Then:
%     \begin{equation}
%         \psi_n = \sum_{m = 0}^{n-2}(-2)^m\pi_{n-m}\cdot h_m(2^1 - 1, 2^2 - 1, \ldots , 2^{n-m - 1} -1)
%     \end{equation}
%     The numbers $\psi_n$ are sequence  \cite[\href{https://oeis.org/A005016}{A005016}]{oeis} in OEIS.
% \end{Lem}



\begin{Thm}[{\cite{Hille_2003}}]
\label{thm::Hille}
    Let $\mathcal{F}_G({\bf a})$ be a flow polytope such that $a_i \geq 0$ for all $i$. Then for $d \geq 0$, the $d$-dimensional faces of $\mathcal{F}_G({\bf a})$ are in one-to-one correspondence with subgraphs $H \subseteq G$ such that $H$ is ${\bf a}$-valid and $\beta_1(H) = d$. The empty face of $\mathcal{F}_G({\bf a})$ corresponds to the empty subgraph of $G$.
\end{Thm}

In this way, we see that the $f$-vector of $CRY_n$ is exactly a generating function over $\Omega_n$, where variable $x$ keeps track of the first Betti number of $H \in \Omega_n$. This connection leads us to define the new notion of primitive $f$-vector of $\Flow_n({\bf a})$ as follows. 

\begin{Def}
    The \textbf{primitive $f$-vector} of $\Flow_n({\bf a})$, denoted $\widetilde{f}^{(n)}({\bf a})$ (or as $\widetilde{f}^{(n)}({\bf a}; x)$ if written as a polynomial) is a generating function over the set of ${\bf a}$-valid subgraphs of $K_{n+1}$ that are primitive (use the entire vertex set) keeping track of the first Betti number. 
\end{Def}
Note that it follows immediately from the definition that $\widetilde{f}^{(n)}(1,0,\ldots, 0;x)|_{x = 1} = \xi_n$ in the same way that $f^{(n)}(1,0,\ldots, 0;x)|_{x = 1} = \psi_n$ from Theorem~\ref{thm::Hille}. See also Figure~\ref{fig::faces_of_CRY_n_as_subgraphs}.

Later in the text, we describe closed-form expressions for the primitive $f$-vector of $\Flow_n({\bf a})$ (Lemma~\ref{lem::primitive_f_vec_arbitrary_net_flow_sum_over_sets} and  Lemma~\ref{lem::primitive_f_vec_as_quasi_sym}) and describe a relationship between $f^{(n)}({\bf a})$ and $\widetilde{f}^{(n)}({\bf a})$ for arbitrary (non-negative) ${\bf a}$ (Lemma~\ref{lem::generalized_psi_xi_relationship}), as well as the special case of $CRY_n$ (Corollary~\ref{cor::CRY_binomial_f_vec_f_primitive_vec_relationship}). Data for $f^{(n)}(1, 0 \ldots , 0)$ and $\widetilde{f}^{(n)}(1, 0 \ldots , 0)$ are included in Table~\ref{tab::f_vectors_of_CRY_n} and Table~\ref{tab::f_primitive_vectors_of_CRY_n}, respectively.

A second, special relationship exists between the $f$-vector and primitive $f$-vector in the case of $CRY_n$, and specializes to  \cite[Prop. 4.1 ]{andresen_kjeldsen_1976} of Andresen--Kjeldsen by setting $x = 1$:

\begin{Lem}
\label{lem::f_vector_product_result}
    For all $n \geq 1$, the $f$-vector and primitive $f$-vector of $CRY_n$ are related as:
    \begin{equation}
        xf^{(n)}(x) = (1+x)^{n-1}\widetilde{f}^{(n)}(x).
    \end{equation}
\end{Lem}

Finally, we remark that Jel\'inek \cite{Jelinek_2011} observed that $\Omega_n'$ is in fact in bijection with the set of  \textbf{primitive Fishburn matrices} (upper triangular, $0$-$1$ matrices such that no row nor column is the zero vector) , and consequently is related to the enumeration of interval orders \cite{Bousquet_Melou_2010}, by interpreting $H \in \Omega_n'$ as the upper-triangular matrix determined by its edges. 
%Hwang--Jin--Schlosser \cite{hwang_jin_schlosser_2020} then used this perspective to compute the asymptotics of $\psi_n$ and $\xi_n$.
As discussed in \cite{hwang_jin_schlosser_2020}, the bijections continue, as the more general notion of Fishburn matrices are in bijection with  Stoimenow matchings, ascent sequences, and more \cite{Bousquet_Melou_2010, Stoimenow_1998}. See \cite{hwang_jin_schlosser_2020, Jelinek_2011} for a more comprehensive list of related combinatorial objects.

Either from Corollary~\ref{cor::CRY_f_vec_formula} or from a multivariate generating function of Fishburn matrices due to Jel\'inek \cite[Thm. 2.1]{Jelinek_2011} one obtains the following nice generating function for $d$-dimensional faces of $CRY_n$ for varying $d$ and $n$.

\begin{Cor}
The number of $d$-dimensional faces of $CRY_n$ is given by the coefficient $f^{(n)}_d = [t^nx^{d}]F(t,x)$, where $F(t,x)$ is defined by:
    \begin{equation}
        F(t,x) := \frac{1}{x-xt} + \sum_{n = 0}^{\infty} t^nx^{-n} \prod_{i = 1}^{n}\frac{(1 + x)^i - 1}{1 + ((1+x)^i - 1 - x)tx^{-1}}.
    \end{equation}
\end{Cor}


The rest of this paper is organized as follows: 
%In Section~\ref{sect::direct_enumerative_results_and_recurrences}, we describe some of the direct enumerative results for faces of $CRY_n$ that follow from Theorem~\ref{thm::Hille}, as well as recurrences that can be obtained from such. 
In Section~\ref{sect::main_results}, we derive our main result Theorem~\ref{thm::main_result} as well as results for general primitive $f$-vectors (Lemma~\ref{lem::primitive_f_vec_arbitrary_net_flow_sum_over_sets} and Lemma~\ref{lem::primitive_f_vec_as_quasi_sym}) needed in the proof. We conclude in Section~\ref{sect::formulas_for_CRY_n} by specializing our results to $CRY_n$.



%\section{Recurrence on multivariate generating functions}

%\subsection{Permutation statistics}

\section{Main Results}

\label{sect::main_results}




\begin{remark}
    \textbf{Notations and conventions:}  Our vector ${\bf a}$ used in this paper is often denoted ${\widetilde{\bf a}}$ in the flow polytope literature, as it does not account for the last vertex whose netflow is predetermined by the first $n$ entries. Moreover, we note that in the case of $a_i \geq 0$ for all $i$ as we are assuming in this manuscript,  a consequence of Theorem~\ref{thm::Hille} is that the combinatorial equivalence class of $\mathcal{F}_G\left({\bf a}, -\sum_{i = 1}^n a_i\right)$ is completely determined by the support of ${\bf a}$. Hence we may assume for the rest of the paper that ${\bf a} \in \set{0,1}^n$. An excellent source for any other unexplained terms and notation is \cite{Benedetti_transactions_2018}.
\end{remark}


\begin{figure}
    \centering
    \includegraphics[width = \textwidth]{faces_of_cry_3.png}
    \caption{The elements of $\Omega_3$ grouped by first Betti number, corresponding to the $f$-vector $(1,4,6,4,1)$ of $CRY_3$ (but excluding the empty face which would correspond to the empty graph). The primitive $f$-vector $(0,1,4,4,1)$ corresponds to the number of graphs in each grouping which use all vertices.}
    \label{fig::faces_of_CRY_n_as_subgraphs}
\end{figure}


\begin{table}[t]
    \centering
    \begin{tabular}{cp{15.25cm}}
    \hline
    $n$ & $f$-vector of $CRY_n$\\
    \hline
       $1$   &  $1, 1$\\
       
       $2$  &  $1, 2, 1$ \\
       
       $3$   &  $1, 4, 6, 4, 1$\\
       
       $4$  &  $1, 8, 26, 45, 45, 26, 8, 1$ \\
       
       $5$   &  $1, 16, 98, 327, 681, 944, 897, 588, 262, 76, 13, 1$\\
       $6$  &  \small{$1, 32, 342, 1943, 6982, 17326, 31236, 42198, 43521, 34601, 21249, 10020, 3571, 933, 169, 19, 1$} \\
       \hline
    \end{tabular}
    \caption{The first few $f$-vectors of $CRY_n.$}
    \label{tab::f_vectors_of_CRY_n}
\end{table}


\begin{table}[t]
    \centering
    \begin{tabular}{cp{15.25cm}}
    \hline\\
    $n$ & $\widetilde{f}$-vector of $CRY_n$\\
    \hline
       $1$  &  $0, 1$ \\
       $2$   &  $0, 1, 1$\\
       $3$  &  $0, 1, 4,4,1$ \\
       $4$   &  $0, 1,11,33,42,26,8,1$\\
       $5$  &  $0, 1, 26, 171, 507,840, 865, 584, 262, 76, 13,1$ \\
       $6$ &  $0, 1, 57, 718, 4017, 12866, 26831, 39268, 42211, 34221, 21184, 10015, 3571, 933, 169, 19, 1$\\
       \hline
    \end{tabular}
    \caption{The first few primitive $f$-vectors of $CRY_n.$}
    \label{tab::f_primitive_vectors_of_CRY_n}
\end{table}

We now describe various results that build towards Theorem~\ref{thm::main_result}. 

\subsection{Formulas as sums over subsets}

In \cite{andresen_kjeldsen_1976}, the authors define certain sequences of numbers which prove useful for the exact enumeration of the sets $\Omega_n$ and $\Omega_n'$ (here we require a change of convention to non-increasing sequences instead of non-decreasing sequences). 

\begin{Def}[\cite{andresen_kjeldsen_1976}]
    Let $S_{n,m}$ be the set of all sequences $(i_1, \ldots i_n)$ having length $n$ such that:
    
    \begin{inparaenum} 
    \item[(i)] $i_1 = n-m$, \hspace{1.5cm}
         \item[(ii)] $i_n = 1$, \hspace{1.5cm}
         \item[(iii)] $i_j \geq i_{j+1} \geq i_j - 1$ for all $j < n$.
    \end{inparaenum}
%     \begin{compactitem}
% \item[(i)] $i_1 = n-m$
%         \item[(ii)] $i_n = 1$
%         \item[(iii)] $i_j \geq i_{j+1} \geq i_j + 1$ for all $j < n$
% \end{compactitem}
\end{Def}

For our purposes, it will be simpler to think of the sequences in $S_{n,m}$ as subsets of $\nset{n} := \set{1, \ldots, n}$ through the following correspondence, of which we omit the proof.

\begin{Lem}
\label{lem::sequences_to_subsets}
    The map $\desc: S_{n,m} \rightarrow \binom{\nset{n-1}}{m}$ mapping a sequence in $S_{n,m}$ to the set of indices of its descents is a bijection. 
\end{Lem}
%\begin{proof}
%    Let $s = (i_1, \ldots , i_n) \in S_{n,m}$. Then in particular $s$ is a sequence such that $i_1 = 1, i_n = n-m$, and every element of the sequence is either equal to the previous element or exactly one more than it. In particular, $s$ is a non-decreasing sequence with exactly $m$ ascents $j_1, \ldots j_m$ (note that an \textbf{ascent} $j_k$ is an index such that $i_{j_k} \leq i_{j_k + 1}$). We define $f: S_{n,m} \rightarrow \binom{[n]}{m}$ via the rule $f(s) = \set{j_1, \ldots j_m}$.  To see that $f$ is a bijection, it suffices to note that every such sequence $s$ is completely determined by the locations of its ascents, and every $m$-element subset of $[n]$ can occur as the ascent set of some $s$. 
%\end{proof}

From here on we will be more interested in the inverse bijection of Lemma~\ref{lem::sequences_to_subsets}, and hence will denote by $\seq_n: \nset{n} \rightarrow \bigsqcup_{m = 0}^n S_{n+1,m}$ the map that takes takes a subset of $\nset{n}$ to its corresponding non-increasing sequence of length $n+1$. 

\begin{Ex}
    The following is an example of $\seq_4$ applied to subsets of the set $[4]$ of cardinality $2$:
    
    \begin{tabular}{ccc}
       $\seq_4(\set{1,2}) = (3,2,1,1,1),$  & $\seq_4(\set{1,3})  = (3,2,2,1,1),$ & $\seq_4(\set{1,4})  = (3,2,2,2,1),$ \\
        $\seq_4(\set{2,3})  = (3,3,2,1,1), $& $\seq_4(\set{2,4})  = (3,3,2,2,1), $& $\seq_4(\set{3,4})  = (3,3,3,2,1)$.
    \end{tabular}
    
\end{Ex}

These are all the ingredients we need to write down a first formula for $\widetilde{f}^{(n)}({\bf a};x)$.

\begin{Lem}
\label{lem::primitive_f_vec_arbitrary_net_flow_sum_over_sets}
    For all $n \in \NN$ and non-negative ${\bf a}$ of length $n$, a formula for $\widetilde{f}^{(n)}({\bf a};x)$ (that is, the primitive $f$-vector of  $\Flow_n({\bf a})$ written as a polynomial in $x$) is given by:
    \begin{equation}
    \label{eq::primitive_f_vec_sum_over_sets}
        \widetilde{f}^{(n)}({\bf a};x) = \frac{1}{x^n}\sum_{S \in [\supp({\bf a}'), \nset{n-1} ] }(-1)^{|S| + n + 1} \prod_{j \in \nset{n}}((x+ 1)^{\seq_{n-1}(S)_j} - 1 ) 
    \end{equation}
 where ${\bf a}' = (a_2, a_3, \ldots a_n)$, $\supp$ is the support function ( namely $\supp({\bf a}')$ returns the set of indices $j$ such that $a_{j+1} \neq 0$), and $[\supp({\bf a}'), \nset{n-1} ]$ is the interval of the Boolean lattice from $\supp({\bf a}')$ to $\nset{n-1}$.
\end{Lem}
\begin{proof}[Proof sketch]
    The idea of the proof is to start with the set of all primitive subgraphs of $K_{n+1}$ (not just ${\bf a}$-valid ones) and apply the principle of inclusion and exclusion in order to obtain the set of primitive subgraphs that are also ${\bf a}$-valid.

    Associate to $T \subseteq \set{v_2, \ldots v_n}$ its indicator set $S_T \subseteq \nset{n-1}$ in the canonical way (namely $i \in S_T$ if and only if $v_{i+1} \in T$). For each such $S$, define $R_S$ to be the set of primitive subgraphs of $K_{n+1}$ such that $i \in S^c$ implies $indeg(v_{i+1}) = 0$, where $indeg(v_{i+1})$ is the in-degree of vertex $v_{i+1}$. Then $S_1 \subseteq S_2$ implies $R_{S_1} \subseteq R_{S_2}$, and so the set $Prim_{\bf a}$ of ${\bf a}$-valid primitive subgraphs of $K_{n+1}$ may be found via inclusion-exclusion: 
    \begin{equation}
    \label{eq::lemma_proof_eq1}
        |Prim_{\bf a}| = \sum_{S \in [\supp({\bf a}'), \nset{n-1} ] }(-1)^{|S| + n + 1} |R_S|,
    \end{equation}
    where the lowest set in the interval is $\supp({\bf a}')$ since the elements of any subset of $R_{\supp({\bf a}')}$ are ${\bf a}$-valid. Finally, if we let $r_S(x)$ be the generating function over the set $R_S$ that keeps track of the sum of all outdegrees of each graph in $R_S$, then a modified argument as that appearing in the proof of \cite[Prop 3.2]{andresen_kjeldsen_1976} gives that:
    \begin{equation}
    \label{eq::lemma_proof_eq2}
        r_S(x) = \prod_{j \in \nset{n}}((x+ 1)^{\seq_{n-1}(S)_j} - 1 ).
    \end{equation}
    Combining equations \eqref{eq::lemma_proof_eq1} and \eqref{eq::lemma_proof_eq2} gives a generating function over the set $Prim_{\bf a}$ keeping track of the sum of all outdegrees of each graph. Finally, since our graphs are primitive, the first Betti number of each graph is exactly the sum of all outdegrees minus $n$, from which the final formula follows. 
\end{proof}

The next result describes how the $f$-vector of $\Flow_n({\bf a})$ may be obtained easily as a sum of primitive $f$-vectors.

\begin{Lem}
    \label{lem::generalized_psi_xi_relationship}
    For all $n \in \NN$ and non-negative ${\bf a}$ of length $n$:
\begin{equation}
    f^{(n)}({\bf a};x) = \frac{1}{x} + \sum_{{\bf b} \preceq {\bf a}} \widetilde{f}^{(|{\bf b}|)}({\bf b};x)
\end{equation}
where ${\bf b} \preceq {\bf a}$ if ${\bf b}$ can be obtained from ${\bf a}$ by deleting some subset (possibly empty) of the zeros in ${\bf a}$ and where $|{\bf b}|$ is the length of ${\bf b}$. 
    
\end{Lem}

\begin{proof}[Proof sketch]
    Let $F$ be a face of $\Flow_n({\bf a})$. If $F$ is the empty face, then it does not correspond to a primitive graph and hence contributes a term of $\frac{1}{x}$ to $f^{(n)}({\bf a};x)$. Otherwise, $F$ is non-empty and hence corresponds to an ${\bf a}$-valid subgraph $H \subseteq K_{n+1}$ by Theorem~\ref{thm::Hille}. Let $S_H \subseteq \set{v_1, \ldots, v_{n+1}}$ be the set of vertices which are part of the support of a flow determining $H$. Then $H$ is a primitive graph when restricted to the vertex set $S_H$, hence is counted by $\widetilde{f}^{(|b|)}({\bf b};x)$ for some ${\bf b}$ determined by $S_H$. The possible ${\bf b}$'s that can appear are exactly those described in the lemma statement.
\end{proof}


\begin{Ex}
    As an example, Lemma~\ref{lem::generalized_psi_xi_relationship} would give us the following equivalence:
    \begin{multline*}
        f^{(6)}(1,0,0,1,1,0;x) = \frac{1}{x} +\widetilde{f}^{(6)}(1,0,0,1,1,0;x) + 2\widetilde{f}^{(5)}(1,0,1,1,0;x) + \widetilde{f}^{(5)}(1,0,0,1,1;x)   \\ + \widetilde{f}^{(4)}(1,1,1,0;x)  + 2\widetilde{f}^{(4)}(1,0,1,1;x) + \widetilde{f}^{(3)}(1,1,1;x)
    \end{multline*}
    where the coefficient $2$ arises in front of  $\widetilde{f}^{(5)}(1,0,1,1,0;x)$, for example, as there are two ways to delete zeros that result in this input vector.
    
\end{Ex}



\subsection{Formulas as evaluations of sums of quasisymmetric polynomials}
\label{subsect::formulas_as_evaluations_of_sums_of_quasisymmetric_polynomials}

We can rewrite Lemma~\ref{lem::primitive_f_vec_arbitrary_net_flow_sum_over_sets} as an evaluation of a certain polynomial by using the standard bijection of subsets of $\nset{n-1}$ with integer compositions of $n$. Indeed, given a composition $\alpha$ and corresponding set $S_{\alpha}$ we define the multivariate polynomial:

\begin{equation}
\label{eq::polynomial_P}
    P_{\alpha}(x_1, \ldots, x_n) := \sum_{\beta \succeq \alpha} (-1)^{\ell(\beta) - \ell(\alpha)} {\bf x}^{\beta}  
\end{equation}
where ${\bf x}^{\beta} := x_1^{\beta_1}\cdots x_{\ell(\beta)}^{\beta_{\ell(\beta)}}$, and where the relation $\succeq$ is the standard relation of \textit{ refinement} on compositions.  

\begin{remark}
    The polynomial $P_{\alpha}$ may look familiar to the reader. Indeed, we recall that the monomial quasisymmetric functions, $M_{\alpha}$, and Gessel's fundamental quasisymmetric functions, $F_{\alpha}$, are defined in infinitely many variables $x_i$ respectively via:
\begin{equation*}
    M_{\alpha} := \sum_{i_1 < i_2 < \ldots < i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}, \hspace{2cm}  F_{\alpha} := \sum_{\substack{i_1 \leq i_2 \leq \ldots \leq i_k \\ i_j < i_{j+1} \text{ if } j \in S_{\alpha}}} x_{i_1}x_{i_2} \cdots x_{i_k}.
\end{equation*}
A standard result of quasisymmetric functions describes how to write the monomial quasisymmetric functions in terms of Gessel's fundamental quasisymmetric functions and vice versa. Namely we have the equations (c.f. \cite{EC2,Petersen_2005}):
\begin{equation}
    F_{\alpha} = \sum_{\beta \succeq \alpha} M_{\beta}, \hspace{2cm}  M_{\alpha} = \sum_{\beta \succeq \alpha} (-1)^{\ell(\beta) - \ell(\alpha)} F_{\beta}.
\end{equation}

Hence, the polynomial $P_{\alpha}(x_1, \ldots x_n)$ from above is exactly the expansion of $M_{\alpha}$ into the fundamental basis, except that we only keep the first term of each $F_{\beta}$; that is:
\begin{equation}
    P_{\alpha}(x_1, \ldots , x_n) = \sum_{\beta \succeq \alpha} (-1)^{\ell(\beta) - \ell(\alpha)} F_{\beta}(x_1, \ldots, x_{\ell(\beta)}) .
\end{equation}
\end{remark} 

The polynomials $P_\alpha$ capture all of the data needed to compute the primitive $f$-vector $\widetilde{f}_n({\bf a};x)$.

\begin{Def}
    For a subset $S \subseteq [n -1]$, let the \textbf{reverse} of $S$, denoted $\rev(S)$,  be defined as:
    \begin{equation}
        \rev(S) = \{n - i \, | \, i \in S \}
    \end{equation} 
For a natural number vector ${\bf a} := (a_1, \ldots, a_n)$, we define the \textbf{reverse composition}, denoted $\revcomp({\bf a})$,  as the composition corresponding to the set $\rev(\supp({\bf a}))$.    Computationally, $\revcomp({\bf a})$ may be obtained quickly by reading the entries of ${\bf a}$ from right to left, inductively creating blocks whenever a new nonzero entry is encountered, and recording the tuple of sizes coming from the list of blocks. 
\end{Def}

\begin{Ex}
\label{ex::revcomp_ex}
  If ${\bf a} = (1,1,0,0,1,0,1,0)$, then when we read ${\bf a}$ right to left, we first encounter the block $(0,1)$, followed by $(0,1)$, followed by $(0,0,1)$ and finally $(1)$. The reverse composition of ${\bf a}$ is then obtained by writing down the sizes of these blocks, hence $\revcomp({\bf a}) = (2,2,3,1)$.  For a non $0$-$1$ vector, we may first replace every nonzero entry with a $1$ and then perform the same procedure described here.
\end{Ex}

% \begin{remark}
%     We note that $\revcomp({\bf a})$ is exactly the signature of the vector ${\bf b}$, where ${\bf b}$ is the vector obtained by first reversing ${\bf a}$ and then flipping every bit \cite{}. 
% \end{remark}

\begin{Lem}
   \label{lem::primitive_f_vec_as_quasi_sym}
    For all $n \in \NN$ and non-negative ${\bf a}$ of length $n$, let $\alpha$ be the composition of $n$ given by $\alpha = \revcomp({\bf a})$. Then the primitive $f$-vector of $\Flow_n({\bf a})$ written as a polynomial is given by:
    \begin{equation}
        \widetilde{f}^{(n)}({\bf a}; x) = \frac{1}{x^n}P_{\alpha}(x, (x+1)^2 - 1, \ldots, (x+1)^{n} - 1)
    \end{equation}
\end{Lem}

\begin{proof}[Proof sketch]
    The proof follows from Lemma~\ref{lem::primitive_f_vec_arbitrary_net_flow_sum_over_sets} by applying the standard bijection between sets of size $n-1$ and compositions of $n$ and interpreting all quantities involved. Each term of equation~\eqref{eq::primitive_f_vec_sum_over_sets} translates to a term of $P$, and subset inclusion translates under this bijection to refinement of compositions. %Finally, the product $\prod_{j \in [n]}((x+ 1)^{\seq_{n-1}(S)_j} - 1 ) $ 
\end{proof}

We may combine Lemma~\ref{lem::generalized_psi_xi_relationship} and Lemma~\ref{lem::primitive_f_vec_as_quasi_sym} to obtain an explicit formula for the $f$-vector of  $\Flow_n({\bf a})$ for ${\bf a}$ non-negative, but first we need one more definition.

Aside from the refinement partial order on the set of integer compositions for some fixed $n$, recall that the set of \textit{all} compositions (of all positive integers) forms a poset $\mathcal{C} := (\mathcal{C}, \leq)$ where there are two types of cover relations (which we will denote $\cover_1$ and $\cover_2$). For compositions $\alpha$ and $\beta$, these are described by (\cite{Bjorner_Stanley_2005}):

\medskip

\begin{compactitem}
     \item $\alpha \cover_1 \beta$ if $\beta$ can be obtained from $\alpha$ by adding $1$ to a part, and
    \item $\alpha \cover_2 \beta$ if $\beta$ can be obtained from $\alpha$ by adding $1$ to a part and then splitting this part into two parts.
\end{compactitem}

\begin{Def}
    Define $\widetilde{\mathcal{C}} := (\mathcal{C}, \leq_1)$ to be the coarsening of $\mathcal{C}$ by  taking only the transitive closure of $\cover_1$. See Figure \ref{fig::composition_poset} for an example.
\end{Def}

\begin{figure}
    \centering
    \includegraphics[width = \textwidth]{composition_poset.png}
    \caption{The composition poset $(\mathcal{C}, \leq)$ of \cite{Bjorner_Stanley_2005} with lassos indicating the downsets determined by $\cover_1$ (left) and the coarsening $(\mathcal{C}, \leq_1)$ (right).}
    \label{fig::composition_poset}
\end{figure}


\begin{Lem}
\label{lem::f_vec_as_sums_of_downsets_of_poset}
     For all $n \in \NN$ and non-negative ${\bf a} \in \NN^n$, let $\alpha$ be the composition of $n$ given by $\alpha = \revcomp({\bf a})$. Then the $f$-vector of $\Flow_n({\bf a})$ written as a Laurent polynomial is given by:
    \begin{equation}
        f^{(n)}({\bf a}; x) = \frac{1}{x} + \frac{1}{x^n}\sum_{\beta \leq_1 \alpha} x^{|\alpha| - |\beta|}\left(\prod_{i = 1}^{\ell(\alpha)}\binom{\alpha_i - 1}{\alpha_i - \beta_i - 1}\right)  P_{\beta}(x, (x+1)^2 - 1, \ldots, (x+1)^{|\beta|}  - 1)
    \end{equation}
\end{Lem}

\begin{proof}[Proof sketch]
    Combining the results of Lemma~\ref{lem::generalized_psi_xi_relationship} and Lemma~\ref{lem::primitive_f_vec_as_quasi_sym} we obtain:
    \begin{equation*}
        f^{(n)}({\bf a};x) = \frac{1}{x} + \sum_{{\bf b} \preceq {\bf a}} \frac{1}{x^{|{\bf b}|}}P_{\beta}(x, (x+1)^2 - 1, \ldots, (x+1)^{|\beta| - 1})
    \end{equation*}
    where $\leq$ is the partial order on $0$-$1$ vectors described in Lemma~\ref{lem::generalized_psi_xi_relationship} and $\beta = \revcomp(\bf b)$. Translating both ${\bf a}$ and ${\bf b}$ into compositions via $\revcomp$, we find that the resulting partial order is exactly that of $(\mathcal{C}, \leq_1)$ (see Figure 2). Indeed, the number of parts of $\revcomp({\bf a})$ corresponds to the number of $1$'s appearing in ${\bf a}$, and deleting a $0$ in ${\bf a}$ corresponds to decreasing the corresponding part of $\revcomp{({\bf a})}$ by $1$. In Lemma~\ref{lem::generalized_psi_xi_relationship} we are only able to delete $0$'s and not $1$'s, hence the number of parts of $\revcomp({\bf b})$ must be the same as the number of parts of $\revcomp({\bf a})$. Finally, the product of binomial coefficients $\left(\prod_{i = 1}^{\ell(\alpha)}\binom{\alpha_i - 1}{\alpha_i - \beta_i - 1}\right) $ keeps track of the number of ways of deleting $0$'s from ${\bf a}$ that result in the same ${\bf b}$, and the factor of $x^{|\alpha| - |\beta|}$ arises as a result of taking the common denominator of all terms.
\end{proof}

All of the work has now been done in order to prove our main result, Theorem~\ref{thm::main_result}.

\begin{proof}[Proof sketch of Theorem~\ref{thm::main_result}]
    Lemma~\ref{lem::f_vec_as_sums_of_downsets_of_poset} gives $f^{(n)}({\bf a}; x)$ as a linear combination of $P_{\beta}$'s coming from downsets of the poset $(\mathcal{C}, \leq_1)$. However, each $P_{\beta}$ is also a sum over compositions (equation~\eqref{eq::polynomial_P}). The result follows from expanding the $P_{\beta}$'s, keeping track of all indices, and cancelling sums that telescope; see the upcoming full version of this text for more details.
\end{proof}



\section{Formulas for $CRY_n$}

\label{sect::formulas_for_CRY_n}

Given the significance of $CRY_n$ in the research community, we dedicate this section to the explicit formulas for $CRY_n$ obtained by specializing the results in the previous section. We first obtain the following result by setting ${\bf a} = (1,0, \ldots, 0)$ in Lemma~\ref{lem::primitive_f_vec_as_quasi_sym}. We remark that it is a generalization of \cite[Prop. 3.2]{andresen_kjeldsen_1976} which one can recover by setting $x = 1$.

\begin{Cor}
    Let $\widetilde{f}^{(n)}(x)$ be the primitive $f$-vector of $CRY_n$ written as a polynomial. Then for all $n \geq 1$:
    \begin{equation}
        \widetilde{f}^{(n)}(x) = \frac{1}{x^n}\sum_{m = 0}^{n-1}(-1)^m\pi_{n-m}(x)\cdot h_m((x+1)^1 - 1, (x+1)^2 - 1, \ldots , (x+1)^{n-m} -1).
    \end{equation} 
\end{Cor}

\begin{proof}[Proof sketch]
    In the case of $CRY_n$, ${\bf a} = (1, 0, \ldots, 0)$, hence $\revcomp({\bf a}) = (n)$. Hence $P_{\alpha}(x_1, \ldots, x_n)$ in Lemma~\ref{lem::primitive_f_vec_as_quasi_sym} has a term for every integer composition of $n$. Factoring out $x_1 \cdots x_{n-m}$ from the terms coming from level $n-m$ in the poset of compositions by refinement leaves $h_{m}(x_1, \ldots, x_{n-m})$. We then evaluate each $x_i$ in the same way as Lemma~\ref{lem::primitive_f_vec_as_quasi_sym}.
\end{proof}

We omit the proof of Corollary~\ref{cor::CRY_f_vec_formula}, as it follows similarly, except by specializing to ${\bf a} = (1,0, \ldots ,0)$ in Theorem~\ref{thm::main_result} instead of Lemma~\ref{lem::primitive_f_vec_as_quasi_sym}.

The following result is a specialization of Lemma~\ref{lem::generalized_psi_xi_relationship} to the case of ${\bf a} = (1, 0, \ldots, 0)$ and further gives \cite[eq. (1)]{andresen_kjeldsen_1976} by summing over all $d$:
\begin{Cor}
\label{cor::CRY_binomial_f_vec_f_primitive_vec_relationship} The $f$-vector and primitive $f$-vector of $CRY_n$ satisfy $f^{(n)}_d  = \sum_{i = 0}^{n-1}\binom{n-1}{i}\widetilde{f}^{(n - i)}_d.$
\end{Cor}
\begin{proof}
    By Lemma~\ref{lem::generalized_psi_xi_relationship}, we can obtain $f^{(n)}({\bf a}; x)$ from $\widetilde{f}^{(n)}({\bf a}; x)$ by summing over all subsets of zeros in ${\bf a}$. For $CRY_n$, ${\bf a} = (1, 0, \ldots, 0)$, so all possible subsets of $0$'s occur. 
\end{proof}

We conclude with a proof sketch of the intriguing relationship between $f^{(n)}$ and $\widetilde{f}^{(n)}$ described in Lemma~\ref{lem::f_vector_product_result}.

\begin{proof}[Proof sketch of Lemma~\ref{lem::f_vector_product_result}]
        The proof is analogous to that of \cite[Prop. 4.1]{andresen_kjeldsen_1976}.  We have:
\small{\begin{align*}
    \begin{split}
         \frac{(1+x)^{n}}{x}\widetilde{f}^{(n-1)} - f^{(n)}(x) =  \frac{(1+x)^{n}}{x}\cdot \frac{1}{x^{n-1}} \sum_{m = 0}^{n-2} (-1)^m \pi_{n-m-1}(x)h_m((x+1)^1 - 1, \ldots , (x+1)^{n-m-1} - 1) ) \\ - \frac{1}{x} - \frac{1}{x^n} \sum_{m = 0}^{n-2} (-1)^m (1 + x)^m \pi_{n-m}(x)h_m((x+1)^1 - 1, \ldots, (x+1)^{n-m-1} - 1).
    \end{split}
\end{align*}}
Which after algebraic manipulations simplifies to:
\begin{equation*}
     \frac{(1+x)^{n}}{x}\widetilde{f}^{(n-1)} - f^{(n}(x) = - \frac{1}{x} + \frac{1}{x^n}\sum_{m = 0}^{n-2} \pi_{n-m-1}(x) h_m(-(x+1)^2 + x+1, \ldots, -(x+1)^{n-m} + x+1)
\end{equation*}
 We may use the path model for the complete homogeneous symmetric functions to rewrite this expression as:
    \begin{equation}
    \label {eq::proof_of_lem_4.8}
        \frac{(1+x)^{n}}{x}\widetilde{f}^{(n-1)} - f^{(n}(x) = -\frac{1}{x} + \frac{1}{x^n}\sum_{i = 0}^{\infty} (N(x))^{n-1}_{1,i}
    \end{equation}
    where $N(x)$ is the weighted adjacency matrix for the infinite path graph having a self loop at each vertex, with loop at vertex $i$  ($i \geq 2$) having weight $(x+1)^i - 1$ and with edge $(i, i+1)$ having weight $-(x + 1)^{i+1} + (x+1)$. In other words, $N(x)$ has the following form:
    % \begin{equation*}
    %     N(x) := \setlength\arraycolsep{1.5pt}\begin{bmatrix}
    %         0 & x & 0 & 0 & \cdots & 0 \\
    %         0 & -(x+1)^2 + (x+1) & (x+1)^2 - 1 & 0 & \cdots & 0 & \cdots\\
    %          0 & 0 & -(x+1)^3 + (x+1)  & (x+1)^3 - 1 & \cdots & 0 & \cdots\\
    %           \vdots & \vdots & \vdots & \vdots & \ddots & 0 & \cdots\\
    %            0 & 0 & 0 & 0 & -(x+1)^i + (x+1) & (x+1)^i - 1 & \cdots \\
    %             \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \cdots\\
    %     \end{bmatrix}.
    % \end{equation*}
        \begin{equation*}
        N(x) := \setlength\arraycolsep{2pt}\begin{bmatrix}
            0 & x & 0  & \cdots & 0 \\
            0 & -(x+1)^2 + (x+1) & (x+1)^2 - 1  & \cdots & 0 & \cdots\\
              \vdots & \vdots & \vdots  & \ddots & 0 & \cdots\\
               0 & 0 & 0  & -(x+1)^i + (x+1) & (x+1)^i - 1 & \cdots \\
                \vdots & \vdots & \vdots  & \vdots & \ddots & \cdots\\
        \end{bmatrix}.
    \end{equation*}
    A simple induction shows that $\sum_{i = 0}^{\infty} (N(x))^{n-1}_{1,i} = x^{n-1}$, and after plugging into equation~\eqref{eq::proof_of_lem_4.8}, gives the result.
\end{proof}

% \section{Direct enumerative results and recurrences}

% \label{sect::direct_enumerative_results_and_recurrences}


% It was known to Chan--Robbins--Yuen \cite{Chan_Robbins_Yuen_2000} that their eponymous polytope has $2^{n-1}$ vertices. We provide a brief alternate proof of this result here to demonstrate how Theorem~\ref{thm::Hille} can be used to enumerate faces of flow polytopes. The rest of the results in this section arise similarly.

% \begin{Lem}[\cite{Chan_Robbins_Yuen_2000}]
% Let $f^{(n)} = (f^{(n)}_{d})_{d \geq -1}$ be the $f$-vector of $CRY(n)$. Then $f^{(n)}_0 = 2^{n-1}.$
% \end{Lem}

% \begin{proof}
% Vertices of $CRY_n$ are $0$-dimensional faces, hence by Theorem~\ref{thm::Hille} we need to find $(1,0,\ldots, 0, -1)$-valid graphs of $K_{n+1}$ that have first Betti number equal to $0$. These are exactly paths from $v_1$ to $v_{n+1}$, and each such path is completely determined by the support of edges it uses from the set $\set{(v_1, v_2), (v_2, v_3), \ldots, (v_{n}, v_{n+1})}$. Hence the vertices of $CRY_n$ are in bijection with words of length $n-1$ in the alphabet $\set{0,1}$, which gives the result.
% \end{proof}

% The next result is proved similarly, except that instead of counting paths we count graphs having first Betti number $1$. Each such graph must have exactly one vertex of out-degree $2$, which gives the recurrence. We omit the full proof. 

% \begin{Lem}
% Let $f^{(n)} = (f^{(n)}_{d})_{d \geq -1}$ be the $f$-vector of $CRY(n)$. Then the $f^{(n)}_1$ satisfy the recurrence relation:
% \begin{equation}
%     f^{(n)}_1 = f^{(n)}_1 + ... + f^{(n)}_1 + 3^n - 2^n
% \end{equation}
% and have a closed form expression:
% \begin{equation}
%     f^{(n)}_1 = 2\cdot 3^{n-1} - (n+3)\cdot 2^{n-2}
% \end{equation}
% \end{Lem}

% This method of direct enumeration stops working as well for higher dimensional faces, with the exception of working very well for low codimension. The following formulas are obtained by starting with all of $K_{n+1}$ and removing edges to lower the first Betti number, while discarding any edge deletion that results in a graph that is not $(1,0,\ldots, 0, -1)$-valid.

% \begin{Lem}
%     For $1 \leq d \leq n-1$, we have:
%     $$f^{(n)}_{\binom{n}{2} - d} = \sum_{i = 0}^d a_i \binom{\binom{n}{2} - i}{d - i}$$
%     where $a_i = [x^i] \prod_{k\geq1} (1 - x^k)^2$, the number of partitions of $n$ into an even number of distinct, bicolored parts minus number of partitions of $n$ into an odd number of distinct, bicolored parts;  see \cite[\href{https://oeis.org/A002107}{A002107}]{oeis}.
% \end{Lem}

% \begin{Ex}
%     For $n \geq d + 1$ arbitrary, let $N := \binom{n}{2}$. Then the first few codimensions of the $f$-vector for $CRY_n$ are given by:
%     \begin{align*}
%         f^{(n)}_{N - 1} & = N - 2\\
%         f^{(n)}_{N - 2} & = \binom{N}{2} - 2(N - 1) - 1\\
%         f^{(n)}_{N - 3} & = \binom{N}{3} - 2\binom{N - 1}{2} - (N - 2) + 2\\
%         f^{(n)}_{N - 4} & = \binom{N}{4} - 2\binom{N - 1}{3} - \binom{N - 2}{2} + 2\binom{N-3}{1} + 1 \\
%         f^{(n)}_{N - 4} & = \binom{N}{5} - 2\binom{N - 1}{4} - \binom{N - 2}{3} + 2\binom{N-3}{2} + (N-4) + 2
%     \end{align*}
% \end{Ex}




%\acknowledgements{The author is indebted to Alejandro Morales for many insightful conversations and feedback about this project, including proposing the project initially and suggesting the connection to quasisymmetric functions appearing in Section~\ref{subsect::formulas_as_evaluations_of_sums_of_quasisymmetric_polynomials}}.

\acknowledgements{The author is indebted to Alejandro Morales for proposing this project and for many insightful conversations and feedback, including suggesting the connection to quasisymmetric functions appearing in Section~\ref{subsect::formulas_as_evaluations_of_sums_of_quasisymmetric_polynomials}}. The author further wishes to thank Martha Yip and Rafael Gonz\'alez D'Le\'on for helpful conversations about flow polytopes generally, and LACIM at UQAM for a productive work environment in October 2023.


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