# Recent results on homological properties of binomial edge ideal of graphs

Priya Das  Vellore Institute of Technology, Vellore, Tamilnadu-632014, India
<EMAIL_ADDRESS>
###### Abstract.

In this article, we give a comprehensive survey of the recent progress of
research on the binomial edge ideal of a graph since 2018.

###### Key words and phrases:

Binomial edge ideal, regularity, Betti number, syzygy, free resolution, depth

AMS Classification 2010. Primary: 13D02, 05E40, 16E05, 13D05, 16E65, 13F65

##  1\. Introduction

Let $G$ be a finite simple graph on $n$ vertices with set of edges, $E(G)$
with no isolated vertices. Let
$S=K[x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n}]$ be the polynomial
ring over a field $\mathbb{K}$ and $f_{ij}=x_{i}y_{j}-x_{j}y_{i},\\{i,j\\}\in
E(G)$, the ideal $J_{G}$ in $S$ generated by $f_{ij},1\leq i<j\leq n$ is
called the binomial edge ideal (BEI) of $G$. It was introduced by Herzog-Hibi-
Kahle-Rauh in the contest of study of conditional independence ideals [19] and
independently by [51]. It can be also seen as a special case of the
generalized binomial edge ideal as defined by [54], the collection of 2-minors
of the generic $(2\times n)$-matrix.

In [60], Madani has given an overview of Gröbner bases, primary decomposition,
and minimal graded free resolution of binomial edge ideal. The survey by
Madani loc. cit. is a comprehensive survey of all the works till the year of
its publication (2018), related to the binomial edge ideal in the context of
homological studies. In this article, we will provide a survey of all the
works mainly those that are related to the regularity of the binomial edge
ideal, depth, Betti number, generalised binomial edge ideal, and parity
binomial edge ideal, since [60].

Gröbner bases of binomial edge ideal are studied in [19], [51], the authors of
loc. cit. proved that the generators of the binomial edge ideal form a Gröbner
basis for closed graphs. In [15], the authors proved that $S/J_{G}$ is Koszul
when $G$ is a closed graph. The primary decomposition of the binomial edge
ideal is studied in [19], using the primary decomposition the authors have
described the minimal prime ideals of $J_{G}$.

The study of the minimal free resolution of binomial edge ideals is one of the
important topics in combinatorial commutative algebra. as the binomial ideals
are geometrically and algebraically an important class. Also since the work of
[4] has a very thorough discussion for the monomial ideals, it makes sense to
look for a combinatorial understanding of the situation in the binomial
ideals. Among the binomial ideals, binomial edge ideals of a graph is a major
stream of work currently. Also a number of works have been done in the
binomial toric ideals associated to distributive lattices, namely the Hibi
ideal [12]. The authors in [10] have given the generators of the first syzygy
of the Hibi ideal of a planar lattice in terms of four types of sublattices.
In [61], the authors proved that BEI of a graph has a linear resolution if $G$
is a complete graph and vice versa. The question of a pure resolution of a BEI
is discussed in [35].

One of the most important invariants of an ideal is the Castelnuovo-Mumford
regularity. It is proved in [49], for any graph $G$, $l\leq reg(S/J_{G})\leq
n-1$, where $n$ is the number of vertices of $G$ and $l$ is the length of the
largest induced path in $G$. Also, in [37], authors proved that
reg$(S/J_{G})=n-1$ if and only if $G$ is a path. Madani-Kiani in [62] has
given the following conjecture

######  Conjecture 1.1.

Let $G$ be a simple graph and $c(G)$ the number of maximal cliques of $G$.
Then

reg $(S/J_{G})\leq c(G)$.

Madani and Kiani proved the above conjecture for closed graphs and generalized
block graphs in [61], and [34]. The conjecture in general remains as one of
the important open problem in this area. For a block graph, $c(G)$ coincides
with the number of blocks in $G$. Trees being a subclass of the class of block
graphs and combining it with above result we have that, for a tree $T$, which
has $n$ vertices $c(T)=n-1$. In [30], authors have shown that
reg$(S/J_{G})\leq n-1$, thus proved the conjecture for some classes of trees.
Also, this conjecture is proved for the class of chordal graphs and for fan
graphs of complete graphs in [28]. Independently, the authors in loc. cit.
prove this conjecture for chordal graphs in [59]. Recently, this conjecture
has been proved for $P_{4}$-free graphs in [32]. For the classes of block
graphs and semi block graph the conjecture has been settled in [40]. Recently,
in [58], authors proved the Conjecture 1.1 for all graphs and has given a
sharp bound of it. The authors proved that reg$(S/J_{G})\leq\eta{(G)}$ (for
definition of $\eta{(G)}$, see 3.24).

In the article [14], the authors conjectured that the regularity of the
binomial edge ideal of a graph coincides with the regularity of its initial
ideal. If the conjecture holds for two graphs $G_{1},G_{2}$ then it also holds
for the join of two graphs, in Theorem 2.1 in [63]. The above result was used
by the authors to completely characterize the BEI of regularity 3, (Theorem
3.2 [63]). Threshold graphs which are also known as
$(2K_{2},C_{4},P_{4})$-free graphs are the graphs which have regularity 3. For
more details about threshold graph, see [45]. Whereas authors have
characterized the binomial edge ideal of regularity 2 in [61]. A new general
upper bound for the regularity of $S/J_{G}$ has been given in terms of the
dimension of a simplicial complex in [17]. In [38], authors of loc. cit.
obtained an improved lower and upper bound for the regularity of the BEI of a
generalized block graph. Generalized block graphs are the generalization of
block graphs and it is introduced in [43]. In [24], Hibi-Matsuda conjectured
the following

######  Conjecture 1.2 ([24], Conjecture 0.1).

Let $G$ be a graph on $n$ vertices. Then

reg$(S/J_{G})\leq$ deg $h_{S/J_{G}}(t)$.

They proved that this conjecture is true if $S/J_{G}$ has a unique extremal
Betti number. In [64], Schenzel and Zafar have shown complete bipartite graphs
have unique extremal Betti number. Also, Zafar and Zahid proved that
$n$-cycle, $C_{n}$ has a unique extremal Betti number, see [66]. In [21],
Herzog-Rinaldo characterized block graphs which admits unique extremal Betti
number. In [38], the author characterized a generalized block graph which
admits a unique extremal Betti number. In [40], authors provide a sufficient
condition for this conjecture.

The depth of an ideal is another commutative algebraic invariant of primary
importance, in the context of BEI there have been a number of works in this
area, but it is far from being complete. In [3], authors proved that depth of
$S/J_{G}$ is $n+1$, for a connected block graph $G$. In [66], the authors
showed that depth $S/J_{G}$ is $n,$ for $n>3$. In [36], authors gave the depth
of the BEI of generalised block graphs. For a connected graph $G$ on
$n$-vertices the depth of binomial edge ideal is at most $n$ and further, if
$G$ is a connected graph on $n$ vertices such that $S/J_{G}$ is Cohen-Macaulay
then depth of it is exactly $n+1$, see, [3]. Also, in the same article, the
authors provided upper bounds for the depth of binomial edge ideal of a
general graph in terms of certain graph invariants. Depth of binomial edge
ideal for a cone graph remains invariant under the process of taking cone on
connected graph, see [44]. In the same article they have given a formula for
the depth of binomial edge ideal of join of two graphs. Recently, in [46] they
have completely characterized the graphs for which is depth of the BEI is 5.

Betti numbers of binomial edge ideal of cycle, complete bipartite graphs,
trees, unicyclic graphs, and cone graph are known, see [66], [64], [29], [44].
In [29], the authors have given the generators the first syzygy of binomial
edge ideal of cycle and unicyclic graphs explicitly.

Generalized binomial edge ideal is introduced by Rauh in [54] as a
generalization to encompass a variety of binomial ideals. As a result it is an
important ideal to look at and the algebraic invariants of it are of primary
importance. There are only relatively few results on this ideal, apart from
the results in the particular case of graph binomial ideals. The generalized
binomial edge ideal is defined as the ideal generated by a collection of
$2$-minors of a generic $2\times n$ matrix. The determinantal ideal is of
classical importance to algebraic geometry and commutative algebra. Apart from
the geometric significance, another motivation to study these ideals comes
from their connection to conditional independence ideals, a topic in algebraic
statistics. Let $m,n\geq 2$ be integers and $G$ be a simple graph on the
vertex set $[n]$. Let $X=(x_{ij})$ be an $m\times n$ matrix of indeterminates
and $S=K[X]$ be the polynomial ring in the variables $x_{ij},1\leq i\leq
m,1\leq j\leq n$, over a field $K$. For $1\leq k<l\leq m$ and $\\{i,j\\}\in
E(G)$ with $1\leq i<j\leq n$ we set,

$p^{kl}_{ij}=[k,l][i,j]=x_{ki}x_{lj}-x_{li}x_{kj}$.

The ideal $\mathcal{J}_{G}=(p^{kl}_{ij}:1\leq k<l\leq m,\\{i,j\\}\in E(G))$ is
called the generalized binomial edge ideal. In [54], it is proved that
$\mathcal{J}_{G}$ is a radical ideal and its minimal primes are determined by
the sets with the cut point property of $G$. Regarding the minimal free
resolution of generalized binomial edge ideal, not much is known. But there
have been a few key works in this area. Madani and Kiani in [62], proved that
$\mathcal{J}_{G}$ has linear resolution if and only if $m=2$ and $G$ is a
complete graph. In [7], the authors proved the equality of the depth of
generalized binomial edge ideal of generalized block graph and the depth of
its initial ideal. Also they found the regularity of these two classes of
generalized block graphs. Since a tree is a block graph, one can get an
equivalent condition, which is given in [7]. Also, for a path, regularity of
generalized binomial edge ideal is computed in [7], and independently computed
in [39]. Regularity of the generalized binomial edge ideal for the complete
graph is known in [39]. In [2], the authors have proved that the generalized
binomial edge ideal is Cohen-Macaulay when the graph is a complete graph.

Another class of binomial ideals related to the binomial edge ideal is the
parity binomial edge ideal which was introduced in [33]. The permanental
binomial edge ideal and Lovasz-Saks-Schrjiver (in short, LSS) ideal in [20]
are also important classes of binomial edge ideals associated to graphs. Not
much work has been done on these classes of ideals and the authors of the
present article feels that much work on these are also important to further
understanding of the homological properties of the binomial ideals. The parity
binomial edge ideal has generated some recent interest among the combinatorial
commutative algebra community. Let $G$ be a simple graph with edge set $E(G)$
and $S=K[x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n}]$ be a polynomial
ring, the parity of binomial edge ideal of $S$ is denoted by $\mathcal{I}_{G}$
and is defined as $\mathcal{I}_{G}=(x_{i}x_{j}-y_{i}y_{j}:\\{i,j\\}\in E(G))$,
whereas, the permanental edge ideal is denoted by $\Pi_{G}$ and is defined as
$\Pi_{G}=(x_{i}y_{j}+x_{j}y_{i}:\\{i,j\\}\in E(G))$. Let $d\geq 1$ be an
integer, then the Lovasz-Saks-Schrjiver ideal is denoted by $L_{G}^{K}(d)$ and
is defined as,

$L_{G}^{K}(d)=(\displaystyle\sum_{l=1}^{d}x_{il}x_{jl}:\\{i,j\\}\in E(G))$

in the polynomial ring $K[x_{kl}:1\leq k\leq n,1\leq l\leq d]$. For $d=1$,
$L_{G}^{K}(d)$ it coincides with the edge ideal of graph $G$. For $d=2$, LSS
ideal of $G$ is the binomial ideal defined as
$L_{G}=(x_{i}x_{j}+y_{i}y_{j}:\\{i,j\\}\in E(G))\subset
K[x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n}]$. It is known that
$L_{G}$ is a radical ideal if char$(K)\neq 2$, in [20]. Also, the authors in
loc. cit. determined the primary decomposition of $L_{G}$ when
$\sqrt{-1}\notin K$ and char$(K)\neq 2$. In [33], the authors proved that the
parity binomial edge ideal is radical if and only if the graph is bipartite.
Also, in the same paper they have determined the minimal primes and the
primary decomposition. In [9], the authors proved that $L_{G}^{K}(2)$ is
complete intersection if and only if $G$ does not contain a claw or an even
cycle (Theorem 1.4). Also they have shown that $L_{G}^{K}(3)$ is prime if and
only if $G$ does not contain a claw or $C_{4}$. In [20], authors computed a
Gröbner basis of the permanental edge ideal of graphs and also they have shown
that it is a radical ideal. In [41], the author characterizes the graphs whose
parity binomial edge ideal is a complete intersection, see Theorem 3.2 and 3.5
of [41]. In the loc. cit., the author characterized the graphs for LSS ideals,
parity binomial edge ideal and permanental edge ideals that are complete
intersections. In [42], the authors have given a lower bound for the
regularity of parity binomial edge ideal of graphs, and also classified the
graphs whose parity binomial edge ideal has regularity 3. In the same article
they have characterized the graphs whose parity binomial edge ideal have pure
resolutions. In [11], the authors have given an explicit formula for the
Hilbert-Poincare series of the parity binomial edge ideal of a complete graph.

##  2\. Preliminaries

In this section, we recall basic definitions, notations, and terminologies of
graphs and algebra which will be needed further.

###  2.1. Basic notions from Algebra

Let $S=K[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial ring in $n$ variables over
a field $K$. Then $S$ is called a graded ring, graded by degree, if
$S=\oplus_{m\geq 0}S_{m}$, where $S_{m}$ is generated by all monomials of
degree $m$, and if $I$ is a graded ideal of $S$, then $R=S/I$ is called graded
algebra.

A graded free resolution of a finitely generated $S$-module $M$ is an exact
sequence

$\mathbb{F}:\ldots
F_{i}\overset{\phi_{i}}{\longrightarrow}F_{i-1}\longrightarrow\ldots\longrightarrow
F_{1}\overset{\phi_{1}}{\longrightarrow}F_{0}\overset{\phi_{0}}{\longrightarrow}M\longrightarrow
0$

where $F_{i}=\oplus_{j\in\mathbb{Z}}S(-j)^{\beta_{ij}},\forall j$ are the free
$S$-modules. The numbers $\beta_{ij}=\beta_{ij}(M)$ are called the graded
Betti numbers of $M$, and $\beta_{i}=\sum_{j}\beta_{ij}$ is called the total
$i$th Betti number of $M$.

The projective dimension of $M$ is defined by

$pd(M)=max\\{i:\beta_{ij}\neq 0,\text{for some }i\\}$

The regularity of $M$ is defined by

$reg(M)=max\\{j-i:\beta_{ij}\neq 0\\}$.

The depth of $M$ is defined by

$depth(M)=n-\text{proj dim}(M)$

If $\mathbf{m}=(x_{1},x_{2},\ldots,x_{n})$ is the maximal ideal of $S$, then
free resolution is called minimal if
$\phi_{i+1}(F_{i+1})\subset\mathbf{m}F_{i},\forall i$. Minimal free resolution
of a finitely generated module is finite which follows from the following
theorem.

######  Theorem 2.1 (Hilbert Syzygy Theorem).

Let $S=K[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial ring of $n$ variables over
a field $K$. Then the graded minimal free resolution of a graded finitely
generated $S$-module is finite, and its length is at most $n$.

A finitely generated $S$-module $M$ has a $d$-linear resolution if the minimal
free resolution is of the form

$0\rightarrow S(-d-i)^{\beta_{i}}\rightarrow\ldots\rightarrow
S(-d-1)^{\beta_{1}}\rightarrow S(-d)^{\beta_{0}}\rightarrow M\rightarrow 0$

where the degree of each generators of $M$ is $d$.
The module $M$ has a pure resolution if the minimal free resolution is of the
following form

$0\rightarrow S(-d_{i})^{\beta_{i}}\rightarrow\ldots\rightarrow
S(-d_{1})^{\beta_{1}}\rightarrow S(-d_{0})^{\beta_{0}}\rightarrow M\rightarrow
0$

such that $0<d_{0}<d_{1}<\ldots<d_{i}$ are all integers.
An ideal $I$ is said to be Cohen-Macaulay if the Krull dimension coincide with
the depth.

###  2.2. Basic notions of Graph

Let $G$ be a finite simple graph on $n$-vertices without isolated vertices. A
subgraph $H$ of $G$ is called induced, if for every vertices $u$ and $v$ in
$H$ whenever $\\{u,v\\}$ is an edge of $G$, it is an edge of $H$. A graph $G$
is called chordal graph if every induced subgraph of $G$ has cycle of length
3, and it is called co-chordal if its complement is chordal. A complete graph
is called clique. The largest number of the clique is called clique number of
$G$. A vertex $v$ of $G$ whose deletion from the graph gives a graph with more
connected components, then $v$ is called a cut point of $G$. A subset
$T\subset[n]$ is said to have a cut point property (in short, cut point set)
for $G$, if for every $v\in T$, $c(T\setminus\\{v\\})<c(T)$, where $c(T)$ is
the number of connected components of the restriction of $G$ to $[n]\setminus
T$. A cut set of a graph $G$ is a subset of the vertices whose deletion
increase the number of connected components of $G$.

Let $G_{1}$ and $G_{2}$ be two graphs with vertex sets $V_{1}$ and $V_{2}$ and
edge sets $E_{1}$ and $E_{2}$ respectively. The join of two graphs $G_{1}$ and
$G_{2}$ denoted by $G_{1}*G_{2}$, is a graph defined on the vertex set
$V_{1}\cup V_{2}$ and on the edge set $E_{1}\cup E_{2}\cup\\{\\{x,y\\}:x\in
V_{1},y\in V_{2}\\}$. For a graph $G$, a maximal subgraph of $G$ without cut
vertex is called a block of $G$. A graph $G$ is said to be a block graph if
each block of $G$ is a clique.

######  Definition 2.2.

(See, [40]) a graph $G$ is said to be a quasi-block graph if $G$ satisfies the
following:

  1. (1)

Each block of $G$ is either a clique or a quasi-block

  2. (2)

If $v$ is an internal vertex of a quasi-block $B$, then for any $u\in
N_{G}(v)\setminus V(B)$, $u$ is not an internal vertex for any block.

A graph $G$ is called an interval graph if every vertex $v\in V(G)$ can be
labelled with a real closed interval $I_{v}=[a_{v},b_{v}]$ in such a way that
two distinct vertices $v,w\in V(G)$ are adjacent if their corresponding
intervals have non-empty intersection. The vertices of the interval graph $G$,
are intervals namely $V(G)=\\{I_{1},\ldots,I_{r}\\}$, where
$I_{j}=[a_{j},b_{j}]$ with $a_{j}\leq b_{j}$, for all $1\leq j\leq r$.

Let $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. Also, let
$J_{0}=[0],J_{i}=[i-1,i],i=1,\ldots,k$ and $I_{j}=[a_{j},b_{j}]$, such that
$a_{j}\in\mathbb{N}_{0}$ and $I_{j}\subseteq[0,k]\ \\{k\\},$ for all
$j=1,2,\ldots,r$. Then we call the interval graph on the vertex set
$\\{J_{i}\\}_{i=0}^{k}\cup\\{I_{j}\\}_{j=1}^{r}$ a connected strong interval
graph or simply a strong interval graph.

##  3\. Regularity of binomial edge ideal of graphs

In this section, we will provide an overview of regularity of binomial edge
ideal of graphs. In [61] and [63], authors have characterized regularity of
binomial edge ideal of 2 and 3 respectively and its initial ideal. In the next
theorem the authors characterize when binomial edge ideal and its initial
ideal have a linear resolution that is reg$(J_{G})=2$.

######  Theorem 3.1 ([6], Theorem 1.4 and [61], Theorem 2.1).

Let $G$ be a simple graph, and $<$ be any term order. Then the following are
equivalent.

  1. (1)

$J_{G}$ has a linear resolution.

  2. (2)

in${}_{<}(J_{G})$ has a linear resolution.

  3. (3)

$G$ is a complete graph.

In [14], authors conjectured that the regularity of binomial edge ideal of a
graph is equal to the regularity of its initial ideal. This conjecture holds
for the join of two graphs.

######  Theorem 3.2 ([63], Theorem 2.1).

Let $G_{1}$ and $G_{2}$ be graphs on disjoint vertex sets $V_{1}$ and $V_{2}$
respectively, not both complete, let $<$ be any term order on ring $S$. Then

  1. (1)

reg$(J_{G_{1}*G_{2}})$=max$\\{reg(J_{G_{1}}),reg(J_{G_{2}}),3\\}$

  2. (2)

reg
$(in_{<}J_{G_{1}*G_{2}})$=max$\\{reg(in_{<}J_{G_{1}}),reg(in_{<}J_{G_{2}}),3\\}$

As an application of Theorem 3.2, they have characterized binomial edge ideal
of regularity 3.

######  Theorem 3.3 ([63], Theorem 3.2).

Let $G$ be a non-complete graph with $n$ vertices, and no isolated vertices.
Then reg$(J_{G})=3$ if and only if either

  1. (1)

$G=K_{r}\sqcup K_{s}$, with $r,s\geq 2$ and $r+s=n$, or

  2. (2)

$G=G_{1}*G_{2}$, where $G_{i}$ is a graph with $n_{i}<n$ vertices such that
$n_{1}+n_{2}=n$ and reg$(J_{G_{i}})\leq 3$, for $i=1,2$.

In [62], Madani-Kiani conjectured that the regularity of binomial edge ideal
of a graph is at most $c(G)+1$, where $c(G)$ is the number of maximal cliques
of $G$. This conjecture is proved for closed graphs, generalized block graphs,
some class of chordal graphs and for fan graphs of complete graph. Let $H$ be
a connected closed graph on $[n]$ such that $S/J_{H}$ is Cohen-Macaulay. Then
by ([14] Theorem 3.1), there exist integers
$1=a_{1}<a_{2}\ldots<a_{s}<a_{s+1}=n$ such that $F_{i}=[a_{i},a_{i+1}]$, for
$1\leq i\leq s$ and $F_{1},\ldots,F_{s}$ is a leaf order of $\triangle(H)$.
Set $e=\\{1,n\\}$. The graph $G=H\cup\\{e\\}$ is called the quasi-cycle
associated with $H$.

Let $H$ be a connected closed graph on the vertex set $[m]$ such that
$S_{H}/J_{H}$ is Cohen-Macaulay. Then by ([14], Theorem 3.1), there exist
integer $1=a_{1}<a_{2}<\ldots<a_{s}<a_{s+1}=m$ such that
$F_{i}=[a_{i},a_{i+1}],1\leq i\leq s$ and $F_{1},F_{2},\ldots,F_{S}$ is a leaf
order of $\triangle(H)$. Let $F_{s+1}=[m,n]\cup\\{1\\}$. The graph on the
vertex set $[n]$ and edge set $E(G)=E(H)\cup\\{\\{i,j\\}:i\neq j,i,j\in
F_{s+1}\\}$ is called a semi-cycle graph associated with $H$.

######  Definition 3.4.

A block $B$ of a graph $G$ is said to be a semi-block if $B$ is a semi-cycle
with $B\neq K_{3}$. A graph $G$ is said to be a semi-block graph if all except
one block are cliques and the block which is not a clique is a semi-block.

In [40], the author proved this conjecture for quasi block graphs and for semi
block graphs.

######  Theorem 3.5 ([40], Theorem 3.7 and Theorem 3.11).

For a quasi-block graph as well as semi block graph $G$, reg$(S/J_{G})\leq
c(G)$.

######  Definition 3.6.

The Jahangir graph denoted by $J_{m,n}$ is a graph on the vertex set
$[m,n+1],m\geq 1,n\geq 3$ such that the induced subgraph on $[mn]$ is $C_{mn}$
and the neighbourhood of the vertex $mn+1$ is $\\{1,m+1,\ldots,m(n-1)+1\\}$.

In [40], the author proved the same conjecture independently for chordal graph
see, Theorem 3.15 and for Jahangir graphs see, Theorem 4.5. In [24], Hibi-
Matsuda conjectured that for a graph $G$ on $n$-vertices, reg$(S/J_{G})\leq
degh_{S/J_{G}}(t)$. Characterization of generalized block graphs which admit
unique extremal Betti number is given in [38]. In [40], author provide a
sufficient condition for this conjecture.

######  Theorem 3.7 ([40], Theorem 5.1).

Let $G$ be a connected graph on vertex set $[n]$. If $S/J_{G}$ admits a unique
extremal Betti number, then reg$(S/J_{G})\leq degh_{S/J_{G}}(t)$.

In [40], Example 5.3 author has given a counter example for this conjecture.
Also the author posed a question which is the following:

######  Question 3.8.

When does the binomial edge ideal of a graph admit a unique extremal Betti
number?

In [30], authors proved that regularity of $S/J_{G}$ is less than or equal to
$n-1$, for some classes of trees. An improved upper bound for the regularity
of binomial edge ideal of trees is given as a corollary of the Theorem 0.1,
[31]

######  Corollary 3.9 ([31], Corollary 0.1).

Let $T$ be a tree on $[n]$ with spine $P$ of length $l$. Let $e_{2}$ denote
the number of edges that are not in $P$ and with both end points having degree
at most 2 and $d_{3}$ denote the number of vertices, not in $P$, and having
degree at least 3. Then

$reg(S/J_{T})\leq e_{2}+l+2d_{3}$.

######  Definition 3.10.

Let $I$ and $J$ be two proper ideals of a local regular ring $R$, they are
called directly linked, we denote by $I\sim J$, if there exists a regular
sequence $z=z_{1},\ldots,z_{n}$ in $I\cap J$ such that $J=(z):I$ and
$I=(z):J$. We say that $I$ and $J$ belong to the same linkage class if there
exist a sequence a direct links

$I=I_{0}\sim I_{1}\sim\ldots\sim I_{m}=J$.

$I$ is said to be linkage class complete intersection, in short licci, if $J$
is a complete intersection ideal.

If $I$ and $J$ are linked, then if one of them is Cohen-Macaulay then other is
too. In particular, any licci ideal is always Cohen-Macaulay. A necessary
condition for a homogeneous ideal in a polynomial ring which is Cohen-Macaulay
as well as licci is given in [26].

######  Theorem 3.11 ([26], Corollary 5.13).

Let $I$ be a Cohen-Macaulay homogeneous ideal in a standard graded polynomial
ring $S=K[x_{1},\ldots,x_{n}]$ with the graded maximal ideal $\mathfrak{m}$.
If $I_{\mathfrak{m}}\subset R=S_{\mathfrak{m}}$ is licci, then

$reg(S/I)\geq(heightI-1)(indegI-1)$

where $indegI$ is the initial degree of the ideal $I$, that is
$indegI=min\\{i:I_{i}\neq 0\\}$.

In [17], the authors have given a new upper bound for the regularity of
$S/J_{G}$.

######  Theorem 3.12 ([17], Theorem 2.1).

Let $G$ be a connected graph on vertex set $[n]$. Then

$reg(S/J_{G})\leq n-dim\triangle(G)$

where $\triangle(G)$ is a simplicial complex of $G$.

For a disconnected graph $G$, the authors have found an upper bound, and it is
the following

######  Theorem 3.13 ([17], Corollary 2.2).

Let $G$ be a graph on $n$ vertices with the connected components
$G_{1},\ldots,G_{c}$. Then

$reg(S/J_{G})\leq n-(dim\triangle(G_{1})+\ldots+dim\triangle(G_{c}))$.

Next theorem has improved the upper bound given by Matsuda and Murai in [49].

$e_{1}$$e_{r}$$e_{1}^{{}^{\prime\prime}}$$e_{t}^{{}^{\prime\prime}}$$e_{1}^{{}^{\prime}}$$e_{s}^{{}^{\prime}}$
Figure 1. Licci graphs

######  Theorem 3.14 ([17], Theorem 3.5).

Let $G$ be a connected graph on the vertex set $[n]$. Then the following are
equivalent

  1. (1)

$(J_{G})_{\mathfrak{m}}\subset R=S_{\mathfrak{m}}$ is licci.

  2. (2)

$J_{G}$ is Cohen-Macaulay and $n-2\leq reg(S/J_{G})\leq n-1$

  3. (3)

$G$ is a path graph or it is isomorphic to one of the graphs in Figure 1,
where $r,s,t$ are non-negative integers. In other words, $G$ is a triangle
with possibly some paths connected to some of its vertices.

An equivalent statement of 3.14 for chordal graph is the following.

######  Theorem 3.15 ([17], Theorem 4.2).

Let $G$ be a connected chordal graph on the vertex set $[n]$. Then the
following are equivalent

  1. (1)

$(J_{G})_{\mathfrak{m}}\subset R$ is licci.

  2. (2)

$J_{G}$ is Cohen-Macaulay and $n-2\leq reg(S/J_{G})\leq n-1$.

  3. (3)

$J_{G}$ is unmixed and $n-2\leq reg(S/J_{G})\leq n-1$.

  4. (4)

$G$ is a path graph or it is isomorphic to a graph in Figure 1.

An explicit formula for the regularity of binomial edge ideal for the block
graphs in terms of combinatorics of the graph is an open problem. An algorithm
for dimension of binomial edge ideal for block graph is given in [47],
Algorithm 2.5.

For a flower graph, extremal Betti number is given in [47], Theorem 3.4. As a
consequence, one can get regularity of binomial edge ideal for flower graph
$F(v)$.

######  Corollary 3.16 ([47], Corollary 3.5).

Let $F(v)$ be a flower graph, then

$regS/J_{F(v)}=i(F(v))+cdeg(v)-1$

where $cdeg(v)$ is the clique degree of $v$, is the number of maximal cliques
to which $v$ belongs and $i(F(v))$ is the inner vertices of $F(v)$.

######  Definition 3.17.

Let $G$ be a block graph. If $G$ has no flower graph as an induced subgraph,
then $G$ is called flower free graph.

######  Definition 3.18.

Let $G$ be a block graph and $F(v)$ be a flower graph as an induced subgraph
of $G$. $F(v)$ is called an end-flower of $G$ if $G=G_{1}\cup\ldots\cup
G_{c}$, where $c=cdeg(v)$, such that $G_{i}\cap G_{j}=\\{v\\}$, for all $1\leq
i<J\leq c$ and $G_{2},\ldots,G_{c}$ are flower free graphs.

The formula for the regularity of binomial edge ideal of block graphs.

######  Theorem 3.19 ([47], Theorem 4.2).

Let $G$ be a block graph, $v_{1},\ldots,v_{r}\in V(G)$

$H_{j}=G\ \\{v_{1},\ldots,v_{j}\\}$

$j=1,2,\ldots,r$ and $H_{0}=G$. If

  1. (1)

$F(v)$ is an end-flower for $H_{j-1}$, for all $j=1,\ldots,r$

  2. (2)

$H_{r}$ is flower-free

then

$regS/J_{G}=regS/J_{H_{r}}=c+i(H_{r})$

where $c$ is the number of connected components of $H_{r}$ which are not
isolated vertices.

In [38], the author has given improved lower and upper bound for the
regularity of binomial edge ideal of generalized block graphs. In the same
article, they have also characterized generalized block graph in which
binomial edge ideal admits a unique extremal Betti number.

######  Theorem 3.20 ([38], Theorem 3.11).

Let $G$ be a connected indecomposable generalized block graphs. Then the
following are equivalent

  1. (1)

$S/J_{G}$ admits a unique extremal Betti number.

  2. (2)

For any $v\in V(G)$, $F_{h,k}(v)$ is not an induced subgraph of $G$, for any
$h,k\geq 0$ with $h+k\geq 3$.

In this case, reg$(S/J_{G})=m(G)+1$.

where $F_{h,k}(v)$ is a flower graph obtained by gluing of $h$ copies of the
complete graph $K_{3}$ and $k$ copies of the star graph $K_{1,3}$ at a common
free vertex $v$ and $m(G)$ is the number of minimal cut sets of the graph $G$.

Let $deg_{G}(v)$ denote the degree of a vertex $v$ of a graph $G$. If
$deg_{G}(v)=1$, then we say $v$ is a pendant vertex. Let for $v\in V(G)$, the
number of maximal cliques of $G$ which contain $v$, be denoted by
$cdeg_{G}(v)$ and the number of pendant vertices adjacent to $v$ be denoted by
$pdeg_{G}(v)$. A vertex $v\in V(G)$ such that $cdeg_{G}(v)=pdeg_{G}(v)+1$ with
$pdeg_{G}(v)\geq 1$ is said to be of type 1, and of type 2 if $cdeg_{G}(v)\geq
pdeg_{G}(v)+2$. Let $\alpha(G)$ be the number of vertices of type 1, and
$pv(G)$ be the number of pendant vertices of $G$.

With the same notations as in above, in [38], the author obtained upper bound
for the regularity of binomial edge ideal of connected indecomposable
generalized block graphs.

######  Theorem 3.21 ([38], Theorem 4.5).

Let $G$ be a connected indecomposable generalized block graph on $[n]$
vertices, which is not a star graph. Then

reg$(S/J_{G})\leq c(G)+\alpha(G)-pv(G)$

where $c(G)$ is number of maximal cliques of $G$.

Let $G$ be a graph on the vertex set $V(G)$, and for subset $T\subseteq V(G)$
the induced subgraph of $G$ on the vertex set $V(G)\setminus T$, be denoted by
$G-T$. Let $N_{G}(v)$ denote the set of neighbours of the vertex $v$ in $G$.
We set $\hat{G}=G\setminus\mathcal{I}s(G)$, where $\mathcal{I}s(G)$ denotes
the set of isolated vertices of $G$ and $K_{n}$ denote the complete graph on
$n$ vertices. Associated to a vertex $v$ in $V(G)$, there is a graph denote by
$G_{v}$, with the vertex set $V(G)$ and the edge set

$E(G)\cup\\{\\{u,w\\}:\\{u,w\\}\subseteq N_{G}(v)\\}$

In [58], the authors give a general upper bound for regularity of binomial
edge ideal. For that they have introduced a map, called compatible map, and
the definition is as the following:

######  Definition 3.22.

Let $\mathcal{G}$ be the set of all graphs. We call a map
$\phi:\mathcal{G}\rightarrow\mathbb{N}_{0}$, compatible, if it satisfies the
following conditions

  1. (1)

$\phi(\hat{G})\leq\phi(G)$, for all $G\in\mathcal{G}$

  2. (2)

If $G=\sqcup_{i=1}^{t}K_{n_{i}},n_{i}\geq 2$, for every $1\leq i\leq t$, then
$\phi(G)\geq t$.

  3. (3)

If $G\neq\sqcup_{i=1}^{t}K_{n_{i}}$, then there exists $v\in V(G)$ such that

    1. (a)

$\phi(G-v)\leq\phi(G)$ and

    2. (b)

$\phi(G_{v})<\phi(G)$.

######  Theorem 3.23 ([58], Theorem 2.4).

Let $G$ be a graph on $[n]$ and $\phi$ a compatible map. Then

$reg(S/J_{G})\leq\phi(G)$.

Next we will see a new upper bound for regularity of binomial edge ideal which
is clique disjoint edge set in graph.

######  Definition 3.24.

Let $G$ be a graph and $\mathcal{H}\subseteq E(G)$ with the property that no
two element of $\mathcal{H}$ belong to a clique of $G$. Then we call the set
$\mathcal{H}$, a clique disjoint edge set in $G$. we set

$\eta(G)=max\\{|\mathcal{H}|:\mathcal{H}\text{is a clique disjoint edge set
in}$G$\\}$

######  Theorem 3.25 ([58], Corollary 2.7).

Let $G$ be a graph on vertex set $[n]$. Then

$reg(S/J_{G})\leq\eta(G)$.

So, by above result we get a sharp bound for regularity of binomial edge
ideal, as $\eta(G)\leq c(G)$, for every graph $G$.
In [59], authors proved that regularity of strong interval graph of $G$
coincide with $\mathcal{L}(G)$ as well as $c(G)$, where $\mathcal{L}(G)$ is
the sum of the lengths of the longest induced paths of connected components of
$G$.

######  Theorem 3.26 ([59], Corollary 4.3).

Let $G$ be a chordal graph. Then the following are equivalent

  1. (1)

$reg(S/J_{G})=\mathcal{L}(G)=c(G)$

  2. (2)

$G$ is a strong interval graph.

##  4\. Depth of Binomial edge ideal

In general, it is hard to compute another algebraic invariant such as the
depth of binomial edge ideals. Regarding the depth of binomial edge ideal not
much have been done. In the next result we will see the formula for the depth
of cone graph. The definition of cone graph is the following

######  Definition 4.1.

Let $H$ be a graph on vertex set $[n]$. The cone of $v$ on $H$ is denote by
$v*H$, is a graph with vertex set $V(v*H)=V(H)\sqcup\\{v\\}$ and edge set
$E(v*H)=E(H)\sqcup\\{\\{u,v\\}:u\in V(H)\\}$.

Let $G=v*H$ and $S_{H}=K[x_{i},y_{i}:i\in V(H)]$ and $S=S_{H}[x_{v},y_{v}]$.
In [44], authors has proved that under the process of taking cone on connected
graph depth remains invariant .

######  Theorem 4.2 ([44], Theorem 3.4).

Let $H$ be a connected graph on the vertex set $[n]$ and let $G=v*H$ be the
cone graph. Then

$depth_{S}(S/J_{G})=depth_{S_{H}}(S_{H}/J_{H})$

In particular, if $H$ is Cohen-Macaulay, then $G$ is almost Cohen-Macaulay.

For the binomial edge ideal of cone graph, depth formula is the following.

######  Theorem 4.3 ([44], Theorem 3.9).

Let $G=v*H$, where $H$ is a disconnected graph on vertex set $[n]$. Then

$depth_{S}{S/J_{G}}=min\\{depth_{S_{H}}(S_{H}/J_{H}),n+2\\}$.

Depth formula of binomial edge ideal for join of two graphs can be found in
[44], Theorem 4.1, 4.3, 4.4.

Let $H_{\mathfrak{m}}^{i}(S/J_{G})$ denote the $i$th local cohomology module
of $S/J_{G}$, where maximal ideal associated to it is
$\mathfrak{m}=(x_{1},\ldots,x_{n},y_{1},\ldots,y_{n})$. Then

depth$(S/J_{G})=min\\{i:H_{\mathfrak{m}}^{i}(S/J_{G})\neq 0\\}$.

In [66], authors have shown that depth $(S/J_{G})=n$, for $n>3$. In [14],
authors proved that depth $(S/J_{G})=n+1$, for a connected block graph $G$.
Later in [36], authors computed the depth of generalized block graphs. In
[44], authors have given the formula for depth of join product of two graphs
$G_{1}$ and $G_{2}$, which is denoted by $G_{1}*G_{2}$. In [3], the authors
has given an upper bound in terms of graphs invariant for the depth of
binomial edge ideal of a graph. They proved that for a non-complete connected
graph $G$, depth $(S/J_{G})\leq n-\kappa(G)+2$, where $\kappa(G)$ denotes the
vertex connectivity of $G$.

In [57], authors proved Hochster type formula for the local cohomology modules
of binomial edge ideal, which is based on [1],Theorem 3.9.

######  Theorem 4.4.

([57], Theorem 3.6) Let $G$ be a graph on $[n]$, and $\mathcal{Q}(G)$ be the
poset associated to $J_{G}$. Then we have the $\mathbb{K}$-isomorphism

$H_{\mathfrak{m}}^{i}(S/J_{G})\cong\oplus_{q\in\mathcal{G}}H_{\mathfrak{m}}^{d_{q}}(S/q)^{\oplus
M_{i,q}}$

where $d_{q}=dimS/q$ and
$M_{i,q}=dim_{\mathbb{K}}H^{\tilde{i}-d_{q}-1}((q,1_{\mathcal{Q}_{G}});\mathbb{K})$.

In the next theorem, the authors have given a lower bound for the depth of
binomial edge ideal.

######  Theorem 4.5 ([57], Theorem 5.2).

Let $G$ be a graph on $[n]$. Then

depth$(S/J_{G})\geq 4r+\sum_{i=1}^{n}r_{i}(i+1)$,

where $r$ is the number of non-complete connected components of $G$, and
$r_{i}$ is the number of complete connected components of $G$ of size $i$, for
every $1\leq i\leq n$.

Next, the authors characterized the graphs for depth$(S/J_{G})=4$.

######  Theorem 4.6 ([57], Theorem 5.3).

Let $G$ be a graph on $[n]$ with $n\geq 4$. Then the following are equivalent.

  1. (1)

depth$(S/J_{G})=4$

  2. (2)

$G=G^{{}^{\prime}}*2K_{1}$, for some graph $G^{{}^{\prime}}$,

where $2K_{1}$ is the graph consisting of two isolated vertices.

In [3], authors proved that for a connected non-completed graph $G$,

depth$(S/J_{G})\leq n+2-\kappa(G)$,

where $\kappa(G)$ is the graph connectivity of $G$. In [46], authors proved
that

$f(G)+d(G)\leq depth(S/J_{G})$.

In [27], authors have characterized graphs for which depth of $S/J_{G}$ attain
the lower bound.

######  Theorem 4.7 ([27],Corollary 5.6).

Let $G$ be a unicyclic graph or a quasi-cycle graph such that
depth$(S/J_{G})=d(G)+f(G)$. Then either $G$ is chordal or $G$ has an induced
$C_{4}$.

Next question arises is, whether there exists any graph $G$ such that
$f(G)+d(G)=n+2-\kappa(G)$ or not. Existence of such graphs are characterized
by Hibi and Saeedi Madani in [23]. Also, in [27], author characterizes
connected non-complete graphs $G$ with the property that
$f(G)+d(G)+1=n+2-\kappa(G)$.

######  Theorem 4.8 ([27], Theorem 3.9).

Let $G$ be a graph on $[n]$ such that $d(G)+f(G)+1=n+2-\kappa(G)$.

  1. (1)

If $\kappa(G)=1$, then either $G$ is chordal or $G$ has precisely one induced
$C_{4}$ and has no induced $C_{l}$, for $l\geq 5$.

  2. (2)

If $\kappa(G)\geq 2$ and $d(G)=2$, then $G$ is a chordal graph.

  3. (3)

If $\kappa(G)=2$ and $d(G)=3$, then either $G$ is chordal or $G$ has precisely
one induced $C_{4}$, and has no induced $C_{l}$, for $l\geq 5$.

The authors in ([27], Section 4) described the structure of the graphs with
the property $f(G)+d(G)+1=n+2-\kappa(G)$ and calculated the depth of
$S/J_{G}$. Also in the same paper authors posed the following question.

######  Question 4.9 ([27], Question 5.5).

If $G$ is a graph containing an induced cycle of length at least 5, then is
depth$(S/J_{G})\geq d(G)+f(G+1)$?

##  5\. Results on the other algebraic invariants

###  5.1. Betti number

Betti number is one of the homological invariant which will help us to know
about its structure. Researchers have computed Betti number of binomial edge
ideals. Zofar and Zahid calculated for cycles in [66], Schenzel and Zafar
calculated for complete bipartite graphs in [64] and Jayanthan et. al
calculated for trees and unicycle graphs in [29]. In [44] authors have
calculated Betti number for cone graph [see, Theorem 3.10]. As a consequence
of this, they have calculated Betti number for wheel graph [see, [44],
Corollary 3.11].

In [29], authors computed the first Betti number of binomial edge ideal of
trees (see, Theorem 3.1) and second Betti number of unicyclic graphs (see,
Theorem 3.4). In the same paper, they have calculated first syzygy of binomial
edge ideal for cycle $C_{n}$, Theorem 3.5. Next, they have calculated first
syzygy of binomial edge ideal for unicyclic graphs (Theorem 3.6, 3.7) and for
trees.

Let $A\subset[n]$, and $i\in A$, define $P_{A}(i)=|\\{j\in A:j\leq i\\}|$.
Here, $P_{A}$ denotes the position of an element in $A$ when the elements are
arranged in the ascending order. Now we are ready to state the following
theorem.

######  Theorem 5.1 ([29]).

Let $G$ be a tree on $n$-vertices. Then the first syzygy of $J_{G}$ is
minimally generated by elements of the form

  1. (1)

$f_{i,j}e_{\\{k,l\\}}-f_{k,l}e_{\\{i,j\\}}$, where $\\{i,j\\},\\{k,l\\}\in
E(G)$ and $\\{e_{\\{i,j\\}}:\\{i,j\\}\in E(G)\\}$ is the standard basis of
$S(-2)^{n-1}$.

  2. (2)

$(-1)^{P_{A}(j)}f_{k,l}e_{\\{i,j\\}}+(-1)^{P_{A}(k)}f_{j,l}e_{\\{i,k\\}}+(-1)^{P_{A}(l)}f_{j,k}e_{\\{i,l\\}}$,
where $A=\\{i,j,k,l\\}\in\mathcal{C}_{G}$ with center at $i$.

where $\mathcal{C}_{G}=\sum_{v\in V(G)}\binom{deg_{G}(v)}{3}$.

Rees algebra of an ideal $I$ is $\mathcal{R}(I)=\oplus_{n\geq 0}I^{n}t^{n}$.
The generators of the defining ideal of the Rees algebra of a graph is
described by Villarreal in [65]. He proved that $I(G)$ is of linear type, that
is the Rees algebra is isomorphic to the symmetric algebra if and only if $G$
is either a tree or an odd unicyclic graph. But almost nothing is known about
the Rees algebra of binomial edge ideal of a graph. It is known that for a
connected graph $G,J_{G}$ is complete intersection if and only if $G$ is a
path [14].

Let $G$ be a graph on $n$-vertices and $J_{G}$ be its binomial edge ideal. Let
$R=S[T_{\\{i,j\\}}\in E(G),i<j]$. Let $\delta:R\rightarrow S[t]$ be the
$S$-algebra homomorphism given by $\delta(T_{\\{i,j\\}})=f_{i,j}t$. Then
$Im(\delta)=\mathcal{R}(J_{G})$ and $ker(\delta)$ is called the defining ideal
of $\mathcal{R}(J_{G})$.

The following theorem characterizes the trees whose binomial edge ideal are
almost complete intersection.

######  Theorem 5.2 ([57], Theorem 4.3).

If $G$ is a tree which is not a path, then $J_{G}$ is an almost complete
intersection ideal if and only if $G$ is obtained by adding an edge between
two vertices of two paths.

In general, they have characterized for connected graph which is not a tree in
Theorem 4.4. Also they have shown that the associated graded ring and the Rees
algebra of almost complete intersections binomial edge ideal are Cohen-
Macaulay.

######  Theorem 5.3 ([57], Theorem 4.7).

If $G$ is a graph such that $J_{G}$ is an almost complete intersection ideal,
then $gr_{S}(J_{G})$ and $\mathcal{R}(J_{G})$ are Cohen-Macaulay.

Since, complete intersections are of linear type, binomial edge ideal of paths
are linear type. In [57], Proposition 4.9, authors proved that binomial edge
ideal of $K_{1,n}$ is of linear type. In the same paper authors proved that in
the polynomial ring over an infinite field, almost complete intersection
homogeneous ideals are generated by $d$-sequence, Proposition 4.10. As a
corollary of the above result we have the following.

######  Corollary 5.4 ([57], Corollary 4.11).

Let $G$ be a graph on $n$-vertices. If $J_{G}$ is an almost complete
intersection ideal, then $J_{G}$ is generated by a $d$-sequence. In
particular, $J_{G}$ is of linear type.

Also, they have obtained the defining ideal of Rees algebra of binomial edge
ideal of cycles as a corollary, see [[57], Corollary 4.13]. Authors have asked
the following question:

######  Question 5.5 ([57], Question 4.16).

Classify all bipartite graphs whose binomial edge ideal are of linear type.

The above question is not true for tree. So, one can prove or disprove the
following,

######  Conjecture 5.6 ([57], Conjecture 4.17).

If $G$ is a tree or a unicyclic graph, then $J_{G}$ is of linear type.

###  5.2. Construction of a graph

In [22], Hibi et. al. constructed a graph $G$ such that for $1\leq b\leq r$,
the regularity of monomial edge ideal of $G$ is $r$, and the number of its
extremal Betti number is $b$. Also in [24], for a given pair $(r,s)$ with
$1\leq r\leq s$, Hibi and Matsuda constructed a graph $G$ such that
reg$(S/J_{G})=r$ and the degree of the $h$-polynomial of $S/J_{G}$ is $s$. In
[44], authors constructed the following.

######  Theorem 5.7 ([44], Theorem 5.4).

Let $r$ and $b$ be two positive integers with $1\leq b\leq r-1$. Then there
exist a graph $G=G_{r,b}$ such that reg$(S/J_{G})=r$, and the number of
extremal Betti number of $S/J_{G}$ is $b$.

######  Question 5.8.

Does there exists a graph $G$ such that the projective dimension is bounded by
a linear function of $b$ and $r$, where $r=reg(S/J_{G})$, and $b$ is the
number of extremal Betti number of $S/J_{G}$?

###  5.3. Cohen-Macaulay Binomial edge ideal

Cohen-Macaulay binomial edge ideals are studied by many authors [14], [53].
Also, Cohen Macaulay binomial edge ideal for bipartite graphs and block graphs
were studied in [14], [3], [5], [36]. But the classification of it in terms of
underlying graph is not known. In [55], authors have classified Cohen Macaulay
and unmixed binomial edge ideal with deviation. As an extension of these
results, in [56], authors classified Cohen-Macaulay and unmixed binomial edge
ideal $J(G)$, where $G$ is a cactus graph i.e. a graph whose blocks are
cycles.

In [14], Ene, Herzog and Hibi proved that if $G$ is a closed graph then
$S/J_{G}$ is Gorenstein if and only if $G$ is a path. Motivated by this
result, author in [18] obtained the similar result for connected graph $G$.

######  Theorem 5.9 ([18], Theorem 5.3).

Let $S=K[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$. Suppose the char$(K)=p>0$.
Let $G$ be a connected graph such that $S/J_{G}$ is Gorenstein. Then $G$ is a
path.

The above result also holds for char$(K)=0$ ([18], Theorem 5.4).

###  5.4. Hilbert series

The Hilbert series of binomial edge ideal of cycles and quasi cycles is
computed in [50], [66]. Authors in [48] have computed the Hilbert-Poincare
series of the binomial edge ideal of some Cohen-Macaulay bipartite graphs, Fan
graphs (see Proposition 3.8). In [43], authors obtained the Hilbert series for
decomposable graphs in terms of indecomposable components.

######  Definition 5.10.

A graph $G$ is said to be decomposable, if there exist induced subgraphs
$G_{1}$ and $G_{2}$, such that $G=G_{1}\cup G_{2},V(G_{1})\cap
V(G_{2})=\\{v\\}$, and $v$ is a free vertex of $G_{1}$ and $G_{2}$.

######  Theorem 5.11 ([43], Theorem 3.2).

Let $G=G_{1}\cup G_{2}$ be a graph on vertex set $[n]$. Then

$Hilb_{S/J_{G}}(t)=(1-t)^{2}Hilb_{S_{1}/J_{G_{1}}}(t)Hilb_{S_{2}/J_{G_{2}}(t)}$,

where $S_{i}=K[x_{j},y_{j}:j\in V(G_{i})]$, for $i=1,2$

They also have obtained dimension and multiplicity of $S/J_{G}$. As a
corollary of 5.11, they have computed Hilbert series for a connected graph. In
the same paper, authors computed Hilbert series for join of two graphs.

######  Theorem 5.12 ([43], Theorem 4.2).

Let $H$ and $H^{{}^{\prime}}$ be two disconnected graphs on vertex sets $[p]$
and $[q]$, respectively. Let $G=H*H^{{}^{\prime}}$ be the join of $H$ and
$H^{{}^{\prime}}$. Then

$Hilb_{S/J_{G}}(t)=Hilb_{S_{H}/J_{H}}(t)+Hilb_{S_{H^{{}^{\prime}}}/J_{H^{{}^{\prime}}}}(t)+\frac{(p+r-1)t+1}{(1-t)^{p+q+1}}-\frac{(p-1)t+1}{(1-t)^{p+1}}-\frac{(q-1)t+1}{(1-t)^{q+1}}$

###  5.5. Symbolic power

In general, symbolic power and ordinary power of an ideal do not coincide. But
for some classes of homogeneous ideals in polynomial rings it coincide, e.g.
for a bipartite graph symbolic power and ordinary powers of an edge ideal
coincide. In [13], Ene and Herzog proved that for any binomial edge ideal with
quadratic Gröbner basis, the symbolic powers and ordinary powers of $J_{G}$
coincide. Authors have shown that based on the condition of in${}_{<}(J_{G})$
these two powers coincide.

######  Theorem 5.13 ([13], Theorem 3.3).

Let $G$ be a connected graph on the vertex set $[n]$. If $in_{<}(J_{G})$ is a
normally torsion-free ideal, then

$J_{G}^{(k)}=J_{G}^{k}$, for $k\geq 1$

As a consequence of the above result one can get the equality of these two
powers for a closed graph, see, [13], Corollary 3.4.

###  5.6. Hochster Type formula

Hochster formula originally appeared in [25], it provides a decompostion of
the local cohomology modules $H_{\mathfrak{m}}^{r}(A/I)$ of the Stanley-
Reisner ring $R/I$, associated to a squarefree monomial ideal $I\subseteq
A=K[x_{1},\ldots,x_{n}]$. It also describes the Hilbert series of the local
cohomology modules of $A/I$. In [1] authors have given a Hochster type
decomposition for the local cohomology modules associated to binomial edge
ideal and is as the following.

######  Theorem 5.14 ([1], Theorem 3.9).

Let $A=K[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$ be a polynomial ring over a
field $K$. Let $J_{G}$ be the binomial edge ideal associated to a graph $G$ on
the vertex set $[n]$. Let $Q_{J_{G}}$ be the poset associated to a minimal
primary decomposition of $J_{G}$. Then the local cohomology modules with
respect to $\mathfrak{m}$ of $A/J_{G}$ admit the following decompostion as
$K$-vector spaces

$H_{\mathfrak{m}}^{r}(A/J_{G})\cong\oplus_{q\in
Q_{J_{G}}H_{\mathfrak{m}}^{d_{q}}}(A/I_{q})^{\oplus M_{r,q}}$

where $M_{r,q}=dim_{k}H^{\tilde{r}-d_{q}-1}((q,1_{Q_{J_{G}}});K)$. Moreover,
we have a decomposition as graded $K$-vector spaces.

In [8], when authors comparing invariant of Cartwright-Strumfels ideals with
its generic initial ideal they got the following

######  Conjecture 5.15 ([8], Conjecture 1.14).

Let $I\subseteq A$ be a $\mathbb{Z}^{m}$-graded Cartwright-Strumfels ideal and
gin $(I)$ its $\mathbb{Z}^{m}$-graded generic initial ideal, with $m\leq n$.
Then one has

$dim_{K}H_{\mathfrak{m}}^{r}(A/I)_{a}=dim_{K}H_{\mathfrak{m}}^{r}(A/gin(I))_{a}$.

for every $r\in\mathbb{N}$ and every $a\in\mathbb{Z}^{m}$.

In [1], the author has proved the conjecture 5.15 for binomial edge ideal.

######  Theorem 5.16 ([1], Theorem 4.5).

Let $A=K[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]$ be a polynomial ring over $K$
and $\mathfrak{m}$ be its homogeneous maximal ideal. Let $J_{G}$ be binomial
edge ideal associated to a graph $G$ on the vertex set $[n]$. Then

$dim_{K}H_{\mathfrak{m}}^{r}(A/J_{G})_{a}=dim_{K}H_{\mathfrak{m}}^{r}(A/gin(J_{G}))_{a}$,

for every $r\in\mathbb{N}$ and every $a\in\mathbb{Z}^{n}$.

##  6\. Generalized Binomial edge ideal

Generalized binomial edge ideal is introduced by Rauh in [54]. It is the ideal
generated by a collection of $2$-minors in generic matrix. Motivation to study
these ideals comes from their connection to conditional independence ideals.

######  Definition 6.1.

Let $m,n\geq 2$ be integers. Let $G$ be a simple graph on the vertex set
$[n]$. Let $X=(x_{ij})$ be an $m\times n$ matrix of indeterminate and denote
$S=K[X]$ the polynomial ring in the variables $x_{ij},1\leq i\leq m,1\leq
j\leq n$, over a field $K$. For $1\leq k<l\leq m$ and $\\{i,j\\}\in E(G)$ with
$1\leq i<J\leq n$ we set

$p^{kl}_{ij}=[k,l][i,j]=x_{ki}x_{lj}-x_{li}x_{kj}$

The ideal $\mathcal{J}_{G}=(p^{kl}_{ij}:1\leq k<l\leq m,\\{i,j\\}\in E(G)$ is
called the generalized binomial edge ideal.

In [54], it was proved that $\mathcal{J}_{G}$ is a radical ideal and its
minimal primes are determined by the sets with the cut point property of $G$.
Not much is known about minimal free resolution of generalized binomial edge
ideal. Madani and Kiani in [62], proved that $\mathcal{J}_{G}$ has linear
resolution if and only if $m=2$ and $G$ is a complete graph.

Let $G$ be a generalized block graph. Let $A_{i}(G)$ be the collection of cut
sets of $G$ of cardinality $i$, $i=1,2,\ldots,\omega(G)-1.$ We denote
$a_{i}(G)=|A_{i}(G)|$. In [7], authors proved the equality of depth of
generalized binomial edge ideal of generalized block graph and depth of its
initial ideal, and also found the regularity of these two generalized block
graph.

######  Theorem 6.2 ([7], Theorem 3.3).

Let $m,n\geq 2$, and let $G$ be a connected generalized block graph on the
vertex set $[n]$. Then

  1. (1)

depth $(S/{\mathcal{J}_{G}})$=depth
$(S/{in_{<}{(\mathcal{J}_{G})}})=n+(m-1)-\displaystyle\sum_{i=2}^{\omega(G)-1}a_{i}(G)$

  2. (2)

If $m\geq n$, then reg $S/{\mathcal{J}_{G}}$=reg $S/{in_{<}(\mathcal{J}_{G})}$

  3. (3)

If $m<n$, then reg $S/{\mathcal{J}_{G}}\leq$ reg
$S/{in_{<}{\mathcal{J}_{G}}}\leq n-1$.

As a consequence, one can get similar statements for block graph, as we have
for block graph $a_{i}(G)=0,$ for all $i>1$. Since tree is a block graph, we
can have equivalent result of the theorem 6.2 for tree. For a path graph
regularity of generalized binomial edge ideal is the following

######  Theorem 6.3 ([7], Corollary 3.6).

Let $m,n\geq 2$. If $G$ is a path graph on the vertex set $[n]$, then

reg $S/{\mathcal{J}_{G}}$=reg $S/{in_{<}{(\mathcal{J}_{G})}}=n-1$.

Independently, in [39] author has given regularity bound for generalized
binomial edge ideal. The author has defined in the following way

Let $G_{1}$ and $G_{2}$ be graphs on the vertex set $[m]$ and $[n]$
respectively. Let $e=\\{i,j\\}\in E(G_{1})$, and $e^{{}^{\prime}}=\\{k,l\\}\in
E(G_{2})$. Assign $2$-minor
$p_{e,e^{{}^{\prime}}}=x_{i,k}x_{j,l}-x_{i,l}x_{j,l}$ to the pair
$(e,e^{{}^{\prime}})$. The binomial edge ideal of the pair $(G_{1},G_{2})$ is,

$J_{G_{1},G_{2}}=(p_{e,e^{{}^{\prime}}}:e\in E(G_{1}),e^{{}^{\prime}}\in
E(G_{2}))$.

The generalized binomial edge ideal of a graph $G$ is the binomial edge ideal
of the pair $(K_{m},G)$. When $m=2$, the ideal $J_{K_{2},G}=J_{G}$ is the
classical binomial edge ideal of $G$.

In [62], Madani and Kiani conjectured that, if $G$ is a graph on vertex set
$[n]$, then reg$(S/{J_{K_{m},G}})\leq$ min $\\{\binom{m}{2}c(G),e(G)\\}$,
where $c(G)$ denote the number of maximal cliques of $G$, and $e(G)$ denote
the number of edges in $G$. They have proved the conjecture for closed graphs.
In [39], author proved this conjecture for chordal graphs.

######  Theorem 6.4 ([39], Theorem 3.13).

Let $G$ be a connected chordal graph on the vertex set $[n]$. If $m<n$, then

$reg(S/J_{K_{m},G})\leq min\\{(m-1)c(G),n-1\\}$.

In [39], author computed regularity of generalized binomial edge ideal for
complete graph $K_{n}$.

######  Proposition 6.5 ([39], Proposition 3.3).

Let $G=K_{n}$. Then reg $(S/J_{K_{m},K_{n}})=min\\{m-1,n-1\\}$.

Also, for a connected graph $G$, in the same paper author obtained an upper
bound for the regularity of generalized binomial edge ideal.

######  Theorem 6.6 ([39], Theorem 3.6).

Let $G$ be a connected graph on vertex set $[n]$ and $m\geq 2$. Then

$reg(S/{J_{K_{m},G}})\leq n-1$.

For chordal graph, the upper bound for regularity is the following.

######  Theorem 6.7 ([39], Theorem 3.11).

Let $G$ be a connected chordal graph on the vertex set $[n]$. Then
reg$(S/J_{K_{m},G})\leq(m-1)c(G)$.

In [39], author conjectured for generalized binomial edge ideal for a
connected graph, for $m<n$.

######  Conjecture 6.8 ([39], Conjecture 3.15).

Let $G$ be a connected graph of vertex set $[n]$. Then

$reg(S/J_{K_{m},G})\leq min\\{(m-1)c(G),n-1\\}$, if $m<n$.

One can ask the following question for pair of a graphs $G_{1}$ and $G_{2}$.

######  Question 6.9 ([39], Question 3.16).

Let $G_{1}$ and $G_{2}$ be graphs on the vertex set $[m]$ and $[n]$
respectively. Then

$reg(S/J_{G_{1},G_{2}})\leq min\\{(m-1)c(G_{2}),(n-1)c(G_{1})\\}$.

In [7],[16], for some special cases unmixedness and Cohen-Macaulayness of
binomial edge ideal of a pair of graphs are characterized. It is well-known
that all Cohen-Macaulay ideal are unmixed. In [2], author characterizes all
the unmixed ideal $J_{G,m}$. Before that we will see the definition of power-
cycle.

Let $S\subseteq\\{1,2,\ldots,\lfloor\frac{n}{2}\rfloor\\}$. The circulant
graph $G=C_{n}(S)$ is a simple graph with
$V(G)=\mathbb{Z}_{n}=\\{1,2,\ldots,n-1\\}$ and $E(G=\\{\\{i,j\\}:|j-i|_{n}\in
S\\})$, where $|k|_{n}=min\\{|k|,n-|k|\\}$. $C_{n}(S)$ is the circulant graph
of order $n$ with generating set $S$ and $|k|_{n}$ is the circular distance
modulo $n$. It is known that if the generating set $S=\\{\pm 1,\pm
2,\ldots,\pm d\\}$, where $1\leq d\leq\lfloor\frac{n}{2}\rfloor$ is a given
integer, then the circulant graph $C_{n}(S)$ is equivalent to the $d$-th power
of $C_{n}$, where two vertices are adjacent if and only if their distance is
at most $d$. In this case, we will denote $C_{n}(S)$ by $C_{n}(1,2,\ldots,d)$,
and is called $d$th power-cycle.

######  Theorem 6.10 ([2], Theorem 3.14).

Let $G=C_{n}(1,2,\ldots,r)$ be a non-complete power-cycle. Then $J_{G,m}$ is
unmixed if and only if $m$ is odd, $n\in\\{m+1,\ldots,\frac{3m+1}{2}\\}$ and
$r=\frac{m-1}{2}$.

In the same paper the author characterizes when $J_{G,m}$ is Cohen-Macaulay.

######  Theorem 6.11 ([2], Corollary 4.3).

Let $J_{G,m}$ be a generalized binomial edge ideal with $m\geq 3$. Then
$J_{G,m}$ is Cohen-Macaulay if and only if $G$ is the complete graph.

##  7\. Other Binomial Edge Ideals

In this section, we will give an overview of other binomial ideals namely the
parity binomial edge ideal, the permanental edge ideal and the Lovasz-Saks-
Schrjiver ideal. In [33], the authors have given Gröbner basis for parity
binomial edge ideal $\mathcal{I}_{G}$, see Theorem 3.6 and minimal primes in
Theorem 4.15. Also they have proved when $\mathcal{I}_{G}$ is radical ideal.

######  Theorem 7.1 ([33], Theorem 5.5).

Let $G$ be a graph. If char$(K)\neq 2$, then $\mathcal{I}_{G}$ is a radical
ideal.

In the same article they have calculated primary decomposition of parity
binomial edge ideal. In [41], the author has given an alternative form of the
results from [9], for LSS ideals in terms of parity binomial edge ideal.

######  Theorem 7.2 ([41], Theorem 3.2).

Let $G$ be a bipartite graph on $[n]$. Then $L_{G}$ is complete intersection,
if and only if $\mathcal{I}_{G}$ is complete intersection, if and only if $G$
is a disjoint union of paths.

They have also characterized the non-bipartite graphs whose LSS ideals,
permanental edge ideal and parity binomial edge ideals are complete
intersection.

######  Theorem 7.3 ([41], Theorem 3.5).

Let $G$ be a non-bipartite graph on $[n]$. Then $L_{G}$ is complete
intersection, if and only if $G$ is an odd cycle, if and only if
$\mathcal{I}_{G}$ is complete intersection.

In the same article, they have computed projective dimension of the parity
binomial edge ideal of an odd unicyclic graphs.

######  Theorem 7.4 ([41], Theorem 4.4).

For a connected odd unicyclic graph on $[n]$, projective dimension of
$\mathcal{I}_{G}$ is pd$(S/\mathcal{I}_{G})=n$.

Next, they have computed second Betti number and first syzygy of LSS ideals of
trees.

######  Theorem 7.5 ([41], Theorem 5.1).

Let $G$ be a tree on $[n]$. Then

$\beta_{2}(S/L_{G})=\beta_{2,4}(S/L_{G})=\binom{n-1}{2}+\displaystyle\sum_{v\in
V(G)}\binom{deg_{G}(v)}{3}$.

######  Theorem 7.6 ([41], Theorem 5.2).

Let $G$ be a tree on $[n]$. If $\\{e_{\\{i,j\\}}:\\{i,j\\}\in E(G)\\}$ is
standard basis for $S^{n-1}$, then the first syzygy of $L_{G}$ is generated by
the following elements

  1. (1)

$g_{i,j}e_{\\{k,l\\}}-g_{k,l}e_{\\{i,j\\}}$, where $\\{i,j\\}\neq\\{k,l\\}\in
E(G)$ and

  2. (2)

$(-1)^{p_{A}(j)}f_{k,l}e_{\\{i,j\\}}+(-1)^{p_{A}(k)}f_{j,l}e_{\\{i,k\\}}+(-1)^{p_{A}(l)}f_{j,k}e_{\\{i,l\\}}$,
where $A=\\{i,j,k,l\\}\in\mathcal{C}_{G}$, with center at $i$.

Also, they have computed second Betti number and first syzygy of LSS ideals
for odd unicyclic graphs in Theorem 5.3 and 5.4. In [42], the author has given
upper bound for the regularity of parity binomial edge ideal of a graph and
for an odd cycle.

######  Theorem 7.7 ([42], Theorem 3.2).

Let $G$ be a connected bipartite graph on $n$-vertices. Then
reg$(S/\mathcal{I}_{G})\leq n-1$. Moreover, reg$(S/\mathcal{I}_{G})=n-1$, if
and only if $G$ is a path graph.

######  Theorem 7.8 ([42], Theorem 3.4).

Let $G=C_{n}$, where $n$ is odd. Then reg$(S/\mathcal{I}_{G})=n$.

In the next theorem, the author has characterized the graphs whose parity
binomial edge ideal have regularity three.

######  Theorem 7.9 ([42], Theorem 3.9).

Let $G$ be a graph on $n$-vertices with no isolated vertex. Then
reg$(S/\mathcal{I}_{G})=2$ if and only if either $G=K_{2}\sqcup K_{2}$ or $G$
is a complete bipartite graph other than $K_{2}$.

In the following theorem, the author has characterizes graphs whose parity
binomial edge ideal have pure resolution.

######  Theorem 7.10 ([42], Theorem 3.14).

Let $G$ be a graph on $n$-vertices. Then $S/\mathcal{I}_{G}$ has pure
resolution if and only if $G$ is one of the following

  1. (1)

$G$ is a complete bipartite graph.

  2. (2)

$G$ is a disjoint union of some odd cycles and some paths.

Let $H_{S/\mathcal{I}_{G}}$ be the Hilbert function of $S/\mathcal{I}_{G}$.
Then the Hilbert-Poincare series of the $S$-module $S/\mathcal{I}_{G}$ is

$HP_{S/\mathcal{I}_{G}}(t)=\displaystyle\sum_{i\geq
0}H_{S/\mathcal{I}_{G}}(i)t^{i}$.

From ([52], Theorem 16.2), the series has the following expression

$HP_{S/\mathcal{I}_{G}}(t)=\frac{P_{S/\mathcal{I}_{G}}(t)}{(1-t)^{n}}$.

$P_{S/\mathcal{I}_{G}}(t)$ is the Hilbert-Poincare polynomial of
$S/\mathcal{I}_{G}$ and has the following form

$P_{S/\mathcal{I}_{G}}(t)=\displaystyle\sum_{i=0}^{p}\sum_{j=0}^{p+r}(-1)^{i}\beta_{i,j}(S/\mathcal{I}_{G})t^{j}$.

In the following theorem the authors have calculated Hilbert-Poincare
polynomial of $S/\mathcal{I}_{K_{n}}$.

######  Theorem 7.11 ([11], Theorem 3.6).

The Hilbert-Poincare polynomial of $S/\mathcal{I}_{K_{n}}$ is

$P_{S/\mathcal{I}_{K_{n}}}(t)=2(1-t)^{n}+[-1+3t+(\frac{n^{2}+n-6}{2})t^{2}+(\frac{n^{2}-3n+2}{2})t^{3}](1-t)^{2n-3}$.

In particular, depth$(S/\mathcal{I}_{K_{n}})\geq 3$ and
reg$(S/\mathcal{I}_{K_{n}})\leq 3$.

Acknowledgement: The author is not funded by any authorities.

## References

  * [1] J. Àlvarez Montaner.  Local cohomology of binomial edge ideals and their generic initial ideals.  Collect. Math., 71(2):331–348, 2020.
  * [2] L. Amata, M. Crupi, and G. Rinaldo.  Generalized cohen-macaulay binomial edge ideals.  arXiv preprint arXiv:2112.15136, 2021.
  * [3] A. Banerjee and L. Núñez Betancourt.  Graph connectivity and binomial edge ideals.  Proc. Amer. Math. Soc., 145(2):487–499, 2017.
  * [4] D. Bayer, I. Peeva, and B. Sturmfels.  Monomial resolutions.  Math. Res. Lett., 5(1-2):31–46, 1998.
  * [5] D. Bolognini, A. Macchia, and F. Strazzanti.  Binomial edge ideals of bipartite graphs.  European J. Combin., 70:1–25, 2018.
  * [6] A. Boocher.  Free resolutions and sparse determinantal ideals.  Math. Res. Lett., 19(4):805–821, 2012.
  * [7] F. Chaudhry and R. Irfan.  On the generalized binomial edge ideals of generalized block graphs.  Math. Rep. (Bucur.), 22(72)(3-4):381–394, 2020.
  * [8] A. Conca, E. De Negri, and E. Gorla.  Cartwright-Sturmfels ideals associated to graphs and linear spaces.  J. Comb. Algebra, 2(3):231–257, 2018.
  * [9] A. Conca and V. Welker.  Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties.  Algebra Number Theory, 13(2):455–484, 2019.
  * [10] P. Das and H. Mukherjee.  The first syzygy of Hibi rings associated with planar distributive lattices.  Acta Math. Vietnam., 47(3):689–707, 2022.
  * [11] T. H. Do and T. Kahle.  Hilbert-Poincaré series of parity binomial edge ideals and permanental ideals of complete graphs.  Collect. Math., 72(3):471–479, 2021.
  * [12] V. Ene.  Syzygies of Hibi rings.  Acta Math. Vietnam., 40(3):403–446, 2015.
  * [13] V. Ene and J. Herzog.  On the symbolic powers of binomial edge ideals.  In Combinatorial structures in algebra and geometry, volume 331 of Springer Proc. Math. Stat., pages 43–50. Springer, Cham, [2020] ©2020.
  * [14] V. Ene, J. Herzog, and T. Hibi.  Cohen-Macaulay binomial edge ideals.  Nagoya Math. J., 204:57–68, 2011.
  * [15] V. Ene, J. Herzog, and T. Hibi.  Koszul binomial edge ideals.  In Bridging algebra, geometry, and topology, volume 96 of Springer Proc. Math. Stat., pages 125–136. Springer, Cham, 2014.
  * [16] V. Ene, J. Herzog, T. Hibi, and A. A. Qureshi.  The binomial edge ideal of a pair of graphs.  Nagoya Math. J., 213:105–125, 2014.
  * [17] V. Ene, G. Rinaldo, and N. Terai.  Licci binomial edge ideals.  J. Combin. Theory Ser. A, 175:105278, 23, 2020.
  * [18] R. González-Martínez.  Gorenstein binomial edge ideals.  Math. Nachr., 294(10):1889–1898, 2021.
  * [19] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, and J. Rauh.  Binomial edge ideals and conditional independence statements.  Adv. in Appl. Math., 45(3):317–333, 2010.
  * [20] J. Herzog, A. Macchia, S. Saeedi Madani, and V. Welker.  On the ideal of orthogonal representations of a graph in $\mathbb{R}^{2}$.  Adv. in Appl. Math., 71:146–173, 2015.
  * [21] J. Herzog and G. Rinaldo.  On the extremal Betti numbers of binomial edge ideals of block graphs.  Electron. J. Combin., 25(1):Paper No. 1.63, 10, 2018.
  * [22] T. Hibi, K. Kimura, and K. Matsuda.  Extremal Betti numbers of edge ideals.  Arch. Math. (Basel), 113(2):149–155, 2019.
  * [23] T. Hibi and S. S. Madani.  Diameter and connectivity of finite simple graphs.  arXiv preprint arXiv:2103.14260, 2021.
  * [24] T. Hibi and K. Matsuda.  Regularity and h-polynomials of binomial edge ideals.  Acta Mathematica Vietnamica, pages 1–6, 2021.
  * [25] M. Hochster.  Cohen-Macaulay rings, combinatorics, and simplicial complexes.  In Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975), pages 171–223. Lecture Notes in Pure and Appl. Math., Vol. 26, 1977.
  * [26] C. Huneke and B. Ulrich.  The structure of linkage.  Ann. of Math. (2), 126(2):277–334, 1987.
  * [27] A. Jayanthan and R. Sarkar.  Depth of binomial edge ideals in terms of diameter and graph connectivity.  arXiv preprint arXiv:2112.04835, 2021.
  * [28] A. V. Jayanthan and A. Kumar.  Regularity of binomial edge ideals of Cohen-Macaulay bipartite graphs.  Comm. Algebra, 47(11):4797–4805, 2019.
  * [29] A. V. Jayanthan, A. Kumar, and R. Sarkar.  Almost complete intersection binomial edge ideals and their Rees algebras.  J. Pure Appl. Algebra, 225(6):Paper No. 106628, 19, 2021.
  * [30] A. V. Jayanthan, N. Narayanan, and B. V. Raghavendra Rao.  Regularity of binomial edge ideals of certain block graphs.  Proc. Indian Acad. Sci. Math. Sci., 129(3):Paper No. 36, 10, 2019\.
  * [31] A. V. Jayanthan, N. Narayanan, and B. V. Raghavendra Rao.  An upper bound for the regularity of binomial edge ideals of trees.  J. Algebra Appl., 18(9):1950170, 7, 2019.
  * [32] T. Kahle and J. Krüsemann.  Binomial edge ideals of cographs.  arXiv preprint arXiv:1906.05510, 2019.
  * [33] T. Kahle, C. Sarmiento, and T. Windisch.  Parity binomial edge ideals.  J. Algebraic Combin., 44(1):99–117, 2016.
  * [34] D. Kiani and S. S. Madani.  The regularity of binomial edge ideals of graphs.  arXiv preprint arXiv:1310.6126, 2013.
  * [35] D. Kiani and S. Saeedi Madani.  Binomial edge ideals with pure resolutions.  Collect. Math., 65(3):331–340, 2014.
  * [36] D. Kiani and S. Saeedi Madani.  Some Cohen-Macaulay and unmixed binomial edge ideals.  Comm. Algebra, 43(12):5434–5453, 2015.
  * [37] D. Kiani and S. Saeedi Madani.  The Castelnuovo-Mumford regularity of binomial edge ideals.  J. Combin. Theory Ser. A, 139:80–86, 2016.
  * [38] A. Kumar.  Binomial edge ideals of generalized block graphs.  Internat. J. Algebra Comput., 30(8):1537–1554, 2020.
  * [39] A. Kumar.  Regularity bound of generalized binomial edge ideal of graphs.  J. Algebra, 546:357–369, 2020.
  * [40] A. kumar.  Binomial edge ideals and bounds for their regularity.  J. Algebraic Combin., 53(3):729–742, 2021.
  * [41] A. Kumar.  Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs.  European J. Combin., 93:Paper No. 103274, 19, 2021.
  * [42] A. Kumar.  Regularity of parity binomial edge ideals.  Proc. Amer. Math. Soc., 149(7):2727–2737, 2021.
  * [43] A. Kumar and R. Sarkar.  Hilbert series of binomial edge ideals.  Comm. Algebra, 47(9):3830–3841, 2019.
  * [44] A. Kumar and R. Sarkar.  Depth and extremal Betti number of binomial edge ideals.  Math. Nachr., 293(9):1746–1761, 2020.
  * [45] N. V. R. Mahadev and U. N. Peled.  Threshold graphs and related topics, volume 56 of Annals of Discrete Mathematics.  North-Holland Publishing Co., Amsterdam, 1995.
  * [46] M. R. Malayeri, S. S. Madani, and D. Kiani.  On the depth of binomial edge ideals of graphs.  arXiv preprint arXiv:2101.04703, 2021.
  * [47] C. Mascia and G. Rinaldo.  Krull dimension and regularity of binomial edge ideals of block graphs.  J. Algebra Appl., 19(7):2050133, 17, 2020.
  * [48] C. Mascia and G. Rinaldo.  Extremal Betti numbers of some Cohen-Macaulay binomial edge ideals.  Algebra Colloq., 28(3):415–430, 2021.
  * [49] K. Matsuda and S. Murai.  Regularity bounds for binomial edge ideals.  J. Commut. Algebra, 5(1):141–149, 2013.
  * [50] F. Mohammadi and L. Sharifan.  Hilbert function of binomial edge ideals.  Comm. Algebra, 42(2):688–703, 2014.
  * [51] M. Ohtani.  Graphs and ideals generated by some 2-minors.  Comm. Algebra, 39(3):905–917, 2011.
  * [52] I. Peeva.  Graded syzygies, volume 14 of Algebra and Applications.  Springer-Verlag London, Ltd., London, 2011.
  * [53] A. Rauf and G. Rinaldo.  Construction of Cohen-Macaulay binomial edge ideals.  Comm. Algebra, 42(1):238–252, 2014.
  * [54] J. Rauh.  Generalized binomial edge ideals.  Adv. in Appl. Math., 50(3):409–414, 2013.
  * [55] G. Rinaldo.  Cohen-Macauley binomial edge ideals of small deviation.  Bull. Math. Soc. Sci. Math. Roumanie (N.S.), 56(104)(4):497–503, 2013.
  * [56] G. Rinaldo.  Cohen-Macaulay binomial edge ideals of cactus graphs.  J. Algebra Appl., 18(4):1950072, 18, 2019.
  * [57] M. Rouzbahani Malayeri, S. Saeedi Madani, and D. Kiani.  Binomial edge ideals of small depth.  J. Algebra, 572:231–244, 2021.
  * [58] M. Rouzbahani Malayeri, S. Saeedi Madani, and D. Kiani.  A proof for a conjecture on the regularity of binomial edge ideals.  J. Combin. Theory Ser. A, 180:Paper No. 105432, 9, 2021.
  * [59] M. Rouzbahani Malayeri, S. Saeedi Madani, and D. Kiani.  Regularity of binomial edge ideals of chordal graphs.  Collect. Math., 72(2):411–422, 2021.
  * [60] S. Saeedi Madani.  Binomial edge ideals: a survey.  In Multigraded algebra and applications, volume 238 of Springer Proc. Math. Stat., pages 83–94. Springer, Cham, 2018.
  * [61] S. Saeedi Madani and D. Kiani.  Binomial edge ideals of graphs.  Electron. J. Combin., 19(2):Paper 44, 6, 2012.
  * [62] S. Saeedi Madani and D. Kiani.  On the binomial edge ideal of a pair of graphs.  Electron. J. Combin., 20(1):Paper 48, 13, 2013.
  * [63] S. Saeedi Madani and D. Kiani.  Binomial edge ideals of regularity 3.  J. Algebra, 515:157–172, 2018.
  * [64] P. Schenzel and S. Zafar.  Algebraic properties of the binomial edge ideal of a complete bipartite graph.  An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat., 22(2):217–237, 2014.
  * [65] R. H. Villarreal.  Rees algebras of edge ideals.  Comm. Algebra, 23(9):3513–3524, 1995.
  * [66] S. Zafar and Z. Zahid.  On the Betti numbers of some classes of binomial edge ideals.  Electron. J. Combin., 20(4):Paper 37, 14, 2013.


# Describe Data to get Science-Data-Ready Tooling: Awkward as a Target for
Kaitai Struct YAML

Manasvi Goyal1 Andrea Zonca2 Amy Roberts3 Jim Pivarski1 and Ianna Osborne1 1
Princeton University, Princeton, NJ 08544, USA  2 San Diego Supercomputer
Center, La Jolla, CA 92093, USA  3 University of Colorado Denver, Denver, CO
80204, USA

###### Abstract

In some fields, scientific data formats differ across experiments due to
specialized hardware and data acquisition systems. Researchers need to
develop, document, and maintain experiment-specific analysis software to
interact with these data formats. These software are often tightly coupled
with a particular data format. This proliferation of custom data formats has
been a prominent challenge for small to mid-scale experiments. The widespread
adoption of ROOT has largely mitigated this problem for the Large Hadron
Collider experiments. However, many smaller experiments continue to use custom
data formats to meet specific research needs. Therefore, simplifying the
process of accessing a unique data format for analysis holds immense value for
scientific communities within HEP. We have added Awkward Arrays as a target
language for Kaitai Struct for this purpose.

Researchers can describe their custom data format in the Kaitai Struct YAML
(KSY) language. The Kaitai Struct Compiler generates C++ code to fill the
LayoutBuilder buffers using the KSY format. In a few steps, the Kaitai Struct
Awkward Runtime API can convert the generated C++ code into a compiled Python
module. Finally, the raw data can be passed to the module to produce Awkward
Arrays. This paper introduces the Awkward Target for the Kaitai Struct
Compiler and the Kaitai Struct Awkward Runtime API. It also demonstrates the
conversion of a given KSY for a specific custom file format to Awkward Arrays.

##  1 Introduction

Collaborations that use a custom data format spend many hours writing their
own tools to read and analyze their data. It is difficult to fund such tools
because they are not usable outside the collaboration, and as a result,
maintenance is difficult, leading to poor documentation and testing. It also
poses a significant barrier for scientists entering the collaboration and
those wishing to perform analysis outside what the original author envisioned.

Switching to a supported standard data format sounds like an obvious solution.
However, in the case of the Cryogenic Dark Matter Search Collaboration [1, 2],
for example, this would require substantial rewriting of the data acquisition
system or switching to a different one. This would require additional
personnel and substantial time investment. In addition, there are legacy
datasets that still have the potential for new science. This project provides
a solution to this problem of reading and analyzing custom data formats for
small and mid-scale collaborations across the sciences. Instead of developing
their own tools, the collaborations need to describe their custom data formats
in KSY format just once and then directly use the Kaitai Struct Awkward
Runtime to access their data as Awkward Arrays [3].

##  2 Kaitai Struct YAML

Kaitai-Struct YAML (KSY) [4] is a declarative language that takes YAML-like
descriptions of a data-format structure and generates parsing code in any of
the supported languages. The user describes the structure of the data, not how
to read or write it. KSY can describe a wide variety of file types, including
image formats, network stream packet formats, and binary formats.

###  2.1 An overview of Kaitai Struct

The user describes their data structure in a ‘.ksy‘ description file using
Kaitai Struct format rules [5]. The Kaitai Struct Web IDE can be used to debug
the format and ensure that the data is parsed properly. The user then compiles
the description file with the Kaitai Struct Compiler [6] to create importable
libraries in a specified target language. These libraries include generated
code for a parser, which can be included in any external project, to read the
described data structure from a file or stream. The Kaitai Struct Compiler
uses an extra layer of stream API to access the data to allow compilation to
many target languages. This API includes Kaitai Struct runtime libraries for
the respective languages used. Kaitai Struct currently supports twelve target
languages including C++, Python, and Java. Figure 1 shows the process of
conversion of a data structure to importable libraries of the supported target
languages.

Figure 1: Kaitai Struct YAML process flowchart. Figure 2: AnimalData Example
a) Data structure; b) An animal entry in binary; c) animal.ksy

###  2.2 Example: animalData

Take a simple data structure, as shown in Figure 2(a), containing multiple
entries for animals, and each entry describes some details of the particular
animal. The actual format of the binary file is slightly more complicated.
Take an example with just one entry to illustrate this, as shown in Figure
2(b). The first byte of this entry contains an integer value denoting the
number of letters in the species name. The next N-bytes are ASCII values that
represent the species name. After the ASCII characters, there is one byte for
the animal’s age and, finally, two bytes for the weight. Fields larger than
one byte are written in little-endian format, in this case, just the weight.
The given entry describes a 6-year-old cow that weighs 1500 pounds. This data
structure can be described in KSY as shown in Figure 2(c).

Everything in KSY starts with a `meta` section. It contains the top-level
information about the entire structure. The most information in `meta`
includes `id` which specifies the name of the structure and `endian` which
specifies default endianness. After this section, the data structure is
described using the `seq` element to describe the attributes of the specific
structure. Every attribute includes several keys, namely, `id` which
represents the attribute a name, and `type` which designates the attribute
type. Most real-life file formats do not contain only one copy of some element
but might contain several copies, i.e., they repeat the same pattern over and
over. Kaitai Struct supports the following types of repetition:

  * •

eos: element repeated up to the very end of the stream.

  * •

repeat-expr: element repeated a pre-defined number of times.

  * •

repeat-until: element repeated while some condition is not satisfied or until
it becomes true.

##  3 Awkward Arrays

The `animal.ksy` is a simple example, but actual scientific data can be
significantly larger with a complex structure. An example is the MIDAS event
format [7], which wraps a complex but fixed binary structure with a header and
footer that contain information about the length of that structure. Other
scientific formats, such as the octree representations for variable-resolution
data, have even more complex structures. The `kaitai_struct_python_runtime`
library, for example, stores all data structures as a dictionary. While this
is a familiar interface to many users, it is also extremely slow for files
even in the MB range.

Awkward arrays, a Scikit-HEP [8] library, offer a powerfully dynamic and
efficient approach to represent complex data structures in Numpy-like arrays
[9, 10]. They store data in jagged nested arrays of arbitrary types and
variable lengths while maintaining speed [11]. These capabilities make Awkward
an appealing target language for Kaitai Struct. Therefore, the C++ header-only
`LayoutBuilder` [12] libraries of Awkward Array are used to represent the
scientific data formats in Numpy-like arrays.

##  4 Awkward Target for KSY

The objective is to combine the features of Awkward with the Kaitai Struct
ecosystem. Awkward target has been added to `kaitai_struct_compiler` as an
`AwkwardCompiler` to adapt the existing `CppCompiler` to build Awkward arrays.
The user only needs to focus on describing their particular data structure
into `’.ksy’` format. They have to do this only once for a specific format.
The entire code generation is handled by the `kaitai_struct_awkward_runtime`
[13]. With a few simple commands, the user can load their raw data file in the
Python module to represent their data in well-structured Awkward Arrays.

Figure 3: Kaitai Struct C++ Runtime vs Kaitai Struct Awkward Runtime

###  4.1 Kaitai Struct Awkward Runtime User Interface

As shown in Figure 3, the user always starts by describing their data
structure in KSY format. Then, use `kaitai_struct_compiler` with the desired
target language to generate the modules that parse the KSY file. When users
generate code with C++ target, they must write a `main()` function to access
the data, which can be time consuming when dealing with complex scientific
data. However, when the user generates the parsing code with the Awkward
target, containing `LayoutBuilder` filling instructions [14], they can load
the generated shared library (.so) and the raw data into Awkward Arrays in a
Python environment and can immediately start writing their analysis code.

Figure 4: KSY data structure as LayoutBuilder.

###  4.2 Procedure to use Kaitai Struct Awkward Runtime

The `kaitai_struct_awkward_runtime` repository contains the step-by-step
procedure [13] to use the Kaitai Struct Awkward Runtime to generate Awkward
arrays for a given KSY file. Once the user has installed the required
dependencies, they can use the `kaitai-struct-compilper` tool to generate the
parsing code for `awkward` target. Figure 4 shows the representation of the
KSY structure in LayoutBuilder code using the example in Section 2.2. The
generated LayoutBuilder code can be compiled into a shared library using a
`awkward-kaitai-build` command with the required command line options.

The procedure involves the installation of the `awkward-kaitai` module using
`pip` to enable the integration of LayoutBuilder C++ code with Python via
ctypes allowing dynamic linking and execution through the generated shared
library. The `awkward-kaitai` package provides the necessary Python tools to
connect the data structures of the parsing code with Awkward Array operations.

Now, the user can open the Python terminal and import the `awkward_kaitai`
module. They can pass the path of the generated static library to the `Reader`
class and then pass the path of the raw data file to the `load` function to
fill the Awkward array layout with the raw data. Finally, the generated
`ak.Array` can be printed or used for further analysis. An example of the
Python terminal steps using the `animal.ksy` is as follows.

    import awkward_kaitai
    animal = awkward_kaitai.Reader("./src-animal/libanimal.so")
    awkward_array = animal.load("example_data/data/animal.raw")
    awkward_array.to_list()

Finally, `animal.ksy` is represented in Awkward Arrays as:

    [{’animalA__Zentry’:[
        {’animal_entryA__Zstr_len’: 3, ’animal_entryA__Zspecies’: ’cat’,
        ’animal_entryA__Zage’: 5, ’animal_entryA__Zweight’: 12},
        {’animal_entryA__Zstr_len’: 3, ’animal_entryA__Zspecies’: ’dog’,
        ’animal_entryA__Zage’: 3, ’animal_entryA__Zweight’: 43},
        {’animal_entryA__Zstr_len’: 6,’animal_entryA__Zspecies’: ’turtle’,
        ’animal_entryA__Zage’: 10, ’animal_entryA__Zweight’: 5}
    ]}]

##  5 Conclusion

Awkward Target for Kaitai Struct provides a promising solution for custom
scientific data formats in small to mid-scale experiments. It leverages the
descriptive power and ecosystem of the Kaitai Struct and combines it with the
features of Awkward Arrays. Researchers can easily convert the KSY
descriptions of their custom data formats into analysis-ready code using the
Kaitai Struct Awkward Runtime API. This approach holds the potential to
benefit various scientific disciplines, within and beyond HEP.

##  6 Acknowledgment

This work is supported by NSF cooperative agreements OAC-1836650 and
PHY-2323298 (IRIS-HEP) and grants OAC-2104003 (PONDD) and OAC-2103945 (Awkward
Array).

## References

## References

  * [1] Agnese R et al 2019 Search for low-mass dark matter with CDMSlite using a profile likelihood fit Phys. Rev. D `https://doi.org/10.1103/PhysRevD.99.062001`
  * [2] Albakry M F et al 2023 A strategy for low-mass dark matter searches with cryogenic detectors in the SuperCDMS SNOLAB facility Phys. Rev. D `https://doi.org/10.48550/arXiv.2203.08463`
  * [3] Pivarski J, Osborne I, Ifrim I, Schreiner H, Hollands A, Biswas A, Das P, Roy Choudhury S, Smith N and Goyal M 2018 Awkward Array [Computer software] Zenodo `https://doi.org/10.5281/zenodo.4341376`
  * [4] Kaitai Struct `https://kaitai.io/`
  * [5] Serialization guide of Kaitai Struct `https://doc.kaitai.io/serialization.html`
  * [6] Kaitai Struct Compiler `https://github.com/kaitai-io/kaitai_struct_compiler`
  * [7] Ritt S, Amaudruz P A 1999 New components of the MIDAS data acquisition system IEEE Conference on Real-Time Computer Applications in Nuclear Particle and Plasma Physics `https://doi.org/10.1109/RTCON.1999.842578`
  * [8] Rodrigues E 2019 The Scikit-HEP project EPJ Web Conf. 214 06005 `https://doi.org/10.1051/epjconf/201921406005`
  * [9] Harris C R et al 2020 Array programming with NumPy Nature 585 357–362. `https://doi.org/10.1038/s41586-020-2649-2`
  * [10] Pivarski J, Osborne I, Das P, Biswas A and Elmer P 2020 Awkward Array: JSON-like data, NumPy-like idioms Proc. of the 19th Python in Science Conf. (SCIPY 2020) 78-84
  * [11] Pivarski J, Elmer P and Lange D 2020 Awkward Arrays in Python, C++, and Numba EPJ Web Conf. 245 05023 `https://doi.org/10.1051/epjconf/202024505023`
  * [12] Goyal M, Osborne I, Pivarski J 2022 The awkward world of python and c++. it Advanced Computing and Analysis Techniques in Physics Research Workshop `https://doi.org/10.48550/arXiv.2303.0220`
  * [13] Kaitai Struct Awkward Runtime `https://github.com/det-lab/kaitai_struct_awkward_runtime`
  * [14] Goyal M 2023 Awkward target for kaitai struct PyHEP 2023 Workshop Zenodo `https://doi.org/10.5281/zenodo.10001237`