\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P22}{20(3)}{2013}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{setspace}
\usepackage{amsthm}
\usepackage{epsfig,color,colordvi,wasysym}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\bibliographystyle{amsplain}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand\commentout[1]{}
\newcommand{\sidenote}[1]{\marginpar{\bf#1}}
\newcommand\fl[1]{\left\lfloor {#1} \right\rfloor}
\def\th{$^{\text{th}}$}
\def\mult{\operatorname{mult}}
\newcommand{\conv}{\operatorname{conv}}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\I}{\mathcal{I}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\def\e{\mathbf{e}}
\def\m{\mathbf{m}}
\def\w{\mathbf{w}}
\def\x{\mathbf{x}}
\def\z{\mathbf{z}}
\renewcommand\emptyset{\varnothing}

\title{\bf The combinatorics of\\ interval-vector polytopes}  

\author{Matthias Beck\\
\small Department of Mathematics\\[-0.8ex]
\small San Francisco State University\\[-0.8ex]
\small San Francisco, U.S.A.\\
\small\tt mattbeck@sfsu.edu\\
\and
Jessica De Silva\\
\small Department of Mathematics\\[-0.8ex]
\small University of Nebraska\\[-0.8ex]
\small Lincoln, U.S.A.\\
\small\tt jessica.desilva@huskers.unl.edu\\
\and
Gabriel Dorfsman--Hopkins\\
\small Department of Mathematics\\[-0.8ex]
\small Dartmouth College\\[-0.8ex]
\small Hanover, U.S.A.\\
\small\tt Gabriel.D.Dorfsman-Hopkins.13@dartmouth.edu\\
\and
Joseph Pruitt\\
\small Department of Mathematics \\[-0.8ex]
\small University of Illinois\\[-0.8ex]
\small Urbana--Champaign, U.S.A.\\
\small\tt j92pruitt@gmail.com\\
\and
Amanda Ruiz\\
\small Department of Mathematics\\[-0.8ex]
\small Harvey Mudd College\\[-0.8ex]
\small Claremont, U.S.A.\\
\small\tt amruiz@hmc.edu
}

\date{\dateline{Dec 18, 2012}{Aug 12, 2013}{Aug 23, 2013}\\
\small Mathematics Subject Classifications: 52B05, 05A15, 52B20}

% 05A15 Exact enumeration problems, generating functions
% 52B05 Combinatorial properties of polytopes
% 52B20 Lattice polytopes

\begin{document}

\maketitle

\begin{abstract}
An \emph{interval vector} is a $(0,1)$-vector in $\mathbb{R}^n$ for which all the $1$'s
appear consecutively, and an \emph{interval-vector polytope} is the convex hull of a
set of interval vectors in $\mathbb{R}^n$.
We study three particular classes of interval vector polytopes which exhibit interesting
geometric-combinatorial structures; e.g., one class has volumes equal to the Catalan
numbers, whereas another class has face numbers given by the Pascal 3-triangle.

  \bigskip\noindent \textbf{Keywords:} Interval vector, lattice polytope, Ehrhart polynomial, root polytope, Catalan number, $f$-vector
\end{abstract}

%--------------------------------------

\section{Introduction}

An \emph{interval vector} is a $(0,1)$-vector $x\in\mathbb{R}^n$ such
that, if $x_i = x_k = 1$ for $i<k$, then $x_j = 1$ for every $i\le j\le k$. 
In \cite{MR2825295} Dahl introduced the class of \emph{interval-vector polytopes}, 
 which are formed by taking the convex hull of a set of interval vectors in
$\mathbb{R}^{n}$. Our goal is to derive combinatorial properties of certain interval-vector polytopes.

For $i\le j$, let
$\alpha_{i,j}:=e_i + e_{i+1} + \dots + e_j$, where $e_i$ is the
$i^{\textit{th}}$ standard unit vector.  The \emph{interval length} of
$\alpha_{ij}$ is $j-i+1$. 
 Let $S\subset \NN$. For a fixed $n$, let $\I_S$ be the set of interval vectors in $\RR^n$
with interval length in $S$. (If $S$ is small, we may leave out the brackets in
the set notation; e.g., we will denote $\I_{\{i,j\}}$ by $\I_{i,j}$.) We will
denote the set of all non-zero interval vectors in a given dimension as $\I_{[n]}$.
Let $\P_n(\I_S)$ be the convex hull of $\I_S\subset \RR^n$.
 
There are three classes of interval vector polytopes that we will consider in this
paper. In Section~\ref{complete} we study the \emph{complete interval vector polytope}
$\P_n(\I_{[n]})$, the convex hull of all interval vectors in $\RR^n$ except the zero vector. In Section \ref{fixed} we look at the \emph{fixed interval vector
polytope} $\P_n(\I_i)$ given by the convex hull of all interval vectors with
interval length $i$. In Section \ref{pyramid} we  introduce the first in a class
of \emph{pyramidal interval polytopes}: the \emph{first pyramidal interval vector polytope} $\P_n(\I_{1,n-1})$, the convex hull of all interval vectors in $\RR^n$ with interval length $1$ or $n-1$. 
(The reason for the term \emph{pyramidal interval polytope} will also become clear in Section \ref{pyramid}.)
In Section \ref{conjectures} we generalize this to the \emph{$i^\text{th}$ pyramidal
interval vector polytope} $\P_n(\I_{1,n-i})$.  We examine combinatorial characteristics of these polytopes such as the $f$-vector and volume and discover  unexpected relations to well-known numerical sequences. 

Let $t$ be a positive integer variable. For a lattice polytope $\P$ (i.e., the
vertices of $\P$ all have integer coordinates), the \emph{Ehrhart polynomial}
$L_{\mathcal{P}}(t)$ is the counting function 
yielding the number of lattice points in 
$t\mathcal{P}:=\{tv\;|\;v\in\mathcal{P}\}$.
Ehrhart \cite{ehrhartpolynomial} proved that $L_{\mathcal{P}}(t)$ is indeed a
polynomial; see, e.g., \cite{ccd} for more about Ehrhart polynomials.
The  Ehrhart polynomial  contains useful geometric information about a polytope;
in particular, the leading coefficient of the Ehrhart polynomial gives the volume of the polytope.

In \cite{MR2487491}, Postnikov defines the \emph{complete root polytope}
$Q_n\subset\mathbb{R}^n$ as the convex hull of $0$ and $e_i-e_j$ for all $i<j$ where $e_i$ is the $i^{\text{th}}$ standard unit vector. 
He showed (among many other things) that the volume of $Q_{n+1}$ is $C_n:= \frac{1}{n+1}{2n\choose n}$, the $n^{\textrm{th}}$ Catalan number.
In Section \ref{complete} we prove, in a discrete-geometric
sense, that $Q_{n+1}$ and the complete interval vector polytope $\P_n(\I_{[n]})$ are interchangeable, that is, the two polytopes
have the same Ehrhart polynomial.

\begin{theorem}\label{CompleteRootEquiv}
$L_{Q_{n+1}}(t) = L_{\P_n(\I_{[n]})}(t) \, .$
\end{theorem}

\begin{corollary}\label{CIPvolume}
The volume of the complete interval vector polytope $\P_n(\I_{[n]})$ equals 
the $n^{\textrm{th}}$ Catalan number.
\end{corollary}

A \emph{unimodular simplex} in $\RR^d$ is an $n$-dimensional lattice simplex $\Delta$ whose edge direction at any vertex form a lattice basis for $\ZZ^d \cap
\aff(\Delta)$, where $\aff(\Delta)$ is the affine hull of~$\Delta$. 
In Section \ref{fixed} we prove: 
 
\begin{theorem}\label{unimodular}
The fixed interval vector polytope $\P_n(\I_{i})$ is an $(n-i)$-dimensional unimodular simplex.
\end{theorem}
 
Given an $n$-dimensional polytope
$\mathcal{P}$ with $f_{k}$ $k$-dimensional faces, the \emph{$f$-vector} of
$\mathcal{P}$ is written as
$f(\mathcal{P}):=(f_{-1},f_{0},f_{1},\dots,f_{n})$ where $f_{-1},f_n:=1$ (see,
e.g., \cite{MR1976856} for more about $f$-vectors).
In Section~\ref{pyramid} we show:

\begin{theorem}\label{fvector}
For $n\ge 3$, the $f$-vector of the first pyramidal interval vector polytope
satisfies $f_k(\P_n(\I_{1,n-1})) = \binom{ n-1 }{ k } + \binom{ n+1 }{ k+1 } \,
.$
\end{theorem}
The $f$-vector of $\P_n(\I_{1,n-1})$ is thus the $n^\text{th}$ row of the
\emph{Pascal 3-triangle} (see, e.g., \cite[Sequence A028262]{sloaneonlineseq}), in particular, it is symmetric. % The Pascal 3-triangle is a  Pascal's triangle added to a shifted Pascal's triangle. Where the Pascal's triangle has a row $1$ $2$ $1$, the Pascal 3-triangle has a row $1$ $3$ $1$, and follows the same addition pattern  as in Pascal's triangle.   
We also show that the volume of the $1^\text{st}$ pyramidal interval vector polytope is simple:

\begin{theorem}\label{volpyramid}
For $n \geq 3$, $ \vol ( \P_n(\I_{1,n-1})) = 2(n-2) \, .$
\end{theorem}

Finally, in Section \ref{conjectures} we lay out future work on $i^\text{th}$
pyramidal interval vector polytopes.

%--------------------------------------

\section{Preliminaries}

In this paper, we will be analyzing the properties of certain classes of
\emph{convex polytopes} which are formed by taking the convex hull of finitely
many points in $\mathbb{R}^{n}$. The \emph{convex hull} of a set 
$A=\{v_{1},v_{2},\dots,v_{m}\}\subset\mathbb{R}^{n}$, denoted
$\operatorname{conv}(A)$, is defined as

\begin{equation}\label{hull} \left\{\lambda_{1}v_{1}+\lambda_{2}v_{2}+\dots+\lambda_{m}v_{m}
\mid\lambda_{1},\lambda_{2},\dots,\lambda_{m}\in\mathbb{R}_{\ge
0}\ \textrm{ and }\ \sum_{i=1}^{m}\lambda_{i}=1\right\}.\end{equation} 
The
polytope $\operatorname{conv}(A)$ is contained in  the \emph{affine hull} $\operatorname{aff}(A)$ of
$A$, defined as in \eqref{hull} but without the restriction
that $\lambda_{1},\lambda_{2},\dots,\lambda_{m}\ge 0$. We call a set of points
\emph{affinely} (resp.\ \emph{convexly}) \emph{independent} if each point is not
in the affine (resp.\ convex) hull of the rest. The \emph{vertex set} of a polytope is the minimal convexly
independent set of points whose convex hull form the polytope. 
% The \emph{affine space} of a polytope is the affine hull of its vertices. 
A polytope is \emph{d-dimensional} if the dimension of its affine hull
is $d$. We denote the dimension of the polytope $\mathcal{P}$ as
$\operatorname{dim}(\mathcal{P})$. We call a $d$-dimensional polytope a
\emph{d-simplex} if it has $d+1$ vertices.

A \emph{lattice point} is a point with integral coordinates. A \emph{lattice
polytope} is a polytope whose vertices are lattice points.
% A \emph{lattice basis} of a $d$-dimensional affine space is a set of $d$ integral vectors where, fixing a lattice point on the affine space $v$, any lattice point inside the affine space can be written as $v$ plus an integral linear combination of these vectors. 
The \emph{normalized volume} of a polytope $\mathcal{P}$, denoted $\operatorname{vol}(\mathcal{P})$, is the volume with respect to a unimodular simplex (recall definition in Section 1). We will refer to the normalized volume of a polytope as its \emph{volume}.
Note that the leading coefficient of the Ehrhart polynomial of a lattice polytope
$\P$ is $\frac{1}{d!} \vol(\P)$. 

A \emph{hyperplane} is a set of the form
\[H:=\left\{x\in\mathbb{R}^{n} \, | \, a_{1}x_{1}+\cdots+a_{n}x_{n}=b\right\},\] where not all
$a_{j}$'s are 0. The \emph{half-spaces} defined by this hyperplane are formed by
the two weak inequalities corresponding to the equation defining the hyperplane.
% The \emph{half-space description} of a polytope is the smallest finite set of closed half-spaces whose intersection is the polytope. 
A \emph{face} of
$\mathcal{P}$ is the intersection of a hyperplane and $\mathcal{P}$ such that
$\mathcal{P}$ lies completely in one half-space of the hyperplane. This face is
a polytope called a \emph{$k$-face} if its dimension is $k$. A vertex is a
$0$-face and an \emph{edge} is a $1$-face. Given an $n$-dimensional polytope
$\mathcal{P}$ with $f_{k}$ $k$-dimensional faces, the \emph{$f$-vector} of
$\mathcal{P}$ is written as
$f(\mathcal{P}):=(f_{-1},f_{0},\dots,f_{n})$. For example, a triangle
$\triangle$  is a $2$-dimensional polytope with $3$ vertices and $3$ edges and thus has $f$-vector $f(\triangle)=(1,3,3,1)$. 
% As we look at the following polytopes we will see interesting patterns in these properties.

%--------------------------------------

\section{Complete Interval Vector Polytopes}\label{complete}

\commentout{
In \cite{MR2825295} Dahl introduces a class of polytopes based on interval
vectors. An $interval$ $vector$ is a $(0,1)$-vector $x\in\mathbb{R}^n$ such
that, if $x_i = x_k = 1$ for $i<k$, then $x_j = 1$ for every $i\le j\le k$.  Let
$\alpha_{i,j}:=e_i + e_{i+1} + \dots + e_j$ for $i\le j$.  The \emph{interval length} of
$\alpha_{ij}$ is $j-i+1$. If $\mathcal{I}$ is a set of interval vectors then we
define the polytope $P_{[n]}(\mathcal{I}):=$ $\operatorname{conv}(\mathcal{I})$.  We
are interested in a number of polytopes that arise when we consider various such
sets $\mathcal{I}$.

Denote $\{1,\cdots,n\}$ by $[n]$.  Let $\mathcal{I}_n =
\{\alpha_{i,j}:i,j\in[n], i\le j\}$.  The \emph{complete interval vector
polytope} is defined as $\mathcal{P}({\mathcal{I}_n} ):=$
$\operatorname{conv}(\mathcal{I}_n)$. Computing the Ehrhart polynomials and
volumes of small-dimensional polytopes with the aid of a computer, we notice an
astounding connection. We computed the volume of the first 9 complete interval
vector polytopes, and found that in each case
\begin{equation*}\label{Catalan}
\operatorname{vol}(\P_n({\I})) = C_n
\end{equation*}
where $C_n := \frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}$ is the
$n^{\textrm{th}}$ Catalan number.  We will prove that this is the case for any
$n$.

In \cite{MR2487491}, Postnikov defines the \emph{complete root polytope}
$Q_n\subset\mathbb{R}^n$ as the convex hull of $0$ and $e_i-e_j$ for all $i<j$. 
It is shown that the volume of $Q_{n}$ is $C_{n-1}$, the same as expected for
$\P_{n+1}({\I})$.  In fact, we prove, in a discrete-geometric
sense, that the two polytopes are interchangeable, that is, the two polytopes
have the same Ehrhart polynomial.
\begin{theorem}\label{CompleteRootEquiv}
$L_{Q_{n+1}}(t) = L_{\P_n({\I})}(t)$.\\
\end{theorem}
}

In \cite{MR2825295} Dahl provides a method for determining
the dimension of these polytopes which we will use throughout this paper. 
We utilized the software packages {\tt polymake} \cite{polymake} and {\tt LattE}
\cite{latte,koeppelatte} to find most of the patterns described by our results.

\begin{proof}[Proof of Theorem \ref{CompleteRootEquiv}] Each of the vertices of $Q_n$ are vectors with entries that sum to
zero, so any linear combination (and specifically any convex combination) of
these vertices also has entries who sum to zero.
%\[\sum_i x_i =\sum_j y_j = 0 \Longrightarrow \sum_i ax_i + \sum_j by_j = a\sum_i
%x_i + b\sum_j y_j = 0.\]
Define $B := \{x\in\mathbb{R}^n\, | \, \sum_{i=1}^n x_i = 0\}$; thus $Q_n\subset B$, and 
$B$ is an $(n-1)$-dimensional affine subspace of~$\mathbb{R}^n$.

Consider the linear transformation $T$ given by the $n\times n$ lower triangular
matrix with entries $t_{i,j} = 1$ if $i\ge j$ and $t_{i,j} = 0$ otherwise.  Then
 \[T(B) \subseteq A := \left\{x\in\mathbb{R}^n \, | \, x_n=0\right\}.\]  Since (the matrix representing) $T$ has
determinant 1, it is injective when restricting the domain to $B$.  For the same
reason, we know that for any $y\in A$, there exists $x\in\mathbb{R}^n$ such that
$y=T(x)$.  But since $y_n = \sum_{i=1}^n x_i = 0$, then $x\in B$, so that
$T|_B:B\to A$ is surjective, and therefore a linear bijection.

 Also, the projection $\Pi:A\to \mathbb{R}^{n-1}$ given by
\[\Pi\left((x_1,\ldots, x_{n-1}, 0)\right) = (x_1,\ldots,x_{n-1}),\]
 is clearly a linear bijection.

Now we show that the linear bijection $\Pi\circ T|_{B}: B\to\mathbb{R}^{n-1}$ is
a lattice-preserving map, i.e., an isomorphism from $B \cap \mathbb{Z}^n$ to $\mathbb{Z}^{ n-1 }$ (viewed
as additive groups).  First we find a lattice basis for $B$.  Consider \[C
:= \left\{e_{i,n} = e_i-e_n \, | \, i<n \right\}.\]  We notice that any integer point of $B$ can be
represented as \[\left(a_1,\ldots, a_{n-1}, -\sum_{i=1}^{n-1}a_i\right) =
\sum_{i=1}^{n-1}a_ie_{i,n}\]  and so $C$ is a lattice basis.

Note that $\Pi\circ T(e_{i,n}) = e_i + \cdots + e_{n-1} =: u_i$.  Therefore
\[\Pi\circ T(C) = \{u_i \, | \, i\le n-1\} =: U \, .\]  We notice that $e_{n-1} = u_{n-1}$
and $e_i = u_i - u_{i+1}$, so that each of the standard unit vectors $e_i$ of
$\mathbb{R}^{n-1}$ is an integral combination of the vectors in $U$.  Since the
standard basis is a lattice basis, so is $U$, thus $\Pi\circ T|_{B}$ is a
lattice-preserving map.
Since our bijection is linear and lattice-preserving, all we have left to show
is that the vertices of $Q_n$ map to those of $\P_{n-1}(\I_{[n-1]})$.  By
linearity, $\Pi\circ T(0) = 0$, and  given any vertex $\alpha_{i,j}$ of
$\P_{n-1}(\I_{[n-1]})$, we know that $\Pi\circ T(e_{i,j+1}) = \alpha_{i,j}$
where $i< j+1 \le n$ so that $\Pi\circ T|_{B}$ maps vertices to vertices.
\end{proof}
Corollary \ref{CIPvolume} follows directly from this theorem and \cite{MR2487491}, since the leading coefficient of the Ehrhart polynomial of $\P_{n}$ is $\frac{1}{n!}$ times the volume of~$\P_{n}$.

%--------------------------------------

\section{Fixed Interval Vector Polytopes}\label{fixed}

The following construction is due to \cite{MR2825295}. 
We define the set of \textit{elementary vectors} as containing
all $e_{i,j} = e_i - e_j$, each unit vector $e_i$, and the zero vector.  Let $T$
be the lower triangular matrix from the proof of Theorem
\ref{CompleteRootEquiv}.  We notice that $T(e_i) = \alpha_{i,n}$ and $T(e_{i,j})
= \alpha_{i,j-1}$.  So the image of an elementary vector is an interval vector. 
Since $T$ is invertible, for any set of interval vectors $\mathcal{I}$, there is
a unique set $\mathcal{E}$ of elementary vectors such that $T(\mathcal{E}) =
\mathcal{I}$, namely $  \mathcal{E}=T^{-1}(\mathcal{I})$.

Thus for any interval vector polytope $\mathcal{P}_n(\mathcal{I}_S)\subset\mathbb{R}^{n}$,
we can construct the corresponding \emph{flow-dimension graph} $G_{\mathcal{I}_S}
= (V,E)$ as follows.  Let $\mathcal{E}_S = T^{-1}(\mathcal{I}_S)$.  Let the
vertex set $V = [n]$. Specify a subset $V_1 = \{j\in V \;  | \; 
e_j\in\mathcal{E}_S\}$, and define the directed edge set $E = \{(i,j) \;  | \; 
e_{i,j}\in\mathcal{E}_S\}$. Let $k_0$ denote the number of connected
components $\mathcal{C}$ of the graph $G$ (ignoring direction) so that
$\mathcal{C}\cap V_1 $ is empty.

Recall that the fixed interval vector polytope $\P_n(\I_{i})$
is the convex hull of all interval vectors in $\mathbb{R}^{n}$ with interval length $i$.
For example, the fixed interval vector polytope with $n=5$, $i=3$ is
$$\P_5(\I_{3}) = \operatorname{conv} \big( (1,1,1,0,0) \, , \, (0,1,1,1,0)
\, , \, (0,0,1,1,1) \big)$$
and its flow-dimension graph is depicted in Figure~\ref{flowdim}.

\begin{figure}[htb]
\begin{center}
\includegraphics[scale=.5]{flowdim}
\end{center}
\caption{The flow-dimension graph of $\P_5(\I_{3})$.}\label{flowdim}
\end{figure}

\begin{theorem}[Dahl
%\footnote{Dahl's version of Theorem \ref{graphdimension} in
%\cite{MR2825295} is incorrect.}
 \cite{MR2825295}]\label{graphdimension} % ,Brualdi20131
If $0\in\operatorname{aff}(\I_S)$, then the dimension of $\P_n(\I_S)$ is
$n-k_0$.  Else, if $0\notin\operatorname{aff}(\mathcal{I}_S)$ then the dimension
of $\P_n(\I_S)$ is $n-k_0-1$.
\end{theorem}
For a fixed $i$,
\[
 T^{-1}(\I_{i})=\mathcal{E}_i = \{e_{k,k+i}\;|\;k\le n-i\}\cup\{e_{n-i+1}\} \, .
\]
The corresponding
flow-dimension graph is $G_{\P_n(\I_{i})}=(V,E)$ where $V=\{1,\ldots,n\}$ and
$E = \{ (k,k+i)\,|\,k\in[n-i] \}$.
Then $V_{1}=\{n-i+1\}$ corresponds to $e_{n-i+1}\in\mathcal{E}_i$.

Two nodes $a,b$ in a graph $G=(V,E)$ are said to be \emph{connected} if there
exists a \emph{path} from $a$ to $b$, that is there exist $q_{0}, \dots,
q_{s}\in V$ such that $(a,q_{0}),(q_{0},q_{1}),\dots, (q_{s},b) \in E$.

\begin{lemma}\label{path}
Let $a,b$ be nodes in the flow-dimension graph $G_{\P_n(\I_{i})}$.
Then $a$ and $b$ are connected if and only if $a \equiv b \; \operatorname{mod}i$.
\end{lemma}

\begin{proof}
The edges in $G_{\P_n(\I_{i})}$ are of the form $(k, k+i)$, and therefore the nodes of a path in
$G_{\P_n(\I_{i})}$ are all in the same congruence class modulo~$i$.
\commentout{
Assume without loss of generality $a< b$. Suppose $a$ and $b$ are connected by
the path $q_{0}, \dots, q_{s}\in V$. Therefore by definition of $E$, we have
\begin{align*}
q_{0} &= a + i \\
q_{1} &= q_{0} + i = a + 2i \\
&\ \vdots \\
q_{s} &= q_{s-1} + i = a + (s+1)i \\
b &= q_{s} + i = a + (s+2)i \, .
\end{align*}
Thus $a \equiv b \; \operatorname{mod}i$ by definition. 

Conversely, suppose that $a \equiv b \; \operatorname{mod}i$. Then there
exists $m \in \mathbb{N}$ such that
\[
b = a + mi 
  = a + (m-1)i + i \, .
\]
Since $b$ and $a+(m-1)i$ differ by $i$, then by definition of $E$, there is an
edge between these nodes. Call this edge $(q_{t},b) \in E$. Similarly, we have
\begin{align*}
a + (m-1)i &= a+(m-2)i + i &\Rightarrow& \qquad (q_{t},q_{t-1}) \in E \\
a + (m-2)i &= a+(m-3)i + i &\Rightarrow& \qquad (q_{t-1},q_{t-2}) \in E \\
 \vdots \\
a + 2i &= (a+i) + i  &\Rightarrow& \qquad (q_{1},q_{0}) \in E \\
a + i &= a + i &\Rightarrow& \qquad (q_{0},a) \in E \, .
\end{align*}
Hence $q_0,q_1,\ldots,q_t$ define a path from $a$ to $b$, so $a$ and $b$
are connected.
}
\end{proof}

\begin{proposition}
$\P_n(\I_{i})$ is an $(n-i)$-dimensional simplex.
\end{proposition}

\begin{proof}
For a given dimension and interval length, an interval vector is uniquely
determined by the location of the first 1, hence we can determine the number of
vertices of $\P_n(\I_{i})$ by counting all possible placements of the first
1 in an interval of $i$ 1's.  Since the string must have length $i$, the number
of spaces before the first 1 must not exceed $n-i$ and so there are $n-i+1$
possible locations for the first 1 in the interval to be placed. Thus,
$\P_n(\I_{i})$ has $n-i+1$ vertices.

By Lemma \ref{path} we know there are $i$ connected components in the
flow-dimension graph $G_{\P_n(\I_{i})}$ and since $V_{1}$ has only one
element, $k_{0} = i - 1$. Thus by Theorem \ref{graphdimension} the dimension of
$\P_n(\I_{i})$ is $n - i$. Therefore $\P_n(\I_{i})$ is an
$(n-i)$-dimensional simplex.
\end{proof}

\begin{proof}[Proof of Theorem \ref{unimodular}]
It remains to show that $\P_n(\I_{i})$ is unimodular.
Consider the affine space where the sum over every $i^{\textrm{th}}$ coordinate
is 1,
\[A=\left\{\mathbf{x}\in\mathbb{R}^{n}\;\Bigg|\;\displaystyle{\sum_{j\equiv
k\operatorname{mod}i}}x_{j}=1,\;\text{ for all }\,k\in[i]\right\}.\]
Since the vertices of $\P_n(\I_{i})$ have interval length $i$, they are in
$A$; thus $\P_n(\I_{i})\subset A$. 
We want to show that the following vectors in $\P_n(\I_{i})$ form a
lattice basis for $A$: 
\[
\begin{array}{lrl}
w_1 &=& \alpha_{1,i}- \alpha_{n-i+1,n}\\
w_2 &=& \alpha_{2,i+1}-\alpha_{n-i+1,n}\\
&\vdots&\\
w_{n-i} &=& \alpha_{n-i,n-1}-\alpha_{n - i+1,n} \, . \end{array}\]
We will do this by showing that any integer point $p\in A$ can be expressed as an
integral linear combination of the proposed lattice basis, that is, there exist
integer coefficients $Y_1,\ldots,Y_{n-i}$ so that $p=Y_1w_1 + \cdots +
Y_{n-i}w_{n-i} + \alpha_{n-i+1,n}$.

We first notice that $p$ can be expressed as
\[\left(p_1, p_2, \ldots, p_{n-i}, \sum_{\underset{j\equiv
t-i+1\operatorname{mod}i}{j\le n-i}}(-p_j) + 1,\sum_{\underset{j\equiv
t-i+2\operatorname{mod}i}{j\le n-i}}(-p_j)+ 1, \ldots,\sum_{\underset{j\equiv t
\operatorname{mod}i}{j\le n-i}}(-p_j) + 1\right)\]
by solving for the last term in each of the equations defining $A$. Let
\[Y_t = \left\{\begin{array}{lrl}
	p_1&\text{ if }&t = 1,\\
	p_t - p_{t-1}&\text{ if }&1<t\le i,\\
	p_t - Y_{t-i}&\text{ if }&i<t\le n-i.
\end{array}\right.\]
 Then each $Y_t$ is an integer.  We claim that \[Y_1w_1 + \dots + Y_{n-i}w_{n -
i} + \alpha_{n-i+1,n} = p.\] Clearly the first coordinate is $p_1$ since $w_1$
is the only vector with an element in the first coordinate.  Next consider the
$t^{\text{th}}$ coordinate of this linear combination for $1<t\le i$, by summing
the coefficients of all the vectors who have a 1 in the $t^{\text{th}}$
position:
\[Y_t + Y_{t-1} + Y_{t-2} + \dots + Y_1 = p_t - p_{t-1} + p_{t-1} - p_{t-2} +
\cdots + p_{2} - p_{1} + p_1 = p_t\]
We next consider the $t^{\text{th}}$ coordinate of the combination for $i<t\le
n-i$ by summing the coefficients of the vectors who have a 1 in the
$t^{\text{th}}$ position.
\[Y_t + Y_{t-1} + \cdots + Y_{t-i+1} = (p_t - Y_{t-1} - \dots - Y_{t-i+1}) +
Y_{t-1}  + \dots + Y_{t-i+1} = p_t\]
Finally, we consider the $t^{\text{th}}$ coordinate of the combination for
$n-i<t\le n$, noticing that each coordinate from $w_1$ to $w_t$ has a $-1$ in
the $(t-i)^{\text{th}}$ position, and $\alpha_{n-i+1,n}$ has a 1 in this
position.  This gives 
\[-(Y_1 + Y_2 + \dots + Y_{t-i}) + 1.\]
Applying the two relations we have defined between coordinates, and calling
$\langle t\rangle$ the least residue of $t\operatorname{mod}i$, we see that
\begin{eqnarray*}
-(Y_1 + Y_2 + \dots + Y_{t-i}) + 1 &=& -(Y_1 + Y_2 + \dots + Y_{t-2i} + p_{t-i})
+ 1\\
&=& - (Y_1 + Y_2 + \dots + Y_{t-3i} + p_{t-2i} + p_{t-i}) + 1\\
&=& - \left(Y_1 + Y_2 + \dots + Y_{\langle t\rangle} + \sum_{\underset{j\equiv
t\operatorname{mod}i}{i<j\le n-i}}p_j\right) + 1\\
&=&-\left(\sum_{\underset{j\equiv t\operatorname{mod}i}{j\le n-i}}p_j\right) +
1.
\end{eqnarray*}
Thus $p = Y_1w_1 + Y_2w_2 + \dots + Y_{n-i}w_{n-i} + \alpha_{n-i+1,n}$ and so
$w_1,\ldots,w_{n-i}$ form a lattice basis of $A$.
Thus the vertices of $\P_n(\I_{i})$ form a lattice basis, and so $\P_n(\I_{i})$ is a unimodular simplex.
\end{proof}

\commentout{
\begin{proof}
Consider the affine space where the sum over every $i^{\textrm{th}}$ coordinate
is 1,
\[A=\left\{\mathbf{x}\in\mathbb{R}^{n}\;\Bigg|\;\displaystyle{\sum_{j\equiv
k\operatorname{mod}i}}x_{j}=1,\;\forall\,k\in[i]\right\}.\]
Since the vertices of $\P_n(\I_{i})$ have interval length $i$, they are in
$A$. Thus $\P_n(\I_{i})\subset A$. Define the projection
$\Pi:A\rightarrow\mathbb{R}^{n-i}$ by truncating the last $i$ coordinates of a
vector in $A$. Since $\P_n(\I_{i}) \subset A$, we can solve for the last
$i$ components in terms of the other $n-i$ components using the equations
defining $A$, hence $\Pi$ is a bijection. $\Pi$ is lattice-preserving, thus the
volume of $\Pi(\P_n(\I_{i}))$ is equal to the volume of
$\P_n(\I_{i})$. 

$\Pi$ transforms the vertices of $\P_n(\I_{i})$ to
$\{(v'_{1},\dots,v'_{n-i+1}) \}$, where $v'_{k}$ has the first 1 starting in the
$k^{\textrm{th}}$ position and $v'_{n-i+1}$ is the zero vector. Cayley and
Menger\cite{MR2141304} show that the volume of this simplex is the determinant
of the following matrix
$$\begin{bmatrix}
v'_{1}-v'_{n-i+1} & v'_{2}-v'_{n-i+1} & v'_{3}-v'_{n-i+1} & \dots &
v'_{n-i}-v'_{n-i+1} \\
\end{bmatrix}.$$ Since $v'_{n-i+1}$ is the zero vector, that amounts to finding
the determinant of the matrix
$$\begin{bmatrix}
1 &  & \multicolumn{2}{c}{\text{\kern-1.50em\smash{\raisebox{-2ex}{\Huge 0}}}}
\\
 & \ddots & \\
\multicolumn{2}{c}{\text{\kern -.75em\smash{\raisebox{0ex}{\Huge B}}}}& & 1 \\
 \end{bmatrix}, $$
where B is some combination of 0's and 1's. The determinant of this matrix is 1.
 Thus the volume of this simplex is 1 and so $\P_n(\I_{i})$ is a unimodular
simplex.
%\newline To prove $\{(v'_{1},\dots,v'_{n-i+1}) \}$ is a lattice basis for
$\mathbb{R}^{n-i+1}$ we will prove that all of the standard basis vectors can be
written as a integer combination of $\{(v'_{1},\dots,v'_{n-i+1}) \}$.
%{\bf Claim:} $e_{j} = 0v'_{1} + \dots + 0v'_{j-1} + v'_{j} - v'_{j+1} +
0v'_{j+2} + \dots + 0v'_{j+i-1}+v'_{j+i} - 'v_{j+i+1} + \dots +
v'_{j+hi}-v'_{j+hi+1}$ 
%\newline where $j+hi < n-i < j + (hi + 1)i$.
%\newline
%\newline {\bf Proof} Since  $j+hi < n-i < j + (hi + 1)i$ we have $n-2i < j+hi <
n-i$ so $v_{j+hi} \in \{ ( v_{1}, \dots v_{n-i+1} ) \}$ and $v_{j+hi+1} \in \{ (
v_{1}, \dots v_{n-i+1} ) \}$ and since $v_{j+hi} > 2n-i$ the vectors are all of
the form $(0, \dots, 0, 1, \dots, 1)$ where the interval is of length
$(n-i)-k+1$. Thus $v_{j+hi+1}$ has its first 1 one component later than
$v_{j+hi}$ and has interval length 1 less than $v_{j+hi}$. Hence $v_{j+hi} -
v_{j+hi+1} = (0, \dots,0,1,0,\dots,0)$ where the 1 occurs in the $({j+hi})$-th
position.
%\newline
%\newline For all $v_{k}$ where $k<2n-i \; v_{k}$ is of the form
(0,\dots,1,\dots,1,0,\dots,0) where the interval begins in the k-th position and
is of length i.  Therefore 
%\newline $v_{j}-v_{j+1} = (0,\dots,0,1,0,\dots,0,-1,0,\dots)$ where the 1 is in
the $j$-th position and the -1 is in the $(j+i)$-ith position. Hence
$(v_{j}-v_{j+1})+(v_{j+i}-v_{j+i+1})$ will have a one in the $j$-th position and
a -1 in the $(j+2i)$-th position, continue this process until -1 is in the
$(j+hi)$-th position where $j+hi > n-2i$ Then by the above work
$v_{j+hi}-v_{j+hi+1}$ will have a one in the $(j+hi)$-th position and zeros
elsewhere and so
%$e_{j} = 0v'_{1} + \dots + 0v'_{j-1} + v'_{j} - v'_{j+1} + 0v'_{j+2} + \dots +
0v'_{j+i-1}+v'_{j+i} - 'v_{j+i+1} + \dots + v'_{j+hi}-v'_{j+hi+1}$. 
%Hence $\{(v'_{1},\dots,v'_{n-i+1}) \}$ is a lattice basis of $\mathbb{R}^{n}$
and so $\P_n(\I_{i})$ is a unimodular simplex by Theorem.
\end{proof}
}

%--------------------------------------

\section{The first pyramidal interval vector polytope}\label{pyramid}

Recall that $\P_{n}(\I_{1,n-1})$ is the convex hull of all
vectors in $\mathbb{R}^{n}$ with interval length 1 or $n-1$.
For example,
$$ \P_{4}(\I_{1,3}) = \operatorname{conv} \big( (1,0,0,0) \, , \,(0,1,0,0) \, ,
\,(0,0,1,0) \, , \,(0,0,0,1) \, , \,(1,1,1,0) \, , \,(0,1,1,1) \big) \, , $$
whose flow-dimension graph is depicted in Figure~\ref{firstpyramidflowgraph}.

\begin{figure}[htp]
\begin{center}$\includegraphics[scale=.3]{graph1}$\end{center}
\caption{$G_{\P_{n}(\I_{1,n-1})}$.}\label{firstpyramidflowgraph}
\end{figure}

\begin{proposition}\label{dimension}
The dimension of $\P_{n}(\I_{1,n-1})$ is $n$.
\end{proposition}

\begin{proof}
The affine hull of $e_1, \dots, e_n$ is the $(n-1)$-dimensional set
\[
  \left\{ x \in \RR^n \, | \, x_1 + \dots + x_n = 1 \right\} . 
\]
Since $\alpha_{ 1,n-1 }$ is not in this set, $\dim(\P_{n}(\I_{1,n-1})) = n$. 
\commentout{
For $n\ge 3$, the vertices of $\P_{n}(\I_{1,n-1})$ form the set
$$\mathcal{I}=\left\{\begin{matrix}
e_1 &= (1, 0,\dots, 0, 0)\\
e_2 &= (0, 1,\dots, 0, 0)\\
\vdots\\
e_n &= (0, 0, \dots, 0, 1)\\
\alpha_{1,n-1} &= (1, 1,\dots, 1, 0)\\
\alpha_{2,n} &= (0, 1,\dots, 1, 1)
\end{matrix}\right\}.$$ We convert the interval vectors to the corresponding
elementary vector set \[\mathcal{E} = \{e_{1,2}, e_{2,3}, \ldots, e_{n-1,n},
e_{1,n}, e_2, e_n\}.\]  From this we construct the flow-dimension graph    
$G_{\P_{n}(\I_{1,n-1})} = (V,E)$ as seen in Figure 1, where $V = [n]$ and \[E =
\{(k,k+1)|k\in[n-1]\}\cup\{(1,n)\}\] corresponding to each $e_{i,j}$ in
$\mathcal{E}$.  The subset of vertices $V_1 = \{2, n\}$ (circled in Figure 1)
corresponds to each $e_i$ in $\mathcal{E}$.  Since the underlying graph is
connected, we know \[k_0=\;\#\{\textrm{connected components }C\text{ in
}G_{\P_{n}(\I_{1,n-1})}\text{ such that }C\cap V_1=\emptyset\} = 0.\]
%not doing ref because it numbers funny
Next we notice that
\[\frac{1}{n-2}e_1 + \frac{1}{n-2}e_2+\dots+\frac{1}{n-2}e_{n-1} -
\frac{1}{n-2}\alpha_{1,n-1} = \mathbf{0}\]
where the sum of the coefficients is
\[\frac{n-1}{n-2} - \frac{1}{n-1} = \frac{n-2}{n-2} = 1\]
So $\mathbf{0}\in\operatorname{aff}(\mathcal{I})$ and by Theorem
\ref{graphdimension}, $\operatorname{dim}(P_{n,1}) = n-k_0 = n$.
}
\end{proof}

%\subsection{$f$-Vectors of $\mathcal{P}_{n,1}$}

Recall that the $f$-vector of a polytope tells us the number of faces the polytope
has of each dimension. Our next task is to compute the $f$-vector of
$\P_{n}(\I_{1,n-1})$.

\commentout{
with $n\ge 3$, is precisely the $n^{\textrm{th}}$ row of the Pascal 3-triangle
without 1's. The \emph{Pascal 3-triangle} is an analogue of Pascal's Triangle,
where the third row, instead of being 1 2 1, is replaced with 1 3 1, and then
the same addition pattern is followed as in Pascal's triangle.
}

\begin{lemma}\label{subdimension}
Let  $n\ge 3$.  Then
$\mathcal{B} := \operatorname{conv}(e_1, e_n, \alpha_{1,n-1},\alpha_{2,n})$ is a
2-dimensional face of $\P_{n}(\I_{1,n-1})$.
\end{lemma}

\begin{figure}[htb]
\label{Figure 2}
\begin{center}
\includegraphics[scale=.3]{jerry.pdf}
\end{center}
\caption{$G_{\mathcal{A}}$.}
\end{figure}

\begin{proof}
We first consider
$\mathcal{A}=\operatorname{conv}(e_n,\alpha_{1,n-1},\alpha_{2,n})$.  The
corresponding elementary vectors of the vertex set are $\{e_{1,n}, e_2, e_n\}$. 
So we build the flow-dimension graph as seen in Figure 2, $G_{\mathcal{A}} =
(V,E)$ where $V = [n]$, $E = \{(1,n)\}$ corresponding to $e_{1,n}$. The subset
$V_1 = \{2, n\}$ (circled in Figure 2) corresponds to $e_2$ and $e_n$.  This
graph has $n-1$ connected components, two of which contain elements of $V_1$ so
that $k_0 = n-3$.

If we let $\lambda_1 e_n + \lambda_2 \alpha_{1,n-1} + \lambda_3 \alpha_{2,n} =
\mathbf{0}$, we first notice that $\lambda_2 = 0$ since $\alpha_{1,n-1}$ is the
only vector with a nonzero first coordinate.  But this implies that $\lambda_1 =
\lambda_3 = 0$.  Since the coefficients cannot sum to 1, we conclude that
$\mathbf{0}\notin\operatorname{aff}(e_n, \alpha_{1,n-1}, \alpha_{2,n})$.
So now by Theorem \ref{graphdimension},
\[\operatorname{dim}(\operatorname{conv}(e_n, \alpha_{1,n-1}, \alpha_{2,n})) = n
- k_0 - 1 = n-(n-3) - 1 = 2.\] Finally $e_1 = (1) \alpha_{1,n-1} + (-1)
\alpha_{2,n} + (1)e_n$ is in the affine hull of $\mathcal{A}$ and thus does not add a dimension.  We conclude that $\operatorname{dim}(\mathcal{B}) = 2$.
\end{proof}

\begin{corollary}\label{dimsum}
Let  $\mathcal{I}:=
\{e_1,e_2,\ldots,e_n,\alpha_{1,n-1},\alpha_{2,n}\}$ .  For $2\le
i\le n-1$  each $e_i$ adds a dimension to $\P_{n}(\I_{1,n-1})$, that is,
$e_i\notin\operatorname{aff}(\mathcal{I}\setminus\{e_i\})$.
\end{corollary}
\begin{proof}
This follows from Proposition \ref{dimension} and Lemma \ref{subdimension}.  Since
$\mathcal{B}$ has dimension $2$ and $\P_{n}(\I_{1,n-1})$ has dimension $n$, then
the $n-2$ remaining vertices must add the remaining $n-2$ dimensions. 
\end{proof}

\begin{lemma}\label{basefvector} Let $\mathcal{B}$ as in Lemma
\ref{subdimension}. Then $\mathcal{B}$ has $f$-vector $(1,4,4,1)$.
\end{lemma}

\begin{proof}
Since $\mathcal{B}$ has dimension 2, $f_1 = f_0$.  We know that
$\{e_n,\alpha_{1,n-1},\alpha_{2,n}\}$ are three vertices of $\mathcal{B}$.  If
$e_1\in\operatorname{conv}(e_n,\alpha_{1,n-1},\alpha_{2,n})$ then
\begin{equation}\label{e}e_1 = \lambda_1 e_n + \lambda_2 \alpha_{1,n-1} +
\lambda_3 \alpha_{2,n}\end{equation} where the coefficients sum to 1.  Since
$\alpha_{1,n-1}$ is the only vector with a nonzero coordinate in the first
position,  $\lambda_2 = 1.$ This in turn implies that $\lambda_1 =
\lambda_3 = 0$, contradicting (\ref{e}).  So
$e_1\notin\operatorname{conv}(e_n,\alpha_{1,n-1},\alpha_{2,n})$ and therefore
forms a fourth vertex. 
\end{proof}
We can tie all this together with the following theorem.  First we define a
\textit{d-pyramid} $P$ as the convex hull of a
$(d-1)$-dimensional polytope $K$ (the \textit{basis} of $P$) and a point
$A\notin\operatorname{aff}(K))$ (the \textit{apex} of $P$).
\begin{theorem}[see, e.g., \cite{MR1976856}]\label{facenumbers}
If $P$ is a $d$-pyramid with  basis $K$ then
\begin{eqnarray*}
f_0(P) &=& f_0(K) + 1\\
f_k(P) &=& f_k(K) + f_{k-1}(K)\hspace{10pt}\text{ for }1\le k\le
d-2\\
f_{d-1}(P) &=& 1 + f_{d-2}(K) \, .
\end{eqnarray*}
\end{theorem}
We notice that the rows of Pascal's 3-triangle act in the same manner and we
claim the face numbers for $\P_{n}(\I_{1,n-1})$ can be derived from Pascal's
3-triangle.

\begin{proof}[Proof of Theorem \ref{fvector}]
Recall that $\mathcal{I} = \{e_1,e_2,\ldots,e_n,\alpha_{1,n-1},\alpha_{2,n}\}$ is the
vertex set for $\P_{n}(\I_{1,n-1})$ with $n\ge 3$, and let $\mathcal{R}_{k} :=
\operatorname{conv}(\mathcal{I}\setminus\{e_{k},e_{k+1},\ldots,e_{n-1}\})$ for
$1\le k<n$.  Then it is clear that $\P_{n}(\I_{1,n-1})$ is the convex hull of the
union of the $(n-1)$-dimensional polytope $\mathcal{R}_{n-1}$ and
$e_{n-1}\notin\operatorname{aff}(\mathcal{R}_{n-1})$ (by Corollary
\ref{dimsum}), and thus is a pyramid and its face numbers can be computed as in
Theorem \ref{facenumbers} from the face numbers of $\mathcal{R}_{n-1}$.

Notice next that $\mathcal{R}_{n-1}$ is the convex hull of the
$(n-2)$-dimensional polytope $\mathcal{R}_{n-2}$ and
$e_{n-2}\notin\operatorname{aff}(\mathcal{R}_{n-2})$ (again by Corollary
\ref{dimsum}), so we can compute the face numbers of $\mathcal{R}_{n-1}$ from
those of $\mathcal{R}_{n-2}$ as in Theorem \ref{facenumbers}.

We can continue this process until we get that $\mathcal{R}_{3}$ is the convex
hull of $\mathcal{R}_2$ and $e_2\notin\operatorname{aff}(\mathcal{R}_2)$.  But
we notice that $\mathcal{R}_2 = \mathcal{B}$, so by Lemma \ref{basefvector},
$f_0(\mathcal{R}_2) = f_1(\mathcal{R}_2) = 4$.  From here we can build the 
$f$-vector of $\P_{n}(\I_{1,n-1})$ recursively, using Theorem \ref{facenumbers}.
\end{proof}

%\section{Volume of $\P_{n}(\I_{1,n-1})$}\label{volumepyramid}

Our next goal is to compute the volume of $\P_{n}(\I_{1,n-1})$.
A simple induction proof gives:

\begin{lemma}\label{A2}
The determinant of the $n\times n$-matrix
\[\begin{bmatrix}0 & 1 & 1 & \cdots & 1\\1 & 0 & 1 & \cdots & 1\\ & & \ddots & &
\\1 & \cdots & 1 & 0 & 1\\1 & 1 & \cdots & 1 & 0\end{bmatrix}\] is
$(-1)^{n-1}(n-1)$.\end{lemma}

\commentout{
\begin{proof}
Let $A_{n}$ be the $n\times n$ matrix whose diagonal entries are $0$, and all
entries off the diagonal are $1$. E.g.,\\
$$A_{2}=\begin{bmatrix} 0 & 1 \\ 1 & 0\end{bmatrix}$$
and so $\operatorname{det}(A_{2})=-1$. Assume
$\operatorname{det}(A_{k})=(-1)^{k-1}(k-1)$. $A_{k+1}$ is the
$(k+1)\times(k+1)$-matrix of the form
$$A_{k+1}=\begin{bmatrix}0 & 1 & \cdots & 1 & 1\\1 & 0 & 1 & \cdots & 1\\ & &
\ddots & & \\1 & 1 & \cdots & 0 & 1\\1 & 1 & \cdots & 1 & 0\end{bmatrix}.$$
Subtracting the second row from the first, which does not change the value of
the determinant, will give us the matrix 
$$\begin{bmatrix}-1 & 1 & 0 & \cdots & 0\\1 & 0 & 1 & \cdots & 1\\ & & \ddots &
& \\1 & 1 & \cdots & 0 & 1\\1 & 1 & \cdots & 1 & 0\end{bmatrix}.$$
Now the determinant of $A_{k+1}$ is the sum of two determinants by cofactor
expansion. Specifically it is $(-1)\operatorname{det}(A_{k})$ minus the
determinant of the matrix obtained by taking out the first row and second
column. We know that $(-1)\operatorname{det}(A_{k})=(-1)^{k}(k-1)$ by the
inductive hypothesis. So what we have left to compute is the determinant of the
$(k\times k)$-matrix
$$\begin{bmatrix}1 & 1 & \cdots & 1 & 1\\1 & 0 & 1 & \cdots & 1\\ & & \ddots & &
\\1 & 1 & \cdots & 0 & 1\\1 & 1 & \cdots & 1 & 0\end{bmatrix}.$$
We will subtract the first row from each of the rows below it, also not changing
the determinant, to give us the upper triangular matrix
$$\begin{bmatrix}1 & 1 & \cdots & 1 & 1 & 1\\0 & -1 & 0 & \cdots & 0 & 0\\0 & 0
& -1 & 0 & \cdots & 0\\ & & & \ddots & & \\0 & 0 & \cdots & 0 & -1 & 0\\0 & 0 &
\cdots & 0 & 0 & -1\end{bmatrix}$$
whose determinant is $(-1)^{k-1}$. Furthermore,
\begin{align*}\operatorname{det}(A_{k+1})&=(-1)\operatorname{det}(A_{k})-(-1)^{
k-1}\\
&=(-1)^{k}(k-1)+(-1)^{k}\\
&=(-1)^{k}k.\end{align*} 
Therefore, by induction, $\operatorname{det}(A_n)=(-1)^{n-1}(n-1),$ for all
$n\in \mathbb{Z}_{\ge 2}$.\end{proof}
}

\begin{proof}[Proof of Theorem \ref{volpyramid}]
In order to calculate the volume of $\P_{n}(\I_{1,n-1})$ we will first
triangulate the $2$-dimensional base of the pyramid $\mathcal{B}$ from Lemma
\ref{subdimension}: namely, $\mathcal{B}$ is the union of  
\[\triangle_1=\operatorname{conv}(
e_{1},e_{n},\alpha_{1,n-1}) \qquad \text{ and } \qquad \triangle_2=\operatorname{conv}(
e_{n},\alpha_{1,n-1},\alpha_{2,n}).\] 

\commentout{
Let $x$ be a point in the base, then for
some $\lambda_{i}\ge 0,$ where $\displaystyle{\sum_{i=1}^{4}\lambda_{i}=1},$
\begin{align*}
x&=\lambda_{1}e_{1}+\lambda_{2}e_{n}+\lambda_{3}\alpha_{1,n-1}+\lambda_{4}
\alpha_{2,n}\\
&=(\lambda_{1}+\lambda_{3},\lambda_{3}+\lambda_{4},\cdots,\lambda_{3}+\lambda_{4
},\lambda_{2}+\lambda_{4})\\
&=(\lambda_{1}-\lambda_{4})e_{1}+(\lambda_{2}+\lambda_{4})e_{n}+(\lambda_{3}
+\lambda_{4})\alpha_{1,n-1}\\
&=(\lambda_{1}+\lambda_{2})e_{n}+(\lambda_{1}+\lambda_{3})\alpha_{1,n-1}
+(\lambda_{4}-\lambda_{1})\alpha_{2,n}.
\end{align*}
So $x$ is a point in $\triangle_1$ if $\lambda_{1}\ge\lambda_{4}$ and $x$ is a
point in $\triangle_2$ if $\lambda_{4}\ge \lambda_{1}$. Thus $\triangle_1$ and
$\triangle_2$ is a triangulation of the $2$-dimensional base of the pyramid.
}

By Corollary \ref{dimsum}, each $e_{2},\dots,e_{n-1}$ adds a dimension so that
the convex hull of these points and $\triangle_1$ is an $n$-dimensional simplex.
The same can be said of $\triangle_2$. Call these simplices $S_1$ and $S_2$
respectively; thus $S_1$ and $S_2$ triangulate $\P_{n}(\I_{1,n-1})$, and
the sum of their volumes is equal to the volume of $\P_{n}(\I_{1,n-1})$. In order
to calculate the volume of $S_1$ and $S_2$, we will use the Cayley Menger
determinant \cite{MR2141304}. Consider $S_1$, whose volume is the
determinant of the matrix
$$\begin{bmatrix}e_1-\alpha_{1,n-1} & e_2-\alpha_{1,n-1} & \cdots &
e_{n}-\alpha_{1,n-1}\end{bmatrix}=\begin{bmatrix}0 & -1 & -1 & \cdots & -1 &
-1\\-1 & 0 & -1 & \cdots & -1 & -1\\-1 & -1 & 0 & -1 & \cdots & -1\\ & &  &
\ddots & & \\-1 & -1 & \cdots & -1 & 0 & -1\\0 & 0 & 0 & \cdots & 0 &
1\end{bmatrix}.$$
Cofactor expansion on the last row will leave us with the determinant, up to a
sign, of the $(n-1)\times(n-1)$ matrix
\begin{equation}\label{A}\begin{bmatrix}0 & -1 & -1 & \cdots & -1\\-1 & 0 & -1 &
\cdots & -1\\ & & \ddots & & \\-1 & \cdots & -1 & 0 & -1\\-1 & -1 & \cdots & -1
& 0\end{bmatrix},\end{equation}
which, when ignoring sign, by Lemma \ref{A2} is $n-2$. Therefore the volume of
$S_1$ is $n-2$.

\commentout{
Now consider the Cayley Menger determinant of $S_2$, the determinant of
$$\begin{bmatrix}\alpha_{1,n-1}-\alpha_{2,n} & e_{2}-\alpha_{2,n} &
e_3-\alpha_{2,n} & \cdots & e_n-\alpha_{2,n}\end{bmatrix}=\begin{bmatrix}1 & 0 &
0 & 0 & \cdots & 0 \\0 & 0 & -1 & -1 & \cdots & -1\\0 & -1 & 0 & -1 & \dots &
-1\\ & &  & \ddots & & \\0 & -1 & -1 & \cdots & 0 & -1 \\-1 & -1 & -1 & \cdots &
-1 & 0\end{bmatrix}.$$
By cofactor expansion on the first row we are left with the positive determinant
of the matrix (\ref{A}) which is $n-2$. Therefore 
}

A similar computation gives the volume of $S_2$ as $n-2$,
and so the volume of $\P_{n}(\I_{1,n-1})$ is $2(n-2),$ as desired.
\end{proof}

\commentout{
Similar reasoning allows us to make the following conjectures:

If $\frac{n}{2}\ge 2$ the number of $k$-faces for $P_{n,2}$ is 
\[\begin{pmatrix}n-2\\k-1\end{pmatrix} + 2\begin{pmatrix}n-1\\k\end{pmatrix} +
\begin{pmatrix}n+1\\k+1\end{pmatrix}\]

If $\frac{n}{2}\ge 3$ the number of $k$-faces for $P_{n,3}$ is 
\[3\begin{pmatrix}n-2\\k-1\end{pmatrix} + 3\begin{pmatrix}n-1\\k\end{pmatrix} +
\begin{pmatrix}n+1\\k+1\end{pmatrix}\]

If $\frac{n}{2}\ge 4$ the number of $k$-faces for $P_{n,4}$ is 
\[\begin{pmatrix}n-3\\k-4\end{pmatrix} + 15\begin{pmatrix}n-3\\k-3\end{pmatrix}
+ 35\begin{pmatrix}n-3\\k-2\end{pmatrix} +
28\begin{pmatrix}n-3\\k-1\end{pmatrix} + 8\begin{pmatrix}n-3\\k\end{pmatrix} +
\begin{pmatrix}n-2\\k+1\end{pmatrix}\]
It is interesting to note that the $f-vectors$ for $P_{n,1}$ are all symmetric. 
Though this is not the case when $i>1$.

There are a few more interesting observations to be made.  It is easy to see
that the number of vertices of $\mathcal{P}_{n,i}$ is $2n - i + 1$ ($n$ unit
vectors and $n-i+1$ interval vectors with interval length $i$).  In every case
we checked we noticed that the number of faces of $P_{n,i}$ is the number of
vertices plus the $i^\text{th}$ triangle number, that is $2n - i + \frac{(i-1)(i)}{2}$. 
We conjecture that this is also the case in general.

Finally, we noticed that for $n = 2i$, the number of edges or $1$-faces of
$\mathcal{P}_{n,i}$ a shift of 9 times the $n^{\textrm{th}}$ triangle number,
specifically: $\frac{(i)(9i-1)}{2}$.

We hope to be able to generalize and prove these conjectures.
}

%--------------------------------------

\section{The $i^\text{th}$ pyramidal interval vector polytope}\label{conjectures}

Recall that the $i^\text{th}$ pyramidal interval vector polytope is $\P_n(\I_{1,n-i})$, the convex hull of all interval vectors in $\RR^n$ with interval length $1$ or $n-i$. 

\begin{example}For $n=6$ and $i=2$,
\begin{align*}
  \P_6(\I_{1,4})
  = \operatorname{conv}\big(&(1,0,0,0,0,0)\,,\,(0,1,0,0,0,0)\,,\,(0,0,1,0,0,0)\,,\,(0,0,0,1,0,0)\\
                            &(0,0,0,0,1,0)\,,\,(0,0,0,0,0,1)\,,\,(1,1,1,1,0,0)\,,\,(0,1,1,1,1,0)\\
                            &(0, 0,1,1,1,1)\big) \, .
\end{align*}
\end{example}

The following proposition collects certain properties of $\P_n(\I_{1,n-i})$. 
We omit its proof, since it is similar to the proofs in Section \ref{pyramid}.

\begin{proposition}
The dimension of $\P_n(\I_{1,n-i})$ is $n$.
Furthermore, $\P_n(\I_{1,n-i})$ can be constructed by taking iterative pyramids (with the
sequence of top vertices $e_{i+1},e_{i+2},\ldots,e_{n-i}$) over the
$2i$-dimensional base
\[\operatorname{conv}\left(\{e_1,e_2,\ldots,e_i,e_{n-i+1},\ldots,e_n
,\alpha_{1,n-i},\alpha_{2,n-i-1}\ldots,\alpha_{i+1,n}\}\right).\]
\end{proposition}

\commentout{
\begin{proof} Let
\[\mathcal{I}=\{e_1,e_2,\ldots,e_n,\alpha_{1,n-i},\alpha_{2,n-i+1},\ldots,
\alpha_{i+1,n}\}.\] Then $\mathcal{P}_{n,i}=\operatorname{conv}(\mathcal{I})$.
The interval vectors of $\mathcal{I}$ correspond to
\[\mathcal{E}=\{e_{1,2},e_{2,3},\ldots,e_{n-1,n},e_n,e_{1,n-i+1},e_{2,n-i+2},
\ldots,e_{i,n},e_{i+1}\}.\] Now let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ where
\begin{align*}V&=[n]\\ E_1&=\{(j,j+1)\,|\,j<n\}\\ E_2&=\{(j,j+n-i)\,|\,j\le
i\}.\end{align*} Then the flow-dimension graph $G_{\mathcal{P}_{n,i}}=G_1\cup
G_2$. Since $e_n,e_{i+1}\in\mathcal{E}$, then $V_1=\{n,i+1\}$. Notice that
$G_{\mathcal{P}_{n,i}}$ is connected, so the number of connected components that
don't intersect $V_1$ is $k_0=0$.\\
Notice that $(1)\alpha_{1,n-i}+(-1)\alpha_{2,n-i+1}+(1)e_{n-i}=\mathbf{0}$
resulting in $\mathbf{0}\in\operatorname{aff}(\mathcal{P}_{n,i})$. Therefore by
Theorem \ref{graphdimension} of Dahl
\[\operatorname{dim}(\mathcal{P}_{n,i})=n-k_0=n.\]
\end{proof}

\begin{lemma}
For any $k$ such that $i<k\le n-i$,
$e_k\not\in\operatorname{aff}\left(\mathcal{P}_{n,i}\setminus\{e_k\}\right)$.
\end{lemma}

\begin{proof}
Assume $e_k\in\operatorname{aff}\left(\mathcal{P}_{n,i}\setminus\{e_k\}\right)$
where $i<k\le n-i$. Then there exist
$\{x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_{i+1}\}\setminus\{x_k\}\subset\mathbb{R}$
such that
\[x_1e_1+x_2e_2+\cdots+x_{k-1}e_{k-1}+x_{k+1}e_{k+1}+\cdots+x_ne_n+y_1\alpha_{1,
n-i}+y_2\alpha_{2,n-i+1}+\cdots+y_{i+1}\alpha_{i+1,n}=e_k.\] Then since all but
the $k^{\textrm{th}}$ coordinate sums to 0, for each $j\in[n]\setminus\{k\}$
\begin{equation}\label{ekaff}x_j+\sum_{\{m\in[i+1]\,|\,m\le j\le
n-i-m+1\}}y_m=0.\end{equation}
Each $\alpha_{a,n-i-a+1}$ has a 1 in $n-i$ positions, notably every
$\alpha_{a,n-i-a+1}$ has a 1 in the $k^{\textrm{th}}$ position. Thus
(\ref{ekaff}) yields $n-i-1$ appearances of $y_1,y_2,\ldots,y_{i+1}$ and since
each $\alpha_{a,n-i-a+1}$ has a 1 in the $k^{\textrm{th}}$ position
\[y_1+y_2+\cdots+y_{i+1}=1.\]
Taking the sum of each of the $n-1$ equations from (\ref{ekaff}) we have
\begin{align*}
x_1+\cdots+x_{k-1}+x_{k+1}+\cdots+x_n+(n-i-1)(y_1+\cdots+y_{i+1})&=0\\
x_1+\cdots+x_{k-1}+x_{k+1}+\cdots+x_n+(y_1+\cdots+y_{i+1}
)&=-(n-i-2)(y_1+y_2+\cdots+y_{i+1})\\
x_1+\cdots+x_{k-1}+x_{k+1}+\cdots+x_n+(y_1+\cdots+y_{i+1})&=-(n-i-2)(1)\\
x_1+\cdots+x_{k-1}+x_{k+1}+\cdots+x_n+(y_1+\cdots+y_{i+1})&=i+2-n\end{align*}
Since $e_k\in\operatorname{aff}\left(\mathcal{P}_{n,i}\setminus\{e_k\}\right),$
the sum of the coefficients is 1. Also $n>2$ and $i\le\frac{n}{2}$ so we have
\begin{align*}
x_1+x_2+\cdots+x_{k-1}+x_{k+1}+\cdots+x_n+(y_1+y_2+\cdots+y_{i+1})&=i+2-n\\
&\le \frac{n}{2}-n+2\\
&=2-\frac{n}{2}\\
&< 2-1\\
&=1
\end{align*}
The sum of the coefficients, $i+2-n\not=1$ and here lies the contradiction.
Therefore $e_k\not\in\operatorname{aff}(\mathcal{P}_{n,i}\setminus\{e_k\})$.
\end{proof}

\begin{corollary} Let
\[\mathcal{B}=\operatorname{conv}\left(\{e_1,e_2,\ldots,e_i,e_{n-i+1},\ldots,e_n
,\alpha_{1,n-i},\alpha_{2,n-i-1}\ldots,\alpha_{i+1,n}\}\right).\] Then adding
each vector in $\{e_{i+1},e_{i+2},\ldots,e_{n-i}\}$ sequentially pyramids over
the previous base.\end{corollary}
\begin{corollary}$\operatorname{dim}(\mathcal{B})=2i$.\end{corollary}
}

Using {\tt polymake} to generate $f$-vectors for varying $n$, we observed 
that the $f$-vectors of $\P_n(\I_{1,n-i})$
correspond to the sum of multiple shifted Pascal triangles; this is again due to its pyramid
property. 
We also offer the following:

\begin{conjecture}
The volume of $\P_n(\I_{1,n-i})$ equals $2^{i}(n-(i+1))$.
\end{conjecture}

We conjecture something more concrete: 
namely, that $\P_n(\I_{1,n-i})$
can be triangulated into $2^{i}$ simplices, and pyramiding over each of these
simplices each yields a volume of $n-(i+1)$.

%--------------------------------------

\subsection*{Acknowledgements}

\thanks{We thank the creators and maintainers of the software packages {\tt
polymake} \cite{polymake} and {\tt LattE} \cite{latte,koeppelatte}, which were
indispensable for our project.
We also thank an anonymous referee for helpful suggestions, and Ricardo Cortez and the staff at MSRI for creating an ideal research environment at MSRI-UP. 
This research was partially supported by the NSF through the grants DMS-1162638 (Beck) and DMS-1156499 (MSRI-UP REU), and by the NSA through grant H98230-11-1-0213.}

%--------------------------------------

\bibliographystyle{plain}  
%\bibliography{MyBibliography}  

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{ccd}
Matthias Beck and Sinai Robins, \emph{Computing the continuous discretely:
  Integer-point enumeration in polyhedra}, Undergraduate Texts in Mathematics,
  Springer, New York, 2007, Electronically available at \url{http://math.sfsu.edu/beck/ccd.html}.

\bibitem{MR2825295}
Geir Dahl, \emph{Polytopes related to interval vectors and incidence matrices},
  Linear Algebra Appl. \textbf{435} (2011), no.~11, 2955--2960. Correction in:
  Linear Algebra Appl. {\bf 438} (2013), no.~1, 1--6.

\bibitem{MR2141304}
Carlos D'Andrea and Mart\'in Sombra, \emph{The {C}ayley--{M}enger determinant
  is irreducible for {$n\geq 3$}}, Sibirsk. Mat. Zh. \textbf{46} (2005), no.~1,
  90--97.

\bibitem{latte}
Jes{\'u}s~A. De~Loera, Raymond Hemmecke, Jeremiah Tauzer, and Ruriko Yoshida,
  \emph{Effective lattice point counting in rational convex polytopes}, J.
  Symbolic Comput. \textbf{38} (2004), no.~4, 1273--1302.

\bibitem{ehrhartpolynomial}
Eug{\`e}ne Ehrhart, \emph{Sur les poly\`edres rationnels homoth\'etiques \`a
  {$n$}\ dimensions}, C. R. Acad. Sci. Paris \textbf{254} (1962), 616--618.

\bibitem{polymake}
Ewgenij Gawrilow and Michael Joswig, \emph{polymake: a framework for analyzing
  convex polytopes}, Polytopes---combinatorics and computation (Oberwolfach,
  1997), DMV Sem., vol.~29, Birkh\"auser, Basel, 2000, pp.~43--73. Software
  {\tt polymake} available at \url{http://www.polymake.org}.

\bibitem{MR1976856}
Branko Gr{\"u}nbaum, \emph{Convex polytopes}, second ed., Graduate Texts in
  Mathematics, vol. 221, Springer-Verlag, New York, 2003, Prepared and with a
  preface by Volker Kaibel, Victor Klee and G{\"u}nter M. Ziegler.

\bibitem{koeppelatte}
Matthias K{\"o}ppe, \emph{A primal {B}arvinok algorithm based on irrational
  decompositions}, SIAM J. Discrete Math. \textbf{21} (2007), no.~1, 220--236
  (electronic), {\tt arXiv:math.CO/0603308}. Software {\tt LattE macchiato}
  available at \url{http://www.math.ucdavis.edu/~mkoeppe/latte/}.

\bibitem{MR2487491}
Alexander Postnikov, \emph{Permutohedra, associahedra, and beyond}, Int. Math.
  Res. Not. (2009), no.~6, 1026--1106.

\bibitem{sloaneonlineseq}
Neil J.~A. Sloane, \emph{On-line encyclopedia of integer sequences}, \url{http://oeis.org/}.

\end{thebibliography}

\end{document}

