Rigid Gorenstein toric Fano varieties arising from directed graphs

Abstract

A directed edge polytope ${\mathcal {A}}_G$ is a lattice polytope arising from root system $A_n$ and a finite directed graph G. If every directed edge of G belongs to a directed cycle in G, then ${\mathcal {A}}_G$ is terminal and reflexive, that is, one can associate this polytope to a Gorenstein toric Fano variety $X_G$ with terminal singularities. It is shown by Totaro that a toric Fano variety which is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3 is rigid. In the present paper, we classify all directed graphs G such that $X_G$ is a toric Fano variety which is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3.

1 Introduction

1.1 Directed edge polytopes and symmetric edge polytopes

A lattice polytope is a convex polytope all of whose vertices have integer coordinates. Let $G=(V(G),A(G))$ be a finite directed graph on the vertex set $V(G)=[n]:=\{1,\ldots , n\}$ with the directed edge set A(G). For a directed edge $e = (i,j)$ of G, we define $\rho (e) \in {\mathbb {R}}^n$ by setting $\rho (e) = \mathbf{e }_i -\mathbf{e }_j$. The directed edge polytope of G, denoted by ${\mathcal {A}}_G$, is the lattice polytope defined as

$$\begin{aligned} {\mathcal {A}}_G = {{\,\mathrm{conv}\,}}\{ \rho (e) : e \in A(G)\} \subset {\mathbb {R}}^n. \end{aligned}$$

A related polytope is the symmetric edge polytope of G, denoted by ${\mathcal {P}}_G$, and defined as

$$\begin{aligned} {\mathcal {P}}_G = {{\,\mathrm{conv}\,}}\{ \pm \rho (e) : e \in A(G)\} \subset {\mathbb {R}}^n. \end{aligned}$$

Note that one can define the symmetric edge polytope based on the underlying simple graph of G, denoted by $G^{\mathrm{un}}$, since both directions for each edge contribute to the vertices of ${\mathcal {P}}_G$. Here, $G^{\mathrm{un}}$ has an edge $\{i,j\}$ if and only if (i, j) or (j, i) is a directed edge of G. Directed edge polytopes are first introduced in [17] by Ohsugi and Hibi for a tournament graph G. A directed graph G is called symmetric if both (i, j) and $(j,i) \in A(G)$ whenever $\{i,j\}$ is an edge of $G^{\text {un}}$. Notions of directed edge polytopes and symmetric edge polytopes coincide when G is a symmetric directed graph, i.e., ${\mathcal {A}}_G = {\mathcal {P}}_G$. Symmetric edge polytopes are of interest in many fields such as commutative algebra ( [18]), algebraic geometry ( [11]) algebraic combinatorics ( [12, 19, 20]) and number theory ( [6, 15, 22]). One of the reasons the symmetric edge polytopes gained much attraction is due to its connection to the Kuramoto model ( [14]), which describes the behavior of interacting oscillators ( [7]).

It follows from [11, Proposition 1.4] that ${\mathcal {A}}_G$ is a terminal reflexive polytope if and only if every directed edge of G belongs to a directed cycle in G. Therefore, in our study of terminal reflexive polytopes, we assume each directed edge in the associated graph belongs to a directed cycle.

We denote $X_G$ as the projective toric variety associated to the spanning (or face) fan of ${\mathcal {A}}_G \subseteq N_{{\mathbb {R}}} \cong {\mathbb {R}}^n$. Then $X_G$ is a Gorenstein toric Fano variety with terminal singularities. Gorenstein toric Fano varieties are of interest in algebraic geometry and mirror symmetry ( [3, 16]). We assume that the reader is familiar with toric varieties. For an introduction of the toric varieties and the notations, we refer the reader to [8]. In particular the letter $N \cong {\mathbb {Z}}^n$ stands for a lattice and $M=\text {Hom}_{{\mathbb {Z}}}(N, {\mathbb {Z}})$ is its dual lattice. We denote their associated vector spaces as $N_{{\mathbb {R}}}:=N \otimes _{{\mathbb {Z}}} {\mathbb {R}}$ and $M_{{\mathbb {R}}}:=M \otimes _{{\mathbb {Z}}} {\mathbb {R}}$.

1.2 Deformation theory

Let X be a scheme of finite type over ${\mathbb {C}}$ and let A be an Artinian algebra over ${\mathbb {C}}$. An infinitesimal deformation of X over A is defined as the following cartesian diagram:

where $\pi$ is flat. Let $\pi ': {\mathcal {X}}' \rightarrow {{\,\mathrm{Spec}\,}}(A)$ be another deformation of X over ${{\,\mathrm{Spec}\,}}(A)$. We say that $\pi$ and $\pi '$ are isomorphic, if there exists a map ${\mathcal {X}} \rightarrow {\mathcal {X}}'$ over ${{\,\mathrm{Spec}\,}}(A)$ inducing the identity on X. Let $\text {Def}_X$ be a functor such that $\text {Def}_X(A)$ is the set of deformations of X over ${{\,\mathrm{Spec}\,}}(A)$ modulo isomorphisms. X is called rigid, if the first-order deformation space $T_X^1 : = \text {Def}_X({\mathbb {C}}[t]/t^2) = 0$. This implies that X has no nontrivial infinitesimal deformations. It turns out that the toric varieties arising from graphs recover interesting rigid examples. One of them is the famous rigid singularity which is the cone over the Segre embedding ${\mathbb {P}}^m \times {\mathbb {P}}^n$ in ${\mathbb {P}}^{(m+1)(n+1)-1}$ except for $m=n=1$. Equivalently, this is the affine toric variety arising from the complete bipartite graph $K_{m+1,n+1}$. The rigidity of toric varieties associated to undirected graphs has been first studied [5] for complete bipartite graphs with one edge removal. A generalization of this family and a sufficient condition for rigidity have been examined in [21]. In the present paper, we will discuss infinitesimal deformations of the Gorenstein toric Fano varieties associated to directed edge polytopes. This connection between three different areas of mathematics gives us the opportunity to present high dimensional concrete examples of rigid Gorenstein toric Fano varieties purely in terms of graphs, which is in general a hard computational problem (see Section 5).

1.3 Smooth toric Fano varieties arising from directed graphs

For toric Fano varieties, a sufficient condition for their rigidity is known. In fact, ${\mathbb {Q}}$-factorial toric Fano varieties with terminal singularities, in particular, smooth toric Fano varieties are rigid [10, Theorem 1.4], [4, Theorem 3.2]. In [11], Higashitani classified directed graphs G such that $X_G$ is ${\mathbb {Q}}$-factorial. All undefined terms are specified in the sections below.

Theorem 1.1

( [11, Theorem 2.2]) Let G be a finite directed graph such that every directed edge belongs to a directed cycle in G. Then the following arguments are equivalent:

• (1) $X_G$ is smooth;

• (2) $X_G$ is ${\mathbb {Q}}$-factorial;

• (3) G possesses no homogeneous cycle $C=(e_1,\ldots ,e_l)$ such that

  $$\begin{aligned} \mu _C(i_a)-\mu _C(i_b) \le \mathrm{dist}_G(i_a,i_b) \end{aligned}$$

  for all $1 \le a,b \le l$, where $e_j$ is $(i_j, i_{j+1})$ or $(i_{j+1},i_j)$ for $1 \le j \le l$ with $i_{l+1}=i_1$.

In particular, $X_G$ is rigid.

For symmetric directed graphs, i.e., for symmetric edge polytopes, one obtains the following.

Corollary 1.2

( [11, Corollary 2.2]) Let G be a finite symmetric directed graph. Then the following arguments are equivalent:

• (1) $X_G$ is smooth;

• (2) $X_G$ is ${\mathbb {Q}}$-factorial;

• (3) $G^{\mathrm{un}}$ has no even cycle as subgraphs.

In particular, $X_G$ is rigid.

1.4 Rigid Gorenstein toric Fano varieties arising from directed graphs

The most general rigidity theorem for toric Fano varieties known to this date is the following result of Totaro:

Theorem 1.3

[24, Theorem 5.1] A toric Fano variety which is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3 is rigid.

In the present paper, we classify all directed graphs G such that $X_G$ is a Gorenstein toric Fano variety which is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3.

Theorem 1.4

Let G be a finite directed graph such that every directed edge of G belongs to a directed cycle in G. Then the following arguments are equivalent:

• (1) $X_G$ is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3;

• (2) G satisfies both of the following:

  • G has no directed subgraph $C_1$ whose directed edge set is

    $$\begin{aligned} \{(i_1,i_2), (i_1,i_4), (i_3,i_2), (i_3,i_4)\}; \end{aligned}$$

  • For any directed subgraph $C_2$ of G whose directed edge set is

    $$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_1,i_4), (i_4,i_3)\}, \end{aligned}$$

    it follows that $(i_1,i_3)$ is a directed edge of G or there exists a vertex $j \notin \{i_2,i_4\}$ in G such that $(i_1,j)$ and $(j,i_3)$ are directed edges of G.

In particular, $X_G$ is rigid.

For symmetric directed graphs, i.e., for symmetric edge polytopes, we obtain the following.

Corollary 1.5

Let G be a finite symmetric directed graph. Then the following arguments are equivalent:

• (1) $X_G$ is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3;

• (2) $G^{\mathrm{un}}$ has no 4-cycle as a subgraph.

In particular, $X_G$ is rigid.

The paper is organized as follows: In Section 2, we recall a connection between lattice polytopes and toric Fano varieties. In Section 3, we present a certain characterization of faces of directed edge polytopes. The proof of Theorem 1.4 will be given in Section 4. Finally, we give some examples of Gorenstein toric Fano varieties which are not ${\mathbb {Q}}$-factorial but rigid, and concluding remarks.

2 Fano polytopes

In this section, we recall a connection between lattice polytopes and toric Fano varieties. Let ${\mathcal {P}} \subset {\mathbb {R}}^n$ be a full-dimensional lattice polytope.

• We say that ${\mathcal {P}}$ is Fano if the origin of ${\mathbb {R}}^n$ belongs to the interior of ${\mathcal {P}}$ and the vertices of ${\mathcal {P}}$ are primitive lattice points in ${\mathbb {Z}}^n$.

• A Fano polytope ${\mathcal {P}}$ is called terminal if every lattice point on the boundary is a vertex.

• A Fano polytope ${\mathcal {P}}$ is said to be reflexive if each facet of ${\mathcal {P}}$ has lattice distance one from the origin. Equivalently, its dual polytope

  $$\begin{aligned} {\mathcal {P}}^{\vee } =\{{\mathbf {x}}\in {\mathbb {R}}^n: \langle {\mathbf {x}}, {\mathbf {y}} \rangle \le 1 \text { for all } {\mathbf {y}} \in {\mathcal {P}} \} \end{aligned}$$

  is a lattice polytope.

• A Fano polytope is called ${\mathbb {Q}}$-factorial if it is simplicial.

• A Fano polytope is called smooth if the vertices of each facet form a ${\mathbb {Z}}$-basis of ${\mathbb {Z}}^n$.

We recall algebro-geometric interpretations of these polytopes. For a Fano polytope ${\mathcal {P}}$, denote $X_{\mathcal {P}}$ the normal toric variety associated to the spanning fan of ${\mathcal {P}}$. Then $X_{{\mathcal {P}}}$ is a toric Fano variety. Conversely, every toric Fano variety arises in this way from a Fano polytope (see [8, §8.3]).

• A Fano polytope ${\mathcal {P}}$ is terminal if and only if $X_{{\mathcal {P}}}$ has at worst terminal singularities.

• A Fano polytope ${\mathcal {P}}$ is reflexive if and only if $X_{{\mathcal {P}}}$ is Gorenstein.

• A Fano polytope ${\mathcal {P}}$ is ${\mathbb {Q}}$-factorial if and only if $X_{{\mathcal {P}}}$ is ${\mathbb {Q}}$-factorial.

• A Fano polytope ${\mathcal {P}}$ is smooth if and only if $X_{{\mathcal {P}}}$ is smooth.

Two lattice polytopes ${\mathcal {P}} \subset {\mathbb {R}}^n$ and ${\mathcal {Q}} \subset {\mathbb {R}}^{m}$ are said to be unimodularly equivalent, denoted by ${\mathcal {P}} \cong {\mathcal {Q}}$, if there exists an affine map from the affine span $\mathrm{aff}({\mathcal {P}})$ of ${\mathcal {P}}$ to the affine span $\mathrm{aff}({\mathcal {Q}})$ of ${\mathcal {Q}}$ that maps ${\mathbb {Z}}^n \cap \mathrm{aff}({\mathcal {P}})$ bijectively onto ${\mathbb {Z}}^m \cap \mathrm{aff}({\mathcal {Q}})$ and maps ${\mathcal {P}}$ to ${\mathcal {Q}}$. Each lattice polytope is unimodularly equivalent to a full-dimensional lattice polytope. We say that a lattice polytope is Fano, terminal, reflexive, ${\mathbb {Q}}$-factorial, smooth if it contains the origin in the interior and it is unimodularly equivalent to a full-dimensional Fano, terminal, reflexive, ${\mathbb {Q}}$-factorial, smooth polytope, respectively. The author of [11] classified all graphs whose directed edge polytopes are Fano.

Proposition 2.1

( [11, Proposition 1.4]) Let G be a finite directed graph. Then the following arguments are equivalent:

• (1) ${\mathcal {A}}_G$ is Fano;

• (2) ${\mathcal {A}}_G$ is terminal reflexive;

• (3) Every directed edge of G belongs to a directed cycle in G.

In particular, $X_{G}$ is a Gorenstein toric Fano variety with terminal singularities.

Given two Fano polytopes ${\mathcal {P}} \subset {\mathbb {R}}^n$ and ${\mathcal {Q}} \subset {\mathbb {R}}^m$, set

$$\begin{aligned} {\mathcal {P}} \oplus {\mathcal {Q}}:=\mathrm{conv}\{ ({\mathcal {P}}, {\mathbf {0}}) \cup ({\mathbf {0}}, {\mathcal {Q}})\} \subset {\mathbb {R}}^{n+m}. \end{aligned}$$

We call ${\mathcal {P}} \oplus {\mathcal {Q}}$ the free sum of ${\mathcal {P}}$ and ${\mathcal {Q}}$. Then one has $X_{{\mathcal {P}} \oplus {\mathcal {Q}}} \cong X_{{\mathcal {P}}} \times X_{{\mathcal {Q}}}$. In particular, ${\mathcal {P}} \oplus {\mathcal {Q}}$ is smooth if and only if both ${\mathcal {P}}$ and ${\mathcal {Q}}$ are smooth. Thus, if G is not connected, we have the following result by definition.

Proposition 2.2

Let G be a finite directed graph with connected components $G_1,\ldots ,G_r$ such that ${\mathcal {A}}_G$ is terminal and reflexive. Then one has

$$\begin{aligned} {\mathcal {A}}_G \cong {\mathcal {A}}_{G_1} \oplus \cdots \oplus {\mathcal {A}}_{G_r}. \end{aligned}$$

In particular, we obtain

$$\begin{aligned} X_{G} \cong X_{{G_1}} \times \cdots \times X_{{G_r}}. \end{aligned}$$

We have the following combinatorial criterion for rigidity of Gorenstein toric Fano varieties with terminal singularities.

Proposition 2.3

Let ${\mathcal {P}}$ be a terminal reflexive polytope. Then

• (1) $X_{{\mathcal {P}}}$ is smooth in codimension 2,

• (2) all 2-faces of ${\mathcal {P}}$ are triangles if and only if $X_{{\mathcal {P}}}$ is ${\mathbb {Q}}$-factorial in codimension 3.

In particular, $X_{{\mathcal {P}}}$ is rigid.

Proof

Since ${\mathcal {P}}$ is terminal and reflexive, each edge of ${\mathcal {P}}$ has lattice length 1 and is contained in some hyperplane which has height 1 with respect to the origin. This implies that $X_{\mathcal {P}}$ is smooth in codimension 2. For the second part, $X_{{\mathcal {P}}}$ is ${\mathbb {Q}}$-factorial in codimension 3 if and only if all 3-cones of the spanning fan of ${\mathcal {P}}$ is simplicial. Therefore, $X_{{\mathcal {P}}}$ is ${\mathbb {Q}}$-factorial in codimension 3 if and only if all 2-faces of ${\mathcal {P}}$ are triangles. The last statement on rigidity of $X_{{\mathcal {P}}}$ follows from Theorem 1.3. $\square$

The reason that we only consider connected graphs for 2-faces is explained with the following result.

Proposition 2.4

Let ${\mathcal {P}}$ and ${\mathcal {Q}}$ be terminal reflexive polytopes. If all 2-faces of ${\mathcal {P}}$ and ${\mathcal {Q}}$ are triangles, all 2-faces of ${\mathcal {P}}\oplus {\mathcal {Q}}$ are also triangles. In particular, $X_{{\mathcal {P}}\oplus {\mathcal {Q}}}$ is rigid.

Proof

This follows from the fact that faces of ${\mathcal {P}} \oplus {\mathcal {Q}}$ are convex hulls of faces of ${\mathcal {P}}$ and ${\mathcal {Q}}$ and the fact that ${\mathcal {P}}\oplus {\mathcal {Q}}$ is a terminal reflexive polytope. Moreover, it follows from Propsition 2.3 that $X_{{\mathcal {P}}\oplus {\mathcal {Q}}}$ is rigid. $\square$

3 Faces of directed edge polytopes

In this section, we discuss faces of terminal reflexive directed edge polytopes. Let G be a connected finite directed graph on the vertex set [n] and the directed edge set A(G). We assume that every directed edge of G belongs to a directed cycle in G, i.e. ${\mathcal {A}}_G$ is terminal and reflexive by Proposition 2.1. First, we show that each proper face of ${\mathcal {A}}_G$ is the directed edge polytope of a finite acyclic directed graph. Here a finite directed graph is called acyclic if it has no directed cycles.

Lemma 3.1

Let G be a connected finite directed graph such that ${\mathcal {A}}_G$ is terminal and reflexive. Then each proper face of the directed edge polytope ${\mathcal {A}}_G$ is the directed edge polytope of a finite acyclic directed subgraph H of G.

Proof

It is clear that each proper face of ${\mathcal {A}}_G$ is the directed edge polytope ${\mathcal {A}}_H$ of a directed subgraph H of G. If H is not acyclic, then there exists a directed cycle

$$\begin{aligned} (i_1,i_2),(i_2,i_3),\ldots ,(i_r,i_1) \end{aligned}$$

of H. Hence ${\mathbf {e}}_{i_1}-{\mathbf {e}}_{i_2},{\mathbf {e}}_{i_2}-{\mathbf {e}}_{i_3}, \ldots , {\mathbf {e}}_{i_r}-{\mathbf {e}}_{i_1}$ belong to ${\mathcal {A}}_H$. Then since

$$\begin{aligned} \dfrac{1}{r}(({\mathbf {e}}_{i_1}-{\mathbf {e}}_{i_2})+({\mathbf {e}}_{i_2}-{\mathbf {e}}_{i_3})+ \cdots +({\mathbf {e}}_{i_r}-{\mathbf {e}}_{i_1}))={\mathbf {0}}, \end{aligned}$$

the origin also belongs to ${\mathcal {A}}_H$. However, this contradicts that the origin belongs to the relative interior of ${\mathcal {A}}_G$ and ${\mathcal {A}}_H$ is a proper face of ${\mathcal {A}}_G$. Therefore, H is acyclic. $\square$

Next, we show for which acyclic directed graph H, $\dim ({\mathcal {A}}_H)=2$ and ${\mathcal {A}}_H$ is not a triangle. In fact, one has the following.

Lemma 3.2

Let H be an acyclic directed graph without isolated vertices such that $\dim ({\mathcal {A}}_H)=2$. Then ${\mathcal {A}}_H$ is a square if and only if H is a directed graph $C_1$ whose directed edge set is

$$\begin{aligned} \{(i_1,i_2), (i_1,i_4), (i_3,i_2), (i_3,i_4)\} \end{aligned}$$

or a directed graph $C_2$ whose directed edge set is

$$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_1,i_4), (i_4,i_3)\}. \end{aligned}$$

Otherwise, ${\mathcal {A}}_H$ is a triangle.

Proof

Let d be the number of vertices of H and let r be the number of connected components of H. It then follows from $\dim ({\mathcal {A}}_H)=2$ that $d \ge 3$ and H has at least 3 edges. Since the rank of the incidence matrix of the directed graph H is $d-r$, we have $d-r-1 \le \dim ({\mathcal {A}}_{H})=2$, hence, $d \le r+3$. Since H has no isolated vertices, each connected component has at least two vertices. Hence one has $d \ge 2r$. Therefore, we obtain $2r \le d \le r+3$. This implies that $r \le 3$ and $3 \le d \le 6$. If $r=1$, namely, H is connected, then $d=3$ or $d=4$. Since $\dim ({\mathcal {A}}_H)=2$, H is one of a path of length 3, a 3-cycle, a 4-cycle, and a (1, 3)-complete bipartite graph with some orientation. If $r=2$, then $d=4$ or $d=5$. In this case, H is a disjoint union of one edge and a path of length 2 with some orientation. If $r=3$, then $d=6$. In this case, H is a disjoint union of 3 edges with some orientation. By a routine calculation, it follows that if $H=C_1$ or $H=C_2$, then ${\mathcal {A}}_H$ is a square, otherwise, ${\mathcal {A}}_H$ is a triangle. $\square$

In what follows, we see that a cycle of G determines a proper face of ${\mathcal {A}}_G$. We first introduce some terminology and notation to state this fact. For a directed edge $e=(i,j)$ of G, denote $e^{\mathrm{un}}$ the undirected edge $\{i,j\}$ of $G^{\mathrm{un}}$. A sequence $\Gamma =\{e_1,\ldots , e_l\}$ of directed edges of G is called a cycle if $\{e^{\mathrm{un}}_1,\ldots ,e^{\mathrm{un}}_l\}$ forms a cycle in $G^{\mathrm{un}}$. Let $\Gamma =(e_1, \ldots , e_l)$ be a cycle in G such that $e^{\mathrm{un}}_j=\{i_j,i_{j+1}\}$ for each j, where $i_{l+1}=i_1$. Then we define

$$\begin{aligned} \Delta _{\Gamma }^+&= \{e_j \in \{e_1, \ldots , e_l\} : e_j = (i_j, i_{j+1})\},\\ \Delta _{\Gamma }^-&= \{e_j \in \{e_1, \ldots , e_l\} : e_j = (i_{j+1}, i_j)\}. \end{aligned}$$

A cycle $\Gamma$ is called homogeneous if $|\Delta _{\Gamma }^+| = |\Delta _{\Gamma }^-|$ and nonhomogeneous if $|\Delta _{\Gamma }^+| \ne |\Delta _{\Gamma }^-|$. We note that the two directed edges (i, j) and (j, i) form a non-homogeneous cycle of length two, although they do not form a cycle in $G^{\mathrm{un}}$.

Example 3.3

Let G be the directed graph given in Figure 1. Consider the cycles $\Gamma _1=\{i_1,i_2,i_5,i_6\}$ and $\Gamma _2=\{i_2,i_3,i_4,i_5\}$. Then $\Gamma _1$ is a homogeneous cycle whereas $\Gamma _2$ is not because $|\Delta _{\Gamma _1}^+| = 2= |\Delta _{\Gamma _1}^-|$ and $|\Delta _{\Gamma _2}^+| =3 \ne 1= |\Delta _{\Gamma _1}^-|.$

Fig. 1

Directed graph G

Assume that G has a homogeneous cycle $\Gamma$ on the vertices $\{i_1,\ldots ,i_l\}$. Then there exists a unique function

$$\begin{aligned} \mu _{\Gamma }: \{i_1,\ldots ,i_l\} \rightarrow {\mathbb {Z}}_{\ge 0} \end{aligned}$$

such that

• $\mu _{\Gamma }(i_{j+1})=\mu _{\Gamma }(i_j)-1$ if $e_j=(i_j,i_{j+1})$ for $1 \le j \le l$;

• $\mu _{\Gamma }(i_{j+1})=\mu _{\Gamma }(i_j)+1$ if $e_j=(i_{j+1},i_j)$ for $1 \le j \le l$;

• $\min (\{\mu _{\Gamma }(i_1),\ldots ,\mu _{\Gamma }(i_l)\})=0$.

For two distinct vertices i and j of G, the distance from i to j, denoted by $\mathrm{dist}_G(i,j)$, is the length of the shortest directed path in G from i to j. If there exists no directed path from i to j, then the distance from i to j is defined to be infinity. The following result defines a face and its supporting hyperplane of ${\mathcal {A}}_G$ containing a homogenous cycle.

Lemma 3.4

( [11, Proof of Theorem 2.2]) Let G be a connected finite directed graph on the vertex set [n] such that ${\mathcal {A}}_G$ is terminal and reflexive. Assume that there exists a homogeneous cycle $\Gamma =(e_1,\ldots ,e_l)$ of G such that

$$\begin{aligned} \mu _{\Gamma }(i_a)-\mu _{\Gamma }(i_b) \le \mathrm{dist}_G(i_a,i_b) \end{aligned}$$

for all $1 \le a,b \le l$, where $e^{\mathrm{un}}_j=\{i_j,i_{j+1}\}$ for $1 \le j \le l$ with $i_{l+1}=i_1$. Let ${\mathcal {H}} \subset {\mathbb {R}}^{n}$ be the hyperplane defined by the equation $a_1x_1+\cdots +a_nx_n=1$, where

$$\begin{aligned} a_k={\left\{ \begin{array}{ll} \mu _{\Gamma }(k) &{}:\text{ if } k \in \{i_1,\ldots ,i_l\},\\ \max (\{a_{i_j}-\mathrm{dist}_G(i_j,k): j=1,\ldots , l\} \cup \{0\}) &{} :\text{ otherwise }. \end{array}\right. } \end{aligned}$$

Then ${\mathcal {H}}$ is a supporting hyperplane of ${\mathcal {A}}_G$ and the proper face ${\mathcal {F}}={\mathcal {A}}_G \cap {\mathcal {H}}$ contains $\rho (e_1),\ldots ,\rho (e_l)$.

For a finite acyclic directed graph $D=([n], A(D))$, we define a lattice polytope $\widetilde{{\mathcal {A}}}_D$ by

$$\begin{aligned} \widetilde{{\mathcal {A}}}_D:=\mathrm{conv}\{{\mathbf {0}}, {\mathbf {e}}_i-{\mathbf {e}}_j : (i,j) \in A(D)\} \subset {\mathbb {R}}^n. \end{aligned}$$

Let ${\mathcal {A}}_{D_1},\ldots , {\mathcal {A}}_{D_r}$ be the facets of ${\mathcal {A}}_G$ with acyclic directed graphs $D_1,\ldots , D_r$. Since the origin of ${\mathbb {R}}^n$ belongs to the interior of ${\mathcal {A}}_G$, the directed edge polytope ${\mathcal {A}}_G$ is divided by $\widetilde{{\mathcal {A}}}_{D_1},\ldots , \widetilde{{\mathcal {A}}}_{D_r}$. In particular, each face of $\widetilde{{\mathcal {A}}}_{D_i}$ which does not contain the origin is a face of ${\mathcal {A}}_{D_i}$, hence a face of ${\mathcal {A}}_G$. We recall a combinatorial description of the faces of $\widetilde{{\mathcal {A}}}_D$ from [23].

Definition 3.5

Let $D=(V(D),A(D))$ be a finite acyclic directed graph and $H \subset D$ directed subgraph of D with $V(H)=V(D)$ and the directed edge set A(H). Let $H^{\mathrm{un}}_1,\ldots ,H^{\mathrm{un}}_m$ be the connected components of the underlying undirected graph $H^{\mathrm{un}}$ of H. Here H may have isolated vertices and we regard them as connected components of $H^{\mathrm{un}}$. The directed multi-graph $H_{\mathrm{comp}}$ is the graph with vertex set

$$\begin{aligned} V(H_{\mathrm{comp}})=\{H^{\mathrm{un}}_i : i \in [m]\} \end{aligned}$$

and edge multiset

$$\begin{aligned} A(H_{\mathrm{comp}})=\{ (H^{\mathrm{un}}_i,H^{\mathrm{un}}_j) : (v_i,v_j) \in A(D) \setminus A(H), v_i \in V(H^{\mathrm{un}}_i), v_j \in V(H^{\mathrm{un}}_j) \}. \end{aligned}$$

Fig. 2

Directed graph D and its subgraph H

Example 3.6

Let D be the directed graph given in Figure 2a. Consider its subgraph H given in Figure 2b. The directed graph $H_{\mathrm{comp}}$ has three vertices $H^{\mathrm{un}}_1, H^{\mathrm{un}}_2$ and $H^{\mathrm{un}}_3$ corresponding to connected components $H_1, H_2$ and $H_3$ of H. Note that $V(H_1)=\{i_1,i_2,i_3,i_4\}$, $H_2=\{i_5\}$ and $H_3=\{i_6\}$.

Fig. 3

$H_{\mathrm{comp}}$

There is a loop at vertex $H^{\mathrm{un}}_1$ since $(i_1,i_3) \in A(D) \setminus A(H)$ where $i_1,i_3 \in H_1$. Additionally, $H_{\mathrm{comp}}$ has two edges $(H^{\mathrm{un}}_1, H^{\mathrm{un}}_2)$ and $(H^{\mathrm{un}}_3, H^{\mathrm{un}}_2)$ because $(i_3,i_5)\in A(D) \setminus A(H)$ where $i_3~\in H_1$ and $i_5\in H_2$, and $(i_6,i_5)\in A(D) \setminus A(H)$ where $i_6\in H_3$ and $i_5\in H_2$.

Definition 3.7

Let H be a finite acyclic directed graph with n vertices. For a pair of vertices $i,j \in [n],$ consider an undirected path $p^{\mathrm{un}}$ in $H^{\mathrm{un}}$ connecting i to j. Let $i=i_1, i_2, \ldots , i_k=j$ be vertices of $p^{\mathrm{un}}$ (in order) where $\{i_1,\ldots , i_k\} \subseteq [n]$. Let p be a subset of A(H) whose underlying undirected graph is $p^{\mathrm{un}}.$ We define the net length of p as

$$\begin{aligned} \mathrm{net} (p) = |\{ (i_l,i_{l+1}) \in p : l \in [k]\}|-|\{(i_{l+1},i_l) \in p : l \in [k] \}|. \end{aligned}$$

In other words, the net length of p is the difference between the number of “correctly" oriented edges and the number of “incorrectly" oriented edges in p.

Definition 3.8

(path consistent) Let H be a finite acyclic directed graph with n vertices. We say H is path consistent if for any pair $i,j \in [n]$ and two undirected paths $p^{\mathrm{un}}$ and $q^{\mathrm{un}}$ in $H^{\mathrm{un}}$ connecting i to j, we have

$$\begin{aligned} \mathrm{net} (p) = \mathrm{net} (q), \end{aligned}$$

where p and q are the subsets of A(H) whose underlying undirected graphs are the paths $p^{\mathrm{un}}$ and $q^{\mathrm{un}}$ in $H^{\mathrm{un}}$.

Note that H is path consistent, if the difference between the number of correctly oriented edges and the number of incorrectly oriented edges in any path depends only on i and j.

Remark 3.9

The homogeneous cycles are path consistent by definition.

Example 3.10

Consider the following finite directed acyclic graph $C_1$ given in Figure 4.

Fig. 4

Path consistent directed graph $C_1$

Consider the paths between the vertices $i_1$ and $i_4$. The first path has only one directed edge $(i_1,i_4)$ which has one correctly oriented edge and no incorrectly oriented edges. The second path consists of the directed edges $(i_1,i_2), (i_3,i_2), (i_3,i_4)$ such that the two edges $(i_1,i_2), (i_3,i_4)$ are correctly oriented whereas $(i_3,i_2)$ is incorrectly oriented.

Definition 3.11

Let H be a path consistent graph such that $H^{\text {un}}$ is connected. For any two vertices $u, v \in V(H),$ pick any undirected path $p^{\text {un}}$ connecting u to v and define

$$\begin{aligned} \ell _{uv} = \mathrm{net } (p) \end{aligned}$$

where p is a subset of A(H) whose underlying undirected graph is $p^{\mathrm{un}}$ in $H^{\mathrm{un}}.$ We call a vertex $u_{*} \in V(H)$ a weight source if there is a vertex $v_{*} \in V(H)$ such that

$$\begin{aligned} \ell _{u_{*}v_{*}} = \text {max}_{u,v} \ell _{uv}\end{aligned}$$

Note that $\ell _{uv}$ is well-defined because H is path consistent. Moreover, a weight source always exists but it is not necessarily unique. As we shall see in Proposition 3.13, the choice of a weight source does not matter.

Definition 3.12

Let H be a path consistent graph such that $H^{\text {un}}$ is connected. Let $u_{*}$ be a weight source. The weight function (with respect to $u_{*}$) of H is defined as

$$\begin{aligned} \omega _{u_{*}} :V(H)&\rightarrow {\mathbb {Z}} \\ i&\mapsto \ell _{u_{*},i}. \end{aligned}$$

Proposition 3.13

( [23, Proposition 3.13]) Let H be a path consistent graph and $H^{\text {un}}$ be connected. Let $\omega _{u_{*}}$ be the weight function of H with respect to $u_{*}$. Then:

• (1) The equality $\omega _{u_{*}}(i)=\omega _{u_{*}}(j)-1$ holds for each directed edge $(i,j) \in A(H)$.

• (2) $\omega _{u_{*}}(i) \ge 0$ for all $i\in V(H)$. The equality holds if and only if i is a weight source.

• (3) If $u'_{*}$ is another weight source then $\omega _{u_{*}} = \omega _{u'_{*}}$. Thus the weight function of H is well-defined, i.e. independent of weight source.

Definition 3.14

Let H be a path consistent graph such that $H^{\mathrm{un}}_1, \ldots H^{\mathrm{un}}_k$ are the connected components of $H^{\mathrm{un}}$. Let $H_1, \ldots , H_k$ be directed subgraphs of H such that

• A(H) is the disjoint union of $A(H_1), \ldots , A(H_k)$, and

• underlying undirected graph of $H_j$ is $H^{\mathrm{un}}_j$ for each $j \in [k]$.

The weight function of H is the function $\omega :V(H) \rightarrow {\mathbb {Z}}$ obtained by gluing the weight functions $\omega _j :V(H_j) \rightarrow {\mathbb {Z}}$ of each $H_j$.

Definition 3.15

Let $D=(V(D),A(D))$ be a finite acyclic directed graph and $H \subset D$ a directed subgraph of D with $V(H) = V(D)$ and the directed edge set A(H). Assume that H is path consistent. Each directed edge $e=(H^{\mathrm{un}}_i, H^{\mathrm{un}}_j) \in A(H_{\mathrm{comp}})$ corresponds to a unique directed edge $(v_i,v_j) \in A(D) \setminus A(H)$. We define the weight decrease of e to be the quantity

$$\begin{aligned} \mathrm{wd}(e):=\omega (v_i)-\omega (v_j). \end{aligned}$$

Definition 3.16

(admissible) Let $D=(V(D),A(D))$ be a finite acyclic directed graph and $H \subset D$ a directed subgraph of D with $V(H) = V(D)$ and the directed edge set A(H). Assume that H is path consistent. We say that H is admissible (with respect to D) if, for every directed cycle C in $H_{\mathrm{comp}}$, the condition

$$\begin{aligned} \sum _{e \in C} \mathrm{wd}(e) > -|C| \end{aligned}$$

(3.1)

holds.

Example 3.17

Consider the graph D given in Figure 5. Let H be a directed subgraph of D given with the blue vertices and directed edges. Then $H^{\mathrm{un}}$ has three connected components $H^{\mathrm{un}}_1, H^{\mathrm{un}}_2$ and $H^{\mathrm{un}}_3$. As in Example 3.10 one can show that H is path consistent.

Fig. 5

Directed graph D

Let $H_1$ be the homogeneous cycle on the vertices $i_1,i_2,i_3,i_4$, $H_2$ be the single directed edge $(i_5,i_6)$, and $H_3$ be the single vertex $i_7$ where $H^{\mathrm{un}}_i$ is the underlying undirected graph of $H_i$ for $i\in [3].$ As a weight source, one may choose $i_1$ or $i_3$ in $H_1$, $i_5$ in $H_2$ and $i_7$ in $H_3$. Then, by Proposition 3.13, values of the weight function is given as

$$\begin{aligned} \omega (i)={\left\{ \begin{array}{ll} 1, &{} i \in \{i_2,i_4,i_6\},\\ 0, &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Then the multi-graph $H_{\mathrm{comp}}$ is given as in Figure 6.

Fig. 6

$H_{\mathrm{comp}}$

There are three directed cycles in $H_{\mathrm{comp}}$. The first one is the loop $e_0$ associated to the directed edge $(i_1,i_3)$ for which $\mathrm{wd}(e)=\omega (i_1)-\omega (i_3)=0>-1$. Thus condition in (3.1) holds. The remaining directed cycles in $H_{\mathrm{comp}}$ are given by $e_1,e_2,e_4$ and $e_1,e_3,e_4$ where $e_1,e_2,e_3, e_4$ are associated to the edges $(i_3,i_5), (i_6,i_7), (i_5,i_7), (i_7,i_2)$ in $A(D)\setminus A(H)$, respectively. Consider the directed cycle with the edges $e_1,e_2,e_4$. Then

$$\begin{aligned} \mathrm{wd}(e_1) + \mathrm{wd}(e_2) + \mathrm{wd}(e_4)= 0 > - 3 \end{aligned}$$

satisfying condition (3.1). Similarly, one can check that the remaining directed cycle satisfies condition (3.1), as well. Thus H is admissible with respect to D.

Theorem 3.18

( [23, Theorem 3.18]) Let $D=(V(D),A(D))$ be a finite acyclic directed graph and $H \subset D$ a directed subgraph of D with $V(H) = V(D)$ and the directed edge set A(H). Then the polytope ${\mathcal {A}}_H$ is a face of $\widetilde{{\mathcal {A}}}_D$ if and only if H is path consistent and admissible.

4 Proof of theorem 1.4

In this section, we prove Theorem 1.4. By Proposition 2.3, it suffices to characterize the graphs G where ${\mathcal {A}}_G$ has only triangle 2-faces. We recall that if ${\mathcal {A}}_G$ has non-triangle 2-faces, then G has $C_1$ or $C_2$ as directed subgraphs from Lemma 3.1 and 3.2 . First, we consider the case that G has $C_1$ as directed subgraphs.

Lemma 4.1

Let G be a connected directed graph such that ${\mathcal {A}}_G$ is terminal and reflexive. If G has a directed subgraph $C_1$ whose directed edge set is

$$\begin{aligned} \{(i_1,i_2), (i_3,i_2), (i_3,i_4), (i_1,i_4)\}, \end{aligned}$$

then ${\mathcal {A}}_G$ has a square 2-face.

Proof

The cycle $C_1=\{(i_1,i_2), (i_3,i_2), (i_3,i_4), (i_1,i_4)\}$ of G is homogeneous. Then one has $\mu _{C_1}(i_1)=\mu _{C_1}(i_3)=1$ and $\mu _{C_1}(i_2)=\mu _{C_1}(i_4)=0$. Hence for all $1 \le a,b \le 4$, one has

$$\begin{aligned}\mu _{C_1}(i_a)-\mu _{C_1}(i_b) \le \mathrm{dist}_G(i_a,i_b).\end{aligned}$$

Let ${\mathcal {H}} \subset {\mathbb {R}}^{d}$ be the hyperplane defined by the equation $a_1x_1+\cdots +a_dx_d=1$ as in Lemma 3.4, where

$$\begin{aligned} a_k={\left\{ \begin{array}{ll} \mu _{C_1}(k) &{} :\text{ if } k \in \{i_1,\ldots ,i_4\},\\ \max (\{a_{i_j}-\mathrm{dist}_G(i_j,k) : j=1,\ldots ,4\} \cup \{0\}) &{} :\text{ otherwise }. \end{array}\right. } \end{aligned}$$

Then ${\mathcal {F}}:={\mathcal {A}}_G \cap {\mathcal {H}}$ is a face of ${\mathcal {A}}_G$ containing ${\mathcal {A}}_{C_1}$, since every proper face of ${\mathcal {A}}_G$ is the directed edge polytope ${\mathcal {A}}_D$ of a finite acyclic directed graph D. Let D be a finite acyclic directed graph such that ${\mathcal {F}}={\mathcal {A}}_D$. Since ${\mathcal {F}}$ contains ${\mathcal {A}}_{C_1}$, $C_1$ is a directed subgraph of D. Our goal is to show that ${\mathcal {A}}_{C_1}$ is a face of ${\mathcal {A}}_D$. Let H be a subgraph of D on the vertex set V(D) and the directed edge set $A(C_1)$ with $|V(D)|-4$ isolated vertices. Recall from Example 3.10 that $C_1$ is path consistent and it implies that H is path consistent as well. It remains to show that H is admissible with respect to D.

Let $H^{\mathrm{un}}_1$ be the connected component of $H^{\mathrm{un}}$ whose edge set is

$$\begin{aligned} \{\{i_1,i_2\}, \{i_2,i_3\}, \{i_3,i_4\}, \{i_4,i_1\}\} \end{aligned}$$

and $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3}$ be the other connected components of $H^{\mathrm{un}}$ where $m=|V(D)|$. Note that $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3}$ are isolated vertices of $H^{\mathrm{un}}$. By choosing $i_1$ as a weight source of $C_1$ and the corresponding isolated vertices as weight sources of remaining subgraphs of H, we obtain the weight function of H as

$$\begin{aligned} \omega (i)={\left\{ \begin{array}{ll} 1 &{} :i \in \{i_2,i_4\},\\ 0 &{} : \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Hence for any directed edge e of $H_{\mathrm{comp}}$, one has $-1 \le \mathrm{wd}(e) \le 1$. In particular, for a directed edge $e=(H^{\mathrm{un}}_i,H^{\mathrm{un}}_j)$ of $H_{\mathrm{comp}}$ corresponding to a directed edge $(v_i,v_j)/ \in A(D) \setminus A(H)$, one has $\mathrm{wd}(e)=-1$ if and only if $v_j \in \{i_2,i_4\}$. Hence for any directed cycle C in $H_{\mathrm{comp}}$, there is at most one directed edge e in C such that $\mathrm{wd}(e) < 0$. Moreover, $H_{\mathrm{comp}}$ has no loops since it follows from the definition of ${\mathcal {H}}$ that for $v_i,v_j \in \{i_1,\ldots ,i_4\}$, $(v_i, v_j) \in A(D)$ if and only if $(v_i,v_j) \in A(H)$. This implies that for every directed cycle C in $H_{\mathrm{comp}}$, one has

$$\begin{aligned} \sum _{e \in C} \mathrm{wd}(e) > -|C|. \end{aligned}$$

Therefore, H is admissible with respect to D. Thus, ${\mathcal {A}}_H$ is a face of $\widetilde{{\mathcal {A}}}_D$ from Theorem 3.18. In particular, ${\mathcal {A}}_H$ is a face of ${\mathcal {A}}_G$. Since ${\mathcal {A}}_H$ is a square, ${\mathcal {A}}_G$ has a square 2-face. $\square$

Next, we consider the case that G has $C_2$ as directed subgraphs.

Lemma 4.2

Let G be a connected directed graph such that ${\mathcal {A}}_G$ is terminal and reflexive. Assume that G has a directed subgraph $C_2$ whose directed edge set is

$$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_4,i_3),(i_1,i_4)\}. \end{aligned}$$

If $(i_1,i_3)$ is not a directed edge of G and there does not exist a vertex j with $j \notin \{i_2,i_4\}$ in G such that $(i_1,j)$ and $(j,i_3)$ are directed edge of G, then ${\mathcal {A}}_G$ has a square 2-face.

Proof

The cycle $C_2=\{(i_1,i_2), (i_2,i_3), (i_4,i_3), (i_1,i_4)\}$ of G is homogeneous. Then one has $\mu _{C_2}(i_1)=2,\mu _{C_2}(i_3)=0$ and $\mu _{C_2}(i_2)=\mu _{C_2}(i_4)=1$. Since $(i_1,i_3)$ is not a directed edge of G, for all $1 \le a,b \le 4$, one has

$$\begin{aligned}\mu _{C_2}(i_a)-\mu _{C_2}(i_b) \le \mathrm{dist}_G(i_a,i_b).\end{aligned}$$

Let ${\mathcal {H}} \subset {\mathbb {R}}^{d}$ be the hyperplane defined by the equation $a_1x_1+\cdots +a_dx_d=1$, where

$$\begin{aligned} a_k={\left\{ \begin{array}{ll} \mu _{C_2}(k) &{}:\text{ if } k \in \{i_1,\ldots ,i_4\},\\ \max (\{a_{i_j}-\mathrm{dist}_G(i_j,k): j=1,\ldots ,4\} \cup \{0\}) &{} :\text{ otherwise }. \end{array}\right. } \end{aligned}$$

Similarly to the Proof of Lemma 4.1, we define ${\mathcal {F}}:={\mathcal {A}}_G \cap {\mathcal {H}}$ a face of ${\mathcal {A}}_G$ containing ${\mathcal {A}}_{C_2}$ and we show that ${\mathcal {A}}_{C_2}$ is a face of ${\mathcal {A}}_D$.

Then $C_2$ is path consistent. Now, we define the path consistent subgraph H of D on the vertex set V(D) and the directed edge set $A(C_2)$, namely, H has $|V(D)|-4$ isolated vertices. Let $H^{\mathrm{un}}_1$ be the connected component of $H^{\mathrm{un}}$ whose edge set is

$$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_4,i_3),(i_1,i_4)\} \end{aligned}$$

and $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3}$ be the other connected components of $H^{\mathrm{un}}$, where $m=|V(D)|$. Note that $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3}$ are isolated vertices of $H^{\mathrm{un}}$. By choosing $i_1$ as a weight source in $C_2$ and the corresponding isolated vertices as weight sources of remaining subgraphs of H, we obtain the weight function of H as

$$\begin{aligned} \omega (i)={\left\{ \begin{array}{ll} 2 &{} : i =i_3,\\ 1 &{}: i \in \{i_2,i_4\},\\ 0 &{} : \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Hence, for any directed edge e of $H_{\mathrm{comp}}$, one has $-2 \le \mathrm{wd}(e) \le 2$. In particular, for a directed edge $e=(H^{\mathrm{un}}_i,H^{\mathrm{un}}_j)$ of $H_{\mathrm{comp}}$ corresponding to a directed edge $(v_i,v_j) \in A(D) \setminus A(H)$, one has $\mathrm{wd}(e)=-2$ if and only if $v_j=i_3$ and $v_i \in V(D) \setminus \{i_1,i_2,i_3,i_4\}$. Furthermore, $\mathrm{wd}(e)=-1$ if and only if $v_j \in \{i_2,i_4\}$ and $v_i \in V(D) \setminus \{i_1,i_2,i_3,i_4\}$. Indeed, $H_{\mathrm{comp}}$ has no loops since it follows from the definition of ${\mathcal {H}}$ that for $v_i,v_j \in \{i_1,\ldots ,i_4\}$, $(v_i, v_j) \in A(D)$ if and only if $(v_i,v_j) \in A(H)$. Thus, for any directed cycle C in $H_{\mathrm{comp}}$, there is at most one directed edge e in C such that $\mathrm{wd}(e) < 0$. Suppose that there exists a directed cycle C in $H_{\mathrm{comp}}$ such that

$$\begin{aligned} \sum _{e \in C} \mathrm{wd}(e) \le -|C|. \end{aligned}$$

Then we may assume the extreme cycle case $C=(e_1,e_2)$ with $\mathrm{wd}(e_1)=-2$ and $\mathrm{wd}(e_2)$=0. This implies that there exists a vertex j with $j \ne i_2,i_4$ in G such that $(i_1,j)$ and $(j,i_3)$ are directed edges of G, contrary to assumption. Therefore, H is admissible with respect to D. Thus, we conclude that ${\mathcal {A}}_H$ is a square 2-face of $\widetilde{{\mathcal {A}}}_D$ from Theorem 3.18 and hence of ${\mathcal {A}}_G$.

$\square$

Finally, we see the case where ${\mathcal {A}}_G$ has a non-triangle 2-face.

Lemma 4.3

Let G be a connected directed graph such that ${\mathcal {A}}_G$ is terminal and reflexive. If ${\mathcal {A}}_G$ has a non-triangle 2-face, then G satisfies one of the following:

• G has a directed subgraph $C_1$ whose directed edge set is

  $$\begin{aligned} \{(i_1,i_2), (i_1,i_4), (i_3,i_2), (i_3,i_4)\}; \end{aligned}$$

• There exists a directed subgraph $C_2$ of G whose directed edge set is

  $$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_1,i_4), (i_4,i_3)\}, \end{aligned}$$

  such that $(i_1,i_3)$ is not a directed edge of G and there does not exist a vertex j in G such that $(i_1,j)$ and $(j,i_3)$ are directed edge of G.

Proof

It follows from Lemmas 3.1 and 3.2 that G has $C_1$ or $C_2$ as subgraphs. Suppose that G does not have $C_1$ as a subgraph. Then we can assume that G has $C_2$ as a subgraph such that ${\mathcal {A}}_{C_2}$ is a face of ${\mathcal {A}}_G$. If $(i_1,i_3)$ is a directed edge of G, then ${\mathcal {A}}_{C_2}$ is not a face of ${\mathcal {A}}_G$. Indeed, the open line segment between the origin and the lattice point $\rho ((i_1,i_3))$ intersects ${\mathcal {A}}_{C_2}$. Since the origin belongs to the relative interior of ${\mathcal {A}}_G$, this implies that ${\mathcal {A}}_{C_2}$ intersects the relative interior of ${\mathcal {A}}_G$. This contradicts that ${\mathcal {A}}_{C_2}$ is a proper face of ${\mathcal {A}}_G$. Hence $(i_1,i_3)$ is not a directed edge of G.

In the last part of the proof, we will show that there exists no j in $V(G)\setminus \{i_2,i_4\}$ such that $(i_1,j)$ and $(j,i_3)$ are directed edges of G. On the contrary, suppose that there exists such a vertex $j \in V(G) \setminus \{i_2,i_4\}$. Let $j_1,\ldots ,j_k \in V(G) \setminus \{i_2,i_4\}$ be the vertices of G such that for any $1 \le l \le k$, $(i_1,j_l)$ and $(j_l,i_3)$ are directed edges of G. Let $G'$ be the subgraph of G whose directed edge set is

$$\begin{aligned} \{(i_1,i_2), (i_2,i_3), (i_1,i_4), (i_4,i_3)\} \cup \{ (i_1,j_l), (j_l,i_3) : 1 \le l \le k \}. \end{aligned}$$

Observe that $G'$ is path consistent. We show that ${\mathcal {A}}_{G'}$ is face of ${\mathcal {A}}_G$. Set $n=|V(G)|$ and $A=V(G) \setminus \{i_1,i_2,i_3,i_4,j_1,\ldots ,j_k\}$. Let ${\mathcal {H}} \subset {\mathbb {R}}^n$ be the hyperplane defined by the equation $a_1x_1+\cdots +a_n x_n=1$ and $\mathcal {H }^{+} \subset {\mathbb {R}}^n$ the closed half-space defined by the inequality $a_1x_1+\cdots +a_nx_n \le 1$, where

$$\begin{aligned} a_l={\left\{ \begin{array}{ll} 2 &{}:\text{ if } l=i_1,\\ 1 &{}:\text{ if } l \in \{i_2,i_4,j_1,\ldots ,j_k\},\\ 0 &{}:\text{ if } l=i_3,\\ \max (\{a_{v}-\mathrm{dist}_G(v,l): v \in V(G) \setminus A\} \cup \{0\}) &{} :\text{ if } l \in A. \end{array}\right. } \end{aligned}$$

Here, for $l \in A$, one has $a_l=0$ if there is no v with $\mathrm{dist}_G(v,l) < \infty$. We claim that for $l \in A$, one has

$$\begin{aligned} a_l \le a_l', \end{aligned}$$

(4.1)

where $a_l'=\min (\{a_v+\mathrm{dist}_G(l,v):v \in V(G) \setminus A\} \cup \{0\})$. Indeed, if $a_l > a_l'$, then there are $v,v' \in V(G) \setminus A$ such that $\mathrm{dist}_G(v,l)<\infty$, $\mathrm{dist}_G(l,v') < \infty$ and

$$\begin{aligned}a_v-\mathrm{dist}_G(v,l) > a_{v'}+\mathrm{dist}_G(l,v'). \end{aligned}$$

Since $\mathrm{dist}_G(v,l)+\mathrm{dist}_G(l,v') \ge \mathrm{dist}_G(v,v')$, one has that

$$\begin{aligned} a_v-a_{v'} > \mathrm{dist}_G(v,l)+\mathrm{dist}_G(l,v') \ge \mathrm{dist}_G(v,v'). \end{aligned}$$

However, since $(i_1,i_3)$ is not a directed edge of G, it follows that for any $v,v' \in V(G) \setminus A$, one has

$$\begin{aligned} a_v-a_{v'} \le \mathrm{dist}_G(v,v'), \end{aligned}$$

a contradiction.

Now, we see that ${\mathcal {H}}$ is a supporting hyperplane of ${\mathcal {A}}_G$. Since ${\mathcal {A}}_{G'} \subset {\mathcal {H}}$, it is enough to show ${\mathcal {A}}_{G} \subset {\mathcal {H}}^+$. Let $e=(i,j)$ be a directed edge of G. When $i \in V(G) \setminus A$ and $j \in A$, one has that $a_j \ge \max \{a_i-1,0\}$ by the definition of $a_j$. Hence $a_i-a_j \le 1$. This implies $\rho (e) \in {\mathcal {H}}^+$. For any $l \in A$, one has $a_l = 0$ or 1. If $i \in A$, then $a_i-a_j \le 1$ for any $j \in V(G)$. This implies $\rho (e) \in {\mathcal {H}}^{+}$. Therefore, ${\mathcal {A}}_{G} \subset {\mathcal {H}}^+$. Thus ${\mathcal {H}}$ is a supporting hyperplane of ${\mathcal {A}}_G$ and the proper face ${\mathcal {F}}={\mathcal {A}}_G \cap {\mathcal {H}}$ contains ${\mathcal {A}}_{G'}$.

Recall from Lemma 3.1 that every proper face of ${\mathcal {A}}_G$ is the directed edge polytope of a finite acyclic directed graph. Let D be a finite acyclic directed graph such that ${\mathcal {F}}={\mathcal {A}}_D$. Since ${\mathcal {F}}$ contains ${\mathcal {A}}_{G'}$, $G'$ is a subgraph of D. We show that ${\mathcal {A}}_{G'}$ is a face of ${\mathcal {A}}_D$. Since the origin belongs to the relative interior of ${\mathcal {A}}_{G}$, it is enough to show that ${\mathcal {A}}_{G'}$ is a face of $\widetilde{{\mathcal {A}}}_D$.

Let H be the subgraph of D on the vertex set V(D) and the directed edge set $A(G')$, namely, H has $|V(D)|-4-k$ isolated vertices. Let $H^{\mathrm{un}}_1$ be the connected component of $H^{\mathrm{un}}$ whose edge set is

$$\begin{aligned} \{\{i_1,i_2\}, \{i_2,i_3\}, \{i_3,i_4\}, \{i_4,i_1\}\} \cup \{ \{i_1,j_l\},\{j_l,i_3\} : 1 \le l \le k \} \end{aligned}$$

and $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3-k}$ be the other connected components of $H^{\mathrm{un}}$, where $m=|V(D)|$. Note that $H^{\mathrm{un}}_2,\ldots ,H^{\mathrm{un}}_{m-3-k}$ are isolated vertices of $H^{\mathrm{un}}$. Then we have

$$\begin{aligned} \omega (i)={\left\{ \begin{array}{ll} 2 &{} :\text{ if } i =i_3,\\ 1 &{} :\text{ if } i \in \{i_2,i_4,j_1,\ldots ,j_k\},\\ 0 &{} :\text{ otherwise }. \end{array}\right. } \end{aligned}$$

Hence for any directed edge e of $H_{\mathrm{comp}}$, one has $-2 \le \mathrm{wd}(e) \le 2$. In particular, for a directed edge $e=(H^{\mathrm{un}}_i,H^{\mathrm{un}}_j)$ of $H_{\mathrm{comp}}$ corresponding to a directed edge $(v_i,v_j) \in A(D) \setminus A(H)$, one has $\mathrm{wd}(e)=-2$ if and only if $v_j=i_3$ and $v_i \in V(D) \setminus \{i_1,i_2,i_3,i_4,j_1,\ldots ,j_k\}$, and $\mathrm{wd}(e)=-1$ if and only if $v_j \in \{i_2,i_4,j_1,\ldots ,j_k\}$ and $v_i \in V(D) \setminus \{i_1,i_2,i_3,i_4,j_1,\ldots ,j_k\}$. Indeed, $H_{\mathrm{comp}}$ has no loops since it follows from the definition of ${\mathcal {H}}$ that for $v_i,v_j \in \{i_1,\ldots ,i_4,j_1,\ldots ,j_k\}$, $(v_i, v_j) \in A(D)$ if and only if $(v_i,v_j) \in A(H)$. Hence for any directed cycle C in $H_{\mathrm{comp}}$, there is at most one directed edge e in C such that $\mathrm{wd}(e) < 0$. Suppose that there exists a directed cycle C in $H_{\mathrm{comp}}$ such that

$$\begin{aligned} \sum _{e \in C} \mathrm{wd}(e) \le -|C|. \end{aligned}$$

Then we can assume that $C=(e_1,e_2)$ and $\mathrm{wd}(e_1)=-2$ and $\mathrm{wd}(e_2)$=0. This implies that there exists a vertex j with $j \notin \{i_2,i_4,j_1,\ldots ,j_k\}$ in G such that $(i_1,j)$ and $(j,i_3)$ are directed edge of G. However, there is no such j except for $\{j_1,\ldots ,j_k\}$, a contradiction. Therefore, H is admissible with respect to D. Thus, ${\mathcal {A}}_H$ is a face of $\widetilde{{\mathcal {A}}}_D$ from Theorem 3.18. In particular, ${\mathcal {A}}_{H}$ is a face of ${\mathcal {A}}_G$. On the other hand, ${\mathcal {A}}_{C_2}$ is not a face of ${\mathcal {A}}_{G'}$. Indeed, $C_2$ is not admissible with respect to $G'$. This contradicts the fact that for any two proper faces ${\mathcal {F}}_1$ and ${\mathcal {F}}_2$ of a convex polytope, ${\mathcal {F}}_1 \cap {\mathcal {F}}_2$ is a face of both ${\mathcal {F}}_1$ and ${\mathcal {F}}_2$. Because one can let ${\mathcal {F}}_1 = {\mathcal {A}}_{C_2}$ and ${\mathcal {F}}_2 = {\mathcal {A}}_{G'}$, where ${\mathcal {F}}_1 \cap {\mathcal {F}}_2={\mathcal {A}}_{C_2}$.$\square$

Now, we prove Theorem 1.4.

Proof of Theorem 1.4

$X_G$ is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3 if and only if all 2-faces of ${\mathcal {A}}_G$ are triangles from Proposition 2.3. Therefore, Lemmas 4.1 and 4.2 imply $(1) \Rightarrow (2)$, and Lemma 4.3 implies $(2) \Rightarrow (1)$. $\square$

A simple argument proves Corollary 1.5 as follows.

Proof of Corollary 1.5

If $X_G$ is smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3, then the fact that G has no directed subgraph $C_1$ along with the fact that G is symmetric, implies that $G^{\mathrm{un}}$ does not have a 4-cycle. On the other hand, if $G^{\mathrm{un}}$ has no 4-cycles, then G does not have $C_1$ nor $C_2$. $\square$

5 Examples and concluding remarks

In this section we present two different families of directed graphs such that their associated Gorenstein toric Fano variety is not ${\mathbb {Q}}$-factorial (equivalently smooth by [11, Theorem 2.2]) but rigid. Recall that we consider connected directed graphs such that every directed edge belongs to a directed cycle. We conclude this section with some remarks about the calculation of $T^1_{X_G}$ when ${\mathcal {A}}_G$ a square 2-face.

Proposition 5.1

Let $G_{2k}$ be a symmetric directed graph with $k \ge 2$ such that $G_{2k}^{\mathrm{un}}$ is a 2k-cycle. Then $\dim ({\mathcal {P}}_{G_{2k}})=2k-1$ and every $(2k-3)$-face of ${\mathcal {P}}_{G_{2k}}$ is a simplex. Hence $X_{G_{2k}}$ is ${\mathbb {Q}}$-factorial in codimension $2k-2$. In particular, $X_{G_{2k}}$ is rigid when $k \ge 3$.

Proof

This follows from [9, Proposition 4.3]. $\square$

This proposition presents a family of directed graphs G such that $X_G$ is rigid and ${\mathbb {Q}}$-factorial in higher codimension. Higashitani gave a characterization of all directed graphs whose associated Gorenstein toric Fano varieties are ${\mathbb {Q}}$-factorial. On the other hand, Theorem 1.4 is a characterization of all directed graphs whose associated Gorenstein toric Fano varieties are ${\mathbb {Q}}$-factorial in codimension 3. Then the following problem naturally occurs.

Problem 5.2

For any positive integer $k \ge 4$, characterize all directed graphs whose associated Gorenstein toric Fano varieties are ${\mathbb {Q}}$-factorial in codimension k.

Note that a Gorenstein toric Fano variety $X_{{\mathcal {P}}}$ with terminal singularities is ${\mathbb {Q}}$-factorial in codimension k if and only if all $(k-1)$-faces of the associated terminal reflexive polytope ${\mathcal {P}}$ are simplices. We recall that each proper face of a terminal reflexive directed edge polytope is the directed edge polytope of a finite acyclic directed graph by Lemma 3.1. Hence in order to solve this problem, we should investigate acyclic directed graphs whose directed edge polytopes are simplices.

Problem 5.3

Classify all acyclic directed graphs whose associated directed edge polytopes are simplices.

Fig. 7

Graph G

Next, we introduce another family of non-smooth rigid Gorenstein toric Fano varieties.

Proposition 5.4

Let G be a connected directed graph without multiple edges constructed by gluing directed 2k-cycle and 2l-cycle along any number of edges. Then $X_G$ is rigid.

Proof

If $k \ge 3$ or $l \ge 3$, it suffices to consider the case $k=2$ and $l\ge 3$. Then the two even cycles can be glued along one, two or three edges. In all cases, G has no directed subgraph $C_1$ and $C_2$. If $k=l=2$, then the only case where G contains $C_2$ (or $C_2$) is the case where we glue the cycles along two edges. By Theorem 1.4, since there exists a vertex j with satisfied property, $X_G$ is rigid. $\square$

The investigation of the necessary condition for rigidity of $X_G$ is more challenging. If the directed edge polytope ${\mathcal {A}}_G$ has a square 2-face characterized as in Section 4, one can consult the comparison theorems of Kleppe in [13, Theorem 3.9] to relate $T^1_{X_P}$ to the degree zero part of $T^1_{{{\,\mathrm{cone}\,}}(X_P)}$. Namely one obtains the following isomorphism

$$\begin{aligned} T^1_{X_P} \cong (T^1_{{{\,\mathrm{cone}\,}}(X_P)})_{0}. \end{aligned}$$

Here ${{\,\mathrm{cone}\,}}(X_P)$ is the cone over $X_P$ and is an affine Gorenstein toric variety. We consider the associated cone to this affine toric variety as ${{\,\mathrm{cone}\,}}(({\mathcal {A}}_G),1)) \subseteq N_{{\mathbb {R}}} \oplus {\mathbb {R}} \cong {\mathbb {R}}^{n+1}$. The first-order deformations of affine (Gorenstein) toric varieties has been studied by Altmann and it is known that $T^1$ admits an M-grading [1, Theorem 2.3]. The degree zero part means that we consider the multidegrees $R\in M \times \{0\} \cong {\mathbb {Z}}^{n+1}$.

Any ${\mathbb {Q}}$-Gorenstein affine toric variety smooth in codimension 2 and ${\mathbb {Q}}$-factorial in codimension 3 is rigid [2, Corollary 6.5.1]. Moreover by [2, Corollary 6.5], the existence of a non-triangle 2-face implies that $\dim (T^1_{{{\,\mathrm{cone}\,}}(X_G)})=\infty$ for $\dim ({\mathcal {A}}_G)\ge 3$. However, this fact does not directly guarantee the existence of a degree zero component as explained in [21, Proposition 3.9] for $\dim ({\mathcal {A}}_G)\ge 4$. In particular for $\dim ({\mathcal {A}}_G)=3$, since ${\mathcal {A}}_G$ is reflexive, one obtains a non-zero homogenous component of $T^1_{{{\,\mathrm{cone}\,}}(X_G)}$ for the multidegree (m, 0) where $m \in M \cong {\mathbb {R}}^n$ is defining the affine supporting hyperplane of the square 2-facet. This computation can be done by following the combinatorial recipes presented in [1, 2] which we do not present in detail here. In general, this question is not trivial and needs to be explored.

Example 5.5

Let us consider the four dimensional symmetric edge polytope ${\mathcal {P}}_G$ of the graph G as in the Figure 7.

The symmetric edge polytope ${\mathcal {P}}_G$ has 10 square 2-faces, but each of them have lattice distance 2 to the origin. However for the multidegree $R=[a+1,a,a+1,a,a,0] \in M \times \{0\}$, for $a \in {\mathbb {Z}}$, one obtains that $T^1_{X_G}(-R) \ne 0$, hence $X_G$ is not rigid.

Problem 5.6

Suppose that ${\mathcal {A}}_G$ has a square 2-face. Determine whether $X_G$ is rigid or not.

In the perspective of this paper, this is a computational open question which would conclude the classification of all directed graphs G such that $X_G$ is rigid.