# Gröbner basis and Krull dimension of Lovász-Saks-Sherijver ideal associated
to a tree

Mohammad Farrokhi D. G<EMAIL_ADDRESS><EMAIL_ADDRESS>Research Center for Basic Sciences and Modern Technologies (RBST), Institute
for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran  and
Ali Akbar Yazdan Pour<EMAIL_ADDRESS>Department of Mathematics, Institute
for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran

###### Abstract.

Let $\mathbb{K}$ be a field and $n$ be a positive integer. Let
$\Gamma=([n],E)$ be a simple graph, where $[n]=\\{1,\ldots,n\\}$. If
$S=\mathbb{K}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$ is a polynomial ring,
then the graded ideal

$L_{\Gamma}^{\mathbb{K}}(2)=\left(x_{i}x_{j}+y_{i}y_{j}\colon\quad\\{i,j\\}\in
E({\Gamma})\right)\subset S,$

is called the Lovász-Saks-Schrijver ideal, LSS-ideal for short, of $\Gamma$
with respect to $\mathbb{K}$. In the present paper, we compute a Gröbner basis
of this ideal with respect to lexicographic ordering induced by
$x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$ when $\Gamma=T$ is a tree. As a
result, we show that it is independent of the choice of the ground field
$\mathbb{K}$ and compute the Hilbert series of $L_{T}^{\mathbb{K}}(2)$.
Finally, we present concrete combinatorial formulas to obtain the Krull
dimension of $S/L_{T}^{\mathbb{K}}(2)$ as well as lower and upper bounds for
Krull dimension.

###### Key words and phrases:

Gröbner basis, Lovász-Saks-Sherijver ideal (LSS-ideal), Hilbert series, Krull
dimension

###### 2010 Mathematics Subject Classification:

Primary: 13P10, 05E40; Secondary: 05C62

##  1\. introduction and preliminaries

Gröbner bases of an ideal, as special kinds of generating sets of the ideal,
give rise to computational tools to determine many properties of the ideal. It
is one of the main practical tools for solving systems of polynomial equations
and computing the images of algebraic varieties under projections or rational
maps. Gröbner bases were introduced in 1965, together with an algorithm to
compute them (Buchberger’s algorithm), by Bruno Buchberger in his Ph.D.
thesis. This notion has been introduced for ideals in the polynomial rings and
extended to various noncommutative algebras such as free non-commutative
algebra and exterior algebra [2].

Let $I$ be an ideal in the polynomial ring $R=\mathbb{K}[x_{1},\ldots,x_{n}]$.
We denote by $\mathrm{Mon}(R)$ the set of all monomials in $R$, that is the
set $\\{x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}\colon\;\alpha_{1},\ldots,\alpha_{n}\in\mathbb{N}\cup\\{0\\}\\}$.
Let $\leq$ be a monomial ordering on $R$ by which we mean $\leq$ is a total
ordering on $\mathrm{Mon}(R)$ such that:

  * (i)

$1<u$ for all $1\neq u\in\mathrm{Mon}(R)$;

  * (ii)

if $u,v\in\mathrm{Mon}(R)$ and $u<v$, then $uw<vw$ for all
$w\in\mathrm{Mon}(R)$.

Some well-known monomial orders are lexicographic $\leq_{\mathrm{lex}}$,
degree lexicographic $\leq_{\mathrm{dlex}}$, and degree reverse lexicographic
$\leq_{\mathrm{revlex}}$ ordering (see [1] for detailed descriptions).

Let $\leq$ be a fixed monomial ordering on $\mathrm{Mon}(R)$ and
$\mathbb{N}_{\circ}$ be the set of non-negative integers. If
$f=\sum_{\alpha\in\mathbb{N}_{\circ}^{n}}a_{\alpha}\textbf{x}^{\alpha}$ is a
nonzero polynomial of $R$ with each $a_{\alpha}\in\mathbb{K}$, then the
initial monomial of $f$ with respect to $\leq$ is the biggest monomial with
respect to $\leq$ among the monomials belonging to
$\mathrm{supp}(f):=\\{\mathbf{x}^{\alpha}\colon\;a_{\alpha}\neq 0\\}$. Let
$\mathrm{in}_{\leq}(f)$ be the initial monomial of $f$ with respect to $\leq$.
If $I$ is a nonzero ideal of $R$, the initial ideal of $I$ with respect to
$\leq$ is the monomial ideal of $R$ generated by
$\\{\mathrm{in}_{\leq}(f)\colon\;0\neq f\in I\\}$. Let $\mathrm{in}_{\leq}(I)$
denote the initial ideal of $I$, i.e.

$\mathrm{in}_{\leq}(I)=(\mathrm{in}_{\leq}(f)\colon\;0\neq f\in I).$

######  Definition.

Let $I$ be a nonzero ideal of $R$. A finite set of nonzero polynomials
$\\{g_{1},\ldots,g_{s}\\}$ where $g_{i}\in I$ is said to be a Gröbner basis of
$I$ with respect to $\leq$ if the initial ideal $\mathrm{in}_{\leq}(I)$ of $I$
is generated by the monomials
$\mathrm{in}_{\leq}(g_{1}),\ldots,\mathrm{in}_{\leq}(g_{s})$.

Let $\leq$ be a monomial ordering on $R$. The following facts are well-known
in the theory of Gröbner bases:

  * •

Gröbner bases always exist for any ideal $I$ of $R$. Moreover, any Gröbner
basis of $I$ can be transformed into a reduced Gröbner basis
$\\{g_{1},\ldots,g_{m}\\}$ in the following sense:

    * –

the coefficient of $\mathrm{in}_{\leq}(g_{i})$ in $g_{i}$ is $1$, for all
$1\leq i\leq m$,

    * –

If $i\neq j$, then none of the monomials belonging to $\mathrm{supp}(g_{j})$
is divisible by $\mathrm{in}_{\leq}(g_{i})$.

  * •

If $\mathcal{G}$ is a Gröbner basis of $I$ then so is $\mathcal{G}^{\prime}$
for any $\mathcal{G}\subseteq\mathcal{G}^{\prime}\subseteq I$.

  * •

Any Gröbner basis of $I$ is a set of generators for $I$.

  * •

If $\mathcal{G}=\\{g_{1},\ldots,g_{s}\\}$ is a Gröbner basis of $I$ and if
$f_{1},\ldots,f_{s}\in I$ are nonzero polynomials with
$\mathrm{in}_{\leq}(f_{i})=\mathrm{in}_{\leq}(g_{i})$, then
$\\{f_{1},\ldots,f_{s}\\}$ is also a Gröbner basis of $I$.

  * •

If $\mathcal{G}=\\{g_{1},\ldots,g_{s}\\}$ is a Gröbner basis of $I$, then
every polynomial $f\in R$ has a unique remainder $r$ with respect to
$g_{1},\ldots,g_{s}$ (see [7, Lemma 2.2.3]). In this case, we say that $f$
reduces to $r$ with respect to $g_{1},\ldots,g_{s}$.

  * •

If $\mathcal{G}=\\{g_{1},\ldots,g_{s}\\}$ is a Gröbner basis of $I$, then a
nonzero polynomial $f\in R$ belongs to $I$ if and only if the unique remainder
of $f$ with respect to $g_{1},\ldots,g_{s}$ is $0$.

  * •

If $f,g_{1},\ldots,g_{s}$ are non-zero polynomials in $R$, then division
algorithm (see e.g. [7, Theorem 2.2.1]) guarantees the existence of the
following standard form

$f=f_{1}g_{1}+\cdots+f_{s}g_{s}+r$

for $f$, where

    * (a)

if $r\neq 0$ and $u\in\mathrm{supp}(r)$, then none of the initial monomials
$\mathrm{in}_{\leq}(g_{1}),\ldots,\mathrm{in}_{\leq}(g_{s})$ divides $u$,

    * (b)

if $f_{i}\neq 0$, then
$\mathrm{in}_{\leq}(f)\geq\mathrm{in}_{\leq}(f_{i}g_{i})$.

Let $\mathcal{G}=\\{f_{1},\ldots,f_{s}\\}$ be a set of generators of $I$. The
Buchberger’s criterion provides an efficient way to check whether
$\mathcal{G}$ is a Gröbner basis of $I$ or not. Given nonzero polynomials
$f,g\in R$, let $c_{f}$ and $c_{g}$ denote the coefficients of
$\mathrm{in}_{\leq}(f)$ and $\mathrm{in}_{\leq}(g)$ in $f$ and $g$,
respectively. The polynomial

$S(f,g)=\frac{\mathrm{lcm}(\mathrm{in}_{\leq}(f),\mathrm{in}_{\leq}(g))}{c_{f}\cdot\mathrm{in}_{\leq}(f)}f-\frac{\mathrm{lcm}(\mathrm{in}_{\leq}(f),\mathrm{in}_{\leq}(g))}{c_{g}\cdot\mathrm{in}_{\leq}(g)}g$

is called the $S$-polynomial of $f$ and $g$. We now come to the most important
theorem in the theory of Gröbner bases.

######  Theorem 1.1 (Buchberger’s criterion).

Let $I$ be a nonzero ideal of $R$ and $\mathcal{G}=\\{g_{1},\ldots,g_{s}\\}$
be a system of generators of $I$. Then $\mathcal{G}$ is a Gröbner basis of $I$
if and only if $S(g_{i},g_{j})$ reduces to $0$ with respect to
$g_{1},\ldots,g_{s}$, for all $i\neq j$.

The Buchberger criterion (Theorem 1.1) supplies an algorithm to compute a
Gröbner basis starting from a system of generators of an ideal. This algorithm
is so-called as Bughberger’s algorithm. In general, the complexity of this
algorithm is of double exponential order. Finding an explicit and quick
algorithm for computing a Gröbner basis of some families of ideals is very
important in the context of computational commutative algebra. The aim of this
paper is to compute explicitly a Gröbner basis of LSS-ideals associated to
trees.

Let $\mathbb{K}$ be a field, $n$ be a positive integer, and set
$[n]=\\{1,\ldots,n\\}$. Let $\Gamma=([n],E)$ be a simple graph with vertex set
$[n]$ and edge set $E$. In [6] and later in [5, 8], the authors study the
graded ideal

$L_{\Gamma}^{\mathbb{K}}(d)=\left(x_{i,1}x_{j,1}+\cdots+x_{i,d}x_{j,d}\colon\quad\\{i,j\\}\in
E({\Gamma})\right)$

in the polynomial ring
$\mathbb{K}[x_{i,k}\colon\;i=1,\ldots,n,\;k=1,\ldots,d]$. The ideal
$L_{\Gamma}^{\mathbb{K}}(d)$ is called the Lovász-Saks-Schrijver ideal, LSS-
ideal for short, of $\Gamma$ with respect to $\mathbb{K}$. For $d=1$, the
ideal $L_{\Gamma}^{\mathbb{K}}(d)$ is a square-free monomial ideal known as
the edge ideal of $\Gamma$. The algebraic properties of LSS-ideal, such as
being prime, radical, and complete intersection are studied in [5, 6]. Also,
in [6] the (minimal) primary decomposition of $L_{\Gamma}^{\mathbb{K}}(2)$ has
been presented in terms of combinatorial properties of $\Gamma$. Let
$S=\mathbb{K}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$. In [8, Corollary 3.6]
the author shows that $L_{\Gamma}^{\mathbb{K}}(2)$ is a complete intersection
if and only if the parity binomial edge ideal $\mathcal{I}_{\Gamma}\subseteq
S$ of $\Gamma$, defined as below, is a complete intersection:

$\mathcal{I}_{\Gamma}=\left(x_{i}x_{j}-y_{i}y_{j}\colon\quad\\{i,j\\}\in
E(\Gamma)\right).$

Recall that an ideal $I\subseteq R$ is called complete intersection if $I$ is
generated by a sequence $a_{1},\ldots,a_{m}$ such that $a_{i}$ is not a zero-
divisor of $R/(a_{1},\ldots,a_{i-1})$, for $i=1,\ldots,m$. Note that
$L_{\Gamma}^{\mathbb{K}}(2)=\mathcal{I}_{G}$ if $\mathrm{char}(\mathbb{K})=2$.
However, it is shown in [8] that the graded Betti numbers
$\beta_{i,j}(S/L_{\Gamma}^{\mathbb{K}}(2))$ and
$\beta_{i,j}(S/\mathcal{I}_{\Gamma})$ coincide in any characteristic. It turns
out that the algebraic invariants of the LSS-ideal and parity binomial ideal
(such as dimension, depth, regularity, projective dimension, etc.) are the
same.

When $\mathbb{K}=\mathbb{R}$ the vanishing set of the ideal
$L_{\Gamma}^{\mathbb{K}}(d)$ coincides with the variety of orthogonal
representations of complement of $\Gamma$ in $\mathbb{R}^{d}$. Orthogonal
representations of graphs were introduced by Lovász in 1979 [10], and it is
shown that they are intimately related to important combinatorial properties
of graphs (see [9, Chapter 10]). An orthogonal representation of $\Gamma$ in
$\mathbb{R}^{d}$ assigns to each $i\in[n]$ a vector $u_{i}\in\mathbb{R}^{d}$
such that $u^{T}_{i}u_{j}=0$, whenever
$\\{i,j\\}\in\bar{E}=\binom{[n]}{2}\setminus E$. The variety of orthogonal
representations was studied in the works of Lovász, Saks, and Schrijver [11,
12]. The reference [10] is a nice reference for a comprehensive treatment of
orthogonal representations, their varieties, and their relations to important
combinatorial properties of graphs.

We find a Gröbner basis of $L_{T}^{\mathbb{K}}(2)$ with respect to
lexicographic ordering induced by $x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$ when
$T$ is a tree, that is a connected graph without any cycle. Theorem 2.1 shows
that Gröbner basis of $L_{T}^{\mathbb{K}}(2)$ can be described by paths of
even and odd length in $T$. We show in Corollary 2.2 that Gröbner basis has a
simple form if we restrict ourselves to a monomial ordering induced by an
ascending labeling on vertices of $T$. It turns out that the Gröbner basis of
$L_{T}^{\mathbb{K}}(2)$ (and hence its Hilbert series and Krull dimension)
with respect to this ordering is independent of the choice of the ground field
$\mathbb{K}$. Also, in Theorem 3.2 and Proposition 3.4, we present explicit
formulas for the Krull dimension of $S/L_{T}^{\mathbb{K}}(2)$ in terms of the
combinatorics of $T$. Finally, in Corollary 3.3, we show that the Krull
dimension of $S/L_{T}^{\mathbb{K}}(2)$ is bounded below by $n+1$ and bounded
above by $n-1+p(T)$ where $p(T)$ is the number of pendants of $T$. Recall that
a pendant vertex in $T$ is a vertex which has a unique neighbour in $T$. For
the graph theoretical concepts in this paper, the reader may refer to [3].

##  2\. Gröbner basis of LSS-ideal of trees

In this section, we compute a Gröbner basis of LSS-ideal of a given tree $T$
with respect to lexicographic ordering induced by

$x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}.$

It turns out that the Gröbner basis is characterized by even and odd paths in
$T$.

In what follows, any set of vertices of a path $P\colon v_{1},\ldots,v_{2m+1}$
of even length including vertices of odd indices except the end vertices is
called an odd subset of $P$. For any binomial $w=u\pm v$ with
$u,v\in\mathrm{Mon}(S)$ and $u>v$ let $\mathrm{in}_{\leq}(w):=u$ and
$\mathrm{ter}_{\leq}(w):=v$.

######  Theorem 2.1.

Let $T$ be a tree with vertex set $[n]$ and $I:=L_{T}^{\mathbb{K}}(2)$ be the
LSS-ideal of $T$. Put

  * (i)

for every path $P\colon v_{1},v_{2},\ldots,v_{2m}$ of $T$ of odd length

$g_{P}:=(x_{v_{1}}x_{v_{2m}}+y_{v_{1}}y_{v_{2m}})z_{P},$

where $z_{P}=y_{v_{3}}\cdots y_{v_{2m-1}}$ and $v_{1}<v_{2m}$;

  * (ii)

for any path $P\colon v_{1},v_{2},\ldots,v_{2m+1}$ of $T$ of even length and
any odd subset $\mathcal{O}$ of $P$,

$g^{\prime}_{P,\mathcal{O}}:=(x_{v_{1}}y_{v_{2m+1}}-x_{v_{2m+1}}y_{v_{1}})z^{\prime}_{P,\mathcal{O}},$

where
$z^{\prime}_{P,\mathcal{O}}=(\prod_{v\in\mathcal{O}}x_{v})\cdot(\prod_{v\in
V(P)\setminus(\mathcal{O}\cup\\{v_{1},v_{2m+1}\\})}y_{v})$ and
$v_{1}<v_{2m+1}$.

Then

$\displaystyle\mathcal{G}:=$ $\displaystyle\\{g_{P}\colon\quad P\emph{ is a
path of odd length in }T\\}$
$\displaystyle\cup\\{g^{\prime}_{P,\mathcal{O}}\colon\quad P\emph{ is a path
of even length in }T\emph{ and }\mathcal{O}\emph{ is an odd subset of }P\\}$

is a Gröbner basis of $I$ with respect to the lexicographic ordering induced
by $x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$. In particular, $I$ is a radical
ideal.

###### Proof.

First we show that $\mathcal{G}\subseteq I$. To do this, we show that every
polynomial in parts (i)–(ii) belongs to $I$.

(i) Let $P\colon v_{1},\ldots,v_{2m}$ be a path of odd length in $T$, and
assume without loss of generality that $v_{i}=i$ for $i=1,\ldots,2m$. Then

$g_{P}=\frac{z}{y_{1}y_{2}}(x_{1}x_{2}+y_{1}y_{2})\\\
+\sum_{i=1}^{m-1}\left(\frac{x_{1}x_{2i+2}z}{y_{1}y_{2i}y_{2i+1}y_{2i+2}}(x_{2i}x_{2i+1}+y_{2i}y_{2i+1})-\frac{x_{1}x_{2i}z}{y_{1}y_{2i}y_{2i+1}y_{2i+2}}(x_{2i+1}x_{2i+2}+y_{2i+1}y_{2i+2})\right)$

belongs to $I$, where $z=y_{1}\cdots y_{2m}$.

(ii) Let $P\colon v_{1},\ldots,v_{2m+1}$ be a path of even length in $T$,
$\mathcal{O}$ be an odd subset of $P$, and assume without loss of generality
that $v_{i}=i$ for $i=1,\ldots,2m+1$. If $\mathcal{O}=\varnothing$,

$g^{\prime}_{P,\mathcal{O}}=\sum_{i=1}^{m}\left(-\frac{x_{2i+1}z}{y_{2i-1}y_{2i}y_{2i+1}}(x_{2i-1}x_{2i}+y_{2i-1}y_{2i})+\frac{x_{2i-1}z}{y_{2i-1}y_{2i}y_{2i+1}}(x_{2i}x_{2i+1}+y_{2i}y_{2i+1})\right)$

belongs to $I$, where $z=y_{1}\cdots y_{2m+1}$. Now, assume that
$\mathcal{O}=\\{i_{1},\ldots,i_{t}\\}$ is non-empty with $i_{1}<\cdots<i_{t}$.
Put $\mathcal{O}^{\prime}:=\mathcal{O}\cup\\{1,2m+1\\}$. Also, let $P_{j}$
denote the path from $i_{j}$ to $i_{j+1}$ for all $1\leq j<t$. Then

$g^{\prime}_{P,\mathcal{O}}=\sum_{j=1}^{m}\frac{z}{x_{i_{j}}x_{i_{j+1}}z^{\prime}_{P_{j},\varnothing}}\cdot
g^{\prime}_{P_{j},\varnothing}$

belongs to $I$, where $z=(\prod_{v\in\mathcal{O}}x_{v})\cdot(\prod_{v\in
V(P)\setminus\mathcal{O}^{\prime}}y_{v})$.

In what follows, we show that $\mathcal{G}$ is a Gröbner basis for $I$ with
respect to the lexicographic ordering induced by
$x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$. Accordingly, we put
$\mathrm{in}(w):=\mathrm{in}_{\leq}(w)$ and
$\mathrm{ter}(w):=\mathrm{ter}_{\leq}(w)$ for any binomial $w\in S$. Since
polynomials with coprime leading terms reduce to zero modulo $\mathcal{G}$
(see [7, Lemma 2.3.1]), we always assume that the polynomials under
considerations have non-coprime leading terms. Also, we consider a superficial
direction from $v_{1}$ to $v_{2m+1}$ on any path $v_{1},\ldots,v_{2m+1}$ of
type (ii). We have three cases to consider:

Case (i,i). Let $P\colon u_{1},\ldots,u_{2m}$ and
$Q:v_{1},\ldots,v_{2m^{\prime}}$ be paths in $T$ of length at least one. Then
either $\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g_{Q}))|z_{P}$ or
$\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g_{Q}))\nmid z_{P}$. In the former case,

$\displaystyle S(g_{P},g_{Q})$
$\displaystyle=\frac{z_{P}z_{Q}x_{v_{1}}x_{v_{2m^{\prime}}}y_{u_{1}}y_{u_{2m}}}{z}-\frac{z_{P}z_{Q}x_{u_{1}}x_{u_{2m}}y_{v_{1}}y_{v_{2m^{\prime}}}}{z}$
$\displaystyle=g_{Q}\left(\prod_{v\in V(P)\setminus
V(Q)}y_{v}\right)-g_{P}\left(\prod_{v\in V(Q)\setminus V(P)}y_{v}\right)$

is in standard form assuming that
$x_{v_{1}}x_{v_{2m^{\prime}}}>x_{u_{1}}x_{u_{2m}}$, where
$z=\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g_{Q}))$. Also, in the latter case,

$S(g_{P},g_{Q})=\frac{z_{P}z_{Q}y_{u_{1}}y_{u_{2m}}x_{v_{j^{\prime}}}}{z}-\frac{z_{P}z_{Q}x_{u_{i^{\prime}}}y_{v_{1}}y_{v_{2m^{\prime}}}}{z}$

and either

$S(g_{P},g_{Q})=g^{\prime}_{R,\varnothing}\left(\prod_{v\in V(P)\cap
V(Q)}y_{v}\right),$

is in standard form if $V(P)\subseteq V(Q)$ or $V(Q)\subseteq V(P)$, or

$S(g_{P},g_{Q})=g^{\prime}_{R,\varnothing}\left(\prod_{v\in(V(P)\cap
V(Q))\setminus\\{u_{k}\\}}y_{v}\right),$

is in standard form if neither $V(P)\subseteq V(Q)$ nor $V(Q)\subseteq V(P)$
and $u_{k}$ is the vertex of degree three in the subgraph induced by $V(P)\cup
V(Q)$. Here $R$ is the path between $u_{i^{\prime}}$ and $v_{j^{\prime}}$,
where $i^{\prime},j^{\prime}$ are such that
$x_{u_{i}}z=x_{v_{j}}z=\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g_{Q}))$ if
$\\{i,i^{\prime}\\}=\\{1,2m\\}$ and $\\{j,j^{\prime}\\}=\\{1,2m^{\prime}\\}$.

Case (i,ii). Let $P\colon u_{1},\ldots,u_{2m}$ and
$Q:v_{1},\ldots,v_{2m^{\prime}+1}$ be paths in $T$ of length at least one,
$\mathcal{O}$ be an odd subset of $Q$, and
$\mathcal{S}:=S(g_{P},g^{\prime}_{Q,\mathcal{O}})$. Then either
$\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$ is coprime
to $x_{u_{1}}x_{u_{2m}}$ or
$\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$ is
divisible by $x_{u_{1}}$.

First assume that
$\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$ is coprime
to $x_{u_{1}}x_{u_{2m}}$. We have two cases to consider. If
$y_{v_{2m^{\prime}+1}}\nmid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$,
then

$\displaystyle S(g_{P},g^{\prime}_{Q,\mathcal{O}})$
$\displaystyle=\frac{z_{P}z^{\prime}_{Q,\mathcal{O}}y_{u_{1}}y_{u_{2m}}x_{v_{1}}y_{v_{2m^{\prime}+1}}}{z}+\frac{z_{P}z^{\prime}_{Q,\mathcal{O}}x_{u_{1}}x_{u_{2m}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{z}$
$\displaystyle=g^{\prime}_{Q,\mathcal{O}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}})}+g_{P}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P})},$

is in standard form if $x_{v_{1}}>x_{u_{1}}$ and

$\displaystyle S(g_{P},g^{\prime}_{Q,\mathcal{O}})$
$\displaystyle=g_{P}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P})}+g^{\prime}_{Q,\mathcal{O}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}})},$

is in standard form if $x_{u_{1}}>x_{v_{1}}$, where
$z=\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$. Now
assume that
$y_{v_{2m^{\prime}+1}}\mid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$,
$u_{i}$ is in the connected component of $P-E(Q)$ containing
$v_{2m^{\prime}+1}$, and $i^{\prime}$ be such that
$\\{i,i^{\prime}\\}=\\{1,2m\\}$. Suppose $x_{v_{1}}>x_{u_{1}}$. Then

  * •

if $P_{1}$ is the path between $u_{i}$ and $v_{2m^{\prime}+1}$, $Q_{1}$ is the
path from $v_{1}$ to $u_{i^{\prime}}$ of even length, and
$\mathcal{O}_{1}=\mathcal{O}\cap V(Q_{1})$, then

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}+g_{P_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}$

is in standard form.

  * •

if $P_{1}$ is the path between $u_{i^{\prime}}$ and $v_{2m^{\prime}+1}$,
$Q_{1}$ is the path from $v_{1}$ to $u_{i}$ of even length, and
$\mathcal{O}_{1}=\mathcal{O}\cap V(Q_{1})$, then

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}+g_{P_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}$

is in standard form.

Next suppose $x_{u_{1}}>x_{v_{1}}$. Then

  * •

if $P_{1}$ is the path between $u_{i^{\prime}}$ and $v_{2m^{\prime}+1}$ of odd
length, $Q_{1}$ is the path from $u_{i}$ to $v_{1}$, and
$\mathcal{O}_{1}=\mathcal{O}\cap V(Q_{1})$, then

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}$

is in standard form.

  * •

if the path $P_{1}$ between $u_{i}$ and $v_{2m^{\prime}+1}$ has odd length,
then

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}+g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}$

is in standard form if $x_{v_{1}}>x_{u_{2m}}$, $Q_{1}$ is the path from
$v_{1}$ to $u_{i^{\prime}}$, and $\mathcal{O}_{1}=\mathcal{O}\cap V(Q_{1})$,
and

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}$

is in standard form if $x_{u_{2m}}>x_{v_{1}}$, $Q_{1}$ is the path from
$u_{i^{\prime}}$ to $v_{1}$, and $\mathcal{O}_{1}=\mathcal{O}\cap V(Q_{1})$.

Finally we consider the latter case that
$x_{u_{1}}\mid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$.
Observe that
$x_{v_{2m^{\prime}+1}}\nmid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$.
First assume that
$x_{v_{1}}\nmid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$.
Then for a suitable choices of $i,i^{\prime}$ with
$\\{i,i^{\prime}\\}=\\{1,2m\\}$, one of the following two cases occurs:

  * •

if $x_{v_{1}}>x_{u_{1}}$, $Q_{1}$ is the path from $v_{1}$ to $v_{k}$, $Q_{2}$
is the path from $v_{k}$ to $v_{2m^{\prime}+1}$, and
$\mathcal{O}_{t}=\mathcal{O}\cap V(Q_{t})$ for $t=1,2$, then

$\displaystyle S(g_{P},g^{\prime}_{Q,\mathcal{O}})=$
$\displaystyle\frac{z_{P}z^{\prime}_{Q}y_{u_{1}}y_{u_{2m}}x_{v_{1}}y_{v_{2m^{\prime}+1}}}{zx_{u_{i}}}+\frac{z_{P}z^{\prime}_{Q,\mathcal{O}}x_{u_{i^{\prime}}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{z}$
$\displaystyle=$ $\displaystyle
g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}+g_{P}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P})}+g^{\prime}_{Q_{2},\mathcal{O}_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{v_{1}}x_{v_{k}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{2}})x_{v_{1}}y_{v_{k}}}$

is in standard form.

  * •

if $x_{u_{1}}>x_{v_{1}}$ with $Q_{1}$ and $Q_{2}$ as above, where
$u_{i}=v_{k}$ for some $k\in\mathcal{O}$,
$x_{u_{i}}z=\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$,
and $x_{v_{k}}>x_{2m^{\prime}+1}$ w.l.o.g., then

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g_{P}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P})}+g^{\prime}_{Q_{1},\mathcal{O}_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{1}})}+g^{\prime}_{Q_{2},\mathcal{O}_{2}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{1}}x_{v_{k}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{2}})x_{v_{1}}y_{v_{k}}}$

is in standard form.

Next, if
$x_{v_{1}}\mid\gcd(\mathrm{in}(g_{P}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}}))$,
then $x_{v_{1}}=x_{u_{i}}$ and

$\displaystyle
S(g_{P},g^{\prime}_{Q,\mathcal{O}})=g^{\prime}_{Q,\mathcal{O}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}})}+g_{P}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P})}$

is in standard form.

Case (ii,ii). Let $P\colon u_{1},\ldots,u_{2m+1}$ and $Q\colon
v_{1},\ldots,v_{2m^{\prime}+1}$ be paths in $T$ of even lengths,
$\mathcal{O}_{P}$ and $\mathcal{O}_{Q}$ be odd subsets of $P$ and $Q$,
respectively, $x_{u_{1}}\geq x_{v_{1}}$ by symmetry, and
$\mathcal{S}:=S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})$.
First observe that $\mathcal{S}=0$ when $P=Q$. Hence, in what follows, we
assume that $P\neq Q$. Let
$z^{*}:=\gcd(\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}}),\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}}))$.
We have the following four cases:

Case 1. $z$ is coprime to $y_{u_{2m+1}}y_{v_{2m^{\prime}+1}}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}x_{u_{1}}y_{v_{2m+1}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{z^{*}}-\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}y_{u_{1}}x_{u_{2m+1}}x_{v_{1}}y_{v_{2m^{\prime}+1}}}{z^{*}}$

and one of the followings occurs:

  * •

Subcase 1.1. if $v_{1}\neq u_{1}\notin\mathcal{O}_{Q}$, then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}})}-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})},$

is in standard form.

  * •

Subcase 1.2. if $v_{1}=u_{1}\notin\mathcal{O}_{Q}$, $R$ is the path from
$u_{2m+1}$ to $v_{2m^{\prime}+1}$ (assuming that
$x_{u_{2m+1}}>x_{v_{2m^{\prime}+1}}$ by symmetry), and
$\mathcal{O}_{R}=(\mathcal{O}_{P}\cap V(R))\cup(\mathcal{O}_{Q}\cap V(R))$,
then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{R,\mathcal{O}_{R}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{R,\mathcal{O}_{R}})},$

is in standard form.

  * •

Subcase 1.3. if $u_{1}\in\mathcal{O}_{Q}$, then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}})}-g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{u_{1}\\}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{u_{1}\\}})},$

is in standard form.

Case 2. $z^{*}=zy_{u_{2m+1}}$ is coprime to $y_{v_{2m^{\prime}+1}}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}x_{u_{1}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{z}-\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}y_{u_{1}}x_{u_{2m+1}}x_{v_{1}}y_{v_{2m^{\prime}+1}}}{zy_{u_{2m+1}}}$

and one of the followings occurs:

  * •

Subcase 2.1. $u_{1}=v_{1}$. Let $Q_{1}$ be the path between $u_{2m+1}$ and
$v_{2m^{\prime}+1}$ and $\mathcal{O}_{Q_{1}}=\mathcal{O}_{Q}\cap V(Q_{1})$.
Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\pm
g^{\prime}_{Q_{1},\mathcal{O}_{Q_{1}}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{Q_{1}}})}$

is in standard form with sign being $+$ or $-$ according to
$x_{v_{2m^{\prime}+1}}>x_{u_{2m+1}}$ or not.

  * •

Subcase 2.2. $u_{1}\neq v_{1}$, $u_{1}\notin\mathcal{O}_{Q}$, and
$v_{1}\notin\mathcal{O}_{P}$. If $\mathcal{O}_{Q}\cup\\{u_{2m+1}\\}$ is an odd
subset of $Q$, then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}})}-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})}$

is in standard form. Now assume that $\mathcal{O}_{Q}\cup\\{u_{2m+1}\\}$ is
not an odd subset of $Q$. Let
$\mathcal{O}_{Q}=\\{v_{i_{1}},\ldots,v_{i_{m}}\\}$ with $i_{1}<\cdots<i_{m}$,
and $s$ be such that $u_{2m+1}$ lies on the path between $v_{i_{s}}$ and
$v_{i_{s+1}}$. Let $P_{1}$ be the path between $v_{i_{s}}$ and $u_{2m+1}$,
$P_{2}$ be the path between $u_{2m+1}$ and $v_{i_{s+1}}$, $Q_{1}$ be the path
between $v_{1}$ and $v_{i_{s}}$, and $Q_{2}$ be the path between $v_{i_{s+1}}$
and $v_{2m^{\prime}+1}$. Notice that $P_{1}$ and $P_{2}$ are paths of odd
lengths and $Q_{1}$ and $Q_{2}$ are paths of even lengths, and that
$\mathcal{O}_{Q_{i}}:=\mathcal{O}_{Q}\cap V(Q_{i})$ is an odd subset of
$V(Q_{i})$ for $i=1,2$. In the case where $Q_{i}$ ($i=1,2$) is a path of
length zero, we define $g^{\prime}_{Q_{i},\mathcal{O}_{Q_{i}}}:=1$. Also, put
$\varepsilon_{i}:=1-\delta_{|V(Q_{i})|,1}$ for $i=1,2$. Then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g^{\prime}_{P,\mathcal{O}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}})}-g_{P_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}+\varepsilon_{1}g^{\prime}_{Q_{1},\mathcal{O}_{Q_{1}}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{i_{s}}}y_{u_{2m+1}}}{\mathrm{in}(g^{\prime}_{Q_{1},\mathcal{O}_{Q_{1}}})x_{v_{i_{s}}}x_{u_{2m+1}}}$
$\displaystyle+g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{1}}x_{u_{2m+1}}}{\mathrm{in}(g_{P_{2}})x_{u_{1}}y_{u_{2m+1}}}\pm\varepsilon_{2}g^{\prime}_{Q_{2},\mathcal{O}_{Q_{2}}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{i_{s}}}y_{u_{2m+1}}y_{v_{1}}x_{v_{i_{s}}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{Q_{2}}})x_{v_{i_{s}}}x_{u_{2m+1}}x_{v_{1}}y_{v_{i_{s}}}}$

is in standard form with sign being $+$ or $-$ according to $Q_{1}$ being in
direction of $Q$ or not.

  * •

Subcase 2.3. $u_{1}\neq v_{1}$, $u_{1}\in\mathcal{O}_{Q}$, and
$v_{1}\notin\mathcal{O}_{P}$. Let
$\mathcal{O}^{\prime}_{Q}:=(\mathcal{O}_{Q}\cup\\{u_{2m+1}\\})\setminus\\{u_{1}\\}$.
Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}})}-g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}})}$

is in standard form.

  * •

Subcase 2.4. $u_{1}\neq v_{1}$, $u_{1}\notin\mathcal{O}_{Q}$, and
$v_{1}\in\mathcal{O}_{P}$. Let
$\mathcal{O}^{\prime}_{P}:=\mathcal{O}_{P}\setminus\\{v_{1}\\}$ and
$\mathcal{O}^{\prime}_{Q}:=\mathcal{O}_{Q}\cup\\{u_{2m+1}\\}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}^{\prime}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}^{\prime}_{P}})}-g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}})}$

is in standard form.

Case 3. $z^{*}=zy_{v_{2m^{\prime}+1}}$ is coprime to $y_{u_{2m+1}}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}x_{u_{1}}y_{u_{2m+1}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{zy_{v_{2m^{\prime}+1}}}-\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}y_{u_{1}}x_{u_{2m+1}}x_{v_{1}}}{z}$

and one of the followings occurs:

  * •

Subcase 3.1. $u_{1}=v_{1}$. Let $P_{1}$ be the path between $u_{2m+1}$ and
$v_{2m^{\prime}+1}$, and $\mathcal{O}_{P_{1}}=\mathcal{O}_{Q}\cap V(P_{1})$.
Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\pm
g^{\prime}_{P_{1},\mathcal{O}_{P_{1}}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P_{1},\mathcal{O}_{P_{1}}})}$

is in standard form with sign being $+$ or $-$ according to
$x_{v_{2m^{\prime}+1}}>x_{u_{2m+1}}$ or not.

  * •

Subcase 3.2. $u_{1}\neq v_{1}$, $u_{1}\notin\mathcal{O}_{Q}$, and
$v_{1}\notin\mathcal{O}_{P}$. If
$\mathcal{O}^{\prime}_{P}:=\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}$ is an
odd subset of $P$, then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}^{\prime}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}^{\prime}_{P}})}-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})}$

is in standard form. Now assume that
$\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}$ is not an odd subset of $P$. Let
$\mathcal{O}_{P}=\\{u_{i_{1}},\ldots,u_{i_{m}}\\}$ with $i_{1}<\cdots<i_{m}$,
and $s$ be such that $v_{2m^{\prime}+1}$ lies on the path between $u_{i_{s}}$
and $u_{i_{s+1}}$. Let $P_{1}$ be the path between $u_{i_{s}}$ and
$v_{2m^{\prime}+1}$, $P_{2}$ be the path between $v_{2m^{\prime}+1}$ and
$u_{i_{s+1}}$, and $P_{3}$ be the path between the last member $v_{\max}$ of
$\\{v_{1}\\}\cup\mathcal{O}_{Q}$ and $u_{i_{s+1}}$. Notice that $P_{1}$,
$P_{2}$, and $P_{3}$ are paths of odd lengths. Then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{2}})}-g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}})x_{u_{i_{s+1}}}}$
$\displaystyle-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})}-g_{P_{2}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{1}}x_{v_{2m^{\prime}+1}}}{\mathrm{in}(g_{P_{2}})x_{v_{1}}y_{v_{2m^{\prime}+1}}}$

is in standard form if $x_{u_{1}}>x_{u_{i_{s+1}}}$ and
$x_{v_{1}}>x_{u_{i_{s+1}}}$,

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{2}})}-g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}})x_{u_{i_{s+1}}}}$
$\displaystyle-
g_{P_{3}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(P_{3})}+\varepsilon
g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{v_{\max}\\}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{\max}}y_{v_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{v_{\max}\\}})x_{v_{\max}}x_{v_{i_{s+1}}}}$

is in standard form if $x_{u_{1}}>x_{u_{i_{s+1}}}$ and
$x_{v_{1}}<x_{u_{i_{s+1}}}$ with
$\varepsilon=1-\delta_{\mathcal{O}_{Q},\varnothing}$,

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{2}})}-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})}$
$\displaystyle-
g_{P_{2}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{1}}x_{v_{2m^{\prime}+1}}}{\mathrm{in}(g_{P_{2}})x_{v_{1}}y_{v_{2m^{\prime}+1}}}-g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}})x_{u_{i_{s+1}}}}$

is in standard form if $x_{u_{1}}<x_{u_{i_{s+1}}}$ and
$x_{v_{1}}>x_{u_{i_{s+1}}}$,

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{2}})}-g_{P_{3}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(P_{3})}-g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}\setminus\\{u_{i_{s+1}}\\}})x_{u_{i_{s+1}}}}$
$\displaystyle+\varepsilon
g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{v_{\max}\\}}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{v_{\max}}y_{v_{i_{s+1}}}}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}\setminus\\{v_{\max}\\}})x_{v_{\max}}x_{v_{i_{s+1}}}}$

is in standard form if $x_{u_{1}}<x_{u_{i_{s+1}}}$ and
$x_{v_{1}}<x_{u_{i_{s+1}}}$ with
$\varepsilon=1-\delta_{\mathcal{O}_{Q},\varnothing}$.

  * •

Subcase 3.3. $u_{1}\neq v_{1}$, $u_{1}\in\mathcal{O}_{Q}$, and
$v_{1}\notin\mathcal{O}_{P}$. Let
$\mathcal{O}^{\prime}_{P}:=\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}$ and
$\mathcal{O}^{\prime}_{Q}:=\mathcal{O}_{Q}\setminus\\{u_{1}\\}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}^{\prime}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}^{\prime}_{P}})}-g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}^{\prime}_{Q}})}$

is in standard form.

  * •

Subcase 3.4. $u_{1}\neq v_{1}$, $u_{1}\notin\mathcal{O}_{Q}$, and
$v_{1}\in\mathcal{O}_{P}$. Let
$\mathcal{O}^{\prime}_{P}:=(\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\})\setminus\\{v_{1}\\}$.
Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}^{\prime}_{P}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}^{\prime}_{P}})}-g^{\prime}_{Q,\mathcal{O}_{Q}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}})}$

is in standard form.

Case 4. $z^{*}$ is divisible by $y_{u_{2m+1}}$ and $y_{v_{2m^{\prime}+1}}$. If
$u_{2m+1}=v_{2m^{\prime}+1}$, then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})$
$\displaystyle=\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}x_{u_{1}}x_{u_{2m+1}}y_{v_{1}}}{z}-\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}y_{u_{1}}x_{u_{2m+1}}x_{v_{1}}}{z}$
$\displaystyle=g^{\prime}_{R,\mathcal{O}_{R}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{R,\mathcal{O}_{R}})},$

where $R$ is the path from $u_{1}$ to $v_{1}$ and
$\mathcal{O}_{R}=V(R)\cap(\mathcal{O}_{P}\cup\mathcal{O}_{Q})$. Next assume
that $u_{2m+1}\neq v_{2m^{\prime}+1}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}x_{u_{1}}y_{v_{1}}x_{v_{2m^{\prime}+1}}}{zy_{v_{2m^{\prime}+1}}}-\frac{z^{\prime}_{P,\mathcal{O}_{P}}z^{\prime}_{Q,\mathcal{O}_{Q}}y_{u_{1}}x_{u_{2m+1}}x_{v_{1}}}{zy_{u_{2m+1}}}.$

Clearly,

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g^{\prime}_{P,\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P,\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}})}-g^{\prime}_{Q,\mathcal{O}_{Q}\cup\\{u_{2m+1}\\}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{Q,\mathcal{O}_{Q}\cup\\{u_{2m+1}\\}})}$

is in standard form if $\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}$ is an odd
subset of $P$. Now assume that $\mathcal{O}_{P}\cup\\{v_{2m^{\prime}+1}\\}$ is
not an odd subset of $P$. Let $u_{\max}$ (resp. $v_{\max}$) be the last
element of $\\{u_{1}\\}\cup\mathcal{O}_{P}$ (resp.
$\\{v_{1}\\}\cup\mathcal{O}_{Q}$) that belongs to the path between $u_{1}$ and
$v_{2m^{\prime}+1}$ (resp. $v_{1}$ and $u_{2m+1}$). Also, let $P_{1}$ be the
path between $u_{\max}$ and $v_{2m^{\prime}+1}$, $P_{2}$ be the path between
$u_{1}$ and $u_{\max}$, $Q_{1}$ be the path between $v_{\max}$ and $u_{2m+1}$,
and $Q_{2}$ be the path between $v_{1}$ and $v_{\max}$. We have four cases to
consider:

  * •

Subcase 4.1. $u_{1}=u_{\max}$ and $v_{1}=v_{\max}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{Q_{1}})}$

is in standard form.

  * •

Subcase 4.2. $u_{1}=u_{\max}$ and $v_{1}\neq v_{\max}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{Q_{1}})}\pm
g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{u_{2m+1}}y_{v_{\max}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})})x_{u_{2m+1}}x_{v_{\max}}}$

is in standard form with sign being $+$ or $-$ according to $Q_{2}$ be in
direction of $Q$ or not.

  * •

Subcase 4.3. $u_{1}\neq u_{\max}$ and $v_{1}=v_{\max}$. Then

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g^{\prime}_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{\max}}y_{v_{2m^{\prime}+1}}}{\mathrm{in}(g_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})})x_{u_{\max}}x_{v_{2m^{\prime}+1}}}-g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{Q_{1}})}$

is in standard form if $x_{u_{1}}>x_{u_{\max}}$ and

$S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g^{\prime}_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})})}-g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})x_{u_{1}}y_{u_{\max}}}{\mathrm{in}(g_{Q_{1}})y_{u_{1}}x_{u_{\max}}}$

is in standard form if $x_{u_{1}}<x_{u_{\max}}$.

  * •

Subcase 4.4. $u_{1}\neq u_{\max}$ and $v_{1}\neq v_{\max}$. Then

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g^{\prime}_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})}\cdot\frac{\mathrm{in}(\mathcal{S})y_{u_{\max}}y_{v_{2m^{\prime}+1}}}{\mathrm{in}(g_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})})x_{u_{\max}}x_{v_{2m^{\prime}+1}}}$ $\displaystyle-
g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{Q_{1}})}\pm
g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})}\cdot\frac{\mathrm{ter}(\mathcal{S})y_{u_{2m+1}}y_{v_{\max}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})})x_{u_{2m+1}}x_{v_{\max}}}$

is in standard form if $x_{u_{1}}>x_{u_{\max}}$ and

$\displaystyle
S(g^{\prime}_{P,\mathcal{O}_{P}},g^{\prime}_{Q,\mathcal{O}_{Q}})=$
$\displaystyle
g_{P_{1}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{1}})}-g_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{P_{2},\mathcal{O}_{P}\cap
V(P_{2})})}-g_{Q_{1}}\cdot\frac{\mathrm{ter}(\mathcal{S})x_{u_{1}}y_{u_{\max}}}{\mathrm{in}(g_{Q_{1}})y_{u_{1}}x_{u_{\max}}}$
$\displaystyle\pm g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})}\cdot\frac{\mathrm{ter}(\mathcal{S})x_{u_{1}}y_{u_{\max}}y_{u_{2m+1}}y_{v_{\max}}}{\mathrm{in}(g^{\prime}_{Q_{2},\mathcal{O}_{Q}\cap
V(Q_{2})})y_{u_{1}}x_{u_{\max}}x_{u_{2m+1}}x_{v_{\max}}}$

is in standard form if $x_{u_{1}}<x_{u_{\max}}$ with sign being $+$ or $-$
according to $Q_{2}$ be in direction of $Q$ or not.

Finally, as an ideal with square-free initial ideal, $I$ is actually a radical
ideal (see also [6, Theorems 1.1–1.2]). The proof is complete. ∎

Let $T$ be a tree with $n$ vertices. A labeling $\ell\colon
V(T)\rightarrow[n]$ is called ascending if it has a pendant receiving the
label $n$ whose removal yields a tree with ascending labeling. One observes
that every tree has an ascending labeling. It is obvious from the definition
that every vertex of maximum label in a subgraph of a tree $T$ with ascending
labeling is either an isolated vertex or a pendant. As a result, every path
$P\colon v_{1},\ldots,v_{m}$ of $T$ is unimodal in the sense that

$\ell(v_{1})>\cdots>\ell(v_{k-1})>\ell(v_{k})<\ell(v_{k+1})<\cdots<\ell(v_{m})$

for some $k$. In what follows, we rename every vertex $v$ of $T$ with its
label $\ell(v)$ and assume without loss of generality that $v=\ell(v)$ for all
$v\in V(T)$.

######  Corollary 2.2.

Let $T$ be a tree with an ascending labeling. Then

$\mathcal{G}:=\\{g_{P}\colon\quad P\emph{ is a path of odd length in
}T\\}\cup\\{g^{\prime}_{P,\varnothing}\colon\quad P\emph{ is a path of even
length in }T\\}$

is a Gröbner basis for $L_{T}^{\mathbb{K}}(2)$ with respect to the
lexicographic ordering induced by $x_{1}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$.

###### Proof.

First observe that for any path in $T$ one of the end points has the maximum
label among the other vertices of the path. From the proof of Theorem 2.1 one
observes that $S(g_{P},g_{Q})$ and
$S(g_{P},g^{\prime}_{Q^{\prime},\varnothing})$ reduce to zero modulo
$\mathcal{G}$ for all paths $P$ and $Q$ not both of type (ii). Now, let
$P\colon u_{1},\ldots,u_{2m+1}$ and $Q\colon v_{1},\ldots,v_{2m^{\prime}+1}$
be paths of type (ii) with $\mathcal{O}_{P}=\mathcal{O}_{Q}=\varnothing$.
Following the proof of Theorem 2.1,
$S(g^{\prime}_{P,\varnothing},g^{\prime}_{Q,\varnothing})$ reduces to zero
modulo $\mathcal{G}$ except possibly for the following two cases, which we
consider independently:

(a)
$\gcd(\mathrm{in}(g^{\prime}_{P,\varnothing}),\mathrm{in}(g^{\prime}_{Q,\varnothing}))=zy_{v_{2m^{\prime}+1}}$
is coprime to $y_{u_{2m+1}}$ and $u_{1}\neq v_{1}$. As $v_{2m^{\prime}+1}$
lies on $P$, we have $v_{2m^{\prime}+1}<u_{2m+1}$. Let $P_{1}$ be the path
from $v_{2m^{\prime}+1}$ to $u_{2m+1}$ and $R_{1}$ be the path from $u_{1}$ to
$v_{1}$. Also, let $P_{2}$ be the path between $u_{1}$ and $v_{2m^{\prime}+1}$
and $R_{2}$ be the path between $v_{1}$ and $u_{2m+1}$. Then either
$|V(P_{1})|$ is odd and

$S(g^{\prime}_{P,\varnothing},g^{\prime}_{Q,\varnothing})=g^{\prime}_{P_{1},\varnothing}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g^{\prime}_{P_{1},\varnothing})}+g^{\prime}_{R_{1},\varnothing}\cdot\frac{\mathrm{in}(\mathcal{S})x_{u_{2m+1}}y_{v_{2m^{\prime}+1}}}{\mathrm{in}(g^{\prime}_{P_{1},\varnothing})y_{u_{2m+1}}x_{v_{2m^{\prime}+1}}}$

is in standard form, or $|V(P_{1})|$ is even and

$S(g^{\prime}_{P,\varnothing},g^{\prime}_{Q,\varnothing})=g_{P_{2}}\cdot\frac{\mathrm{in}(\mathcal{S})}{\mathrm{in}(g_{P_{2}})}+g_{R_{2}}\cdot\frac{\mathrm{ter}(\mathcal{S})}{\mathrm{in}(g_{R_{2}})}$

is in standard form.

(b)
$\gcd(\mathrm{in}(g^{\prime}_{P,\varnothing}),\mathrm{in}(g^{\prime}_{Q,\varnothing}))$
is divisible by both $y_{u_{2m+1}}$ and $y_{v_{2m^{\prime}+1}}$, where
$u_{2m+1}\neq v_{2m^{\prime}+1}$. Since $v_{2m^{\prime}+1}$ lies on $P$ and
$u_{2m+1}$ lies on $Q$, we obtain $v_{2m^{\prime}+1}<u_{2m+1}$ and
$u_{2m+1}<v_{2m^{\prime}+1}$, which is impossible. ∎

######  Example.

Utilizing Corollary 2.2, one observes that

  * (i)

if $S_{n}$ be the star graph of order $n$ with central vertex labeled with
$2$, then

$\mathcal{G}:=\\{x_{1}x_{i}+y_{1}y_{i}\colon 2\leq i\leq
n\\}\cup\\{x_{i}y_{1}y_{j}-x_{j}y_{1}y_{i}:2\leq i<j\leq n\\}$

is a reduced Gröbner basis for $L_{S_{n}}^{\mathbb{K}}(2)$, and

  * (ii)

if $P_{n}:1,\ldots,n$ be the path of order $n$, then

$\mathcal{G}:=\\{x_{i}x_{i+1}+y_{i}y_{i+1}:1\leq i\leq
n-1\\}\cup\\{x_{i}y_{i+1}y_{i+2}-y_{i}y_{i+1}x_{i+2}:1\leq i\leq n-2\\}$

is a reduced Gröbner basis for $L_{P_{n}}^{\mathbb{K}}(2)$.

##  3\. Krull dimension of LSS-ideals of trees

The aim of this section is to present a formula for the Hilbert series of LSS-
ideals of trees and the Krull dimension of the quotient ring. To this end, we
use the fact that $S/I$ and $S/\mathrm{in}_{\leq}(I)$ share the same Hilbert
series for all monomial orderings $\leq$ (see [7, Proposition 2.2.5]). In this
regard, Corollary 2.2 provides us with a simple description of
$\mathrm{in}_{\leq}(I)$. Since $\mathrm{in}_{\leq}(L_{T}^{\mathbb{K}}(2))$ is
a square-free monomial ideal, it is the Stanley-Reisner ideal of a simplicial
complex.

A collection $\Delta$ of subsets of a set $V=\\{v_{1},\ldots,v_{n}\\}$ is a
simplicial complex if

  * (a)

$\\{v_{i}\\}\in\Delta$ for all $i$;

  * (b)

if $F\in\Delta$, then all subsets of $F$ are also in $\Delta$ (including the
empty set).

The elements of $\Delta$ are called faces and the maximal faces under
inclusion are called facets of $\Delta$. A subset $F\subseteq[n]$ is called a
non-face of $\Delta$ if $F\notin\Delta$.

The dimension of a face $F$ is $\dim F=|F|-1$, where $|F|$ denotes the
cardinality of $F$ and the dimension of $\Delta$, $\dim(\Delta)$, is defined
as

$\dim(\Delta)=\max\\{\dim F\colon F\in\Delta\\}.$

Let $\Delta$ be a simplicial complex of dimension $d-1$ on the vertex set $V$
and $f_{i}=f_{i}(\Delta)$ denote the number of faces of $\Delta$ of dimension
$i$. Thus, in particular $f_{-1}=1$ and $f_{0}=n$. The sequence

$\textbf{f}(\Delta):=\left(f_{0},\ldots,f_{d-1}\right)$

is called the f-vector of $\Delta$.

To each simplicial complex $\Delta$ on the vertex set $V$ we associate a
square-free monomial ideal $I_{\Delta}\subset\mathbb{K}[x_{1},\ldots,x_{n}]$,
called the Stanley-Reisner ideal of $\Delta$, defined as follows:

$I_{\Delta}=(\prod_{i\in F}x_{i}\colon\,F\notin\Delta).$

Now, let $R:=\mathbb{K}[x_{1},\ldots,x_{n}]$ and
$J\subseteq(x_{1},\ldots,x_{n})^{2}$ be a square-free monomial ideal. Let
$\mathrm{Supp}(u):=\\{i\in[n]\colon x_{i}\mid u\\}$ for any monomial $u\in R$
and let $\Delta(J)$ be the set of all subsets $A$ of $[n]$ for which
$\mathrm{Supp}(u)\nsubseteq A$ for all $u\in\mathcal{G}(J)$. Then $\Delta(J)$
is a simplicial complex and $I_{\Delta(J)}=J$, hence

$\mathrm{Hilb}\left(\frac{R}{J},t\right)=\sum_{i=0}^{d}f_{i-1}\left(\frac{t}{1-t}\right)^{i},$
(1)

where $d=\dim\Delta(J)+1$ and $f_{i-1}=f_{i-1}(\Delta(J))$ for $i=0,\ldots,d$
(see [4, Theorem 5.1.7]). In order to compute $\mathrm{Hilb}(R/J,t)$, we note
from the exact sequence

$0\longrightarrow\frac{R}{J\colon u}(-d)\overset{\cdot
u}{\longrightarrow}\frac{R}{J}\longrightarrow\frac{R}{J+(u)}\longrightarrow 0$

that

$\mathrm{Hilb}\left(\frac{R}{J},t\right)=t^{d}\mathrm{Hilb}\left(\frac{R}{J\colon
u},t\right)+\mathrm{Hilb}\left(\frac{R}{J+(u)},t\right).$ (2)

For any monomial $u\in R$, define

$J\odot_{i}u:=\begin{cases}J\colon u,&i=0,\\\ J+(u),&i=1.\end{cases}$

Accordingly, for any $f\in\\{0,1\\}^{[n]}$ we set

$J_{f}:=J\odot_{f(1)}x_{1}\odot\cdots\odot_{f(n)}x_{n}$

and put $A_{f}:=f^{-1}(0)$ and $B_{f}:=f^{-1}(1)$. Clearly,

$J_{f}=\begin{cases}(x_{i}\colon i\in B_{f}),&A_{f}\in\Delta(J),\\\
(1),&\text{otherwise},\end{cases}$

that is $\Delta(J)=\\{A_{f}\subseteq[n]\colon J_{f}\neq(1)\\}$.

######  Notation.

In what follows, we use the following notation:

  * •

$S:=\mathbb{K}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$ is a polynomial ring.

  * •

For subsets $V\subseteq[n]$,

$(x_{V}):=(x_{i}\colon i\in V)\quad\text{and}\quad(y_{V}):=(y_{i}\colon i\in
V).$

  * •

Let $T$ be a tree on $[n]$ and $\ell\colon V(T)\rightarrow[n]$ be an ascending
labeling of $T$. Then we use the lexicographic ordering $\leq:=\leq_{\ell}$
induced by

$x_{\ell(1)}>\cdots>x_{\ell(n)}>y_{\ell(1)}>\cdots>y_{\ell(n)}$

without further reference. As in the previous section, we further assume that
$v=\ell(v)$ for all $v\in V(T)$, for convenience.

  * •

The set of all paths of a forest $F$ through a vertex $u$ as a middle vertex
is denoted by $\mathrm{Path}(F,u)$. For any path $P$ in $F$, let

$g_{P}^{*}:=\begin{cases}g_{P},&|P|\ \text{is even},\\\
g^{\prime}_{P,\varnothing},&|P|\ \text{is odd}.\\\ \end{cases}$

Also, we define $\mathrm{End}(P)$ to be the set of end vertices of $P$ and
$\mathrm{End}_{x}(P)$ to be the set of end vertices of $P$ labeled by $x$ in
$g_{P}^{*}$.

  * •

Let $J\subseteq S$ be a monomial. For any $f\in\\{0,1\\}^{[n]}$ and $k\in[n]$
we set

$J_{k,f}:=J\odot_{f(1)}x_{1}\odot\cdots\odot_{f(k)}x_{k}$

and put $A_{k,f}:=f^{-1}(0)\cap[k]$ and $B_{k,f}:=f^{-1}(1)\cap[k]$. Also, for
any $g\in\\{0,1\\}^{[n]}$ and $k\in[n]$ we set

$J^{k,g}:=J\odot_{g(n)}y_{n}\odot\cdots\odot_{g(k)}y_{k}$

and put $A^{\prime}_{k,g}:=g^{-1}(0)\cap[n-k]^{c}$ and
$B^{\prime}_{k,g}:=g^{-1}(1)\cap[n-k]^{c}$.

  * •

For any $f\in\\{0,1\\}^{[n]}$, let $\mathrm{Edge}_{f}(T)$ be the set of all
paths $u,v$ of length one such that $u\sim v\sim a$ for some $a\in A_{n,f}$
and $u,v>a$. Also, let $\mathrm{Path}^{\prime}_{f}(T)$ be the set of all paths
$P$ of $T$ satisfying the following conditions:

    * (1)

$\min(P)\in B_{n,f}$,

    * (2)

$\min(P)\cap\mathrm{End}(P)=\varnothing$,

    * (3)

$\mathrm{End}_{x}(P)\subseteq A_{n,f}$,

    * (4)

$V(P)\setminus\mathrm{End}_{2}(P)\subseteq B_{n,f}$,

where by $\min(P)$ we mean the vertex of $P$ with minimum label, and
$\mathrm{End}_{i}(P)$ ($i\geq 0$) denotes the set of vertices of $P$ at
distance at most $i$ from an end point of $P$. Put

$\mathrm{Path}^{*}_{f}(T):=\mathrm{Edge}_{f}(T)\cup\mathrm{Path}_{f}(T),$

where

$\mathrm{Path}_{f}(T):=\\{P-\mathrm{End}_{x}(P)\colon
P\in\mathrm{Path}^{\prime}_{f}(T)\\}$

in which $\mathrm{End}_{x}(P)$ is the set of all (end) vertices $v$ of $P$ for
which $x_{v}\mid\mathrm{in}_{\leq}(g^{*}_{P})$. Finally, for any
$V\subseteq[n]$, let $(y_{V})^{\vee}$ be the ideal of $S$ generated by the
product of $y_{v}$ for all $v\in V$.

For a given ascending labeling $\ell$ of $T$, let $\Delta(T,\ell)$ be the
simplicial complex on $[2n]$ for which
$I_{\Delta(T,\ell)}=\mathrm{in}_{\leq}(L_{T}^{\mathbb{K}}(2))$ as ideals of
$S$. Since $S$ has two sets of indeterminates, namely $x_{1},\ldots,x_{n}$ and
$y_{1},\ldots,y_{n}$ we may identify every element of $\Delta(T,\ell)$ as an
ordered pair $(A,A^{\prime})$, where $A,A^{\prime}\subseteq[n]$ correspond to
subsets of $\\{x_{1},\ldots,x_{n}\\}$ and $\\{y_{1},\ldots,y_{n}\\}$,
respectively. Accordingly,

$\Delta(T,\ell)=\\{(f^{-1}(0),g^{-1}(0))\colon f,g\in\\{0,1\\}^{[n]}\
\text{and}\ (I_{n,f})^{n,g}\neq(1)\\}.$

The following lemma helps us to describe $\Delta(T,\ell)$.

######  Lemma 3.1.

Let $T$ be a tree on $[n]$ with an ascending labeling $\ell$ and
$I=\mathrm{in}_{\leq}(L_{T}^{\mathbb{K}}(2))$. If $f,g\in\\{0,1\\}^{[n]}$,
then

$(I_{n,f})^{n,g}=(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+(y_{B^{\prime}_{n,g}})+\sum_{P\in\mathrm{Path}^{*}_{f}(T)}(y_{V(P)\setminus
A^{\prime}_{n,g}})^{\vee},$

where

$(x_{N_{T}(A_{k,f})})^{*}=\begin{cases}(x_{N_{T}(A_{n,f})}),&A_{n,f}\emph{ is
independent in }T,\\\ (1),&\emph{otherwise}.\end{cases}$

###### Proof.

First observe that if $J=\mathrm{in}_{\leq}(F)$ where $F$ is a subforest of
$T$ and $u$ is the vertex of $F$ of minimum label, then

$\displaystyle J\colon x_{u}$ $\displaystyle=\mathrm{in}_{\leq}(F\setminus
u)+(x_{N_{F}(u)})+\sum_{v\in N_{F}(u)}y_{v}(y_{N_{F}(v)\setminus
u})+\sum_{P\in\mathrm{Path}(F,u)}\mathrm{in}_{\leq}(g_{P}^{*})$ (3)
$\displaystyle=\mathrm{in}_{\leq}(F\setminus u)+(x_{N_{F}(u)})+\sum_{v\in
N_{F}(u)}y_{v}(y_{N_{F}(v)\setminus u}),$ (4) $\displaystyle J+(x_{u})$
$\displaystyle=\mathrm{in}_{\leq}(F\setminus
u)+(x_{u})+\sum_{P\in\mathrm{Path}(F,u)}\mathrm{in}_{\leq}(g_{P}^{*}).$ (5)

In order to obtain (4) from (3) we note that every summand
$\mathrm{in}_{\leq}(g_{P}^{*})$ is either a multiple of $x_{v}$ or a multiple
of $y_{v}y_{w}$ for some $v\in N_{F}(u)$ and $w\in N_{F}(u)\setminus\\{u\\}$.

If $f\in\\{0,1\\}^{[n]}$, then a simple inductive argument yields

$\displaystyle I_{k,f}=$ $\displaystyle
I\odot_{f(1)}x_{1}\odot\cdots\odot_{f(k)}x_{k}$ $\displaystyle=$
$\displaystyle\mathrm{in}_{\leq}(T\setminus[k])+(x_{B_{k,f}})+(x_{N_{T}(A_{k,f})})^{*}+\sum_{\begin{subarray}{c}u\sim
v\sim a\in A_{k,f}\\\ u,v>a\end{subarray}}(y_{u}y_{v})$
$\displaystyle+\sum_{\begin{subarray}{c}i\in B_{k,f}\\\
P\in\mathrm{Path}(T,i)\\\ \mathrm{End}_{x}(P)\cap
B_{k,f}=\varnothing\end{subarray}}\frac{\mathrm{in}_{\leq}(g_{P}^{*})}{\prod_{j\in\mathrm{End}_{x}(P)\cap
A_{k,f}}x_{j}},$

for all $k\in[n]$. In particular, for $k=n$, we get

$I_{n,f}=(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+\sum_{\begin{subarray}{c}u\sim
v\sim a\in A_{n,f}\\\
u,v>a\end{subarray}}(y_{u}y_{v})+\sum_{\begin{subarray}{c}i\in B_{n,f}\\\
P\in\mathrm{Path}(T,i)\\\ \mathrm{End}_{x}(P)\cap
B_{n,f}=\varnothing\end{subarray}}\frac{\mathrm{in}_{\leq}(g_{P}^{*})}{\prod_{j\in\mathrm{End}_{x}(P)\cap
A_{n,f}}x_{j}}.$

Let $P$ be a path in the second sum for which $\mathrm{in}_{\leq}(g^{*}_{P})$
is not divisible by $y_{u}y_{v}$ for some $uv\in\mathrm{Edge}_{f}(T)$. In the
following, we show that $P$ satisfies the conditions (1)–(4) of the definition
of $\mathrm{Path}^{\prime}_{f}(T)$. From the unimodality of paths in $T$ it
follows that $V(P)\setminus\mathrm{End}_{2}(P)\subseteq B_{n,f}$. We can
further assume that $\min(P)\in B_{n,f}$ and
$\min(P)\cap\mathrm{End}(P)=\varnothing$. If $A_{n,f}$ is not independent,
then $I_{n,f}=(x_{N_{T}(A_{n,f})})^{*}=(1)$ and our assumption is superfluous.
Suppose $A_{n,f}$ is an independent set in $T$ and $P$ is the path
$v_{1},\ldots,v_{m}$ with $v_{1}<v_{m}$ and $\min(P)=v_{k}\in A_{n,f}$. Notice
that $v_{1}\in A_{n,f}$. Then $k\leq 3$ and $m-k\leq 2$ otherwise
$\mathrm{in}_{\leq}(g^{*}_{P})$ is divisible by either
$y_{v_{k-2}}y_{v_{k-1}}$ when $k>3$ or $y_{v_{k+1}}y_{v_{k+2}}$ when $m-k>2$
so that $P\notin\mathrm{Path}^{\prime}_{f}(T)$. If $k=1$, then since
$\mathrm{in}_{\leq}(g^{*}_{P})$ is not divisible by $y_{v_{2}}y_{v_{3}}$ we
must have $m=2$. Then $v_{2}\in A_{n,f}$ for $\mathrm{End}_{x}(P)\cap
B_{n,f}=\varnothing$, which contradicts the fact that $A_{n,f}$ is
independent. As $v_{1}\in A_{n,f}$ and $A_{n,f}$ is independent, it follows
that $k=3$. If $m=5$, then $\mathrm{in}_{\leq}(g^{*}_{P})$ is divisible by
$y_{v_{4}}y_{v_{5}}$, a contradiction. Thus $m=4$ and
$\mathrm{in}_{\leq}(g^{*}_{P})=x_{v_{1}}y_{v_{2}}y_{v_{3}}x_{v_{4}}$ with
$v_{4}\in A_{n,f}$ contradicting the fact that $A_{n,f}$ is independent. It
turns out that

$I_{n,f}=(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+\sum_{uv\in\mathrm{Edge}_{f}(T)}(y_{u}y_{v})+\sum_{P\in\mathrm{Path}^{\prime}_{f}(T)}\frac{\mathrm{in}_{\leq}(g_{P}^{*})}{\prod_{j\in\mathrm{End}_{x}(P)\cap
A_{n,f}}x_{j}}.$

Recall that

$\mathrm{Path}_{f}(T):=\\{P-\mathrm{End}_{x}(P)\colon
P\in\mathrm{Path}^{\prime}_{f}(T)\\}$

and

$\mathrm{Path}^{*}_{f}(T):=\mathrm{Edge}_{f}(T)\cup\mathrm{Path}_{f}(T).$

Next, we observe that

$\begin{split}(I_{n,f})^{k,g}=&I_{n,f}\odot_{g(n)}y_{n}\odot\cdots\odot_{g(k)}y_{k}\\\
=&(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+(y_{B^{\prime}_{n+1-k,g}})+\sum_{P\in\mathrm{Path}^{*}_{f}(T)}(y_{V(P)\setminus
A^{\prime}_{n+1-k,g}})^{\vee}\end{split}$ (6)

for all $f,g\in\\{0,1\\}^{[n]}$ and $k\in[n]$. Recall that $(y_{V(P)\setminus
A^{\prime}_{n+1-k,g}})^{\vee}$ is the ideal of $S$ generated by products of
all $y_{v}$ for $v\in V(P)\setminus A^{\prime}_{n+1-k,g}$. Therefore,

$(I_{n,f})^{n,g}=(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+(y_{B^{\prime}_{n,g}})+\sum_{P\in\mathrm{Path}^{*}_{f}(T)}(y_{V(P)\setminus
A^{\prime}_{n,g}})^{\vee},$

as required. ∎

One observes from the statement of Lemma 3.1 that

  * (1)

$(x_{N_{T}(A_{n,f})})^{*}\neq(1)$ if and only if $A_{n,f}$ is an independent
set in $T$,

  * (2)

$(y_{V(P)\setminus A^{\prime}_{n+1-k,g}})^{\vee}=(1)$ for a path $P$ of
$\mathrm{Path}^{*}_{f}(T)$ if and only if $V(P)\subseteq A^{\prime}_{n,g}$.

It follows that $(I_{n,f})^{n,g}\neq(1)$ if and only if
$(x_{N_{T}(A_{n,f})})^{*}\neq(1)$ and $(y_{V(P)\setminus
A^{\prime}_{n+1-k,g}})^{\vee}\neq(1)$ for all $P\in\mathrm{Path}^{*}_{f}(T)$.
In this case, $N_{T}(A_{n,f})\subseteq B_{n,f}$, $\varnothing\neq
V(P)\setminus A^{\prime}_{n,g}\subseteq B^{\prime}_{n,g}$ for all
$P\in\mathrm{Path}^{*}_{f}(T)$, and consequently

$\displaystyle(I_{n,f})^{n,g}$
$\displaystyle=(x_{B_{n,f}})+(x_{N_{T}(A_{n,f})})^{*}+(y_{B^{\prime}_{n,g}})+\sum_{P\in\mathrm{Path}^{*}_{f}(T)}(y_{V(P)\setminus
A^{\prime}_{n,g}})^{\vee}$
$\displaystyle=(x_{B_{n,f}})+(y_{B^{\prime}_{n,g}}).$

Let $T$ be a tree on $[n]$ with a given ascending labeling $\ell$. In view of
the above equalities, we are interested in those $f,g$ for which
$(I_{n,f})^{n,g}\neq(1)$ in order to compute the Hilbert series of
$S/L_{T}^{\mathbb{K}}(2)$. The above arguments show that $\Delta(T,\ell)$ is
actually the set of all ordered pairs $(A,A^{\prime})$ of subsets of $[n]$
such that $A$ is independent in $T$ and $V(P)\nsubseteq A^{\prime}$ for all
$P\in\mathrm{Path}^{*}_{A}(T)$, where
$\mathrm{Path}^{*}_{A}(T):=\mathrm{Path}^{*}_{f}(T)$ for $f\in\\{0,1\\}^{[n]}$
with $f^{-1}(0)=A$.

According to (1), [7, Proposition 2.2.5], and [4, Theorem 5.1.4], we have the
following proposition:

######  Proposition 3.2.

Let $T$ be a tree on $[n]$ with an ascending labeling $\ell$. Then

$\mathrm{Hilb}\left(\frac{S}{L_{T}^{\mathbb{K}}(2)},t\right)=\sum_{(A,A^{\prime})\in\Delta(T,\ell)}\left(\frac{t}{1-t}\right)^{|A|+|A^{\prime}|}.$

In particular,

$\dim\left(\frac{S}{L_{T}^{\mathbb{K}}(2)}\right)=\dim\Delta(T,\ell)+1=\max\left\\{|A|+|A^{\prime}|\colon\
(A,A^{\prime})\in\Delta(T,\ell)\right\\}.$

######  Corollary 3.3.

If $T$ is a tree on $[n]$, then

$n+1\leq\dim\left(\frac{S}{L_{T}^{\mathbb{K}}(2)}\right)\leq p(T)+n-1,$

where $p(T)$ denotes the number of pendants of $T$.

###### Proof.

Let $P(T^{\prime})$ stand for the set of all pendants of a tree $T^{\prime}$
and put $p(T^{\prime}):=|P(T^{\prime})|$. Suppose without loss of generality
that $n\geq 3$. If $A=\\{n\\}$ and $A^{\prime}=[n]$, then
$(A,A^{\prime})\in\Delta(T,\ell)$ for any ascending labeling $\ell$ of $T$.
Thus $\dim(S/L_{T}^{\mathbb{K}}(2))\geq n+1$ by Proposition 3.2. To prove the
upper bound, let $A$ be an independent set in $T$, and let $v\in P(T)$. We may
view $T$ as a rooted tree with root $v$ and take a labeling $\ell\colon
V(T)\rightarrow[n]$ of $T$ with $\ell(u)<\ell(u^{\prime})$ whenever
$d(u,v)<d(u^{\prime},v)$. Clearly, $\ell$ is an ascending labeling of $T$. Let
$(A,A^{\prime})\in\Delta(T,\ell)$. Let $a\neq v$ be an element of $A$ that is
neither a pendant of $T$ nor a pendant of $T\setminus(P(T)\setminus\\{v\\})$
that is $a\in
A\setminus(P(T)\setminus\\{v\\})\cup(P(T\setminus(P(T)\setminus\\{v\\}))\setminus\\{v\\})$.
Let $f\in\\{0,1\\}^{[n]}$ be such that $f^{-1}(0)=A$. From the definition of
$\Delta(T,\ell)$, it follows that either $s\notin A^{\prime}$ or $t\notin
A^{\prime}$ for any children $s$ of $a$ and children $t$ of $s$, otherwise the
path $s,t$ of $\mathrm{Edge}_{f}(T)\subseteq\mathrm{Path}^{*}_{f}(T)$ is
contained in $T[A^{\prime}]$, contradicting the fact that
$(A,A^{\prime})\in\Delta(T,\ell)$. Thus

$|A^{\prime}|\leq
n-|A\setminus((P(T)\setminus\\{v\\})\cup(P(T\setminus(P(T)\setminus\\{v\\}))\setminus\\{v\\}))|,$

which implies that

$|A|+|A^{\prime}|\leq
n+|A\cap((P(T)\setminus\\{v\\})\cup(P(T\setminus(P(T)\setminus\\{v\\}))\setminus\\{v\\}))|.$

Since $A$ does not contain an element $u$ of
$P(T\setminus(P(T)\setminus\\{v\\}))\setminus\\{v\\}$ and any of its children
$u^{\prime}$ in $P(T)\setminus\\{v\\}$ simultaneously, it follows that

$|A\cap((P(T)\setminus\\{v\\})\cup(P(T\setminus(P(T)\setminus\\{v\\}))\setminus\\{v\\}))|\leq|A\cap(P(T)\setminus\\{v\\})|\leq|P(T)\setminus\\{v\\}|=p(T)-1.$

Therefore, $|A|+|A^{\prime}|\leq p(T)+n-1$. ∎

######  Remark 1.

Let $R$ be a standard graded $\mathbb{K}$-algebra and $I$ be a graded ideal of
$R$. If $u_{1},\ldots,u_{k}$ are homogeneous elements of $R$ such that the
sequence $u_{1}+I,\ldots,u_{k}+I$ forms an ${R}/{I}$-regular sequence, then
the Hilbert series of $\frac{{R}}{(I,u_{1},\ldots,u_{k})}$ is of the form

$H_{\frac{{R}}{(I,u_{1},\ldots,u_{k})}}(t)=\prod_{i=1}^{k}\left(1-t^{\deg(u_{i})}\right)\cdot
H_{\frac{{R}}{I}}(t).$

######  Remark 2.

Let $T$ be a tree on $[n]$ with an ascending labeling $\ell$. Let
$d:=\dim\Delta(T,\ell)$ and

$\Delta_{i}(T,\ell):=\\{(A,A^{\prime})\in\Delta(T,\ell)\colon|A|+|A^{\prime}|=i\\},$

for all $0\leq i\leq d$. Then

$\mathrm{Hilb}\left(\frac{S}{L_{T}^{\mathbb{K}}(2)},t\right)=\frac{1}{(1-t)^{d}}\sum_{i=0}^{d}|\Delta_{i}(T,\ell)|t^{i}(1-t)^{d-i}.$

In particular, $|\Delta_{i}(T,\ell)|$ is independent of the choice of the
labeling $\ell$, for all $i=0,\ldots,d$.

######  Example.

In this example, we compute $\Delta_{i}(T,\ell)$ when $T$ is a path or a star
graph.

  * (1)

If $T=P_{n}$ is a path with $n$ vertices, then $S/L_{T}^{\mathbb{K}}(2)$ is a
complete intersection by [5, Theorem 1.5(2)]. As
$\dim(S/L_{T}^{\mathbb{K}}(2))=n+1$ (see Corollary 3.3), it follows that
$L_{T}^{\mathbb{K}}(2)$ is generated by a homogeneous regular sequence
$f_{1},\ldots,f_{n-1}$ of degree $2$. Thus in view of Remark 1, we have

$\displaystyle\mathrm{Hilb}\left(\frac{S}{L_{T}^{\mathbb{K}}(2)},t\right)$
$\displaystyle=(1-t^{2})^{n-1}\mathrm{Hilb}\left(S,t\right)=\frac{(1+t)^{n-1}}{(1-t)^{n+1}}$
$\displaystyle=\frac{1}{(1-t)^{n+1}}\sum_{i=0}^{n-1}\binom{n-1}{i}t^{i}.$

On the other hand,

$\mathrm{Hilb}\left(\frac{S}{L_{T}^{\mathbb{K}}(2)},t\right)=\frac{1}{(1-t)^{n+1}}\sum_{i\geq
0}|\Delta_{i}(T,\ell)|t^{i}(1-t)^{n+1-i},$

for a given ascending labeling $\ell$ of $T$ from which it follows that

$|\Delta_{i}(T,\ell)|=\sum_{k=0}^{i}\binom{n+1-k}{i-k}\binom{n-1}{k}.$

for all $i$ with $0\leq i\leq n+1$.

  * (2)

Suppose $T=S_{n}$ is the star graph with $n$ vertices and let $\ell$ be an
ascending labeling of $T$ that assigns $1$ to the central vertex. Then
$(A,A^{\prime})\in\Delta_{i}(T,\ell)$ if and only if one of the following
cases holds:

    * (a)

$A=\varnothing$ and $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=i$,

    * (b)

$A=\\{1\\}$ and $A^{\prime}\subseteq[n]$ with $|A|=i-1$,

    * (c)

$1\notin A\neq\varnothing$ and either

      * (c1)

$A^{\prime}\subseteq[n]\setminus\\{1\\}$ with $|A^{\prime}|=i-|A|$, or

      * (c2)

$1\in A^{\prime}$ and $A^{\prime}\subseteq[\min(A)]$ with
$|A^{\prime}|=i-|A|$,

The number of $(A,A^{\prime})$ in cases (a) and (b) are simply $\binom{n}{i}$
and $\binom{n}{i-1}$. Also, this number for case (c.c1) is equal to
$\sum_{k=1}^{i}\binom{n-1}{k}\binom{n-1}{i-k}$, where $\binom{n-1}{k}$ and
$\binom{n-1}{i-k}$ are the number of subsets $A$ and $A^{\prime}$ of
$[n]\setminus\\{1\\}$ of size $k$ and $i-k$, respectively. To count the number
of $(A,A^{\prime})$ in case (c.c2), notice that either $A\cap
A^{\prime}=\varnothing$ and $A\cup A^{\prime}=\\{1=t_{1}<\cdots<t_{i}\\}$ is a
subset of $[n]$ including $1$ where $A^{\prime}=\\{t_{1},\ldots,t_{k}\\}$ and
$A=\\{t_{k+1},\ldots,t_{i}\\}$ for $1\leq k<i$, or $|A\cap A^{\prime}|=1$ and
$A\cup A^{\prime}=\\{1=t_{1}<\cdots<t_{i-1}\\}$ is a subset of $[n]$ including
$1$ where $A^{\prime}=\\{t_{1},\ldots,t_{k}\\}$ and
$A=\\{t_{k},\ldots,t_{i-1}\\}$ for $1<k<i$. In the former case, we have
$(i-1)\binom{n-1}{i-1}$ pairs $(A,A^{\prime})$, and in the later case, we have
$(i-2)\binom{n-2}{i-2}$ pairs $(A,A^{\prime})$. Thus

$\displaystyle|\Delta_{i}(T,\ell)|=$
$\displaystyle\binom{n}{i}+\binom{n}{i-1}+\sum_{k=1}^{i}\binom{n-1}{k}\binom{n-1}{i-k}$
$\displaystyle+\left[(i-1)\binom{n-1}{i-1}+(i-2)\binom{n-1}{i-2}\right]$
$\displaystyle=$
$\displaystyle\binom{n}{i}+\binom{n}{i-1}+\binom{2n-2}{i}-\binom{n-1}{i}+(n-1)\binom{n-1}{i-2}$
$\displaystyle=$
$\displaystyle\binom{2n-2}{i}+(n-1)\binom{n-1}{i-2}+\binom{n}{i-1}+\binom{n-1}{i-1}$

as

$\sum_{k=0}^{i}\binom{m}{k}\binom{m}{i-k}=\binom{2m}{i}$

for all $0\leq i\leq m$.

In [6], Herzog, Macchia, Saeedi Madani, and Welker present a primary
decomposition for $L_{G}^{\mathbb{K}}(2)$ when $\sqrt{-1}\notin\mathbb{K}$ and
apply it to give a formula for the dimension of $S/L_{G}^{\mathbb{K}}(2)$ in
this case. Indeed, they show that if $\Gamma$ is a graph on $[n]$,
$I=L_{\Gamma}^{\mathbb{K}}(2)$, and $\sqrt{-1}\notin\mathbb{K}$, then

$\dim\left(\frac{S}{I}\right)=\max\left\\{|V|+b(\Gamma[V])\colon\
V\subseteq[n]\right\\},$

where $b(\Gamma)$ denotes the number of bipartite connected components of a
graph $\Gamma$. It follows that, if $T$ is a tree, $I=L_{T}^{\mathbb{K}}(2)$,
and $\sqrt{-1}\notin\mathbb{K}$, then

$\dim\left(\frac{S}{I}\right)=\max\left\\{|V|+c(T[V])\colon\
V\subseteq[n]\right\\},$ (7)

where $c(\Gamma)$ denotes the number of connected components of a graph
$\Gamma$. According to Proposition 3.2, the Hilbert series of $S/I$ is
independent of the underlying field $\mathbb{K}$. Thus the formula (7) for the
dimension of $S/I$ is valid for any field $\mathbb{K}$. In Corollary 3.4
below, we give an explicit formula for the dimension of the ring $S/I$.

We say that a path $P$ in a tree $T$ is pendant if it contains a pendant
vertex and that all of its vertices have at most two neighbors in $T$. For a
tree $T$, we put
$\mathscr{P}_{0}^{*}(T)=\mathscr{P}_{0}(T)=\mathscr{Q}_{0}(T)=\varnothing$,
and define $\mathscr{P}_{i}^{*}(T),\mathscr{P}_{i}(T),\mathscr{Q}_{i}(T)$
inductively as follows for all $i\geq 1$: if
$T_{i}:=T-\cup_{j=0}^{i-1}(\mathscr{P}_{j}(T)\cup\mathscr{Q}_{j}(T))$ and
$\mathscr{P}_{i}^{*}(T)$ is the set of all maximal pendant paths of $T_{i}$,
then $\mathscr{P}_{i}(T):=V(\cup\mathscr{P}_{i}^{*}(T))$ and
$\mathscr{Q}_{i}(T):=N_{T_{i}}(\mathscr{P}_{i}(T))\setminus\mathscr{P}_{i}(T)$.
Also, we put $\mathscr{P}^{*}(T):=\cup_{i}\mathscr{P}_{i}^{*}(T)$,
$\mathscr{P}(T):=\cup_{i}\mathscr{P}_{i}(T)$, and
$\mathscr{Q}(T):=\cup_{i}\mathscr{Q}_{i}(T)$.

######  Example.

Let $T$ be the tree in Fig. 1. Then $\mathscr{P}_{1}(T)$,
$\mathscr{P}_{2}(T)$, $\mathscr{Q}_{1}(T)$, and $\mathscr{Q}_{2}(T)$ are the
sets of all black square vertices, black circle vertices, white square
vertices, and white circle vertices, respectively. Also, $\mathscr{P}^{*}(T)$
is the set of all black-vertex paths.

Figure 1.

######  Proposition 3.4.

If $T$ is a tree on $[n]$ and $I=L_{T}^{\mathbb{K}}(2)$, then

$\dim\left(\frac{S}{I}\right)=|\mathscr{P}(T)|+|\mathscr{P}^{*}(T)|.$

###### Proof.

Let $d(V):=|V|+c(T[V])$ for any subset $V$ of $[n]$. We show that

$d(\mathscr{P}(T)\cup Q)=d(\mathscr{P}(T))+2|Q|-\sum_{q\in
Q}\deg_{T[\mathscr{P}]}(q)-|E(T[Q])|$ (8)

for every subset $Q$ of $\mathscr{Q}(T)$. Clearly, the equality (8) holds for
$Q=\varnothing$. Suppose we have proved the equality (8) for some subset $Q$
of $\mathscr{Q}(T)$ and $q\in\mathscr{Q}(T)\setminus Q$. Assume
$q\in\mathscr{Q}_{i}(T)$. Then

$\displaystyle d(\mathscr{P}(T)\cup Q\cup\\{q\\})$
$\displaystyle=d(\mathscr{P}(T)\cup Q)+1-(\deg_{T[\mathscr{P}(T)]}(q)-1)$
$\displaystyle=d(\mathscr{P}(T))+2|Q\cup\\{q\\}|-\sum_{q^{\prime}\in
Q\cup\\{q\\}}\deg_{T[\mathscr{P}]}(q^{\prime})-|E(T[Q\cup\\{q\\}])|$

for all vertices in $\mathscr{P}(T)\cup Q$ which are adjacent to $q$ in $T$
belong to distinct connected components of $T[\mathscr{P}(T)\cup Q]$ and that
these components turn into a single connected component when $q$ is added to
$\mathscr{P}(T)\cup Q$. It follows that the equality (8) holds for
$Q\cup\\{q\\}$ as well. Next, we show that

$d((\mathscr{P}(T)\setminus P)\cup Q)=d(\mathscr{P}(T)\cup
Q)-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+\sum_{p\in P}\deg_{T[Q]}(p)$ (9)

for all subsets $P$ of $\mathscr{P}(T)$ and $Q$ of $\mathscr{Q}(T)$. Let $Q$
be a fixed subset of $\mathscr{Q}(T)$. Clearly, the equality (9) holds for
$P=\varnothing$. Assume the equality (9) is true for a subset $P$ of
$\mathscr{P}(T)$ and that $p\in\mathscr{P}(T)\setminus P$. We further assume
that $p\in\mathcal{P}$ for some $\mathcal{P}\in\mathscr{P}_{i}^{*}(T)$. We
have the following cases to consider:

  * (i)

$p\not\in\mathrm{End}(\mathcal{P})$. Then either $N_{\mathcal{P}}(p)\cap
P=\varnothing$ for which

$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-2+\deg_{T[\mathscr{P}(T)\cup Q]}(p)$

or $N_{\mathcal{P}}(p)\cap P\neq\varnothing$ so that

$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)-1$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-2+\deg_{T[\mathscr{P}(T)\cup Q]}(p).$

  * (ii)

$p$ is adjacent to some vertices of $\mathscr{Q}_{i-1}(T)$, say
$q_{1},\ldots,q_{k}$. As $q_{1},\ldots,q_{k}$ belong to distinct connected
components of $T[(\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q]$, it follows
that

$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-1+k-\deg_{T[P\cup\\{p\\}]}(p)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-2+\deg_{T[\mathscr{P}(T)\cup Q]}(p).$

  * (iii)

$p$ is adjacent to a vertex of $\mathscr{Q}_{i}(T)$ that is unique by our
construction of $\mathscr{P}_{i}(T)$. Then

$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-1+\deg_{T[P\cup\\{p\\}]}(p)$
$\displaystyle=d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-2+\deg_{T[\mathscr{P}(T)\cup Q]}(p).$

The above arguments yield

$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup Q)=$
$\displaystyle d((\mathscr{P}(T)\setminus(P\cup\\{p\\}))\cup
Q)-2+\deg_{T[\mathscr{P}(T)\cup Q]}(p)$ $\displaystyle=$ $\displaystyle
d(\mathscr{P}(T)\cup Q)-2|P\cup\\{p\\}|+|N_{T[\mathscr{P}(T)]}(P\cup\\{p\\})|$
$\displaystyle+\sum_{p^{\prime}\in P\cup\\{p\\}}\deg_{T[Q]}(p^{\prime})$

that is the equality (9) holds for $P\cup\\{p\\}$ as well.

Now, from the equalities (8) and (9) for arbitrary subsets $P$ of
$\mathscr{P}(T)$ and $Q$ of $\mathscr{Q}(T)$, we get

$\displaystyle d((\mathscr{P}(T)\setminus P)\cup Q)=$ $\displaystyle
d(\mathscr{P}(T)\cup Q)-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+\sum_{p\in
P}\deg_{T[Q\cup\\{p\\}]}(p)$ $\displaystyle=$ $\displaystyle
d(\mathscr{P}(T))-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+2|Q|+\sum_{p\in
P}\deg_{T[Q\cup\\{p\\}]}(p)$ $\displaystyle-\sum_{q\in
Q}\deg_{T[\mathscr{P}(T)\cup\\{q\\}]}(q)-|E(T[Q])|$ $\displaystyle=$
$\displaystyle
d(\mathscr{P}(T))-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+2|Q|+\sum_{p\in
P}\deg_{T[Q\cup\\{p\\}]}(p)$ $\displaystyle-\sum_{q\in
Q}\deg_{T[P\cup\\{q\\}]}(q)-\sum_{q\in Q}\deg_{T[(\mathscr{P}(T)\setminus
P)\cup\\{q\\}]}(q)-|E(T[Q])|$ $\displaystyle=$ $\displaystyle
d(\mathscr{P}(T))-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+2|Q|$
$\displaystyle-\sum_{q\in Q}\deg_{T[(\mathscr{P}(T)\setminus
P)\cup\\{q\\}]}(q)-|E(T[Q])|$ $\displaystyle\leq$ $\displaystyle
d(\mathscr{P}(T))-2|P|+|N_{T[\mathscr{P}(T)]}(P)|+2|Q|-\sum_{q\in
Q}\deg_{T[(\mathscr{P}(T)\setminus P)\cup\\{q\\}]}(q).$

Let $P_{1}$ be the set of all vertices in $P$ that are not end-points of some
paths in $\mathscr{P}^{*}(T)$, and $P_{2}:=P\setminus P_{1}$. One observes
that,

$\displaystyle-2|P|+|N_{T[\mathscr{P}(T)]}(P)|$
$\displaystyle\leq(-2|P_{1}|+|N_{T[\mathscr{P}(T)]}(P_{1})|)+(-2|P_{2}|+|N_{T[\mathscr{P}(T)]}(P_{2})|)$
$\displaystyle\leq-2|P_{2}|+|N_{T[\mathscr{P}(T)]}(P_{2})|$
$\displaystyle\leq-|P_{2}|.$

Also, let $Q_{1}$ be the set of vertices in $Q$ adjacent to at least two
vertices in $\mathscr{P}(T)\setminus P$, and put $Q_{2}:=Q\setminus Q_{1}$.
Then

$\displaystyle 2|Q|-\sum_{q\in Q}\deg_{T[(\mathscr{P}(T)\setminus
P)\cup\\{q\\}]}(q)=$ $\displaystyle(2|Q_{1}|-\sum_{q_{1}\in
Q_{1}}\deg_{T[(\mathscr{P}(T)\setminus P)\cup\\{q_{1}\\}]}(q_{1}))$
$\displaystyle+(2|Q_{2}|-\sum_{q_{2}\in Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus
P)\cup\\{q_{2}\\}]}(q_{2}))$ $\displaystyle\leq$ $\displaystyle
2|Q_{2}|-\sum_{q_{2}\in Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus
P)\cup\\{q_{2}\\}]}(q_{2})$ $\displaystyle=$ $\displaystyle
2|Q_{2}|-\sum_{q_{2}\in Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus
P_{2})\cup\\{q_{2}\\}]}(q_{2}).$

Thus

$d((\mathscr{P}(T)\setminus P)\cup Q)\leq
d(\mathscr{P}(T))-|P_{2}|+2|Q_{2}|-\sum_{q_{2}\in
Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus P_{2})\cup\\{q_{2}\\}]}(q_{2}).$

From the construction of $\mathscr{P}(T)$ and $\mathscr{Q}(T)$, we know that

$\deg_{T[\mathscr{P}_{i}(T)\cup\mathscr{P}_{i+1}(T)\cup\\{q\\}]}(q)\geq 3$
(10)

for all $q\in\mathscr{Q}_{i}(T)$. Let $m$ be the smallest positive integer for
which $\mathscr{P}_{m+1}(T)=\varnothing$. Also, let $F$ be the subgraph of $T$
induced by edges between $P_{2}$ and $Q_{2}$. Since $F^{\prime}$ is a forest,
we observes that

$\displaystyle|P_{2}|+|Q_{2}|=|V(F^{\prime})|$
$\displaystyle=|E(F^{\prime})|+c(F^{\prime})$ $\displaystyle=\sum_{q_{2}\in
Q_{2}}\deg_{F^{\prime}}(q_{2})+c(F^{\prime})$ $\displaystyle\geq\sum_{q_{2}\in
Q_{2}}\deg_{T[P_{2}\cup\\{q_{2}\\}]}(q_{2}).$

Then

$\displaystyle d((\mathscr{P}(T)\setminus P)\cup Q)\leq$ $\displaystyle
d(\mathscr{P}(T))-|P_{2}|+2|Q_{2}|-\sum_{q_{2}\in
Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus P_{2})\cup\\{q_{2}\\}]}(q_{2})$
$\displaystyle\leq$ $\displaystyle d(\mathscr{P}(T))+3|Q_{2}|-\sum_{q_{2}\in
Q_{2}}\deg_{T[P_{2}\cup\\{q_{2}\\}]}(q_{2})$ $\displaystyle-\sum_{q_{2}\in
Q_{2}}\deg_{T[(\mathscr{P}(T)\setminus P_{2})\cup\\{q_{2}\\}]}(q_{2})$
$\displaystyle\leq$ $\displaystyle d(\mathscr{P}(T))+3|Q_{2}|-\sum_{q_{2}\in
Q_{2}}\deg_{T[\mathscr{P}(T)\cup\\{q_{2}\\}]}(q_{2})$ $\displaystyle\leq$
$\displaystyle d(\mathscr{P}(T))$

for $\deg_{T[\mathscr{P}(T)\cup\\{q_{2}\\}]}(q_{2})\geq 3$ for all $q_{2}\in
Q_{2}$ (see (10)). Therefore,

$\dim(S/I)=\max\\{d((\mathscr{P}(T)\setminus P)\cup Q)\colon\
P\subseteq\mathscr{P}(T),\ Q\subseteq\mathscr{Q}(T)\\}=d(\mathscr{P}(T)),$

as required. ∎

######  Remark 3.

Let $T$ be a tree with an ascending labeling $\ell$. Let $A_{i}(T)$ be the set
of all pendants of paths in $\mathscr{P}_{i}^{*}(T)$ with maximum labels, and
$A^{\prime}_{i}=\mathscr{P}_{i}(T)$, for all $i\geq 1$. If $A=\cup A_{i}$ and
$A^{\prime}=\cup A^{\prime}_{i}$, then $(A,A^{\prime})\in\Delta(T,\ell)$ and
$|A|+|A^{\prime}|=|\mathscr{P}(T)|+|\mathscr{P}^{*}(T)|$. Thus

$\dim(S/I)=|A|+|A^{\prime}|.$

######  Example.

  * (1)

If $I=L_{P_{n}}^{\mathbb{K}}(2)$, then $\dim(S/I)=n+1$ for
$\mathscr{P}(P_{n})=V(P_{n})$ and $\mathscr{P}^{*}(P_{n})=\\{P_{n}\\}$.

  * (2)

If $I=L_{S_{n}}^{\mathbb{K}}(2)$, then $\dim(S/I)=2n-2$ for
$\mathscr{P}(S_{n})=[n-1]$ and $\mathscr{P}^{*}(S_{n})$ is the set of all
pendants of $S_{n}$ as induced subgraphs of $S_{n}$ if $n$ is the central
vertex of $S_{n}$.

  * (3)

If $I=L_{T}^{\mathbb{K}}(2)$ with $T$ being the tree in Fig. 1 with $n$
vertices, then $\dim(S/I)=n+10$ for $|\mathscr{P}(T)|=n-10$ and
$|\mathscr{P}^{*}(T)|=20$.

## References

  * [1] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, Vol. 3, American Mathematical Society, 289 p., 1994.
  * [2] A. Aramova, J. Herzog, and T. Hibi, Gotzman theorems for exterior algebras and combinatorics, J. Algebra 191 (1997), 174–211.
  * [3] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976.
  * [4] W. Bruns and J. Herzog, Cohen-Macaulay Rings, Revised Edition, Cambridge University Press, Cambridge, 1996.
  * [5] A. Conca and V. Welker, Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties, Algebra & Number Theory 13(2) (2019), 455–484.
  * [6] J. Herzog, A. Macchia, S. Saeedi Madani, and V. Welker, On the ideal of orthogonal representations of a graph in $\mathbb{R}^{2}$, Adv. Appl. Math. 71 (2015), 146–173.
  * [7] J. Herzog, T. Hibi, Monomial Ideals, in: GTM 260, Springer, London, 2011.
  * [8] A. Kumar, Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs, Eur. J. Comb. 93 (2021), 103274.
  * [9] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1–7.
  * [10] L. Lovász, Geometric representations of graphs, preprint, 2009.
  * [11] L. Lovász, M. Saks, and A. Schrijver, Orthogonal representations and connectivity of graphs, Linear Algebra Appl. 114/115 (1989), 439–454.
  * [12] L. Lovász, M. Saks, and A. Schrijver, A correction: Orthogonal representations and connectivity of graphs, Linear Algebra Appl. 313 (2000), 101–105.