% !TeX root =./x2.tex
% !TeX program = pdfLaTeX
\section{Introduction}
For a motivation of optimal transportation problems,
Vershik proposed to study
the {fundamental polytope} %$\KR([n],d)$
constructed from a finite metric space %$([n],d)$
in \cite{MR3331969}.
For a metric space $([n],d)$,
the \emph{fundamental polytope}
$\KR([n],d)$ is defined to be the convex hull of
\begin{align*}
  %\EEE([n],d)=
  \Set{\epsilon^{d}_{(i,j)}=\frac{\ee_{i}-\ee_j}{d(i,j)} | i,j\in [n], i\neq j},
\end{align*}
where
 $\{\ee_{1},\ldots,\ee_{n}\}$ is the standard orthonormal basis of $\RR^{n}$.
%It
The polytope $\KR([n],d)$
is also called the \emph{Kantorovich--Rubinstein polytope}
\cite{MR3810570,MR4249903}.
In the case of a tree-like metric space,
Delucchi and Hoessley 
proved a nice formula of the $f$-vector by using the
relation between tree-like metric spaces and hyperplane arrangements
in \cite{MR4081480}.
The starting point of this work was the second author's attempt to extend
their work to graphs with cycles.

%% Motivated by optimal transportation problems,
%% Vershik \cite{MR3331969}
%% proposed to study
%% the convex polytope $\KR(X,d)$
%% constructed from a finite metric space $(X,d)$.
%% When $X=\{1,\ldots,n\}$, it is defined by
%% \[
%%  \KR(X,d) = \conv\ideal{\textstyle \frac{\ee_{i}-\ee_j}{d(i,j)}}{1\le
%%  i,j\le n},
%% \]
%% where $\{\ee_{1},\ldots,\ee_{n}\}$ is the standard orthonormal
%% basis of $\RR^{n}$.
%% This is called the \emph{fundamental polytope} in Vershik's paper.
%% It is also called the \emph{Kantorovich--Rubinstein polytope}
%% \cite{MR3810570,MR4249903}.
%% When $X$ is a tree-like metric space, Delucchi and Hoessley
%% \cite{MR4081480} proved a nice formula of the $f$-vector by using the
%% relation between tree-like metric spaces and hyperplane arrangements.
%% The starting point of this work was second author's attempt to extend
%% their work to graphs with cycles.


For a finite simple graph  $G$ whose vertex set is $[n]$,
we can define a metric $d_G$
on $[n]$ by the minimum length of paths.
The Kantorovich--Rubinstein polytope $\KR([n],d_G)$ 
has already been studied as
the \emph{symmetric edge polytope} $\SE(G)$,
introduced
by Matsui et al.~\cite{MR2842918}.
If $G$ is the complete graph $K_{n}$,
then it is also called the \emph{root polytope} of
the root system A$_{n-1}$ and
Cho completely determined
its faces in \cite{MR1697418}.


%% Give a finite simple graph $G$, define a metric $d_{\mathrm{graph}}$ on
%% the vertex set $G_{0}$ by the shortest length of paths, where each edge
%% is equipped with length one.
%% It turns out that the Kantorovich--Rubinstein polytope of
%% the metric space $(G_{0},d_{\mathrm{graph}})$ has already been studied
%% under different names.
%% It coincides with the \emph{symmetric edge polytope} $\SE(G)$ introduced
%% by Matsui et al.~\cite{MR2842918}.
%% When $G$ is the complete graph $K_{n}$, it is called the \emph{root
%% polytope} of the root system $A_{n}$ and its faces are completely
%% determined by Cho \cite{MR1697418}.

We can also generalize the definition of symmetric edge polytope to
a finite quiver (directed graph).
In this article, a quiver $Q=(Q_{0},Q_{1})$ means
a quiver without loops and multiedges.
Since $Q$ has no loop and no multiedges,
$Q_1$ is realized as a subset of $(Q_0\times Q_0) \setminus \Set{(i,i)|i\in Q_0}$.
Let $Q$ be a quiver with  $Q_0=[n]$. 
We define $\varepsilon_{(i,j)}=\ee_{i}-\ee_{j}$ for $(i,j)\in Q_1$.
Let $\varepsilon(Q_1)$ be the set of $\varepsilon_{(i,j)}$
for all $(i,j)\in Q_{1}$.
We define the \emph{directed edge polytope} 
$\DE(Q)$ to be the convex hull of $\varepsilon(Q_1)$.
In other words,
$\DE(Q)$ is the convex hull of column vectors of the incidence matrix of $Q$.
The directed edge polytope is the  convex polytope whose set of vertices is
$\varepsilon(Q_1)$.
See also \cite{MR3395979}.
The symmetric edge polytope $\SE(G)$ is nothing but $\DE(D(G))$,
where $D(G)$ is the double of $G$, i.e.\ the quiver
whose edge set is the collection of direct edges $(v,w)$ and $(w,v)$
for adjacent vertices $v,w$ in $G$.

%% We may also generalize the definition of symmetric edge polytope to
%% a finite quiver (directed graph) $Q=(Q_{0},Q_{1})$ without loops and
%% multiedges by 
%% \[
%%  \DE(Q) = \conv\ideal{\varepsilon_{(i,j)}=\ee_{i}-\ee_{j}}{(i,j)\in Q_{1}}.
%% \]
%% Here $Q_{0}$ is the set of vertices and the set of edges $Q_{1}$ is
%% regarded as a subset of $Q_{0}\times Q_{0}$.
%% The polytope $\mathrm{DE}(Q)$ is called the \emph{directed edge
%% polytope} of $Q$ in \cite{MR3395979}.
%% The symmetric edge polytope $\SE(G)$ is nothing but $\DE(D(G))$,
%% where $D(G)$ is the double of $G$, i.e.\ the quiver obtained from $G$ by
%% replacing each edge $v - w$ by two directed edges $v\to w$ and
%% $v\leftarrow w$.

The aim of this article is to give an explicit combinatorial description
of all facets of $\DE(Q)$ for a quiver $Q$ and
combinatorial descriptions of
facets of $\SE(G)=\KR(G_{0},d_{\text{graph}})$
for a finite simple graph. 

%% The aim of this paper is to find an explicit combinatorial description
%% of all facets of $\DE(Q)$ and thus obtain combinatorial descriptions of
%% facets of $\SE(G)=\KR(G_{0},d_{\mathrm{graph}})$ for a finite simple
%% graph. 

In general,
the directed edge polytope $\DE(Q)$ with $Q_0=[n]$ is
a convex polytope in the vector space $\RR^n$.
Since the set of vertices  of $\DE(Q)$ is given by $\varepsilon(Q_1)$,
we can describe any face of $\DE(Q)$
in the form $\DE(R)$ for a subquiver $R$ with $R_{0}=Q_0$.  
Let us call such a subquiver a \emph{lluf subquiver}.

%% In general, the directed edge polytope $\DE(Q)$ is defined as a convex
%% polytope in the vector space $\RR^{Q_{0}}=\{\rho:Q_{0}\to\RR\}$.
%% Since the vertex set of $\DE(Q)$ is given by
%% $\Set{\varepsilon_{(v,w)}|(v,w)\in Q_{1}}$, any face of $\DE(Q)$ can be
%% written in the form $\DE(R)$ for a subquiver $R$ with
%% $R_{0}=Q_0$.  
%% Let us call such a subquiver a \emph{lluf subquiver}.

Our problem is to determine
the lluf subquiver $R$ of $Q$ such that
$\DE(R)$ is a facet of $\DE(Q)$, i.e.\ 
$\DE(R)$ is a face of $\DE(Q)$ and
$\dim\DE(R)=\dim\DE(Q)-1$.  
The existence of a rank function
plays a key role in both problems.
We call
$\rho\colon Q_0\to \RR$ a \emph{rank function} of $Q$
if $\rho(v)+1=\rho(w)$ for each edge $(v,w)\in Q_{1}$.
As in \cref{prop:fuga},
such a function makes
the vertex set $Q_{0}$ into a graded poset. 
To consider the dimension,
we also need to consider a connected component $C$ of a quiver $Q$,
i.e. a maximal subquiver  such that
any two distinct vertices in $C$ are connected by an undirected walk in $C$,
where
 an undirected walk is a sequence $(v_0,v_1,\ldots,v_l)$ of vertices in $Q$
 such that $(v_t,v_{t+1})\in Q_1$ or $(v_{t+1},v_t)\in Q_1$ for all $t$.
We define  the \emph{coconnectivity} $c(Q)$ of $Q$
by $c(Q)=\numof{Q_{0}}-\numof{\pi_{0}(Q)}$,
where $\pi_{0}(Q)$ stands for the set of connected components of $Q$.
We can describe the dimension  of $\DE(Q)$ by the coconnectivity as follows:
%% Given a lluf subquiver $R$ of $Q$, our problem is thus to
%% determine when $\DE(R)$ is a facet of $\DE(Q)$, i.e.\ 
%% $\DE(R)$ is a face of $\DE(Q)$ and
%% $\dim\DE(R)=\dim\DE(Q)-1$.  
%% It turns out that the existence of a \emph{rank function}, i.e.~a
%% function $\rho:Q_{0}\to\RR$ satisfying $\rho(v)+1=\rho(w)$ for any edge
%% $v\to w$, plays a key role in both problems.
%% As we see in \cref{prop:fuga}, such a function makes the
%% vertex set $Q_{0}$ into a graded poset. 
%For the dimension of $\DE(Q)$, we have the following formula:
\begin{theorem}
\label{thm:dim}
 For a finite quiver $Q$ without loops and multiedges, we have
 \[
 \dim(\DE(Q))=
  \begin{cases}
   c(Q)-1 & (\text{if $Q$ has a rank function}) \\ 
   c(Q) & (\text{otherwise}).
\end{cases}
 \]
\end{theorem}

To determine faces,
the contraction is also a key notion.
We say that a luff subquiver $R$ of $Q$ is
\defit{component-wise full}
if $C_1=\Set{ (v,w) \in Q_1  | v,w\in C_0}$
for each connected component $C$ of $R$.
For a component-wise full subquiver $R$  of a quiver $Q$,
 we define an equivalence relation $\sim$ on
 $Q_{0}$ by 
 \[
  v \sim w \iff \text{$v$ and $w$
    are
    in the same connected component of $R$
%connected by an undirected walk in $R$
  },
 \]
and the equivalence class of $v\in Q_{0}$ is denoted by $[v]$.
We define the contraction $Q/R$ to be the quiver such that 
  $(Q/R)_{0} = Q_{0}/_{\sim}$ and
  $(Q/R)_{1} = \Set{([v],[w]) | (v,w)\in Q_{1}\setminus R_{1}}$. 
%\begin{definition}
% \label{def:contraction}
%For a subquiver $\check Q$ of $Q$
%such that
%each connected component of $\check Q$ is a full subquiver of $Q$,
%we define a quiver $Q/\check Q$ to be the quiver $(Q_0/\check Q_0,Q_1/\check Q_1)$
%obtained by
%\begin{align*}
%  Q_0/\check Q_0 &= \Set{[v]|v\in Q_0},\\
%  Q_1/\check Q_1 &= \Set{([v],[w])|(v,w)\in Q_1\setminus \check Q_1}, 
%\end{align*}
%where
%$[v]=\Set{w|\text{$v$ and $w$ is weakly connected in $(Q_0,\check Q_1)$}}$.
%\end{definition}
Roughly speaking, $Q/R$ is the quiver obtained from $Q$ by
collapsing each connected component of $R$ to a point.
%Let us denote $c(Q)=\numof{Q_{0}}-\numof{\pi_{0}(Q)}$ and call it the
%\emph{coconnectivity} of $Q$. 
%% Even if $Q$ is connected,
%% a subquiver $R$ such that $\DE(R)$ is a facet of $\DE(Q)$ might be disconnected.
%% In fact,
%% the number of connected components is another key player in our work. 
We can characterize facets as follows:
\begin{theorem}
 \label{thm:facet}
 Let $Q$ be a finite quiver without loops and multiedges.
 For a lluf subquiver $R$ of $Q$ with
 $\dim(\DE(R))=\dim(\DE(Q))-1$, 
 $\DE(R)$ is a facet of $\DE(Q)$ if and only if one of the
 following conditions holds:
 \begin{enumerate}
  \item \label{condition:hogera}
    %$\numof{\pi_{0}(R)}=\numof{\pi_{0}(Q)}+1$,
    $c(R)=c(Q)-1$,
    $R$ is a component-wise full subquiver of $Q$,
%    each connected component of $R$ is a full subquiver of $Q$,
    and the contraction $Q/R$ is acyclic.
  \item \label{condition:piyo}
    %$\numof{\pi_{0}(R)}=\numof{\pi_{0}(Q)}$
    $c(R)=c(Q)$
	and there exists a rank function $\rho$ of $R$ such that
	\[
	 (\rho(v)-\rho(w)+1)(\rho(v')-\rho(w')+1)>0
	\]
	for any $(v,w),(v',w')\in Q_{1}\setminus R_{1}$.
 \end{enumerate} 
\end{theorem}

By iterating the process of taking facets,
we can obtain lower dimensional faces.
Thus we obtain a characterization of faces of $\DE(Q)$ for a quiver $Q$ with a rank
function.  
%% Note that lower dimensional faces can be obtained from facets by
%% iterating the process of taking facets.
%% Thus we obtain the following
%% characterization of all faces of $\DE(Q)$ for any quiver $Q$ with a rank
%% function.  

\begin{theorem}
 \label{thm:face}
 Suppose $Q$ has a rank function.
 For a proper subquiver $R$ of $Q$, the polytope $\DE(R)$ is a face of
 $\DE(Q)$, if and only if
% each connected component of $R$ is a full subquiver
$R$ is a component-wise full subquiver of $Q$
 and $Q/R$ is
 acyclic. 
\end{theorem}

In the case of  $D(G)$ for a simple graph $G$,
it does not have a rank function
and the condition (\ref{condition:piyo}) in \cref{thm:facet} applies.
Hence we have the following:
\begin{cor}
 \label{cor:SE}
 Let $G$ be a finite simple graph.
 For a lluf subquiver $R$ of $D(G)$ with \linebreak $\dim(\DE(R))=\dim(\SE(G))-1$,
 the following are equivalent:
 \begin{enumerate}
  \item $\DE(R)$ is a facet of $\SE(G)$.
  \item $c(R)=c(D(G))$ and there
	exists a rank function $\rho$ of $R$ such that
	\[
	(\rho(v)-\rho(w)+1)(\rho(v')-\rho(w')+1)>0
	\]
	for any $(v,w),(v',w')\in D(G)_{1}\setminus R_{1}$.
  \item \label{SE3}
	$c(R)=c(D(G))$ and there exists a map
	$\rho$ from the set of vertices of $G$ to $\RR$ such that
	\[
	\rho(v)-\rho(w) =
	\begin{cases}
	 1 & ((v,w)\in R_{1}) \\
	 -1 & ((w,v)\in R_{1}) \\
	 0 & (\text{otherwise})
	\end{cases}
	\]
	for $(v,w)\in D(G)_{1}$.
 \end{enumerate}
\end{cor}

%% \begin{remark}
%%  In \cite{MR3949939},
%%  Higashitani, Jochemko and Mateusz
%%  obtained a characterization of facets of symmetric edge
%%  polytopes for a connected simple graph $G$ as the existence of a
%%  function $\rho: G_{0}\to\ZZ$ satisfying the following two conditions:
%%  \begin{enumerate}
%%   \item $\rho(v)-\rho(w)\in \Set{-1,0,1}$ for any edge $(v,w)\in D(G)$, and
%%   \item the underlying graph of the quiver $E^{\rho}$ defined by
%% 	\[
%% 	 E^{\rho}_{1} = \Set{(v,w)\in \SE(G)_{1} | \rho(v)=\rho(w)+1}
%% 	\]
%% 	is a spanning subgraph of $G$.
%%  \end{enumerate}
 
%%  Their characterization can be obtained from \cref{cor:SE} as follows. 
%%  Let $\rho\in\RR^{G_{0}}$ be a function satisfying the third condition
%%  of \cref{cor:SE}. 
%%  Then $\rho(v)-\rho(w)\in \Set{-1,0,1}$ for all $(v,w)\in Q_1$ and we
%%  may assume that $\rho$ takes values in $\ZZ$.
%%  For such a function $\rho$, the quiver $E^{\rho}$ can be easily seen to
%%  coincide with our
%%  subquiver $R$ in \cref{cor:SE}.
%%  Since $G$ is connected, so is $\SE(G)$. The condition $c(R)=c(D(G))$
%%  implies that $R$ is also connected. Since $R$ is a lluf subquiver, it
%%  implies that the underlying graph of $E^{\rho}=R$ is a spanning
%%  subgraph of $G$.
  
%%  Conversely, let $\rho:G_{0}\to\ZZ$ be a function satisfying
%%  $\rho(v)-\rho(w)\in \Set{-1,0,1}$ for all $(v,w)\in Q_1$ and suppose
%%  that the underlying graph of $E^{\rho}$ is a spanning subgraph of $G$.
%%  In particular, $E^{\rho}$ is a lluf subquiver of $D(G)$.
%%  By the connectivity of $E^{\rho}$, we see $c(E^{\rho})=c(D(G))$.
%%  Since $\rho$ is a rank function on $E^{\rho}$, it satisfies the
%%  condition (a) of the third condition of \cref{cor:SE}.
%%  The condition that $\rho(v)-\rho(w)\in\Set{-1,0,1}$ for
%%  $(v,w)\in D(G)$, then, implies the condition (b).
%% \end{remark}

%% When $Q=D(G)$ for a simple graph $G$, it does not have a rank function
%% and the condition (\ref{condition:piyo}) in \cref{thm:facet} applies. It
%% is immediate to translate the condition (\ref{condition:piyo}) into the
%% following form. 
%% \begin{corollary}[\cref{cor:SE}]
%%  For a connected lluf subquiver $R$ of $D(G)$ with
%%  $\dim(\DE(R))=\dim(\SE(G))-1$, $\DE(R)$ is a facet of $\SE(G)$ if and
%%  only if
%%  $\numof{\pi_{0}(R)}=\numof{\pi_{0}(D(G))}$ and there exists a function
%%  $\rho\in \RR^{G_{0}}$ such that
%%  \[
%%  \rho(v)-\rho(w) =
%%  \begin{cases}
%%   1 & ((v,w)\in R_{1}) \\
%%   -1 & ((w,v)\in R_{1}) \\
%%   0 & (\text{otherwise})
%%  \end{cases}
%%  \]
%%  for $(v,w)\in D(G)_{1}$.
%% \end{corollary}
\begin{remark}
This is essentially equivalent to a characterization of facets of
symmetric edge polytopes in Higashitani--Jochemko--Micha{\l}ek \cite{MR3949939} for a connected graph  $G$.
See \cite[Remark 5.5]{2203.14521} for the details.
\end{remark}
%% \begin{remark}
%% The Kantorovich--Rubinstein polytope $\KR([n],d)$ is defined as the convex hull of
%% the set %$\EEE([n],d)$
%% of vectors $\epsilon^{d}_{(i,j)}$ indexed by $i\neq j\in [n]$.
%% Note that the set of vertices of $\KR([n],d)$  might be a proper subset of $\EEE([n],d)$.
%% For a face (\emph{resp.}\ facet) $F$ of  $\KR([n],d)$,
%% the quiver with the edge set %$\Set{ (i,j) |\epsilon^{d}_{(i,j)} \in F}$
%% consisting of $(i,j)$ satisfying $\epsilon^{d}_{(i,j)} \in F$
%% is called the face (\emph{resp.}\ facet) digraph.
%% Note that
%% the set of vertices a facet of $\KR([n],d)$
%% is a subset of the set of vectors $\epsilon^{d}_{(i,j)}$ corresponding to edges $(i,j)$ in the
%% facet digraph.
%% The face (\emph{resp.}\ facet) graph is
%% the undirected graph obtained from the face (\emph{resp.}\ facet) digraph by forgetting the orientation of edges.
%% In Gordon--Petrov \cite[Theorem 3]{MR3664266}, 
%% subgraphs contained by a facet graph of $\KR([n],d)$
%% are characterized by using existence of $1$-Lipschitz functions.
%% In the case of the symmetric edge polytope $\SE(G)$,
%% we define face and facet graphs as subgraphs of $G$.
%% We call them face and facet subgraphs of $G$.
%% In Chen--Davis--Korchevskaia \cite{MR4526533},
%% face and facet subgraphs are characterized in terms of bipartite graphs.
%% \end{remark}
\begin{remark}
In the case of the Kantorovich--Rubinstein polytope $\KR([n],d)$ for a
general metric $d$, Gordon and Petrov \cite{MR3664266} defined a quiver
 $Q(F)$ with 
vertex set $[n]$ from a face $F$ of $\KR([n],d)$ by
 \begin{align*}
  Q(F)_{1} = \Set{(v,w) | \epsilon^{d}_{(v,w)}\in F}.
 \end{align*}
 They proved as Theorem 3 that $E$ is a subset of in $Q(F)_{1}$ for some
 facet $F$ of $\KR([n],d)$ if and only if there exists a function
 $\rho\colon E\to\RR$ such that $\rho(v)-\rho(w)=d(v,w)$ for $(v,w)\in E$.

 When $d=d_{G}$ for a graph $G$ with the vertex set $[n]$,
 $\KR([n],d_{G})=\SE(G)$, the third condition in \cref{cor:SE} is
 closely related to their condition. In fact, if $F$ is a facet of
 $\SE(G)$ represented by a luff subquiver $R$ of $D(G)$ by $F=\DE(R)$,
 then $R_{1}\subset Q(F)$ and Theorem 3 of Gordon-Petrov says that there
 exists a function $\rho\colon [n]\to\RR$ such that $\rho(v)-\rho(w)=1$ for
 $(v,w)\in R_{1}$.

 On the other hand, \cref{cor:SE} gives a complete characterization of
 lluf subquivers $R$ of $D(G)$ such that $\DE(R)$ is a facet of
 $\KR([n],d_{G})$, while Gordon-Petrov's Theorem 3 does not.
\end{remark}

This article is organized as follows:
After fixing notation and terminology in \cref{sec:notation}, 
we see sketches of proofs for
\cref{thm:dim}  in
\cref{sec:dim}, and for \cref{thm:facet} in \cref{sec:facet}.
We end this paper with sample computations in \cref{sec:examples}.
%Note that the case of even cycles recently appeared in a paper
%\cite{1910.05193} by D'Ali, Delucchi, and Micha{\l}ek independently. 
This article is an extended abstract of the preprint \cite{2203.14521}.
We will omit details.  See \cite{2203.14521} for the details.
  

