%% 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]{FPSAC2018}
\articlenumber{87}
%% 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{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}


\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\NN}{\mathbb{N}}

\newcommand\va{\mathbf{a}}
\newcommand\vc{\mathbf{c}}
\newcommand\ve{\mathbf{e}}
\newcommand\vt{\mathbf{t}}
\newcommand\vs{\mathbf{s}}
\newcommand\vp{\mathbf{p}}

\newcommand\F{\mathcal{F}}

\DeclareMathOperator{\PS}{PS}
\DeclareMathOperator{\Car}{Car}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\GD}{GD}
\DeclareMathOperator{\M}{M}
\DeclareMathOperator{\PF}{PF}
\DeclareMathOperator{\U}{U}
\DeclareMathOperator{\Zig}{Zig}

%For tikz
\usepackage{float}
\usepackage{tikz}
\usepackage{tkz-graph}
\tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=4pt]
\newcommand{\vertex}{\node[vertex]}
\tikzstyle{vtx}=[circle, draw, inner sep=0pt, minimum size=12pt]
\newcommand{\vtx}{\node[vtx]}
%--end tikz

\usepackage[all]{xy}

%For the car
\usepackage{fontawesome}

%% define your title in the usual way
\title{The volume of the caracol polytope}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[C.~Benedetti, R.~Gonz\'alez D'Le\'on, C.~Hanusa, P.~Harris,
A.~Khare, A.~Morales, and M.~Yip]
{Carolina Benedetti\thanks{\href{mailto:c.benedetti@uniandes.edu.co}
	{c.benedetti@uniandes.edu.co}. C. Benedetti thanks the Faculty of
	Science of Universidad de los Andes, York University, and Fields
	Institute for their support.}\addressmark{1},
Rafael S. Gonz\'alez D'Le\'on\thanks{\href{mailto:rafael.gonzalez@usa.edu.co}
	{rafael.gonzalezl@usa.edu.co}}\addressmark{2},\\
Christopher R.\,H.\,Hanusa\thanks{\href{mailto:chanusa@qc.cuny.edu}{chanusa@qc.cuny.edu}.
	C.\,R.\,H. Hanusa is grateful for the support of PSC-CUNY Award 
	69120-0047.}\addressmark{3},
Pamela E. Harris\thanks{\href{mailto:peh2@williams.edu}{peh2@williams.edu}.
	P.\,E. Harris was supported by NSF award DMS-1620202.}\addressmark{4},
Apoorva Khare\thanks{\href{mailto:khare@iisc.ac.in}{khare@iisc.ac.in}.
	A. Khare was partially supported by Ramanujan Fellowship
SB/S2/RJN-121/2017 and MATRICS grant MTR/2017/000295 from SERB (Govt.~of
India), by grant F.510/25/CAS-II/2018(SAP-I) from UGC (Govt.~of India),
and by a Young Investigator Award from the Infosys
Foundation.}\addressmark{5},
Alejandro H. Morales\thanks{\href{mailto:ahmorales@math.umass.edu}
	{ahmorales@math.umass.edu}.
	A.\,H. Morales was partially supported by an AMS-Simons 
	travel grant.}\addressmark{6},
\and 
Martha Yip\thanks{\href{mailto:martha.yip@uky.edu}{martha.yip@uky.edu}.
	M. Yip was partially supported by Simons collaboration 
	grant 429920.}\addressmark{7}	
}
	%\thanks{\href{mailto:c.benedetti@uniandes.edu.co}
	%{c.benedetti@uniandes.edu.co}.}
	%\thanks{\href{mailto:rafael.gonzalez@usa.edu.co}
	%{rafael.gonzalezl@usa.edu.co}.}
	%\href{mailto:chanusa@qc.cuny.edu}{chanusa@qc.cuny.edu}.
	%\href{mailto:peh2@williams.edu}{peh2@williams.edu}.
	%\thanks{\href{mailto:khare@iisc.ac.in}{khare@iisc.ac.in}.
	%\href{mailto:ahmorales@math.umass.edu}
	%{ahmorales@math.umass.edu}.
	%\href{mailto:martha.yip@uky.edu}{martha.yip@uky.edu}.

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}
	Departamento de Matem\'aticas, 
	Universidad de los Andes, 
	%c.benedetti@uniandes.edu.co
	%Bogot\'a, 
	Colombia
	\\ 
\addressmark{2}
	Escuela de Ciencias Exactas e Ingenier\'ia, 
	Universidad Sergio Arboleda,
	%rafael.gonzalez@usa.edu.co
	%Bogot\'a, 
	Colombia
	\\
\addressmark{3}
	Department of Mathematics, 
	Queens College (CUNY), 
	%chanusa@qc.cuny.edu
	%Flushing, 
	USA
	\\
\addressmark{4}
	Mathematics and Statistics, 
	Williams College, 
	%peh2@williams.edu
	%Williamstown, 
	USA
	\\
\addressmark{5}
	Department of Mathematics, 
	Indian Institute of Science, 
	%khare@iisc.ac.in
	%Bangalore, 
	India
	\\
\addressmark{6}
	Department of Mathematics and Statistics, 
	University of Massachusetts,
	%ahmorales@math.umass.edu 
	%Amherst, 
	USA
	\\
\addressmark{7}
	Department of Mathematics, 
	University of Kentucky,
	%martha.yip@uky.edu
	%Lexington, 
	USA
	\\
}

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

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We give a combinatorial interpretation of the Lidskii formula for flow polytopes and use it to compute volumes via the enumeration of new families of combinatorial objects which are generalizations of parking functions.  Our model applies to recover formulas of Pitman and Stanley, and compute volumes of previously seemingly unapproachable flow polytopes.  
A highlight of our model is that it leads to a combinatorial proof of an elegant volume formula for a new flow polytope which we call the caracol polytope. We prove that the volume of this polytope is the product of a Catalan number and the number of parking functions.

%We give a combinatorial interpretation of the Lidskii formula for flow polytopes and use it to compute volumes via the enumeration of new families of combinatorial objects which are generalizations of parking functions.  Our model applies to recover formulas of Pitman and Stanley,  prove elegant volume formulas for a new graph which we call the caracol, and compute volumes of previously seemingly unapproachable flow polytopes.

%%We prove that certain sequences which arise in our computations are log-concave, including the rows of the Euler--Bernoulli triangle and a
%%In the enumeration process, 
%a new triangle of numbers which arises from the study of the caracol that interpolates between Catalan numbers and the number of parking functions.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{
%}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{flow polytope, Lidskii formula, Kostant partition function, labeled Dyck path, Catalan number, parking function
}

%% 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, ie. [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{87-AIM2016.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}
\maketitle

%----------------------------------------------------------------------------
\section{Introduction}
%----------------------------------------------------------------------------
Flow polytopes are a family of polytopes with remarkable enumerative and geometric properties.  They are related to other areas of mathematics including toric geometry%~\cite{Hille03}
, 
Verma modules in representation theory%~\cite{Humphreys78}
, special functions%~\cite{ZLF17}
, and algebraic combinatorics. %and~\cite{MS}~\cite{MMR17}. 
Their combinatorial and geometric study started with work of Baldoni and Vergne~\cite{BV08} and unpublished work of Postnikov and Stanley. 

For an acyclic directed graph $G$ on $n+1$ vertices and $m$ edges accompanied by an integer vector $\va=(a_1,\ldots,a_n)\in\ZZ^{n}$, the flow polytope $\F_G(\va)\subset\RR^m$ encodes the set of flows on $G$ with net flow on its vertices given by~$\va':=(a_1,\ldots,a_n,-\sum_{i=1}^n a_i)$. The number of such integer-valued flows is the number of integer lattice points of $\F_G(\va)$; 
it is known in the literature as a Kostant partition function and is denoted by $K_G(\va')$. 
%Equivalently, this quantity counts the number of ways $\va'$ can be written as a sum of the vectors $\ve_i-\ve_j$ corresponding to the edges $(i,j)$ of $G$. 
Also of interest is the normalized volume of $\F_G(\va)$ (hereafter called simply the volume of $\F_G(\va)$), which is the Euclidean volume times the factorial of the dimension of the polytope. 

For certain graphs $G$ and vectors $\va$, the volume and number of lattice points of $\F_G(\va)$ have nice combinatorial formulas. We highlight a few examples involving various special graphs and the vectors $\va=(1,0,\ldots,0)$ and $\va=(1,\ldots,1)$.  
See~\cite{CKM17, MMS} %Meszaros15, MSW
for other examples.  

\begin{enumerate}
\item[(i)] When $G$ is the complete graph $K_{n+1}$ and $\va=(1,0,\ldots,0)$, $\F_G(\va)$ is called the Chan--Robbins--Yuen polytope~\cite{CRY00},
and in the case $\va=(1,\ldots,1)$, $\F_G(\va)$ is called the Tesler polytope~\cite{MMR17}.  Both volume formulas feature products of Catalan numbers:
\[
\vol \F_{K_{n+1}}(1,0,\ldots,0) \,=\, \prod_{i=1}^{n-2} C_i,
\qquad
\vol \F_{K_{n+1}}(1,\ldots,1) = \frac{\binom{n}{2}!}{\prod_{i=1}^{n-1} (2i-1)^{n-i}} \prod_{i=1}^{n-1} C_i,
\]
where $C_k :=\frac{1}{k+1}\binom{2k}{k}$.
The only known proofs of these formulas use a variant of the Morris constant term identity, but these product formulas suggest that combinatorial proofs should be attainable. 
%The original Morris identity is equivalent to the famous Selberg integral, see Zhou, Lu and Fu~\cite{ZLF17}.
\item[(ii)] When $G$ is the zigzag graph $\Zig_{n+1}$
(see Figure~\ref{figure:threegraphs}) and $\va=(1,0,\ldots,0)$,
Stanley~\cite{Stanley10} proved that the polytope $\F_{\Zig_{n+1}}(\va)$ has volume
$\vol\F_{\Zig_{n+1}}(\va) = E_{n-1}$,
where $E_{n-1}$ is half the number of alternating permutations on $n-1$ letters.

\item[(iii)] When $G$ is the graph denoted by $\PS_{n+1}$ (see Figure~\ref{figure:threegraphs}) and
$\va=(1,\ldots,1)$, the polytope $\F_{\PS_{n+1}}(\va)$ is affinely equivalent to the Pitman--Stanley polytope~\cite{SP02}. The number of lattice points in $\F_{\PS_{n+1}}(\va)$ is $K_{\PS_{n+1}}(\va') = C_n$ and $\vol\F_{\PS_{n+1}}(\va) = n^{n-2}$. 
%Pitman and Stanley gave two combinatorial proofs of these results.

\item[(iv)] 
Consider the graph on $n+1$ vertices created by adding to the graph $\PS_n$ (with indices incremented by one) 
an extra source vertex $1$ and the edges $(1,2), \ldots, (1,n)$.  We call this the {\em caracol graph} and denote it by $\Car_{n+1}$. (Caracol is the Spanish word for snail--see Figure~\ref{figure:threegraphs}.) 
When %$G$ is the graph $\Car_{n+1}$ and 
$\va=(1,0,\ldots,0)$, M\'esz\'aros, Morales and Striker~\cite{MMS} proved that $\F_{\Car_{n+1}}(\va)$ is equivalent to the order polytope of the poset $[2]\times[n-2]$. They also showed that 
$\vol \F_{\Car_{n+1}}(\va) = C_{n-2}$,
by counting the number of linear extensions of that poset.
\end{enumerate}

\begin{figure}%[bth]
\centering
\input{pictures/PSandCaracol_graphs_fpsac.tikz}
\input{pictures/zigzag_graph_fpsac.tikz}
\caption{The Pitman-Stanley, caracol, and zigzag graphs.}
\label{figure:threegraphs}
\end{figure}

%The formula for the volume deceivingly suggests an easy proof, like for the CRY. Caracol is the Minkowski sum of those two polytopes. It is unexpected to get the product of their volumes.

In this article, we introduce new combinatorial structures, called {\em gravity diagrams} and {\em unified diagrams}, which are based on classical combinatorial objects known as Dyck paths and parking functions, and whose enumeration provide combinatorial interpretations for terms in the Lidskii volume formulas of Baldoni and Vergne~\cite{BV08}.  In particular, Theorem~\ref{theorem:gravitydiagrams} proves that gravity diagrams provide a combinatorial interpretation for $K_G(\va')$, and Theorem~\ref{theorem:unifieddiagrams} proves that unified diagrams give a combinatorial interpretation of $\vol \F_G(\va)$.
These objects permit us to give new proofs for some of the above-mentioned formulas, 
%for lattice point counts and volumes of flow polytopes.  
and they allow us to compute in Theorem~\ref{thm.main} the volume of the flow polytope (referred to as the {\em caracol polytope}) for $\Car_{n+1}$ with net flow $\va=(1,\ldots,1)$, 
\begin{equation}
\vol \F_{\Car_{n+1}}(1,\ldots,1) = C_{n-2}\cdot n^{n-2},
\end{equation}
whose formula, like the CRY polytope, also features a product of combinatorial numbers.
Our model also allows us to obtain formulas for $\vol \F_{G}(\va)$ for other net flow vectors such as $\va=(a,b,\ldots,b)$ and $\va=(1,1,0,\ldots,0)$, which addresses problems that had previously seemed unapproachable.

Moreover, %via results on the Minkowski sum of polytopes by Stanley~\cite{???},
in the upcoming preprint~\cite{BGHHKMY}, 
we are able to show via the Aleksandrov--Fenchel inequalities that the sequences associated to a graph $G$ and net flow vector $\va$ defined by our {\em level-$i$ unified diagrams} $U_G^i(\va)$ are log-concave.
This includes the Entringer numbers (which are entries of the Euler--Bernoulli triangle~\cite[\href{https://oeis.org/A008282}{A008282}]{OEIS}),
and entries in a new triangle of numbers that we call the {\em parking triangle} (see Table~\ref{table:parkingtriangle}), which arises from our study of the volume of the caracol polytope.

%graph with net flow $\va=(1,\ldots,1)$.

The organization of this extended abstract is as follows.  
We provide background on flow polytopes, the Lidskii 
%volume 
formula and Kostant partition functions in the remainder of this section.
Section~\ref{sec:VectorInterps} introduces gravity diagrams for general graphs and net flow vectors, and provides their combinatorial interpretation. 
Section~\ref{section:LidskiiInterp} builds on gravity diagrams and parking functions to define unified diagrams, and proves that they provide a combinatorial interpretation for $\vol \F_G(\va)$. 
Section~\ref{section:volumecaracol} focuses on proving the formula for $\vol \F_{\Car_{n+1}}(1,\ldots,1)$, and in the process, we uncover the fascinating 
parking triangle.% of numbers.

\subsection{Flow polytopes}\label{sec:flow}

Let $G$ be a connected directed graph on the vertex set $V(G)=\{1,2,\ldots,n+1\}$ and directed edge set $E(G)$, 
where each edge $(i,j)$ satisfies $i<j$, and let $m=|E(G)|$. 
Given %such a graph $G$ and 
a vector $\va=(a_1,\ldots,a_n)$ in $\mathbb{Z}^{n}$, an $\va$-flow on $G$ is a tuple $(b_{ij})_{(i,j) \in E(G)}$ of real numbers such that for $j=1,\ldots,n$,
\begin{align}\label{equation:nodeflowsums}
\sum_{(j,k) \in E(G)} b_{jk} - \sum_{(i,j) \in E(G)} b_{ij} = a_j.
\end{align}
We view an $\va$-flow on $G$ as an assignment of flow $b_{ij}$ to each edge $(i,j)$ such that the net flow at each vertex $j\in [n]:=\{1,\ldots,n\}$ is $a_j$ and the net flow at vertex $n+1$ is $-\sum_{j=1}^n a_j$. Let $\F_G(\va)$ denote the set of $\va$-flows of $G$. We view $\F_G(\va)$ as a polytope in $\mathbb{R}^{m}$ and call it the {\em flow polytope of $G$ with net flow $\va$}. In this article, both $\va$ and $\va'$ will be referred to as the {\em net flow vector} depending on the context, since they refer to the same information. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Lidskii formula and Kostant partition functions}  
Associate to every directed edge $(i,j) \in E(G)$ the vector
$\ve_i-\ve_j = \alpha_i + \cdots + \alpha_{j-1}$,
where $\alpha_i := \ve_i-\ve_{i+1}$ for $1\leq i\leq n$,
and let $\Phi^+_G$ denote the set of such vectors, so that we can view an $\va$-flow on $G$ as a linear combination of positive roots
in the type $A$ root system.  
In this setting, Equation~\eqref{equation:nodeflowsums} is equivalent to writing $\va' = \sum_{(i,j) \in E(G)} b_{ij}[\alpha_i + \cdots + \alpha_{j-1}]$ as a linear combination of the vectors $\alpha_i + \cdots + \alpha_{j-1}$. %:
%\begin{align}\label{equation:vectorpartition}
%$\va'= \sum_{(i,j) \in E(G)} b_{ij}[\alpha_i + \cdots + \alpha_{j-1}] $.
%\end{align}
When the $\va$-flow $(b_{ij})$ is integral, this is an instance of a {\em vector partition} of $\va'$. The number of integral $\va$-flows on $G$ is called the {\em Kostant partition function} of $G$ evaluated at $\va'$ and we denote it by $K_G(\va')$.\\

\noindent{\bf Lidskii volume formula.} %~\cite{BV08} and~\cite{MM}.
%\begin{theorem}[Lidskii formula, {\cite[Theorem 38]{BV08}}, {\cite[Theorem 1.1]{MM}}] \label{thm.Lidskii} 
Baldoni and Vergne proved a remarkable formula for calculating the volume of a flow polytope using residue techniques~\cite[Theorem 38]{BV08}. 
This formula has also been proved by M\'esz\'aros and Morales using polytope subdivisions~\cite[Theorem 1.1]{MM}. 
Let $G$ be a directed graph on $n+1$ vertices. Let $\vt=(t_1,\ldots, t_n)$ be the {\em shifted out-degree vector} whose $i$-th entry is one less than the out-degree of vertex $i$. Let $G|_n$ denote restriction of $G$ to the first $n$ vertices, and let $\va = (a_1,\ldots,a_n)$ be a nonnegative integer vector. Then
\begin{equation} \label{eq:lidskiivol}
%\label{thm.Lidskii}
\vol\F_G(\va)
= \sum_{\vs\rhd \vt} \binom{m-n}{\vs}\cdot \va^{\vs}\cdot 
K_{G|_n}(\vs-\vt),
\end{equation} 
where the sum is over weak compositions $\vs=(s_1,\ldots,s_n)$ of $m-n$  
that dominate the vector~$\vt$, that is, $\sum_{i=1}^k s_i \geq \sum_{i=1}^k t_i$ for every $k\geq1$.  This is denoted by $\vs\rhd\vt$. We also use the standard notation 
%for the multinomial exponent 
$\va^{\vs}:=a_1^{s_1}a_2^{s_2}\cdots a_n^{s_n}$
and %for the multinomial coefficient
$\binom{r}{\vs}:=\frac{r!}{s_1!s_2!\cdots s_n!}$
for multinomial quantities.


The next equation is an immediate corollary of Equation~\eqref{eq:lidskiivol}.
%the Lidskii volume formula. %Theorem~\ref{thm.Lidskii},
\begin{equation}
\label{eq:lidskiivol100}
\vol\F_G(1,0,\ldots,0) = K_{G|_n}(m-n-t_1,-t_2,\ldots,-t_n).
\end{equation}

%---------------------------------------------------------------------------
\section{A combinatorial interpretation of vector partitions}%---------------------------------------------------------------------------
\label{sec:VectorInterps}


\subsection{Gravity diagrams}\label{section:gravitydiagrams}
A {\em line-dot diagram} is a pictorial representation of a vector partition.  Given a partition of $\vc' = \sum_{i=1}^{n+1}c_i\ve_i = \sum_{i=1}^n (c_1+\cdots+c_i)\alpha_i$ into positive roots in $\Phi_G^+$, where $c_i$ is a nonnegative integer for $1\leq i \leq n$,
%\geq0$ for all $1\leq i\leq n$, 
we create a two-dimensional array of dots with $c_1+\cdots+c_i$ dots in column $i$.  A part $[\alpha_i+\cdots+\alpha_{j-1}]$ of the vector partition is represented by drawing a line through dots from column $i$ to column $j-1$.  
%Let $\LD_G(\vc')$ denote the set of line-dot diagrams of $\vc'$ with parts in $\Phi_G^+$.  
Two line-dot diagrams are said to be equivalent if they represent the same vector partition of $\vc'$,
%so to account for the multiplicity, we define an equivalence relation on $\LD_G(\vc')$ such that two line-dot diagrams are equivalent if they correspond to the same vector partition of $\vc'$. 
and we let $\GD_G(\vc')$ denote the set of such equivalence classes.  
An equivalence class is called a {\em gravity diagram}, and the choice of a class representative will depend on the graph $G$.
By construction we have the following result.


\begin{theorem}\label{theorem:gravitydiagrams}
For any graph $G$ on $n+1$ vertices and for any net flow vector $\vc'\in\mathbb{Z}^{n}$,
\[K_{G}(\vc')=\big\lvert\GD_G(\vc')\big\rvert.\]
\end{theorem}
We highlight the use of gravity diagrams in the computation of flow polytope volumes in the next two examples.  

\begin{example} For the caracol graph $G=Car_{n+1}$ we have from Equation~\eqref{eq:lidskiivol100}, 
\[
\vol\F_{\Car_{n+1}}(1,0,\ldots,0) = K_{G|_n}((n-2)\alpha_1+(n-3)\alpha_2+\cdots+\alpha_{n-2}),
\]
where $\Phi_{G|_n}^+= \{\alpha_i \mid 1\leq i \leq n-1\} \cup 
\{\alpha_1+\cdots+\alpha_i \mid 2\leq i \leq n-1\}$.  A gravity diagram in
$\GD_{G|_n}(\vc')$ where $\vc'=(n-2)\alpha_1+\cdots+\alpha_{n-2}$
is a triangular array of $n-2$ columns of dots, and we make the canonical choice of a class representative to be the diagram whose lines are left-justified, and longer lines are bottom-justified (hence the name gravity diagram).  See Figure~\ref{figure:caracol_gravity}.
\end{example}

The enumeration of gravity diagrams leads to a combinatorial proof of a formula that first appeared in M\'esz\'aros--Morales--Striker~\cite{MMS}.
\begin{proposition}\label{prop:Dyck1} The volume of the flow polytope $\F_{\Car_{n+1}}(1,0,\dots,0)$ is the Catalan number $C_{n-2}$.
\end{proposition}
\begin{proof} There is a simple bijection between the set of gravity diagrams for $(\Car_{n+1})|_n$,
%and $\va = (1,0,\ldots,0)$, 
and the set of Dyck paths from $(0,0)$ to $(n-2,n-2)$.
\end{proof}

\begin{figure}
    \centering
    \input{pictures/caracol_gravity_diagrams_fpsac.tikz}
    \caption{The set of gravity diagrams $\GD_{(\Car_6)|_5}(3,-1,-1,-1,0)$.}
    \label{figure:caracol_gravity}
\end{figure}

\begin{example} For the zigzag graph $G=\Zig_{n+1}$, we similarly have
\[
\vol\F_{\Zig_{n+1}}(1,0,\ldots,0) = K_{\Zig_n}((n-2)\alpha_1+(n-3)\alpha_2+\cdots+\alpha_{n-2}),
\]
where $\Phi_{\Zig_n}^+= \{\alpha_i \mid 1\leq i \leq n-1\} \cup 
\{\alpha_i+\alpha_{i+1} \mid 1\leq i \leq n-2\}$.  A gravity diagram in $\GD_{\Zig_n}(\vc')$ where $\vc'=(n-2)\alpha_1+\cdots+\alpha_{n-2}$ is a triangular array of $n-2$ columns of dots, and lines may only connect  dots in two consecutive columns.  A canonical class representative in this case is constructed by placing lines from right to left such that each line occupies the lowest available dots in their respective columns. See Figure~\ref{figure:zigzag_gravity}.
\end{example}

Using gravity diagrams for the zigzag graph, we obtain a new direct proof of a formula that was first proved by Stanley~\cite{Stanley10}.
\begin{proposition}\label{prop:Euler} The volume of the flow polytope $ \F_{\Zig_{n+1}}(1,0,\ldots,0)$ is the $(n-1)$-th Euler number $E_{n-1}$~\cite[\href{https://oeis.org/A000111}{A000111}]{OEIS}.
\end{proposition}
\begin{proof}
The {\em Entringer numbers} $E(n,k)$~\cite[\href{https://oeis.org/A008282}{A008282}]{OEIS} are entries in the Euler--Bernoulli triangle and they enumerate down-up alternating permutations of $n+1$ beginning with $k+1$.
Let $\GD_{\Zig_{n}}(\vc',k)$ denote the subset of gravity diagrams whose first column is incident to exactly $k$ lines. These gravity diagrams satisfy the same recurrence equation as the Entringer numbers, and in fact, $|\GD_{\Zig_{n}}(\vc',k)|=E(n-2,n-2-k)$, so applying Theorem~\ref{theorem:gravitydiagrams},
the volume of $\F_{\Zig_{n+1}}(1,0,\ldots,0)$ is the number of gravity diagrams 
$$|\GD_{\Zig_{n}}(\vc')| 
= \sum_{k=0}^{n-2} |\GD_{\Zig_{n}}(\vc',k)| 
= \sum_{k=0}^{n-2} E(n-2,n-2-k)
= E_{n-1}.
$$
\end{proof}  

\begin{figure}
    \centering
    \input{pictures/zigzag_gravity_diagrams_fpsac.tikz}
    \caption{The set of gravity diagrams $\GD_{(\Zig_6)|_5}(3,-1,-1,-1,0)$.}
    \label{figure:zigzag_gravity}
\end{figure}

%---------------------------------------------------------------------------
\section{A combinatorial interpretation of the Lidskii formula} 
%---------------------------------------------------------------------------
\label{section:LidskiiInterp}

\subsection{Labeled $\vt$-Dyck paths and a generalization of parking functions} \label{section:tDyck} \label{section:parkingfunctions}

A standard way to represent a (classical) Dyck path is as an $\{N,E\}$-word of length $2n$ written in the form $N^{s_1}E N^{s_2} E\cdots N^{s_n}E$ such that $\vs=(s_1,\ldots, s_n)$ is a weak composition of $n$, and in 
every initial segment of the word, the number of $N$s is greater than or equal to the number of $E$s. This condition can be reframed so that we may view a Dyck path as a weak composition $\vs$ that dominates the vector $\vt=(1,\ldots, 1)$, and allows us to generalize Dyck paths in the following way.
Let $\vt = (t_1,\ldots, t_n)$ be a nonnegative integer vector.  The set of {\em $\vt$-Dyck paths} is the set of weak compositions $\vs$ of $|\vt|$ that dominate $\vt$.  

A {\em labeled $\vt$-Dyck path} is a pair $(\vs,\sigma)$ where $\vs$ is a $\vt$-Dyck path and $\sigma$ is a permutation of $|t|$ whose 
descents occur possibly in positions $s_1+\cdots+s_i$ for 
$1\leq i \leq |t|-1$.
It is well-known that labeled $(1,\ldots,1)$-Dyck paths are in bijection with parking functions (see Haglund~\cite[Proposition 5.0.1]{Haglund08}), so for this reason, we let $\PF_\vt$ denote the set of labeled $\vt$-Dyck paths, and these may be viewed as a generalization of parking functions.
The labeled $\vt$-Dyck path $(\vs,\sigma)$ may be visualized as a lattice path from $(0,0)$ to $(n,|\vt|)$ which lies above shaded boxes along a diagonal representing $\vt$ and whose north steps are labeled by the permutation $\sigma$.


\subsection{Unified diagrams}  \label{section:unifieddiagrams}
As the number of labeled $\vt$-Dyck paths is $|\PF_{\vt}|=\sum_{\vs \rhd \vt}\binom{|\vt|}{\vs}$ (see~\cite{BGHHKMY}), we can reformulate the Lidskii volume formula~\eqref{eq:lidskiivol} in terms of generalized parking functions:
\begin{align} \label{eq:lidskiivol_version_2}
\vol\F_G(\va)
= \sum_{(\vs,\sigma) \in\PF_{\vt}} \va^{\vs} \cdot 
K_{G|_n}(\vs-\vt).
\end{align} 
This equation leads us to create a new family of combinatorial diagrams, 
each of which consists of a tuple $U=(\vs,\sigma,\varphi,D)$ where $(\vs,\sigma)$ is a labeled $\vt$-Dyck path, $\varphi\in[a_1]^{s_1}\times\cdots\times[a_n]^{s_n}\subset \ZZ_{>0}^{|\vs|}$, and $D$ is a gravity diagram in  $\GD_{G|_n}(\vs-\vt)$. 

To define a {\em unified diagram} associated to a directed graph $G$ and net flow vector $\va$, begin with a labeled $\vt$-Dyck path $(\vs,\sigma)$.  We supplement the parking function labels on the north steps of the $\vt$-Dyck path with {\em net flow labels} by placing a number from $\{1,\ldots, a_i\}$ on each of the north steps with $x$-coordinate $i-1$.  Furthermore, since $\vs\rhd\vt$, then $\vs-\vt =\sum_{d=1}^{n-1}\left(\sum_{k=1}^d s_k-t_k\right) \alpha_d$, so a gravity diagram $D\in \GD_{G|_n}(\vs-\vt)$ has $\sum_{k=1}^d s_k-t_k$ dots in column $d$, which is precisely the number of cells in column $d$ between the lattice path $\vs$ and $\vt$.  Therefore, we may embed a gravity diagram into $U$.
Let $\U_G(\va)$ denote the set of unified diagrams associated to $G$ and $\va$. See Figure~\ref{figure:caracol_6_111111} for an example.


\begin{figure} 
\centering
\input{pictures/caracol_6_111111_fpsac.tikz}
\caption{A unified diagram $U=(\vs,\sigma,\varphi,D)$ for $G=\Car_6$ with $\va=(1,\ldots,1)$ (net flow labels suppressed) and shifted out-degree vector $\vt=(3,1,1,1,0)$. The $\vt$-Dyck path is $\vs=(4,2,0,0,0)$ with parking label $\sigma=134526$, and $D$ is a gravity diagram in $\GD_{G|_5}(1,1,-1,-1)= \GD_{G|_5}(\alpha_1+2\alpha_2+\alpha_3)$.}
\label{figure:caracol_6_111111}
\end{figure}

By construction, we have the following result.

\begin{theorem} \label{theorem:unifieddiagrams} 
For any graph $G$ on $n+1$ vertices and for any nonnegative net flow vector $\va\in\mathbb{Z}^{n}$,
$$\vol \F_G(\va) = \big\lvert\U_G(\va)\big\rvert.$$
\end{theorem}



When $\va= (1,\ldots,1)$, all net flow labels are $1$, so net flow labels are omitted from the unified diagrams in this case.
We apply Theorem~\ref{theorem:unifieddiagrams} to give a new proof of %Equation~\ref{equation:PitmanStanleyvolume}, 
a classical result of Pitman and Stanley~\cite{SP02}.

\begin{proposition} 
The volume of the flow polytope $\F_{\PS_{n+1}}(1,\ldots,1)$ is the number of parking functions $|\PF_{n-1}| = n^{n-2}$.
%If  $G=\PS_{n+1}$ is the Pitman-Stanley graph and $\va=(1,\ldots,1)$, then $\vol \F_{G}(\va)=n^{n-2}$.
\end{proposition}
\begin{proof}
For $G=\PS_{n+1}$, the shifted out-degree vector is $\vt=(1,\ldots,1,0)$ and $G|_n$ is simply the path on $n$ vertices. Therefore, for every $\vs\rhd\vt$, there is a unique gravity diagram consisting only of dots with no lines connecting the dots.  %Furthermore all net flow labels are 1.  
As such, a unified diagram in $\U_G(\va)$ is completely characterized by its labeled $\vt$-Dyck path, which is a parking function in $\PF_{n-1}=\PF_{(1^{n-1},0)}$ with an additional east step at the end.  
\end{proof}





%---------------------------------------------------------------------------
\section{The volume of \texorpdfstring{$\F_{\Car_{n+1}}(1,\ldots,1)$}{F Car (1,...,1)}} 
%---------------------------------------------------------------------------
\label{section:volumecaracol}

\subsection{Refined unified diagrams}
We enumerate unified diagrams by refining them according to the first east step of the underlying $\vt$-Dyck path. 
For $i\geq0$, the {\em level-$i$ unified diagrams} $\U^i_{G}(\va)$ is the set of unified diagrams whose north steps along the first column are omitted, and whose first east step is along the horizontal line labeled by $i$. This labeling scheme is shown in Example~\ref{ex:example_bijection} for a level $i=4$ unified diagram.  Furthermore, the parking function labels on the remaining north steps of the $\vt$-Dyck path are standardized to lie in the set $[i]$.

As there are $\binom{|\vt|}{|\vt|-i}=\binom{|\vt|}{i}$ choices for the parking function labels and $a_1^{|\vt|-i}$ choices for net flow labels on the north steps in the first column, we have the following proposition.
\begin{proposition}\label{p:iUnified}
Let $G$ be a graph on $n+1$ vertices with shifted out degree vector $\vt=(t_1,\ldots,t_n)$, and let $\va\in\ZZ^n$ be a nonnegative net flow vector.  Then
\begin{align}
    |\U_{G}(\va)|=\sum_{i=0}^{|\vt|}\binom{|\vt|}{i}a_1^{|\vt|-i}|\U^i_{G}(\va)|.
\end{align}
\end{proposition}


\subsection{The parking triangle and $\F_{\Car_{n+1}}(1,\ldots,1)$}

For the remainder of this section, we re-index by setting $r=n-2$ and consider the caracol graph $G=\Car_{n+1}=\Car_{r+3}$.  It has shifted out-degree vector $\vt =(r,1,\ldots,1,0)$, so $|\vt|=2r$.
Since initial east steps only occur at levels $0$ through $r$, the numbers defined by 
\begin{equation}
T(r,i):=\left|\U^i_{\Car_{r+3}}(1,\ldots,1)\right| \hbox{ for $r\geq 0$ and $0\leq i\leq r$}
\end{equation}
contain all the information necessary to compute $\vol\F_{\Car_{r+3}}(1,\ldots,1)$. As a special case of Proposition~\ref{p:iUnified}, we have
\begin{equation} \label{cor:decompositionofunifieddiagrams}
\left|\U_{\Car_{r+3}}(1,\ldots,1)\right|=\sum_{i=0}^{r}\binom{2r}{i}T(r,i).
\end{equation}

We call the array of numbers $T(r,i)$ the {\em parking triangle}. See Table~\ref{table:parkingtriangle} for a table of values.
As there are no north steps in a level-$0$ unified diagram, then the Dyck path in such diagrams can only have east steps, so $T(r,0)$ is the number of gravity diagrams for $\Car_{r+3}$, which was shown in Proposition~\ref{prop:Dyck1} to be the Catalan number $C_r$. On the other hand, since the first east step of the Dyck path in a level-$r$ unified diagram occurs at level $r$, and the associated gravity diagrams for $(\Car_{r+3})|_{r+2}$ can only have lines justified to the leftmost column, then an associated gravity diagram cannot contain any lines.
It follows that $T(r,r)=(r+1)^{r-1}$ is the number of parking functions of $r$.  
We thus have the following result.

\begin{proposition}
The $r$-th row of the parking triangle interpolates between the Catalan number $T(r,0)=C_r$ and the number of parking functions $T(r,r)=(r+1)^{r-1}$.
\end{proposition}

\begin{table}[h] 
$$%\small
\begin{array}{clllllllll}
\hline
r\setminus i & 0& 1& 2& 3& 4& 5& 6& 7& 8\\ \hline
0&	1 & & & & & & & & \\ 
1&	1 & 1 & & & & & & & \\ 
2&	2 & 3 & 3 & & & & & & \\ 
3&	5 & 10 & 16 & 16 & & & & & \\ 
4&	14 & 35 & 75 & 125 & 125 & & & & \\ 
5&	42 & 126 & 336 & 756 & 1296 & 1296 &  &  & \\ 
6&	132 & 462 & 1470 & 4116 & 9604 & 16807 & 16807 &  & \\ 
7&	429 & 1716 & 6336 & 21120 & 61440 & 147456 & 262144 & 262144 
    & \\ 
8&	1430 & 6435 & 27027 & 104247 & 360855 & 1082565 & 2657205 
    & 4782969 & 4782969 \\ \hline
\end{array}
$$
\caption{Values of the parking triangle $T(r,i)$ for $r =0,\ldots, 8$.
} 
\label{table:parkingtriangle}
\end{table}


We provide another family of objects that give a combinatorial interpretation to the parking triangle numbers $T(r,i)$ which allow us to find a closed formula for these numbers. 
For $r\geq0$ and $0\leq i\leq r$, let $\M(r,i)$ be the set of labeled Dyck paths from $(0,0)$ to $(r,r)$ whose north steps are labeled by the multiset $\{0^{r-i}, 1,\ldots,i\}$
such that the labels on consecutive north steps are non-decreasing.  We call these objects {\em multi-labeled Dyck paths}.

\begin{theorem} \label{theorem:bijectiondiagrams}
For $r\geq 0$,  
there is a bijection
\begin{equation}
\Phi:\U_{\Car_{r+3}}^i(1,\ldots,1) \longrightarrow \M(r,i).
\end{equation}
\end{theorem}
\begin{proof}[Outline of proof]
Let $G=\Car_{r+3}$ and $\va=(1,\ldots,1)$.
Recall that a level-$i$ unified diagram $U=(\vs,\sigma,D) \in \U_G^i(\va)$ consists of a Dyck path $\vs$ %=(s_1,\ldots,s_{r+1})$ 
of the form $EN^{s_1}EN^{s_2}\cdots EN^{s_{r+1}}E$, a permutation $\sigma$ of $[i]$, and a gravity diagram $D$ for $(\Car_{r+3})|_{r+2}$ with lines extending from the first column of cells to the multi-set of columns $\{1^{c_1},\ldots, r^{c_r}\}$ such that $\sum_{j=1}^r c_j=r-i$.

Let $\Phi(U)\in \M(r,i)$ be a multi-labeled Dyck path obtained by deleting the first and last east steps of the Dyck path of $U$, and by inserting $c_j$ north steps with $x$-coordinate $j$, each labeled $0$, into the Dyck path of $U$.
The new path is of the form
$N^{s_1+c_1}E\cdots N^{s_{r}+c_r}E$, with $r$ east steps and 
$r$ north steps labeled by $\{0^{r-i},1,\ldots,i\}$.   
\end{proof}


\begin{example}\label{ex:example_bijection}
The following figure depicts a level-$4$ unified diagram $U\in \U_{\Car_{11}}^4(1,\ldots,1)$ and its corresponding multi-labeled Dyck path $M\in\mathcal{M}(8,4)$ under the bijection $\Phi$. The four lines of the gravity diagram in $U$ extend to cells in columns $\{2,2,3,6\}$, and these correspond to the locations of the zero labels in $M$.
\begin{center}
\input{pictures/example_bijection_v2_fpsac.tikz}
\end{center}
%Figure \ref{figure:example_bijection_step_1} 
\end{example}

%\begin{figure}
%    \centering
%    \input{pictures/example_bijection_v2.tikz}
%    \caption{A level-$4$ unified diagram $U\in \U_{\Car_{11}}^4(1,\hdots,1)$ and its corresponding multi-labeled Dyck path $M\in\M(8,4)$ under the bijection $\Phi$ in Theorem~\ref{theorem:bijectiondiagrams}. 
%    %This is described in Example~\ref{ex:example_bijection}.
%    }
%    \label{figure:example_bijection_step_1}
%\end{figure}





We now present a vehicle-parking scenario that models multi-labeled Dyck paths, analogous to the one for classical parking functions (see~\cite{Haglund08}).
With this model, we are able to prove a closed formula for the entries $T(r,i)$ of the parking triangle.

Suppose that there are $r$ parking spots on a one-way street,
$r-i$ identical motorcycles $\textup{\small \faMotorcycle\,}_0,\ldots, \textup{\small \faMotorcycle\,}_0$, %(without plate)
and $i$ distinct cars labeled $\textup{\small \faCar\,}_1,\ldots, \textup{\small \faCar\,}_i$. 
The vehicles have preferred parking spots, and this information is recorded as a {\em preference pair}, which contains a multiset of cardinality $r-i$, indicating parking preferences for the motorcycles, and a vector of length $i$ whose $k$-th entry contains the parking preference of the car $\textup{\small \faCar\,}_k$.  The vehicles advance down the street with the motorcycles parking first and the cars following in numerical order.  As in the classical case, all $r$ vehicles will find a parking spot if and only if the preference pair can be uniquely represented by a multi-labeled Dyck path. 

\begin{figure}
    \centering
    \input{pictures/parking_model_multilabeled_diagrams_fpsac.tikz}
    \caption{The multi-labeled Dyck path $\left((2,3,1,0,0,2,0,0),\, 24003001\right) \in \M(8,4)$ corresponds to the parking preference pair $\vp=\{2,2,3,6\}\times (6,1,2,1)$; the final parking arrangement is given on the right.}
    \label{figure:parking_model_multilabels}
\end{figure}


\begin{theorem}\label{thm:triangleclosedformulas}
For $r \geq 0$ and $0\leq i\leq r$,
$T(r,i) = (r+1)^{i-1} \binom{2r-i}{r}$.
\end{theorem}

\begin{proof}[Outline of proof] 
We adapt an idea of Pollack~\cite[p.13]{FR74}. If there are $r+1$ parking spots on a circular one-way street, then every preference pair for the $r-i$ motorcycles and $i$ cars will allow every vehicle to park, with one empty space left.  There is a cyclic action of the group $\mathbb{Z}_{r+1}$ on the set of preference pairs defined by 
\[a\cdot \vp := \{p_1+a,\ldots, p_{r-i}+a\} \times (q_1+a,\ldots, q_i+a) \mod r+1\]
for $a\in \mathbb{Z}_{r+1}$ and a preference pair $\vp$, so that each orbit has $r+1$ elements under the group action, and the unique element with the $(r+1)$-st space empty corresponds to a multi-labeled Dyck path.

There are 
$\binom{2r-i}{r}$ multisets of preferences for the $r-i$ motorcycles, and $(r+1)^i$ preference vectors for the $i$ cars, and since each $\mathbb{Z}_{r+1}$-orbit has $r+1$ elements, there are $(r+1)^{i-1} \binom{2r-i}{r}$ multi-labeled Dyck paths in $\M(r,i)$.
\end{proof}

This was the last piece of the puzzle needed to prove the main theorem in this manuscript.

\begin{theorem}\label{thm.main}
The volume of the flow polytope $\F_{\Car_{n+1}}(1,\ldots,1)$ is $C_{n-2}\cdot n^{n-2}$.
\end{theorem}
\begin{proof}
%\proof 
For $\va=(1,\ldots,1)$,
Theorem~\ref{theorem:unifieddiagrams}, Equation~\eqref{cor:decompositionofunifieddiagrams}, and Theorem~\ref{thm:triangleclosedformulas} combine to give
\begin{align*}
\vol \F_{\Car_{n+1}}(\va)
&= |\U_{\Car_{n+1}}(\va)|
= \sum_{i=0}^{n-2} \binom{2(n-2)}{i} T(n-2,i)
=C_{n-2}\cdot n^{n-2}.%\qedhere
\end{align*}
\end{proof}


\acknowledgements{This project was initiated at the Polyhedral Geometry and Partition Theory workshop at the American Institute of Mathematics (AIM) in November 2016.  We are extremely grateful to the organizers of the workshop -- Federico Ardila, Benjamin Braun, Peter Paule, and Carla Savage -- and to AIM which led to this collaboration. 
%and future related opportunities.
}

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