# Splittings of toric ideals of graphs

Anargyros Katsabekis  and  Apostolos Thoma  Anargyros Katsabekis, Department
of Mathematics, University of Ioannina, Ioannina 45110, Greece
<EMAIL_ADDRESS>Apostolos Thoma, Department of Mathematics, University of
Ioannina, Ioannina 45110, Greece<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a simple graph on the vertex set $\\{v_{1},\ldots,v_{n}\\}$. An
algebraic object attached to $G$ is the toric ideal $I_{G}$. We say that
$I_{G}$ is subgraph splittable if there exist subgraphs $G_{1}$ and $G_{2}$ of
$G$ such that $I_{G}=I_{G_{1}}+I_{G_{2}}$, where both $I_{G_{1}}$ and
$I_{G_{2}}$ are not equal to $I_{G}$. We show that $I_{G}$ is subgraph
splittable if and only if it is edge splittable. We also prove that the toric
ideal of a complete bipartite graph is not subgraph splittable. In contrast,
we show that the toric ideal of a complete graph $K_{n}$ is always subgraph
splittable when $n\geq 4$. Additionally, we show that the toric ideal of
$K_{n}$ has a minimal splitting if and only if $4\leq n\leq 5$. Finally, we
prove that any minimal splitting of $I_{G}$ is also a reduced splitting.

###### Key words and phrases:

Splittings, toric ideals, graphs, minimal systems of binomial generators.

###### 1991 Mathematics Subject Classification:

13F65, 14M25, 05C25, 05E40.

Corresponding author: Anargyros Katsabekis

##  1\. Introduction

Let $A=\\{{\bf a}_{1},\ldots,{\bf a}_{m}\\}$ be a subset of $\mathbb{N}^{n}$
such that $A$ does not contain the zero vector. Consider the polynomial ring
$K[x_{1},\ldots,x_{m}]$ over any field $K$. We grade $K[x_{1},\ldots,x_{m}]$
by the semigroup $\mathbb{N}A=\\{l_{1}{\bf a}_{1}+\cdots+l_{m}{\bf a}_{m}\\}$
setting ${\rm deg}_{A}(x_{i})={\bf a}_{i}$ for $i=1,\ldots,m$. The $A$-degree
of a monomial ${\bf x}^{\bf u}=x_{1}^{u_{1}}\cdots x_{m}^{u_{m}}$ is defined
by ${\rm deg}_{A}({\bf x}^{\bf u})=u_{1}{\bf a}_{1}+\cdots+u_{m}{\bf
a}_{m}\in\mathbb{N}A$. The $A$-fiber of a vector ${\bf b}\in\mathbb{N}^{n}$ is
the set of all monomials in $K[x_{1},\ldots,x_{m}]$ with $A$-degree equal to
${\bf b}$. The toric ideal $I_{A}$ is the prime ideal generated by all the
binomials ${\bf x}^{\bf u}-{\bf x}^{\bf v}$ such that ${\rm deg}_{A}({\bf
x}^{\bf u})={\rm deg}_{A}({\bf x}^{\bf v})$.

A recent direction in the theory of toric ideals is to decide when $I_{A}$ is
splittable, see [5, 6, 7]. The toric ideal $I_{A}$ is splittable if it has a
toric splitting i.e. if there exist toric ideals $I_{A_{1}},I_{A_{2}}$ such
that $I_{A}=I_{A_{1}}+I_{A_{2}}$ and $I_{A_{i}}\not=I_{A}$, for all $1\leq
i\leq 2$. To every simple graph $G$ one can associate the toric ideal $I_{G}$.
In [5] G. Favacchio, J. Hofscheier, G. Keiper, and A. Van Tuyl consider the
aforementioned problem for the toric ideal $I_{G}$, namely they study when
$I_{G}$ has a toric splitting of the form $I_{G}=I_{G_{1}}+I_{G_{2}}$, where
$I_{G_{i}}$, $1\leq i\leq 2$, is the toric ideal of a subgraph $G_{i}$ of $G$.
More precisely, given a graph $G$ and an even cycle $C$, they consider the
graph $H$ which is formed by identifying any edge of $G$ with an edge of $C$.
They show [5, Theorem 3.7] that $I_{H}=I_{G}+I_{C}$ is a splitting of $I_{H}$.
They also prove [5, Corollary 4.8] that if $G_{1}$ and $G_{2}$ form a
splitting of $G$ along an edge $e$ and at least one of $G_{1}$ or $G_{2}$ is
bipartite, then $I_{G}=I_{G_{1}}+I_{G_{2}}$ is a splitting of $I_{G}$.
Moreover, when $I_{G}$ has such a splitting, they show [5, Theorem 4.11] how
the graded Betti numbers of $I_{G}$ are related with those of $I_{G_{1}}$ and
$I_{G_{2}}$. P. Gimenez and H. Srinivasan showed [6, Theorem 3.4] that if
$G_{1}$ and $G_{2}$ form a splitting of $G$ along an edge $e$, then $I_{G}$
splits into $I_{G}=I_{G_{1}}+I_{G_{2}}$ if and only if at least one of $G_{1}$
or $G_{2}$ is bipartite.

This paper aims to partially answer [5, Question 5.1], namely for what graphs
$G$ can we find $G_{1}$ and $G_{2}$ so that their respective toric ideals
satisfy $I_{G}=I_{G_{1}}+I_{G_{2}}$? More generally, can we classify when
$I_{G}$ is a splittable toric ideal in terms of $G$? We give a complete answer
to the latter question in the case that both $G_{1},G_{2}$ are subgraphs of
$G$. We call splittings like that subgraph splittings and the ideal $I_{G}$ is
called subgraph splittable. Note that there may be splittings of graphs $G$
which are not subgraph splittings, see Remark 4.9. Our approach is based on
the graphs $G\char 92\relax e$ and $G_{S}^{e}$ introduced in section 2, where
$e$ is an edge of $G$ and $S$ is a minimal system of binomial generators of
$I_{G}$. We show that $I_{G}$ is subgraph splittable if and only if there is
an edge $e$ of $G$ and a minimal generating set of binomials $S$ of $I_{G}$
such that $I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax e}$ is a splitting, see
Theorem 2.10. As an application of our results, we prove that the toric ideal
of a complete bipartite graph is not subgraph splittable (see Corollary 2.13)
and the toric ideal of the suspension of a cycle of length $n\geq 3$ is
subgraph splittable if and only if either $n=4$ or $n$ is odd, see Theorem
2.14. In section 3 we study the case that $G$ coincides with the complete
graph $K_{n}$ on $n$ vertices. We show that $I_{K_{n}}$ is subgraph splittable
if and only if $n\geq 4$, see Theorem 3.1. Moreover, we introduce minimal
splittings and show (Theorem 3.10) that $I_{K_{n}}$ does not have a minimal
splitting for $n\geq 6$. In section 4 we define reduced splittings of toric
ideals and prove that every minimal splitting of $I_{G}$ is also reduced, see
Theorem 4.7.

##  2\. Edge splittings

In this section, we first collect important notations and definitions used in
the paper. For unexplained terminology in graph theory, we refer to [10]. Let
$G$ be a finite, connected and undirected graph having no loops and no
multiple edges on the vertex set $V(G)=\\{v_{1},\ldots,v_{n}\\}$, and let
$E(G)=\\{e_{1},\ldots,e_{m}\\}$ be the set of edges of $G$. Two edges of $G$
are called adjacent if they share a common vertex. To each edge
$e=\\{v_{i},v_{j}\\}\in E(G)$, we associate the vector ${\bf
a}_{e}\in\\{0,1\\}^{n}$ defined as follows: the $i$th entry is $1$, the $j$th
entry is 1, and the remaining entries are zero. By $I_{G}$ we denote the toric
ideal $I_{A_{G}}$ in $K[e_{1},\ldots,e_{m}]$, where $A_{G}=\\{{\bf a}_{e}|e\in
E(G)\\}\subset\mathbb{N}^{n}$.

A walk of length $q$ of $G$ connecting $v_{1}\in V(G)$ with $v_{q+1}$ is a
finite sequence of the form
$w=(\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\ldots,\\{v_{q-1},v_{q}\\},\\{v_{q},v_{q+1}\\})$
with each $\\{v_{i},v_{i+1}\\}\in E(G)$, $1\leq i\leq q$. An even
(respectively, odd) walk is a walk of even (respectively, odd) length. The
walk $w$ is called closed if $v_{q+1}=v_{1}$. A cycle is a closed walk

$w=(\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\ldots,\\{v_{q-1},v_{q}\\},\\{v_{q},v_{1}\\})$

with $q\geq 3$ and $v_{i}\not=v_{j}$, for every $1\leq i<j\leq q$. A cut
vertex is a vertex of $G$ whose removal increases the number of connected
components of the remaining subgraph. A graph is called biconnected if it is
connected and does not contain a cut vertex. A block is a maximal biconnected
subgraph of $G$.

Given an even closed walk $w=(e_{i_{1}},e_{i_{2}},\ldots,e_{i_{2q}})$ of $G$,
we write $B_{w}$ for the binomial
$B_{w}=\prod_{k=1}^{q}e_{i_{2k-1}}-\prod_{k=1}^{q}e_{i_{2k}}\in I_{G}$. By
[13, Proposition 10.1.5] the ideal $I_{G}$ is generated by all the binomials
$B_{w}$, where $w$ is an even closed walk of $G$. We say that $w$ is a
primitive walk if the corresponding binomial $B_{w}$ is primitive. Recall that
given a set of vectors $A\subset\mathbb{N}^{n}$, the binomial ${\bf x}^{\bf
u}-{\bf x}^{\bf v}$ in $I_{A}$ is called primitive if there exists no other
binomial ${\bf x}^{\bf w}-{\bf x}^{\bf z}\in I_{A}$ such that ${\bf x}^{\bf
w}$ divides ${\bf x}^{\bf u}$ and ${\bf x}^{\bf z}$ divides ${\bf x}^{\bf v}$.
Every minimal binomial generator of $I_{A}$ is primitive, see [11].

Every even primitive walk $w=(e_{i_{1}},e_{i_{2}},\ldots,e_{i_{2q}})$
partitions the set of edges of $w$ in the two sets $E_{1}=\\{e_{i_{j}}|j\
\textrm{odd}\\}$ and $E_{2}=\\{e_{i_{j}}|j\ \textrm{even}\\}$. The edges of
$E_{1}$ are called odd edges of $w$ and those of $E_{2}$ even. A sink of a
block $B$ is a common vertex of two odd or two even edges of the primitive
walk $w$ which belongs to $B$. The primitive walk $w$ is called strongly
primitive if it has no two sinks with distance one in any cyclic block.

Let $w=(e_{1},e_{2},\ldots,e_{2q})$ be an even primitive walk and
$f=\\{v_{i},v_{j}\\}$ be a chord of $w$ with $i<j$, namely an edge
$f=\\{v_{i},v_{j}\\}$ of $G$ such that $f\notin E(w)$. Then $f$ breaks $w$ in
two walks: $w_{1}=(e_{1},\ldots,e_{i-1},f,e_{j},\ldots,e_{2q})$ and
$w_{2}=(e_{i},\ldots,e_{j-1},f)$. The chord $f$ is called bridge of $w$ if
there exist two different blocks $B_{i}$, $B_{j}$ of $w$ such that $v_{i}\in
B_{i}$ and $v_{j}\in B_{j}$. The chord $f$ is called even (respectively odd)
if it is not a bridge and breaks $w$ in two even walks (respectively odd).

Let $f=\\{v_{i},v_{j}\\}$ be an odd chord of $w$ with $i<j$ and
$f^{\prime}=\\{v_{k},v_{l}\\}$ be another odd chord of $w$ with $k<l$. We say
that the odd chords $f$ and $f^{\prime}$ cross effectively in $w$ if $k-i$ is
odd and either $i<k<j<l$ or $k<i<l<j$. We call an $F_{4}$ of the walk $w$ a
cycle $(e,f,e^{\prime},f^{\prime})$ of length four which consists of two edges
$e,e^{\prime}$ of the walk $w$ both odd or both even, and two odd chords $f$
and $f^{\prime}$ which cross effectively in $w$. We say that the odd chords
$f,f^{\prime}$ cross strongly effectively in $w$ if they cross effectively and
they do not form an $F_{4}$ in $w$.

A binomial $B_{w}\in I_{G}$ is called minimal if it belongs to a minimal
system of binomial generators of $I_{G}$. Since $I_{G}$ is homogeneous, the
graded version of Nakayama’s Lemma implies that every minimal system of
generators of $I_{G}$ has the same cardinality.

The next theorem provides a characterization for the minimal binomials of
$I_{G}$.

######  Theorem 2.1.

([10, Theorem 4.13]) Let $w$ be an even closed walk of $G$. Then $B_{w}$ is a
minimal binomial if and only if

  1. (1)

$w$ is strongly primitive,

  2. (2)

all the chords of $w$ are odd and there are not two of them which cross
strongly effectively and

  3. (3)

no odd chord crosses an $F_{4}$ of the walk $w$.

A binomial $B_{w}\in I_{G}$ is called indispensable if every system of
binomial generators of $I_{G}$ contains $B_{w}$ or $-B_{w}$. The next theorem
provides a characterization for the indispensable binomials of $I_{G}$.

######  Theorem 2.2.

([10, Theorem 4.14]) Let $w$ be an even closed walk of $G$. Then $B_{w}$ is an
indispensable binomial if and only if $w$ is a strongly primitive walk, all
the chords of $w$ are odd and there are not two of them that cross
effectively.

It follows from Theorems 2.1, 2.2 that the binomial $B_{w}$ is not
indispensable due to the existence of $F_{4}$’s in the walk $w$. Moreover, a
minimal binomial $B_{w}$ of $I_{G}$ is indispensable if and only if the walk
$w$ does not have any $F_{4}$.

Note that there may exist a subgraph $H$ of the graph $G$ such that
$I_{H}=I_{G}$. This can happen when there are edges in $G$ that are not used
in any walk $w$ such that $B_{w}$ is a minimal binomial of $I_{G}$.

Given an edge $e$ of $G$, we denote by $G\char 92\relax e$ the graph with the
same vertex set as $G$ and whose edge set consists of all edges of $G$ except
$e$. For any set $F\subset E(G)$ of edges of $G$, we use $G\char 92\relax F$
to denote the subgraph of $G$ containing the same vertices as $G$ but with all
the edges of $F$ removed.

Let $S=\\{B_{w_{1}},B_{w_{2}},\ldots,B_{w_{r}}\\}$ be a minimal generating set
of $I_{G}$. Given an edge $e$ of $G$, we define $G_{S}^{e}$ to be the subgraph
of $G$ on the vertex set

$V(G_{S}^{e})=\bigcup_{1\leq i\leq r\ \text{and}\ e\in E(w_{i})}V(w_{i})$

with edges

$E(G_{S}^{e})=\bigcup_{1\leq i\leq r\ \text{and}\ e\in E(w_{i})}E(w_{i}).$

Thus to form the graph $G_{S}^{e}$ one needs first to find all binomials
$B_{w_{i}}\in S$, $1\leq i\leq r$, such that $e$ is an edge of the walk
$w_{i}$. Then we take all vertices and edges of such walks.

We use the symbol $G_{S}^{e}$ to emphasize that the graph depends not only on
the edge $e$ but also on the minimal system of binomial generators $S$, see
Example 2.3. For a toric ideal $I_{G}$ with a unique minimal system of
binomial generators $S$, we will simply write $G^{e}$ instead of $G_{S}^{e}$.

######  Example 2.3.

Recall that the complete graph $K_{n}$ is the graph with $n$ vertices in which
each vertex is connected to every other vertex. Let $G=K_{4}$ be the complete
graph on the vertex set $\\{v_{1},\ldots,v_{4}\\}$. Let
$w_{1}=(\varepsilon_{12},\varepsilon_{23},\varepsilon_{34},\varepsilon_{14})$,
$w_{2}=(\varepsilon_{12},\varepsilon_{24},\varepsilon_{34},\varepsilon_{13})$
and
$w_{3}=(\varepsilon_{23},\varepsilon_{13},\varepsilon_{14},\varepsilon_{24})$,
where $\varepsilon_{ij}=\\{v_{i},v_{j}\\}$ for $1\leq i<j\leq 4$. Then
$S=\\{B_{w_{1}}=\varepsilon_{12}\varepsilon_{34}-\varepsilon_{23}\varepsilon_{14},B_{w_{2}}=\varepsilon_{12}\varepsilon_{34}-\varepsilon_{24}\varepsilon_{13}\\}$
and
$T=\\{B_{w_{1}},B_{w_{3}}=\varepsilon_{23}\varepsilon_{14}-\varepsilon_{13}\varepsilon_{24}\\}$
are minimal generating sets of $I_{G}$. Let $e=\varepsilon_{23}$, then
$G_{S}^{e}$ is the cycle given by the walk $w_{1}$ while $G_{T}^{e}$ is the
whole graph $G$.

######  Theorem 2.4.

Let $G$ be a graph and $e$ be an edge of $G$. Let
$S=\\{B_{w_{1}},B_{w_{2}},\ldots,B_{w_{r}}\\}$ be a minimal generating set of
$I_{G}$, then $I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax e}$.

Proof. We have that $G\char 92\relax e\subset G$ and $G_{S}^{e}\subset G$, so
$I_{G\char 92\relax e}\subset I_{G}$ and $I_{G_{S}^{e}}\subset I_{G}$. Thus
$I_{G_{S}^{e}}+I_{G\char 92\relax e}\subset I_{G}$. Let $B_{w_{i}}$, $1\leq
i\leq r$, be a minimal binomial in $S$. Then there are two cases:

  1. (1)

$e\in E(w_{i})$. Then $B_{w_{i}}$ belongs to the ideal $I_{G_{S}^{e}}$.

  2. (2)

$e\not\in E(w_{i})$. Then $B_{w_{i}}$ belongs to the ideal $I_{G\char 92\relax
e}$.

Consequently $I_{G}\subset I_{G_{S}^{e}}+I_{G\char 92\relax e}$. $\square$

######  Example 2.5.

We return to Example 2.3. We have that $I_{G_{S}^{e}}=<B_{w_{1}}>$ and
$I_{G_{T}^{e}}=I_{G}$. Also $G\char 92\relax e$ is the graph with edges
$\varepsilon_{12},\varepsilon_{34},\varepsilon_{14},\varepsilon_{13},\varepsilon_{24}$,
thus $I_{G\char 92\relax e}=<B_{w_{2}}>$. Then $I_{G}=I_{G_{S}^{e}}+I_{G\char
92\relax e}$ is a splitting of $I_{G}$, while $I_{G}=I_{G_{T}^{e}}+I_{G\char
92\relax e}$ is not a splitting of $I_{G}$ since $I_{G_{T}^{e}}=I_{G}$.

######  Definition 2.6.

A subgraph splitting $I_{G}=I_{G_{1}}+I_{G_{2}}$ of $I_{G}$ is called edge
splitting if there exist an edge $e$ of $G$ and a minimal generating set $S$
of $I_{G}$ such that $G_{1}=G_{S}^{e}$ and $G_{2}=G\char 92\relax e$ or
$G_{1}=G\char 92\relax e$ and $G_{2}=G_{S}^{e}$. The toric ideal $I_{G}$ is
called edge splittable if there exists an edge splitting of $I_{G}$.

######  Remark 2.7.

It is not necessary for all subgraph splittings (if any) of the toric ideal of
a graph to be edge splittings. Consider the complete graph $K_{5}$ on the
vertex set $\\{v_{1},\ldots,v_{5}\\}$. Let
$\varepsilon_{ij}=\\{v_{i},v_{j}\\}$ for $1\leq i<j\leq 5$. Consider the
subgraphs $G_{1}=K_{5}\char 92\relax\\{\varepsilon_{12},\varepsilon_{34}\\}$
and $G_{2}=K_{5}\char 92\relax\\{\varepsilon_{14},\varepsilon_{23}\\}$ of
$K_{5}$. We have that
$S=\\{\varepsilon_{13}\varepsilon_{24}-\varepsilon_{14}\varepsilon_{23},\varepsilon_{14}\varepsilon_{25}-\varepsilon_{15}\varepsilon_{24},\varepsilon_{23}\varepsilon_{45}-\varepsilon_{24}\varepsilon_{35},\varepsilon_{13}\varepsilon_{25}-\varepsilon_{15}\varepsilon_{23},\varepsilon_{13}\varepsilon_{45}-\varepsilon_{14}\varepsilon_{35}\\}$
is a generating set of $I_{G_{1}}$ and
$T=\\{\varepsilon_{12}\varepsilon_{34}-\varepsilon_{13}\varepsilon_{24},\varepsilon_{24}\varepsilon_{35}-\varepsilon_{25}\varepsilon_{34},\varepsilon_{13}\varepsilon_{45}-\varepsilon_{15}\varepsilon_{34},\varepsilon_{12}\varepsilon_{45}-\varepsilon_{15}\varepsilon_{24},\varepsilon_{12}\varepsilon_{35}-\varepsilon_{13}\varepsilon_{25}\\}$
is a generating set of $I_{G_{2}}$. Also, $S\cup T$ is a generating set of
$I_{K_{5}}$ and $I_{G_{i}}\neq I_{K_{5}}$ for all $1\leq i\leq 2$, so
$I_{K_{5}}=I_{G_{1}}+I_{G_{2}}$ is a splitting of $I_{K_{5}}$ which is not an
edge splitting. Note that both $G_{1},G_{2}$ cannot be written in the form
$K_{5}\char 92\relax e$.

Next two Theorems provide a necessary and sufficient condition for a toric
ideal $I_{G}$ to be subgraph splittable in terms of the graph $G$.

######  Theorem 2.8.

The ideal $I_{G}$ is edge splittable if and only if there is a minimal system
of binomial generators $S=\\{B_{w_{1}},\ldots,B_{w_{r}}\\}$ of $I_{G}$ with
$r\geq 2$ and an edge $e\in E(w_{i})$, $1\leq i\leq r$, such that
$I_{G_{S}^{e}}\not=I_{G}$.

Proof. ($\Longrightarrow$) Suppose that the ideal $I_{G}$ is edge splittable,
then there exist a minimal system of binomial generators
$S=\\{B_{w_{1}},\ldots,B_{w_{r}}\\}$ of $I_{G}$ with $r\geq 2$ and an edge $e$
of $G$ such that $I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax e}$ is a splitting.
Thus $I_{G\char 92\relax e}\not=I_{G}$, so there is $B_{w_{i}}\in I_{G}$,
$1\leq i\leq r$, such that $B_{w_{i}}\notin I_{G\char 92\relax e}$ and
therefore $e\in E(w_{i})$.
($\Longleftarrow$) Suppose that there is a minimal system of binomial
generators $S=\\{B_{w_{1}},\ldots,B_{w_{r}}\\}$ of $I_{G}$ with $r\geq 2$ and
an edge $e\in E(w_{i})$, $1\leq i\leq r$, such that $I_{G_{S}^{e}}\not=I_{G}$.
Then from Theorem 2.4 we have that $I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax
e}$. Since $e\in E(w_{i})$, we have that $B_{w_{i}}\not\in I_{G\char 92\relax
e}$ and therefore $I_{G\char 92\relax e}\not=I_{G}.$ From the hypothesis, it
holds that $I_{G_{S}^{e}}\not=I_{G}$. Consequently, $I_{G}$ is edge
splittable. $\square$

Figure 1. The graph $G_{8}$

######  Example 2.9.

Let $P_{n}$ be the graph with $2n+1$ vertices: the $n$ vertices of a regular
$n$-gon, the $n$ midpoints of the edges of the polygon and the center of the
polygon. The graph $P_{n}$ has $3n$ edges: the $n$ radii $R_{i}$ of the
inscribed circle in the polygon corresponding to the midpoints of the edges of
the polygon and the $2n$ segments $l_{i},r_{i}$ joining the vertices of the
polygon to the two adjacent midpoints. Let $e$ be a new edge attached to the
center of the polygon. To each one of the $n$ radii of the inscribed circle in
the polygon and the edge $e$ we attach two edges $e_{i},R^{\prime}_{i}$ to
create $n$ cycles $(e,R_{i},e_{i},R^{\prime}_{i})$ of length 4. Let $G_{n}$ be
the resulting roundabout graph with $3n+2$ vertices and $5n+1$ edges.

In Figure 1 we plot the graph $G_{8}$ with 26 vertices and 41 edges. Since
$G_{n}$ is bipartite, we have, from [8, Theorem 2.3], that $I_{G_{n}}$ has a
unique minimal system of generators consisting of all binomials $B_{w}$, where
$w$ is an even cycle with no chords. The graph $G_{n}$ has $n$ cycles with no
chords of the form $(e,R_{i},e_{i},R^{\prime}_{i})$, $n$ cycles of the form
$(R_{i},l_{i},r_{i},R_{i-1})$, $1$ cycle of the form
$(l_{1},r_{1},l_{2},r_{2},\ldots,l_{n},r_{n})$ and $2\binom{n}{2}$ cycles of
two forms, namely
$(R^{\prime}_{i},e_{i},r_{i},l_{i},r_{i-1},\ldots,e_{j},R^{\prime}_{j})$ and
$(R^{\prime}_{i},e_{i},l_{i+1},r_{i+1},\ldots,e_{j},R^{\prime}_{j})$, where
$i,j\in\\{1,\cdots,n\\}$, $i-1$ equals $n$ when $i=1$ and $i+1$ equals 1 when
$i=n$. Thus $G_{n}$ has exactly $2n+1+2\binom{n}{2}$ cycles without a chord.
Note that $G_{8}$ has exactly $73$ cycles with no chords, see Figure 1. We
plot in Figure 2 the graph ${G_{8}}\char 92\relax e$ and in Figure 3 the graph
$G_{8}^{e}$. Note that the toric ideal of the graph ${G_{8}}\char 92\relax e$
has 93 minimal binomials, while the toric ideal of $G_{8}^{e}$ has 8 minimal
binomials. In general, $I_{{G_{n}}\char 92\relax e}$ has $n+3\binom{n}{2}+1$
minimal binomials of the form $B_{w}$, where $w$ are even cycles with no
chords of the following form: $n$ cycles of the form
$(R_{i},l_{i},r_{i},R_{i-1})$, $1$ cycle of the form
$(l_{1},r_{1},l_{2},r_{2},\ldots,l_{n},r_{n})$, $2\binom{n}{2}$ cycles of two
forms, namely
$(R^{\prime}_{i},e_{i},r_{i},l_{i},r_{i-1},\ldots,e_{j},R^{\prime}_{j})$ and
$(R^{\prime}_{i},e_{i},l_{i+1},r_{i+1},\ldots,e_{j},R^{\prime}_{j})$, and
$\binom{n}{2}$ cycles which correspond to cycles
$(R_{i},e_{i},R^{\prime}_{i},R^{\prime}_{j},e_{j},R_{j})$ in ${G_{n}}\char
92\relax e$ of length 6 that in the graph $G_{n}$ had $e$ as an even chord.
The ideal $I_{G_{n}^{e}}$ has $n$ minimal binomials corresponding to the
cycles $(e,R_{i},e_{i},R^{\prime}_{i})$. It follows from Theorem 2.8 that
$I_{G_{n}}=I_{G_{n}^{e}}+I_{G\char 92\relax e}$ is an edge splitting.

Figure 2. The graph ${G_{8}}\char 92\relax e$ Figure 3. The graph $G_{8}^{e}$

Next we state and prove the main result of this article, namely if the toric
ideal of a graph has a subgraph splitting then it has also an edge splitting.

######  Theorem 2.10.

The toric ideal $I_{G}$ is subgraph splittable if and only if it is edge
splittable.

Proof. ($\Longleftarrow$) If $I_{G}$ is edge splittable, then
$I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax e}$ is a splitting of $I_{G}$, and
therefore it is subgraph splittable.
($\Longrightarrow$) Suppose that $I_{G}$ is subgraph splittable and let
$I_{G}=I_{G_{1}}+I_{G_{2}}$ be a subgraph splitting of $I_{G}$. Notice that
$I_{G_{1}}\subsetneqq I_{G}$ and $I_{G_{2}}\subsetneqq I_{G}$. Let
$\\{f_{1},\ldots,f_{s}\\}$ be a binomial generating set of $I_{G_{1}}$ and
$\\{g_{1},\ldots,g_{t}\\}$ be a binomial generating set of $I_{G_{2}}$. Then
$\\{f_{1},\ldots,f_{s},g_{1},\ldots,g_{t}\\}$ is a generating set of $I_{G}$,
therefore it contains a minimal binomial generating set
$S=\\{B_{w_{1}},\ldots,B_{w_{r}}\\}$ of $I_{G}$, since toric ideals of graphs
are homogeneous. Note that $r\geq 2$, since $I_{G_{1}}$ and $I_{G_{2}}$ are
nonzero ideals. But $S\subset\\{f_{1},\ldots,f_{s},g_{1},\ldots,g_{t}\\}$, so
each $B_{w_{i}}$, $1\leq i\leq r$, belongs to at least one of
$I_{G_{1}},I_{G_{2}}$. If for every $1\leq i\leq r$ it holds that
$B_{w_{i}}\in I_{G_{2}}$, then $I_{G_{2}}=I_{G}$ a contradiction. Thus there
exists $1\leq i\leq r$ such that $B_{w_{i}}\in I_{G_{1}}$ and $B_{w_{i}}\notin
I_{G_{2}}$, so there is $e\in E(w_{i})$ such that $e\notin E(G_{2})$. For
every even closed walk $w_{j}$ such that $e\in E(w_{j})$ we have that
$B_{w_{j}}\in I_{G_{1}}$, thus $I_{G_{S}^{e}}\subset I_{G_{1}}$ and therefore
$I_{G_{S}^{e}}\neq I_{G}$ since $I_{G_{1}}\subsetneqq I_{G}$. By Theorem 2.8
the toric ideal $I_{G}$ is edge splittable. $\square$

######  Example 2.11.

Consider the graph $G$ on the vertex set $\\{v_{1},\ldots,v_{10}\\}$ with
edges $e_{1}=\\{v_{1},v_{2}\\}$, $e_{2}=\\{v_{2},v_{3}\\}$,
$e_{3}=\\{v_{3},v_{4}\\}$, $e_{4}=\\{v_{4},v_{5}\\}$,
$e_{5}=\\{v_{5},v_{6}\\}$, $e_{6}=\\{v_{6},v_{7}\\}$,
$e_{7}=\\{v_{7},v_{8}\\}$, $e_{8}=\\{v_{8},v_{9}\\}$,
$e_{9}=\\{v_{9},v_{10}\\}$, $e_{10}=\\{v_{1},v_{10}\\}$,
$e_{11}=\\{v_{1},v_{5}\\}$, $e_{12}=\\{v_{2},v_{6}\\}$ and
$e_{13}=\\{v_{6},v_{8}\\}$. Then
$S=\\{e_{1}e_{5}-e_{11}e_{12},e_{1}e_{9}e_{13}-e_{8}e_{10}e_{12},e_{5}e_{8}e_{10}-e_{9}e_{11}e_{13},e_{2}e_{4}e_{6}e_{13}-e_{3}e_{5}e_{7}e_{12},e_{2}e_{4}e_{6}e_{8}e_{10}-e_{3}e_{7}e_{9}e_{11}e_{12}\\}$
is a minimal generating set of $I_{G}$. For the edge $f=e_{1}$ of $G$ we have
that $I_{G\char 92\relax
f}=<e_{5}e_{8}e_{10}-e_{9}e_{11}e_{13},e_{2}e_{4}e_{6}e_{13}-e_{3}e_{5}e_{7}e_{12},e_{2}e_{4}e_{6}e_{8}e_{10}-e_{3}e_{7}e_{9}e_{11}e_{12}>$.
Moreover
$E(G_{S}^{f})=\\{e_{1},e_{5},e_{8},e_{9},e_{10},e_{11},e_{12},e_{13}\\}$ and
also
$I_{G_{S}^{f}}=<e_{1}e_{5}-e_{11}e_{12},e_{1}e_{9}e_{13}-e_{8}e_{10}e_{12},e_{5}e_{8}e_{10}-e_{9}e_{11}e_{13}>$.
Thus $I_{G}\neq I_{G_{S}^{f}}$ and therefore $I_{G}=I_{G_{S}^{f}}+I_{G\char
92\relax f}$ is a splitting of $I_{G}$ by Theorem 2.8.

######  Example 2.12.

In [6, Example 3.5] P. Gimenez and H. Srinivasan provide an example of a graph
$G$ obtained by gluing two bow ties $G_{1}$ and $G_{2}$ along an edge. Since
neither $G_{1}$ nor $G_{2}$ is bipartite, $I_{G_{1}}+I_{G_{2}}$ is not a
splitting of $I_{G}$ by [6, Theorem 3.4(1)]. The ideal $I_{G}$ has a unique
minimal system of generators $S$ consisting of five binomials and
$I_{G_{S}^{e}}=I_{G}$, for every edge $e$ of $G$. By Theorem 2.8, the ideal
$I_{G}$ is not edge splittable, and therefore it is not subgraph splittable by
Theorem 2.10. Thus $I_{G}$ does not have a splitting in the form
$I_{H_{1}}+I_{H_{2}}$ for any subgraphs $H_{1},H_{2}$ of $G$. It is worth
mentioning that if a graph $G$ is a gluing of two arbitrary disjoint connected
graphs $G_{1}$ and $G_{2}$, bipartite or not, along an edge, then from [6,
Theorem 3.4(3)] there exists a $3$-uniform hypergraph $H$ such that
$I_{H}=I_{G_{1}}+I_{G_{2}}$.

Theorems 2.8 and 2.10 are easier to apply when $I_{G}$ has a unique minimal
system of binomial generators. In particular, this is true for the toric ideal
of a bipartite graph since it is minimally generated by all binomials of the
form $B_{w}$, where $w$ is an even cycle with no chords, see [8, Theorem 2.3].

A graph $G$ is called a complete bipartite graph if its vertex set can be
partitioned into two subsets $V_{1}$ and $V_{2}$ such that each edge of $G$
connects a vertex of $V_{1}$ to a vertex of $V_{2}$. It is denoted by
$K_{m,n}$, where $m$ and $n$ are the numbers of vertices in $V_{1}$ and
$V_{2}$ respectively. The next corollary shows that toric ideals of complete
bipartite graphs do not admit a subgraph splitting.

######  Corollary 2.13.

The toric ideal of $K_{m,n}$ is not subgraph splittable.

Proof. Let $V_{1}=\\{x_{1},\ldots,x_{m}\\}$, $V_{2}=\\{y_{1},\ldots,y_{n}\\}$
be the bipartition of the complete bipartite graph $K_{m,n}$ and
$E(K_{m,n})=\\{b_{ij}|1\leq i\leq m,1\leq j\leq n\\}$, where
$b_{ij}=\\{x_{i},y_{j}\\}$. Then $I_{K_{m,n}}$ is minimally generated by the
$2\times 2$ minors of the matrix $M=(b_{ij})$, see [13, Proposition 10.6.2].
Thus $I_{K_{m,n}}$ is minimally generated by the set $S$ of all binomials
$b_{ij}b_{kl}-b_{il}b_{kj}$ which are in the form $B_{w}$, where $w$ is a
cycle in $K_{m,n}$ of length $4$. Since $K_{m,n}$ is bipartite, the set $S$ is
the unique minimal system of binomial generators of $I_{K_{m,n}}$.

Notice that if $m=1$ or $n=1$, then $I_{K_{m,n}}=\\{0\\}$. Moreover if $m=2$
and $n=2$, then $I_{K_{m,n}}$ is minimally generated by
$b_{11}b_{22}-b_{12}b_{21}$ and therefore it is not subgraph splittable.
Assume that $m\geq 2$, $n\geq 2$ and $I_{K_{m,n}}\neq I_{K_{2,2}}$. Let
$e=b_{ij}$ be any edge of $K_{m,n}$. We claim that $K_{m,n}^{e}=K_{m,n}$ which
implies the equality $I_{K_{m,n}^{e}}=I_{K_{m,n}}$. By definition
$K_{m,n}^{e}$ is a subgraph of $K_{m,n}$. It suffices to show that all edges
of $K_{m,n}$ belong also to the graph $K_{m,n}^{e}$. Let $\xi=b_{kl}\in
E(K_{m,n})$. There are four cases:

  1. (1)

$k=i$ and $l=j$. Then $\xi=e$ which belongs to $K_{m,n}^{e}$.

  2. (2)

$k=i$ and $l\not=j$. Let $1\leq i^{\prime}\leq m$ with $i^{\prime}\not=i$.
Consider the cycle $w=(e,\xi,b_{i^{\prime}l},b_{i^{\prime}j})$, then $B_{w}\in
S$ and therefore $\xi$ belongs to $K_{m,n}^{e}$.

  3. (3)

$k\not=i$ and $l=j$. Let $1\leq j^{\prime}\leq n$ with $j^{\prime}\not=j$.
Consider the cycle $w=(e,\xi,b_{kj^{\prime}},b_{ij^{\prime}})$, then $B_{w}\in
S$ and therefore $\xi$ belongs to $K_{m,n}^{e}$.

  4. (4)

$k\not=i$ and $l\not=j$. Consider the cycle $w=(e,b_{il},\xi,b_{kj})$, then
$B_{w}\in S$ and therefore $\xi$ belongs to $K_{m,n}^{e}$.

We conclude that in all cases $\xi$ belongs to $K_{m,n}^{e}$, so
$K_{m,n}^{e}=K_{m,n}$. From Theorem 2.8 it follows that $I_{K_{m,n}}$ is not
edge splittable, and therefore $I_{K_{m,n}}$ is not subgraph splittable by
Theorem 2.10. $\square$

The suspension $\widehat{G}$ of a graph $G$ is the graph obtained from $G$ by
adding a new vertex adjacent to all vertices of $G$. Given a cycle $C_{n}$ in
$G$ of length $n\geq 3$, the next theorem determines when the toric ideal
$I_{\widehat{C_{n}}}$ is subgraph splittable.

######  Theorem 2.14.

Let $C_{n}$ be a cycle of length $n\geq 3$ and $\widehat{C_{n}}$ be the
suspension of $C_{n}$.

  1. (1)

Suppose that $n$ is even. Then $I_{\widehat{C_{n}}}$ is subgraph splittable if
and only if $n=4$.

  2. (2)

If $n$ is odd, then $I_{\widehat{C_{n}}}$ is subgraph splittable.

Proof. Let
$C_{n}=(\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\ldots,\\{v_{n-1},v_{n}\\},\\{v_{1},v_{n}\\})$
and $G=\widehat{C_{n}}$ be the suspension of $C_{n}$ obtained by adding a new
vertex $v_{n+1}$ such that $\\{v_{i},v_{n+1}\\}$ is an edge of $G$, for every
$1\leq i\leq n$.
(1) Suppose that $n\geq 4$ is even. From [9, Proposition 5.5] there is a
bipartite graph $H$ such that $I_{G}=I_{H}$, thus $I_{G}$ has a unique minimal
system of generators. We distinguish the following cases.

  1. (a)

$n=4$. Let
$C_{4}=(\varepsilon_{12}=\\{v_{1},v_{2}\\},\varepsilon_{23}=\\{v_{2},v_{3}\\},\varepsilon_{34}=\\{v_{3},v_{4}\\},\varepsilon_{14}=\\{v_{1},v_{4}\\})$
and $\varepsilon_{i5}=\\{v_{i},v_{5}\\}$ for $1\leq i\leq 4$. Then

$S=\\{\varepsilon_{12}\varepsilon_{45}-\varepsilon_{14}\varepsilon_{25},\varepsilon_{12}\varepsilon_{35}-\varepsilon_{23}\varepsilon_{15},\varepsilon_{12}\varepsilon_{34}-\varepsilon_{23}\varepsilon_{14},\varepsilon_{23}\varepsilon_{45}-\varepsilon_{34}\varepsilon_{25},\varepsilon_{15}\varepsilon_{34}-\varepsilon_{14}\varepsilon_{35}\\}$

is a minimal generating set of $I_{G}$. Let $e=\varepsilon_{15}$, then
$E(G^{e})=\\{\varepsilon_{12},\varepsilon_{14},\varepsilon_{15},\varepsilon_{23},\varepsilon_{34},\varepsilon_{35}\\}.$
Notice that
$\varepsilon_{12}\varepsilon_{45}-\varepsilon_{14}\varepsilon_{25}\in I_{G}$
and $\varepsilon_{12}\varepsilon_{45}-\varepsilon_{14}\varepsilon_{25}\notin
I_{G^{e}}$, so $I_{G^{e}}\neq I_{G}$. Also $e$ is an edge of the cycle
$w=(\varepsilon_{12},\varepsilon_{23},\varepsilon_{35},\varepsilon_{15})$.
Thus $I_{G}=I_{G^{e}}+I_{G\char 92\relax e}$ is a splitting of $I_{G}$ by
Theorem 2.8.

  2. (b)

$n>4$. Let $e$ be an edge of $G$ then there are two cases:

    1. (i)

$e$ is an edge of the cycle $C_{n}$, for the sake of simplicity let
$e=\varepsilon_{12}$. We will show that $G=G^{e}$. Since $C_{n}$ is a cycle
with no chords, $B_{C_{n}}$ is a minimal binomial of $I_{G}$ by Theorem 2.2,
and therefore $E(C_{n})\subset E(G^{e})$. Consider now the odd cycles
$w_{1}=(e,\\{v_{2},v_{n+1}\\},\\{v_{n+1},v_{1}\\})$ and
$w_{2}=(\\{v_{i},v_{i+1}\\},\\{v_{i+1},v_{n+1}\\},\\{v_{n+1},v_{i}\\})$, where
$4\leq i\leq n-2$, which share only one vertex, namely $v_{n+1}$. The even
closed walk $w=(w_{1},w_{2})$ has no chords and no bridges, and therefore
$B_{w}$ is a minimal binomial of $I_{G}$ by Theorem 2.2. Thus
$\\{v_{i},v_{n+1}\\}\in E(G^{e})$ for $i=1,2,4,5,\ldots,n-1$. Consider now the
cycle

$\gamma=(\\{v_{n+1},v_{1}\\},e,\\{v_{2},v_{3}\\},\\{v_{3},v_{n+1}\\})$

and notice that $\gamma$ has exactly one odd chord, namely
$\\{v_{2},v_{n+1}\\}$, so from Theorem 2.2 $B_{\gamma}$ is a minimal binomial
of $I_{G}$. Thus $\\{v_{3},v_{n+1}\\}\in E(G^{e})$. Consider the cycle
$\delta=(\\{v_{n+1},v_{2}\\},e,\\{v_{1},v_{n}\\},\\{v_{n},v_{n+1}\\})$ and
notice that $\delta$ has exactly one odd chord, namely $\\{v_{1},v_{n+1}\\}$.
By Theorem 2.2 $B_{\delta}$ is a minimal binomial of $I_{G}$. Thus
$\\{v_{n},v_{n+1}\\}\in E(G^{e})$ and therefore $E(G)=E(G^{e})$. Consequently
$G=G^{e}$, so from Theorems 2.8, 2.10 the ideal $I_{G}$ is not subgraph
splittable.

    2. (ii)

$e=\\{v_{i},v_{n+1}\\}$ with $1\leq i\leq n$. For the sake of simplicity we
let $i=1$, namely $e=\\{v_{1},v_{n+1}\\}$. Consider the odd cycles
$w_{1}=(e,\\{v_{2},v_{n+1}\\},\\{v_{1},v_{2}\\})$ and
$w_{2}=(\\{v_{i},v_{i+1}\\},\\{v_{i+1},v_{n+1}\\},\\{v_{n+1},v_{i}\\})$, where
$4\leq i\leq n-2$, which share only one vertex, namely $v_{n+1}$. The even
closed walk $w=(w_{1},w_{2})$ has no chords and no bridges, so $B_{w}$ is a
minimal binomial of $I_{G}$ by Theorem 2.2. Thus $\\{v_{i},v_{n+1}\\}\in
E(G^{e})$ for $i=2,4,5,\ldots,n-1$. Moreover $\\{v_{i},v_{i+1}\\}\in E(G^{e})$
for $i=1,4,5,\ldots,n-2$. Consider now the cycle
$\gamma=(e,\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\\{v_{3},v_{n+1}\\})$ and
notice that it has exactly one odd chord, namely $\\{v_{2},v_{n+1}\\}$. By
Theorem 2.2 $B_{\gamma}$ is a minimal binomial of $I_{G}$. Thus
$\\{v_{2},v_{3}\\}\in E(G^{e})$ and also $\\{v_{3},v_{n+1}\\}\in E(G^{e})$.
Consider the cycle
$\delta=(\\{v_{2},v_{n+1}\\},e,\\{v_{1},v_{n}\\},\\{v_{n},v_{n+1}\\})$ and
notice that $\delta$ has exactly one odd chord, namely $\\{v_{1},v_{2}\\}$. By
Theorem 2.2 $B_{\delta}$ is a minimal binomial of $I_{G}$. Thus
$\\{v_{1},v_{n}\\}\in E(G^{e})$ and also $\\{v_{n},v_{n+1}\\}\in E(G^{e})$.
Furthermore

$\mu=(\\{v_{n-1},v_{n}\\},\\{v_{n},v_{1}\\},e,\\{v_{n-1},v_{n+1}\\})$

is an even cycle with exactly one odd chord, namely $\\{v_{n},v_{n+1}\\}$. By
Theorem 2.2 $B_{\mu}$ is a minimal binomial of $I_{G}$, and therefore
$\\{v_{n-1},v_{n}\\}$ is an edge of $G^{e}$. Consider the odd cycles
$\zeta_{1}=(e,\\{v_{1},v_{n}\\},\\{v_{n},v_{n+1}\\})$,
$\zeta_{2}=(\\{v_{3},v_{4}\\},\\{v_{4},v_{n+1}\\},\\{v_{3},v_{n+1}\\})$ and
let $\zeta=(\zeta_{1},\zeta_{2})$. Then $B_{\zeta}$ is a minimal binomial of
$I_{G}$ by Theorem 2.2, since $\zeta$ does not have any chords or bridges, and
therefore $\\{v_{3},v_{4}\\}\in E(G^{e})$. Thus $E(G)=E(G^{e})$, so $G=G^{e}$
and therefore $I_{G}$ is not subgraph splittable by Theorems 2.8, 2.10.

(2) Suppose that $n$ is odd. Then any odd cycle of $G$ either coincides with
$C_{n}$ or has at least three vertices, namely $v_{n+1}$ and two vertices of
$C_{n}$. Thus $G$ has no two odd vertex disjoint cycles. For $n=3$ we have
that $\widehat{C_{3}}$ is the complete graph on the vertex set
$\\{v_{1},\ldots,v_{4}\\}$, so $I_{\widehat{C_{3}}}$ is splittable by Example
2.5. Suppose that $n\geq 5$. Consider a minimal binomial $B_{w}\in I_{G}$. For
the walk $w$ there are two cases:

  1. (1)

$w$ is a cycle of length $4$ with exactly one odd chord. Then $B_{w}$ is
indispensable of $I_{G}$ by Theorem 2.2.

  2. (2)

$w$ has no chords or bridges and it is of the form $w=(w_{1},w_{2})$ where
$w_{1}$, $w_{2}$ are odd cycles of length 3 intersecting in exactly one
vertex, namely $v_{n+1}$. By Theorem 2.2 the binomial $B_{w}$ is indispensable
of $I_{G}$.

Thus $I_{G}$ has a unique minimal system of generators.

Let $e=\\{v_{1},v_{2}\\}$, then there is no cycle of length 4 in $G$
containing the edges $e$ and $\varepsilon_{34}=\\{v_{3},v_{4}\\}$. Consider
the odd cycles $\gamma_{1}=(e,\\{v_{2},v_{n+1}\\},\\{v_{1},v_{n+1}\\})$ and
$\gamma_{2}=(\varepsilon_{34},\\{v_{4},v_{n+1}\\},\\{v_{3},v_{n+1}\\})$
intersecting in $v_{n+1}$. Let $\gamma=(\gamma_{1},\gamma_{2})$, then
$B_{\gamma}$ is not a minimal binomial of $I_{G}$ since there is a bridge
$\\{v_{2},v_{3}\\}$. Thus the edge $\varepsilon_{34}$ does not belong to
$E(G^{e})$. Consider the even cycle
$\zeta=(\\{v_{2},v_{3}\\},\\{v_{3},v_{4}\\},\\{v_{4},v_{n+1}\\},\\{v_{2},v_{n+1}\\})$,
then $B_{\zeta}$ is a minimal binomial of $I_{G}$ and also $B_{\zeta}\notin
I_{G^{e}}$. Thus $I_{G}\neq I_{G^{e}}$ and therefore $I_{G}$ is splittable by
Theorem 2.8. $\square$

##  3\. The complete graph and minimal splittings

In this section, we study the special case of toric ideals of complete graphs.
In contrast to toric ideals of (complete) bipartite graphs which always have a
unique minimal set of binomial generators, toric ideals of complete graphs
have a huge number of different minimal systems of binomial generators.

Let $n\geq 4$ be an integer and $K_{n}$ be the complete graph on the vertex
set $\\{v_{1},\ldots,v_{n}\\}$ with edges $\\{\varepsilon_{ij}|1\leq i<j\leq
n\\}$, where $\varepsilon_{ij}=\\{v_{i},v_{j}\\}$. By [12, Theorem 3.3] the
set

$T=\\{\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{il}\varepsilon_{jk},\varepsilon_{ik}\varepsilon_{jl}-\varepsilon_{il}\varepsilon_{jk}|1\leq
i<j<k<l\leq n\\}$

is a minimal generating set of $I_{K_{n}}$. Let $\\{{\bf e}_{1},\ldots,{\bf
e}_{n}\\}$ be the canonical basis of $\mathbb{R}^{n}$. Since $T$ is a minimal
generating set of $I_{K_{n}}$, the only $A_{K_{n}}$-fibers contributing to
minimal generators are those consisting of all monomials with
$A_{K_{n}}$-degree ${\bf e}_{i}+{\bf e}_{j}+{\bf e}_{k}+{\bf e}_{l}$, where
$1\leq i<j<k<l\leq n$. There are $\binom{n}{4}$ such fibers and each one
consists of three monomials, namely
$\varepsilon_{ij}\varepsilon_{kl},\varepsilon_{il}\varepsilon_{jk}$ and
$\varepsilon_{ik}\varepsilon_{jl}$, which have no common factor other than
$1$. Therefore to generate the ideal $I_{K_{n}}$ we need to take any two of
the three binomials
$\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{il}\varepsilon_{jk},\varepsilon_{ik}\varepsilon_{jl}-\varepsilon_{il}\varepsilon_{jk},\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{ik}\varepsilon_{jl}$,
for every $1\leq i<j<k<l\leq n$, see [2, 4] for more details. The monomials
$\varepsilon_{ij}\varepsilon_{kl},\varepsilon_{il}\varepsilon_{jk}$ and
$\varepsilon_{ik}\varepsilon_{jl}$, where $1\leq i<j\leq n,$ are indispensable
monomials, namely each one is a monomial term of at least one binomial in
every minimal system of binomial generators of $I_{K_{n}}$. Thus every minimal
system of binomial generators of $I_{K_{n}}$ consists of $2\binom{n}{4}$
binomials. By [2, Theorem 2.9] the ideal $I_{K_{n}}$ has $3^{\binom{n}{4}}$
different minimal systems of binomial generators, which is a huge number even
for a small $n$.

######  Theorem 3.1.

The toric ideal of $K_{n}$ is subgraph splittable if and only if $n\geq 4$.

Proof. For $n\in\\{1,2,3\\}$ we have that $I_{K_{n}}=\\{0\\}$, so $I_{K_{n}}$
is not splittable. Suppose that $n\geq 4$. From the analysis above we deduce
that

$S=\\{\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{ik}\varepsilon_{jl},\varepsilon_{il}\varepsilon_{jk}-\varepsilon_{ik}\varepsilon_{jl}|1\leq
i<j<k<l\leq n\\}$

is a minimal generating set for $I_{K_{n}}$. The set $S$ has a nice geometric
interpretation, see [3].

Let $G=K_{n}$ and $e=\varepsilon_{12}$. First we show that the graph
$G_{S}^{e}$ contains all edges of $G$, except perhaps the edges
$\varepsilon_{1n}$ and $\varepsilon_{23}$. Let $\varepsilon_{ij}$ be an edge
of $G$ where $\\{i,j\\}\cap\\{1,2\\}=\emptyset$ and $3\leq i<j\leq n$. Since
$\\{v_{1},v_{2},v_{i},v_{j}\\}$ is a set of vertices of $K_{n}$, the binomials
$\varepsilon_{12}\varepsilon_{ij}-\varepsilon_{1i}\varepsilon_{2j}$ and
$\varepsilon_{i2}\varepsilon_{1j}-\varepsilon_{1i}\varepsilon_{2j}$ belong to
$S$, thus $\varepsilon_{ij}$ is an edge of $G_{S}^{e}$. From the above
binomials we also deduce that $\varepsilon_{1i}$, for $3\leq i\leq n-1$, and
$\varepsilon_{2j}$, for $4\leq j\leq n$, are edges of $G_{S}^{e}$. With the
possible exception of the edges $\varepsilon_{1n}$ and $\varepsilon_{23}$, the
graph $G_{S}^{e}$ contains all edges of $G$. Suppose that $\varepsilon_{1n}$
is an edge of $G_{S}^{e}$, so there exists a binomial $B\in S$ in four
variables which contains the variables $\varepsilon_{12}$ and
$\varepsilon_{1n}$. Then
$B=\varepsilon_{12}\varepsilon_{in}-\varepsilon_{1n}\varepsilon_{2i}$ where
$3\leq i\leq n-1$. But $\\{v_{1},v_{2},v_{i},v_{n}\\}$ is a set of vertices of
$K_{n}$ which contributes the binomials
$\varepsilon_{12}\varepsilon_{in}-\varepsilon_{1i}\varepsilon_{2n}$ and
$\varepsilon_{1n}\varepsilon_{2i}-\varepsilon_{1i}\varepsilon_{2n}$ in $S$.
Thus $B$ does not belong to $S$, a contradiction. Consequently
$\varepsilon_{1n}$ is not an edge of $G_{S}^{e}$. Similar arguments show that
$\varepsilon_{23}$ is not an edge of $G_{S}^{e}$. Since
$\varepsilon_{12}\varepsilon_{3n}-\varepsilon_{1n}\varepsilon_{23}\in I_{G}$
and $\varepsilon_{12}\varepsilon_{3n}-\varepsilon_{1n}\varepsilon_{23}\not\in
I_{G_{S}^{e}}$, we get $I_{G_{S}^{e}}\not=I_{G}$ and therefore
$I_{G}=I_{G_{S}^{e}}+I_{G\char 92\relax e}$ is a splitting of $I_{G}$ by
Theorem 2.8. $\square$

######  Definition 3.2.

Let $I_{G}=I_{G_{1}}+I_{G_{2}}$ be a subgraph splitting of $I_{G}$,
$S=\\{f_{1},\dots,f_{r}\\}$ be a minimal system of binomial generators of
$I_{G_{1}}$ and $T=\\{g_{1},\dots,g_{t}\\}$ be a minimal system of binomial
generators of $I_{G_{2}}$. We say that the splitting
$I_{G}=I_{G_{1}}+I_{G_{2}}$ is a minimal splitting of $I_{G}$ if
$\\{f_{1},\dots,f_{r},g_{1},\dots,g_{t}\\}$ is a minimal system of generators
of $I_{G}$.

######  Remark 3.3.

(1) The property of being minimal splitting does not depend on the minimal
systems of generators chosen in the definition. Suppose that
$\\{f^{\prime}_{1},\dots,f^{\prime}_{r}\\}$ is a minimal system of binomial
generators of $I_{G_{1}}$ and $\\{g^{\prime}_{1},\dots,g^{\prime}_{t}\\}$ is a
minimal system of binomial generators of $I_{G_{2}}$. But
$I_{G}=I_{G_{1}}+I_{G_{2}}$, so
$\\{f^{\prime}_{1},\dots,f^{\prime}_{r},g^{\prime}_{1},\dots,g^{\prime}_{t}\\}$
is a generating set of $I_{G}$ consisting of $r+t$ elements and therefore it
is a minimal system of generators.
(2) Let $I_{G}=I_{G_{1}}+I_{G_{2}}$ be a minimal splitting of $I_{G}$. For any
$f_{i}\in S$, $1\leq i\leq r$, we have that neither $f_{i}$ nor $-f_{i}$
belongs to $T$. For any $g_{j}\in T$, $1\leq j\leq t$, we have that neither
$g_{j}$ nor $-g_{j}$ belongs to $S$.
(3) All the splittings which appeared in [5, 6] are minimal splittings.
(4) The splitting of $I_{G_{n}}$ in Example 2.9 is not minimal, since the
ideal $I_{{G_{n}}\char 92\relax e}$ has a minimal system of generators with
$n+1+3\binom{n}{2}$ binomials, while the ideal $I_{G_{n}^{e}}$ has a minimal
system of generators with $n$ binomials and the ideal $I_{G_{n}}$ is generated
minimally with $2n+1+2\binom{n}{2}$ binomials.

######  Example 3.4.

Let $K_{4}$ be the complete graph on the vertex set
$\\{v_{1},\ldots,v_{4}\\}$. Let $G_{1}=K_{4}\char
92\relax\\{\varepsilon_{12},\varepsilon_{34}\\}$ and $G_{2}=K_{4}\char
92\relax\\{\varepsilon_{14},\varepsilon_{23}\\}$ be subgraphs of $K_{4}$, then
$I_{K_{4}}=I_{G_{1}}+I_{G_{2}}$ is a minimal splitting of $I_{K_{4}}$, since
$I_{G_{1}}=<\varepsilon_{13}\varepsilon_{24}-\varepsilon_{14}\varepsilon_{23}>$,
$I_{G_{2}}=<\varepsilon_{13}\varepsilon_{24}-\varepsilon_{12}\varepsilon_{34}>$
and
$I_{K_{4}}=<\varepsilon_{13}\varepsilon_{24}-\varepsilon_{14}\varepsilon_{23},\varepsilon_{13}\varepsilon_{24}-\varepsilon_{12}\varepsilon_{34}>$.

We will show that the toric ideal of $K_{n}$ has no minimal splitting for
$n\geq 6$.

######  Proposition 3.5.

Let $n\geq 4$ be an integer and $w=(a,b,c,d)$ be an even cycle of $K_{n}$.
Then

$I_{K_{n}}=I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char
92\relax\\{b,d\\}}$

is a splitting of $I_{K_{n}}.$

Proof. Since $K_{n}$ is the complete graph, the cycle $w$ has two chords,
namely $e$ and $f$. Then $ac-ef\in I_{K_{n}}$ does not belong to
$I_{{K_{n}}\char 92\relax\\{a,c\\}}$, thus $I_{{K_{n}}\char
92\relax\\{a,c\\}}\not=I_{K_{n}}$. Also $I_{{K_{n}}\char
92\relax\\{b,d\\}}\not=I_{K_{n}}$ since $ef-bd\in I_{K_{n}}$ does not belong
to $I_{{K_{n}}\char 92\relax\\{b,d\\}}$.

It remains to show that $I_{K_{n}}\subset I_{{K_{n}}\char
92\relax\\{a,c\\}}+I_{{K_{n}}\char 92\relax\\{b,d\\}}$. Let $B_{\gamma}$ be a
binomial belonging to the set $S$ defined in the proof of Theorem 3.1. Clearly
if $B_{\gamma}$ belongs to $I_{{K_{n}}\char 92\relax\\{a,c\\}}$ or
$I_{{K_{n}}\char 92\relax\\{b,d\\}}$, then $B_{\gamma}$ belongs to
$I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char 92\relax\\{b,d\\}}$.
Suppose that $B_{\gamma}$ does not belong to $I_{{K_{n}}\char
92\relax\\{a,c\\}}$ or $I_{{K_{n}}\char 92\relax\\{b,d\\}}$. Then $\gamma$
contains at least one edge from the set $\\{a,c\\}$, say $a$, and at least one
edge from the set $\\{b,d\\}$, say $b$. Let
$\gamma=(a,b,c^{\prime},d^{\prime})$ and $e^{\prime},f^{\prime}$ be the chords
of the walk $\gamma$. Notice that $ac^{\prime}-e^{\prime}f^{\prime}$ belongs
to $I_{{K_{n}}\char 92\relax\\{b,d\\}}$ and $bd^{\prime}-e^{\prime}f^{\prime}$
belongs to $I_{{K_{n}}\char 92\relax\\{a,c\\}}$. Thus

$B_{\gamma}=ac^{\prime}-bd^{\prime}=(ac^{\prime}-e^{\prime}f^{\prime})-(bd^{\prime}-e^{\prime}f^{\prime})\in
I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char 92\relax\\{b,d\\}}.$

So $I_{K_{n}}=I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char
92\relax\\{b,d\\}}$ is a splitting. $\square$

######  Remark 3.6.

Let $I_{A}=I_{A_{1}}+I_{A_{2}}$ be a splitting of $I_{A}$. If there exists a
set $A^{\prime}_{1}$ such that $I_{A_{1}}\subset I_{A^{\prime}_{1}}\subsetneqq
I_{A}$ then $I_{A}=I_{A^{\prime}_{1}}+I_{A_{2}}$ is also a splitting. By
Proposition 3.5, $I_{K_{n}}=I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char
92\relax\\{b,d\\}}$ is a splitting of $I_{K_{n}}$, and therefore
$I_{K_{n}}=I_{{K_{n}}\char 92\relax a}+I_{{K_{n}}\char 92\relax b}$,
$I_{K_{n}}=I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char 92\relax b}$ and
$I_{K_{n}}=I_{{K_{n}}\char 92\relax a}+I_{{K_{n}}\char 92\relax\\{b,d\\}}$ are
also splittings of $I_{K_{n}}$.

######  Proposition 3.7.

Let $n\geq 4$ be an integer and $I_{K_{n}}=I_{G_{1}}+I_{G_{2}}$ be a subgraph
splitting of $I_{K_{n}}$. If $e$ is an edge of $K_{n}$ which does not belong
to $G_{1}$ and $f$ is an edge of $K_{n}$ which does not belong to $G_{2}$,
then the edges $e,f$ are adjacent in $K_{n}$. Moreover, if $h$ is another edge
of $K_{n}$ which does not belong to $G_{2}$, then the edges $f,h$ are not
adjacent in $K_{n}$.

Proof. Suppose that the edges $e$, $f$ are not adjacent. Let
$e=\\{v_{i},v_{j}\\}$, $f=\\{v_{k},v_{l}\\}$ and $e\cap f=\emptyset$. Let
$\\{g_{1},\ldots,g_{r}\\}$ be a system of binomial generators of $I_{G_{1}}$
and $\\{h_{1},\ldots,h_{s}\\}$ be a system of binomial generators of
$I_{G_{2}}$, then $\\{g_{1},\ldots,g_{r},h_{1},\ldots,h_{s}\\}$ is a
generating set of $I_{G}$. Therefore we can find a minimal system of
generators $V$ of $I_{K_{n}}$ formed by binomials belonging to either
$I_{G_{1}}$ or $I_{G_{2}}$. From the introduction of section 3 the monomial
$ef=\varepsilon_{ij}\varepsilon_{kl}$ is indispensable of $I_{K_{n}}$, so it
is a monomial term in a binomial $B_{w}$ of $I_{G_{1}}$ or $I_{G_{2}}$. Since
$e$ is not an edge of $G_{1}$, we have that $B_{w}\notin I_{G_{1}}$. But $f$
is not an edge of $G_{2}$, so $B_{w}\notin I_{G_{2}}$. Thus $B_{w}$ does not
belong to $I_{G_{1}}$ or $I_{G_{2}}$, a contradiction. Consequently, the edges
$e$, $f$ are adjacent.
Let $e=\varepsilon_{ij}$ and $f=\varepsilon_{jk}$. Suppose that $h$ is another
edge of $K_{n}$ which does not belong to $G_{2}$. Since $e$ does not belong to
$G_{1}$, we have, from the first part of the Proposition, that the edges $e$,
$h$ are adjacent. We claim that $f$ and $h$ are not adjacent. Suppose that
$f$, $h$ are adjacent. Since $h$ is adjacent to both $e$ and $f$, there are
two cases for the edge $h$, namely either $h=\varepsilon_{ik}$ or
$h=\varepsilon_{jl}$ for an index $l$ different than $i,j,k$.

  1. (1)

$h=\varepsilon_{ik}$. Let $l$ be an index different than $i,j,k$. In a
previous step we found that there is a minimal system of generators $V$ formed
by binomials belonging to either $I_{G_{1}}$ or $I_{G_{2}}$. Moreover, $V$
must contain exactly two of the following three binomials
$\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{il}\varepsilon_{jk}=e\varepsilon_{kl}-\varepsilon_{il}f,\varepsilon_{ik}\varepsilon_{jl}-\varepsilon_{il}\varepsilon_{jk}=h\varepsilon_{jl}-\varepsilon_{il}f,\varepsilon_{ij}\varepsilon_{kl}-\varepsilon_{ik}\varepsilon_{jl}=e\varepsilon_{kl}-h\varepsilon_{jl}$.
But none of them belongs to $I_{G_{2}}$, since $f,h\not\in E(G_{2})$, while
$e\varepsilon_{kl}-\varepsilon_{il}f$ and
$e\varepsilon_{kl}-h\varepsilon_{jl}$ do not belong to $I_{G_{1}}$, since
$e\not\in E(G_{1})$. A contradiction.

  2. (2)

$h=\varepsilon_{jl}$. We argue similarly as above. The set $V$ must contain
two of the following three binomials
$e\varepsilon_{kl}-\varepsilon_{il}f,\varepsilon_{ik}h-\varepsilon_{il}f,e\varepsilon_{kl}-\varepsilon_{ik}h$.
But none of them belongs to $I_{G_{2}}$, since $f,h\not\in E(G_{2})$, while
$e\varepsilon_{kl}-\varepsilon_{il}f$ and
$e\varepsilon_{kl}-\varepsilon_{ik}h$ do not belong to $I_{G_{1}}$, since
$e\not\in E(G_{1})$. A contradiction.

Consequently, the edges $f,h$ are not adjacent. $\square$

######  Remark 3.8.

From Proposition 3.7 we deduce that any of the graphs $G_{1},G_{2}$ contains
all edges of $K_{n}$ except at most two. Suppose not, and let
$e=\varepsilon_{ij}\not\in E(G_{1})$, $\\{f_{1},f_{2},f_{3}\\}\subset
E(K_{n})$ such that $f_{l}\not\in E(G_{2})$, for every $1\leq l\leq 3$. By
Proposition 3.7, any of the edges $f_{1},f_{2},f_{3}$ is adjacent to
$e=\varepsilon_{ij}$, so $v_{i}$ is a vertex of the edges $f_{1},f_{2},f_{3}$
or $v_{j}$ is a vertex of the edges $f_{1},f_{2},f_{3}$. Thus either $v_{i}$
or $v_{j}$ is a vertex of at least two of the edges $f_{1},f_{2},f_{3}$, and
therefore two of the edges $f_{1},f_{2},f_{3}$ are adjacent, a contradiction
to the second part of Proposition 3.7.

######  Proposition 3.9.

Let $n\geq 4$ be an integer and $I_{K_{n}}=I_{G_{1}}+I_{G_{2}}$ be a subgraph
splitting of $I_{K_{n}}$. Then there exists a cycle $w=(a,b,c,d)$ in $K_{n}$
such that

  1. (1)

$G_{1}={K_{n}}\char 92\relax a$ and $G_{2}={K_{n}}\char 92\relax b$ or

  2. (2)

$G_{1}={K_{n}}\char 92\relax\\{a,c\\}$ and $G_{2}={K_{n}}\char 92\relax b$ or

  3. (3)

$G_{1}={K_{n}}\char 92\relax a$ and $G_{2}={K_{n}}\char 92\relax\\{b,d\\}$ or

  4. (4)

$G_{1}={K_{n}}\char 92\relax\\{a,c\\}$ and $G_{2}={K_{n}}\char
92\relax\\{b,d\\}$.

Proof. Since $I_{G_{1}}\subsetneqq I_{K_{n}}$, there exists an edge $a$ of
$K_{n}$ such that $a$ is not an edge of $G_{1}$. Thus $I_{G_{1}}\subset
I_{{K_{n}}\char 92\relax a}$. Since $I_{G_{2}}\subsetneqq I_{K_{n}}$, there
exists an edge $b$ of $K_{n}$ such that $b$ is not an edge of $G_{2}$. Thus
$I_{G_{2}}\subset I_{{K_{n}}\char 92\relax b}$. By Proposition 3.7, the edges
$a,b$ are adjacent. We distinguish the following cases:

  1. (1)

$G_{1}={K_{n}}\char 92\relax a$ and $G_{2}={K_{n}}\char 92\relax b$. Since
$a,b$ are adjacent edges in the complete graph $K_{n}$ with $n\geq 4$
vertices, there exists a cycle $w$ of length 4 in $K_{n}$ with two consecutive
edges $a,b$.

  2. (2)

$G_{1}\subsetneqq{K_{n}}\char 92\relax a$ and $G_{2}={K_{n}}\char 92\relax b$.
In this case, there exists an edge $c$ of ${K_{n}}\char 92\relax a$ such that
$c$ is not an edge of $G_{1}$. By Proposition 3.7, the edges $a,c$ do not
share a common vertex and they are adjacent to $b$. Furthermore, $G_{1}$
contains all edges of $K_{n}$ except at most two. Thus $G_{1}={K_{n}}\char
92\relax\\{a,c\\}$ and there exists a cycle $w$ of length 4 in $K_{n}$ with
three consecutive edges $a,b,c$.

  3. (3)

$G_{1}={K_{n}}\char 92\relax a$ and $G_{2}\subsetneqq{K_{n}}\char 92\relax b$.
In this case, there exists an edge $d$ of ${K_{n}}\char 92\relax b$ such that
$d$ is not an edge of $G_{2}$. By Proposition 3.7, the edges $b,d$ do not
share a common vertex and they are adjacent to $a$. Moreover, $G_{2}$ contains
all edges of $K_{n}$ except at most two. Thus $G_{2}={K_{n}}\char
92\relax\\{b,d\\}$ and there exists a cycle $w$ of length 4 in $K_{n}$ with
three consecutive edges $d,a,b$.

  4. (4)

$G_{1}\subsetneqq{K_{n}}\char 92\relax a$ and $G_{2}\subsetneqq{K_{n}}\char
92\relax b$. Then there exists an edge $c$ of ${K_{n}}\char 92\relax a$ and an
edge $d$ of ${K_{n}}\char 92\relax b$ such that $c$ is not an edge of $G_{1}$
and $d$ is not an edge of $G_{2}$. By Proposition 3.7, the edges $a,c$ do not
share a common vertex and they are adjacent to both $b,d$. Additionally
$G_{1}$ contains all edges of $K_{n}$ except at most two. By the same
proposition, the edges $b,d$ do not share a common vertex and they are
adjacent to both $a,c$. Furthermore $G_{2}$ contains all edges of $K_{n}$
except at most two. Thus $w=(a,b,c,d)$ is a cycle in $K_{n}$,
$G_{1}={K_{n}}\char 92\relax\\{a,c\\}$ and $G_{2}={K_{n}}\char
92\relax\\{b,d\\}$. $\square$

######  Theorem 3.10.

Let $n\geq 4$ be an integer. Then $I_{K_{n}}$ has a minimal splitting if and
only if $4\leq n\leq 5$.

Proof. Suppose first that $n=4$. Then
$I_{K_{4}}=I_{K_{4}\setminus\\{\varepsilon_{12},\varepsilon_{34}\\}}+I_{K_{4}\setminus\\{\varepsilon_{14},\varepsilon_{23}\\}}$
is a minimal splitting of $I_{K_{4}}$ by Example 3.4. Suppose now that $n=5$
and let $\\{v_{1},\ldots,v_{5}\\}$ be the vertex set of $K_{5}$. Let
$G_{1}=K_{5}\char 92\relax\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\}\\}$ and
$G_{2}=K_{5}\char 92\relax\\{\\{v_{1},v_{4}\\},\\{v_{2},v_{3}\\}\\}$ be
subgraphs of $K_{5}$. Then
$S=\\{\varepsilon_{13}\varepsilon_{24}-\varepsilon_{14}\varepsilon_{23},\varepsilon_{14}\varepsilon_{25}-\varepsilon_{15}\varepsilon_{24},\varepsilon_{23}\varepsilon_{45}-\varepsilon_{24}\varepsilon_{35},\varepsilon_{13}\varepsilon_{25}-\varepsilon_{15}\varepsilon_{23},\varepsilon_{13}\varepsilon_{45}-\varepsilon_{14}\varepsilon_{35}\\}$
is a minimal generating set of $I_{G_{1}}$ and
$T=\\{\varepsilon_{12}\varepsilon_{34}-\varepsilon_{13}\varepsilon_{24},\varepsilon_{24}\varepsilon_{35}-\varepsilon_{25}\varepsilon_{34},\varepsilon_{13}\varepsilon_{45}-\varepsilon_{15}\varepsilon_{34},\varepsilon_{12}\varepsilon_{45}-\varepsilon_{15}\varepsilon_{24},\varepsilon_{12}\varepsilon_{35}-\varepsilon_{13}\varepsilon_{25}\\}$
is a minimal generating set of $I_{G_{2}}$. Also for any binomial $B\in S$ we
have that neither $B$ nor $-B$ belongs to $T$, while for any binomial
$B^{\prime}\in T$ we have that neither $B^{\prime}$ nor $-B^{\prime}$ belongs
to $S$. Moreover $S\cup T$ is a minimal generating set of $I_{K_{5}}$, and
therefore $I_{K_{5}}=I_{G_{1}}+I_{G_{2}}$ is a minimal splitting of
$I_{K_{5}}$.

Finally assume that $n\geq 6$ and let $I_{K_{n}}=I_{G_{1}}+I_{G_{2}}$ be a
minimal splitting of $I_{K_{n}}$. Then there exists a cycle $w=(a,b,c,d)$ of
$K_{n}$ such that $G_{1}$ and $G_{2}$ are of one of the four types of
Proposition 3.9. Without loss of generality we can assume that
$a=\\{v_{1},v_{2}\\}$, $b=\\{v_{2},v_{3}\\}$, $c=\\{v_{3},v_{4}\\}$ and
$d=\\{v_{1},v_{4}\\}$. Since $n\geq 6$, the graph $K_{n}$ has at least two
more vertices, say $v_{5}$ and $v_{6}$. Notice that the complete subgraph of
$K_{n}$ on the vertex set $\\{v_{1},v_{3},v_{5},v_{6}\\}$ is also a subgraph
of both $G_{1}$ and $G_{2}$. Let $S$ be a minimal system of binomial
generators of $I_{G_{1}}$ and $T$ be a minimal system of binomial generators
of $I_{G_{2}}$. Both $S$ and $T$ must contain exactly two of the binomials
$\varepsilon_{13}\varepsilon_{56}-\varepsilon_{15}\varepsilon_{36},\varepsilon_{13}\varepsilon_{56}-\varepsilon_{16}\varepsilon_{35},\varepsilon_{15}\varepsilon_{36}-\varepsilon_{16}\varepsilon_{35}$.
Thus $S$ and $T$ have at least one minimal generator in common which
contradicts the fact that $I_{K_{n}}=I_{G_{1}}+I_{G_{2}}$ is a minimal
splitting of $I_{K_{n}}$. Consequently, for $n\geq 6$ the ideal $I_{K_{n}}$
has no minimal splitting. $\square$

##  4\. Reduced splittings

In this section, we introduce reduced splittings of toric ideals of graphs and
show that every minimal splitting of the toric ideal of a graph is also a
reduced splitting.

######  Definition 4.1.

We say that the subgraph splitting $I_{G}=I_{G_{1}}+I_{G_{2}}$ of $I_{G}$ is
reduced if for any subgraphs $H_{1}$ of $G_{1}$ and $H_{2}$ of $G_{2}$ with
$I_{G}=I_{H_{1}}+I_{H_{2}}$ it holds that $I_{H_{1}}=I_{G_{1}}$ and
$I_{H_{2}}=I_{G_{2}}.$

A basic step towards determining all subgraph splittings of the toric ideal of
a graph is to find its reduced splittings. All other subgraph splittings are
found from a reduced splitting $I_{G}=I_{G_{1}}+I_{G_{2}}$ by adding edges to
one of $G_{1}$, $G_{2}$ or both to get graphs $G_{1}^{\prime},G_{2}^{\prime}$,
as long as $I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}^{\prime}}$ is a splitting.

######  Remark 4.2.

The reduced splittings of $I_{K_{n}}$ are those of the last type in
Proposition 3.9, namely $I_{K_{n}}=I_{G_{1}}+I_{G_{2}}$ where
$G_{1}={K_{n}}\char 92\relax\\{a,c\\}$ and $G_{2}={K_{n}}\char
92\relax\\{b,d\\}$. The other two types in Proposition 3.9 can be taken from
the reduced splittings, by adding edges.

######  Proposition 4.3.

If $I_{G}$ is subgraph splittable, then it has at least one reduced splitting.

Proof. Any subgraph splitting $I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}^{\prime}}$ of
$I_{G}$ is either reduced or there exist a splitting
$I_{G}=I_{G_{1}}+I_{G_{2}}$ such that $G_{1}$ is a proper subgraph of
$G_{1}^{\prime}$ or/and $G_{2}$ is a proper subgraph of $G_{2}^{\prime}$. In
the latter case, $G_{1}$ has fewer edges than $G_{1}^{\prime}$ or/and $G_{2}$
has fewer edges than $G_{2}^{\prime}$. This procedure cannot be repeated
indefinitely, since the number of edges of $G$ is finite. $\square$

To understand the structure of reduced splittings one has to generalize first
the notion of edge splitting by replacing the edge with a set of edges.

Let $S=\\{B_{w_{1}},B_{w_{2}},\ldots,B_{w_{r}}\\}$ be a minimal system of
binomial generators of $I_{G}$. Given a set $F\subset E(G)$, we define
$G_{S}^{F}=\bigcup_{e\in F}G_{S}^{e}$ and get $I_{G}=I_{G_{S}^{F}}+I_{G\char
92\relax F}$, by using similar arguments as in the proof of Theorem 2.4.

Of particular interest is the case that $F$ is the set of all edges of $G$
having a common vertex $v$. Given a vertex $v$ of $G$, we let $G-v$ be the
subgraph of $G$ obtained by deleting the vertex $v$. We denote by $G_{S}^{v}$
the subgraph of $G$ with edges

$E(G_{S}^{v})=\bigcup_{1\leq i\leq r\ \textrm{and}\ v\in V(w_{i})}E(w_{i}).$

It holds that $I_{G}=I_{G_{S}^{v}}+I_{G-v}$.

The next theorem asserts that the reduced splittings of $I_{G}$ are always in
the form $I_{G}=I_{G_{S}^{F}}+I_{G\char 92\relax F}$, for suitable sets $S$
and $F$.

######  Theorem 4.4.

Let $I_{G}=I_{G_{1}}+I_{G_{2}}$ be a reduced splitting of $I_{G}$. Then there
exist a set $F\subset E(G)$ and a minimal system of binomial generators $S$ of
$I_{G}$ such that $I_{G_{1}}=I_{G_{S}^{F}}$ and $I_{G_{2}}=I_{G\char 92\relax
F}$.

Proof. Let $I_{G}=I_{G_{1}}+I_{G_{2}}$ be a reduced splitting of $I_{G}$ and
set $F=G\char 92\relax G_{2}$. Let $\\{f_{1},\ldots,f_{s}\\}$ be a system of
binomial generators of $I_{G_{1}}$, $\\{g_{1},\ldots,g_{t}\\}$ be a system of
binomial generators of $I_{G_{2}}$ and
$S=\\{B_{w_{1}},\ldots,B_{w_{r}}\\}\subset\\{f_{1},\ldots,f_{s},g_{1},\ldots,g_{t}\\}$
be a minimal system of binomial generators of $I_{G}$ as in the proof of
Theorem 2.10. Then $G\char 92\relax F=G_{2}$, so $I_{G\char 92\relax
F}=I_{G_{2}}$, and $I_{G_{S}^{F}}\subset I_{G_{1}}$ since
$I_{G_{S}^{e}}\subset I_{G_{1}}$ for each $e\in F$ from the proof of Theorem
2.10. But $I_{G}=I_{G_{1}}+I_{G_{2}}$ is a reduced splitting of $I_{G}$ and
also $I_{G}=I_{G_{S}^{F}}+I_{G_{2}}$, since $I_{G}=I_{G_{S}^{F}}+I_{G\char
92\relax F}$ and $I_{G\char 92\relax F}=I_{G_{2}}$, with $I_{G_{S}^{F}}\subset
I_{G_{1}}$, therefore $I_{G_{S}^{F}}=I_{G_{1}}$. $\square$

######  Remark 4.5.

A reduced splitting $I_{G}=I_{G_{1}}+I_{G_{2}}$ can be also written in the
form $I_{G}=I_{G\char 92\relax F}+I_{G_{S}^{F}}$ where $F=G\char 92\relax
G_{1}$, $I_{G_{1}}=I_{G\char 92\relax F}$ and $I_{G_{2}}=I_{G_{S}^{F}}$.

######  Example 4.6.

Let $G$ be the bipartite graph consisting of four 4-cycles
$w_{1},w_{2},w_{3},w_{4}$ in a row, i.e. for $i<j$ it holds that $E(w_{i})\cap
E(w_{j})=\emptyset$ except if $j=i+1$ in which case they have one edge in
common. The ideal $I_{G}$ has a unique minimal system of binomial generators
consisting of the binomials $B_{w_{1}},B_{w_{2}},B_{w_{3}},B_{w_{4}}$. Then
there are 19 different splittings. More precisely, four minimal and reduced
splittings in the form $I_{G}=<B_{w_{i}}>+<B_{w_{j}},B_{w_{k}},B_{w_{l}}>$,
where $\\{i,j,k,l\\}=\\{1,2,3,4\\}$. Also three minimal and reduced splittings
in the form $I_{G}=<B_{w_{i}},B_{w_{j}}>+<B_{w_{k}},B_{w_{l}}>$. Finally
twelve non-minimal and non-reduced splittings in the form
$I_{G}=<B_{w_{i}},B_{w_{j}}>+<B_{w_{j}},B_{w_{k}},B_{w_{l}}>$.

The next Theorem asserts that minimal splittings are always reduced.

######  Theorem 4.7.

Every minimal splitting of $I_{G}$ is also a reduced splitting.

Proof. Let $I_{G}=I_{G_{1}}+I_{G_{2}}$ be a minimal splitting which is not
reduced. Then there exist $I_{G_{1}^{\prime}}\subset I_{G_{1}}$ and
$I_{G_{2}^{\prime}}\subset I_{G_{2}}$ such that
$I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}^{\prime}}$, where $I_{G_{1}^{\prime}}$ is a
proper subset of $I_{G_{1}}$ or/and $I_{G_{2}^{\prime}}$ is a proper subset of
$I_{G_{2}}$. Suppose that for instance $I_{G_{1}^{\prime}}$ is a proper subset
of $I_{G_{1}}$. Let $\\{B_{w_{1}},\dots,B_{w_{s}}\\}$ and
$\\{B_{w_{s+1}},\dots,B_{w_{l}}\\}$ be minimal systems of binomial generators
of the ideals $I_{G_{1}}$ and $I_{G_{2}}$, respectively. Since
$I_{G}=I_{G_{1}}+I_{G_{2}}$ is a minimal splitting, the ideal $I_{G}$ is
minimally generated by the set
$\\{B_{w_{1}},\dots,B_{w_{s}},B_{w_{s+1}},\dots,B_{w_{l}}\\}$. Let
$\\{f_{1},\dots,f_{t}\\}$ be a system of binomial generators of
$I_{G_{1}^{\prime}}$ then from the equality
$I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}^{\prime}}$ we have that
$I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}}$, since $G_{2}^{\prime}\subset G_{2}$.
Thus there exists a set
$\\{B_{w_{1}^{\prime}},\dots,B_{w_{s}^{\prime}}\\}\subset\\{f_{1},\dots,f_{t}\\}$
such that
$\\{B_{w_{1}^{\prime}},\dots,B_{w_{s}^{\prime}},B_{w_{s+1}},\dots,B_{w_{l}}\\}$
is a minimal system of generators of $I_{G}$, since toric ideals of graphs are
homogeneous and therefore any two minimal systems of generators have the same
cardinality. Then, after reordering
$B_{w_{1}^{\prime}},\dots,B_{w_{s}^{\prime}}$ if necessary, we can assume that
$B_{w_{j}^{\prime}}=B_{w_{j}}$ if $B_{w_{j}}$ is indispensable, and the
binomials $B_{w_{j}^{\prime}},B_{w_{j}}$ are $F_{4}$-equivalent if $B_{w_{j}}$
is dispensable, namely $B_{w_{j}}$ is not indispensable, since dispensability
of toric ideals of graphs is only caused by $F_{4}$’s. Recall that two
primitive walks $\gamma$, $\gamma^{\prime}$ are $F_{4}$-equivalent if either
$\gamma=\gamma^{\prime}$ or there exists a series of walks
$\gamma_{1}=\gamma,\gamma_{2},\ldots,\gamma_{r-1},\gamma_{r}=\gamma^{\prime}$
such that $\gamma_{i}$ and $\gamma_{i+1}$ differ by an $F_{4}$, where $1\leq
i\leq r-1$, see [10, Section 4]. Since $G_{1}^{\prime}$ is a proper subgraph
of $G_{1}$, there exists an edge $e\in E(w_{i})\subset E(G_{1})$ which is not
in $E(G_{1}^{\prime})$, but $e\not\in E(w_{i}^{\prime})$ for at least one
index $1\leq i\leq s$. Then $B_{w_{i}}$ is dispensable, thus
$w_{i},w_{i}^{\prime}$ are $F_{4}$-equivalent and $e$ belongs to a common
$F_{4}$ of both $w_{i},w_{i}^{\prime}$. Suppose that the edges of the $F_{4}$
belonging to $w_{i}$ are $e,f$ and to $w_{i}^{\prime}$ are $a,b$, thus
$F_{4}=(e,a,f,b)$. Consider the binomial $ef-ab\in I_{G}$, we have that all
$e,f,a,b$ are edges of $G_{1}$, since $G_{1}^{\prime}\subset G_{1}$, and
therefore $ef-ab\in I_{G_{1}}$.

We distinguish the following cases.

  1. (1)

$ef-ab$ is an indispensable binomial of $I_{G}$. The set
$\\{B_{w_{1}^{\prime}},\dots,B_{w_{s}^{\prime}},B_{w_{s+1}},\dots,B_{w_{l}}\\}$
is a minimal system of generators of $I_{G}$ and $ef-ab$ is indispensable of
$I_{G}$, so $ef-ab$ is one of the binomials $B_{w_{i}^{\prime}},1\leq k\leq s$
or $B_{w_{k}},s+1\leq k\leq l$. But $ef-ab\not\in I_{G_{1}^{\prime}}$ since
$e$ is not an edge of $G_{1}^{\prime}$, thus $ef-ab=B_{w_{k}}$ for an index
$s+1\leq k\leq l$. Since the binomial $ef-ab$ is indispensable of $I_{G}$, the
$A_{G}$-fiber of ${\rm deg}_{A_{G}}(ef)$ has only two elements, namely $ef$
and $ab$, see [2]. Then the $A_{G_{1}}$-fiber of ${\rm deg}_{A_{G_{1}}}(ef)$
has at most two elements; in fact, it has exactly two with no common factor
other than 1 since $ef-ab\in I_{G_{1}}$. Thus $ef-ab$ is indispensable of
$I_{G_{1}}$, and therefore $ef-ab=B_{w_{q}}$ for an index $1\leq q\leq s$ a
contradiction to the hypothesis that $I_{G}=I_{G_{1}}+I_{G_{2}}$ is a minimal
splitting.

  2. (2)

$ef-ab$ is not an indispensable binomial of $I_{G}$. Then there is a binomial
$ef-cd$ in $I_{G}$. In this case, the $A_{G}$-fiber of ${\rm deg}_{A_{G}}(ef)$
corresponds to a subgraph of $G$ homomorphic to $K_{4}$ and it consists of
exactly three monomials, namely $ef$, $ab$, and $cd$. Every minimal system of
generators of $I_{G}$ should contain exactly two of the binomials $ef-ab,ef-
cd,ab-cd$. There are two subcases.

    1. (i)

Both edges $c,d$ belong to $G_{1}$. Then all binomials $ef-ab,ef-cd,ab-cd$
belong to $I_{G_{1}}$, so any minimal system of binomial generators of
$I_{G_{1}}$ should contain exactly two of them. Since
$I_{G}=I_{G_{1}}+I_{G_{2}}$ is a minimal splitting, the ideal $I_{G_{2}}$
cannot contain any of the above three binomials. But
$I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}}$ is also a splitting of $I_{G}$ and $e$ is
not an edge of $G_{1}^{\prime}$, therefore only $ab-cd$ can be an element of
$I_{G_{1}^{\prime}}$. Then
$\\{B_{w_{1}^{\prime}},\dots,B_{w_{s}^{\prime}},B_{w_{s+1}},\dots,B_{w_{l}}\\}$
is a minimal generating set of $I_{G}$, which contains at most one of the
binomials $ef-ab,ef-cd,ab-cd$, a contradiction.

    2. (ii)

At least one of $c,d$ does not belong to $G_{1}$. Then the binomial $ef-ab$ is
indispensable of $I_{G_{1}}$, since the $A_{G_{1}}$-fiber of ${\rm
deg}_{A_{G_{1}}}(ef)$ has only two elements, namely $ef$ and $ab$, with no
common factor other than 1. Thus the set $\\{B_{w_{1}},\dots,B_{w_{s}}\\}$
contains the binomial $ef-ab$. The set
$\\{B_{w_{1}},\dots,B_{w_{s}},B_{w_{s+1}},\dots,B_{w_{l}}\\}$ is a minimal
system of generators of $I_{G}$, so $\\{B_{w_{s+1}},\dots,B_{w_{l}}\\}$
contains exactly one of the binomials $ef-cd$ or $ab-cd$ and does not contain
$ef-ab$. But $I_{G}=I_{G_{1}^{\prime}}+I_{G_{2}}$ is a splitting of $I_{G}$
and none of the binomials $ef-ab,ef-cd,ab-cd$ belongs to $I_{G_{1}^{\prime}}$,
since $e$ and at least one of $c,d$ does not belong to $E(G_{1}^{\prime})$.
Thus the set $\\{B_{w_{s+1}},\dots,B_{w_{l}}\\}$ contains exactly two of the
binomials $ef-ab,ef-cd,ab-cd$, a contradiction.

In all cases we reach a contradiction, so every minimal splitting is reduced.
$\square$

######  Remark 4.8.

The converse of Theorem 4.7 is not true. By Theorem 3.10, $I_{K_{n}}$ does not
have a minimal splitting for $n\geq 6$. But from Proposition 3.9 any splitting
$I_{G}=I_{{K_{n}}\char 92\relax\\{a,c\\}}+I_{{K_{n}}\char 92\relax\\{b,d\\}}$
is reduced.

######  Remark 4.9.

In [5, Question 5.1] G. Favacchio, J. Hofscheier, G. Keiper, and A. Van Tuyl
pose the following question: For what graphs $G$ can we find $G_{1}$ and
$G_{2}$ so that their respective toric ideals satisfy
$I_{G}=I_{G_{1}}+I_{G_{2}}$? We answered this question in the case that
$G_{1},G_{2}$ are subgraphs of $G$. The general question seems difficult,
since one has information from $G$ only about the edges and possible closed
walks of $G_{1},G_{2}$, but not about their set of vertices.

The next example shows that there may be splittings
$I_{G}=I_{G_{1}}+I_{G_{2}}$ such that one of $G_{1},G_{2}$ or both are not
isomorphic to any subgraph of $G$.

Figure 4. The graphs $G,G_{1}$ and $G_{2}$ of a non subgraph splitting.

Let $G$ be the grid graph of Figure 4 with 9 vertices and 12 edges. The graph
$G$ has four cycles of length 4 with no chord, namely $w_{1}$, $w_{2}$,
$w_{3}$ and $w_{4}$, and a cycle of length 8 with no chord, namely $w_{5}$.
Then the ideal $I_{G}$ is generated by the binomials $B_{w_{i}},1\leq i\leq
5$. The ideal $I_{G_{1}}$ is generated by $B_{w_{1}},B_{w_{3}}$ and the ideal
$I_{G_{2}}$ is generated by
$B_{w_{2}},B_{w_{4}},B_{w_{5}},B_{w_{6}},B_{w_{7}},B_{w_{8}}$, where $w_{i},\
5\leq i\leq 8$, are closed walks of length 8 with no chord. Then
$I_{G}=I_{G_{1}}+I_{G_{2}}$ is a splitting of $I_{G}$ and $G_{2}$ is not
isomorphic to any subgraph of $G$, since it has 10 vertices. Thus there exist
splittings of graphs that are not subgraph splittings.

Funding The authors did not receive support from any organization for the
submitted work.

Data availability Data sharing not applicable to this article as no datasets
were generated or analysed during the current study.

Declaration

Conflict of interest The authors declare that there are no conflict of
interest that are directly or indirectly related to the work submitted for
publication.

## References

  * [1] CoCoATeam, CoCoA: A system for doing computations in commutative algebra, available at http://cocoa.dima.unige.it.
  * [2] H. Charalambous, A. Katsabekis, A. Thoma, Minimal systems of binomial generators and the indispensable complex of a toric ideal, Proc. Amer. Math. Soc. 135 (2007), 3443-3451.
  * [3] J. A. De Loera, B. Sturmfels, R. Thomas, Gröbner bases and triangulations of the second hypersimplex, Combinatorica 15 (1995), 409-424.
  * [4] M. Drton, B. Sturmfels, S. Sullivant, Lectures on algebraic statistics, Oberwolfach Seminars, vol. 39. Birkhäuser Verlag, Basel, 2009, viii+171 pp.
  * [5] G. Favacchio, J. Hofscheier, G. Keiper, A. Van Tuyl, Splittings of toric ideals, J. Algebra 574 (2021), 409–433.
  * [6] P. Gimenez, H. Srinivasan, Gluing and splitting of homogeneous toric ideals, arXiv:2402.17112v1 (2024).
  * [7] G. Keiper, Toric Ideals of Finite Simple Graphs, PhD thesis, McMaster University, 2022. http://hdl.handle.net/11375/27878
  * [8] H. Ohsugi, T. Hibi, Indispensable binomials of finite graphs. J. Algebra Appl. 4 (2005), 421–434.
  * [9] H. Ohsugi and T. Hibi, Centrally symmetric configurations of integer matrices, Nagoya Math. J. 216 (2014), 153-170.
  * [10] E. Reyes, C. Tatakis, A. Thoma, Minimal generators of toric ideals of graphs, Adv. Appl. Math. 48 (2012), 64-78.
  * [11] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, MAS, R.I., 1995.
  * [12] R. H. Villarreal, Normality of subrings generated by square free monomials, J. Pure Appl. Algebra 113 (1996), 91-106.
  * [13] R. H. Villarreal, Monomial Algebras, 2nd edn. CRC Press, Boca Raton FL, 2015.