%%%%%%%%%%%%%%%%%%%% March 29 , 2012 %%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Preprinted version %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass{amsart} \usepackage{amsmath,amssymb,amsfonts,enumerate,amsthm,graphicx,color} %\em %------ GENERAL MACROS ----- % Standard rings and fields, affine and projective space % \def\NZQ{\Bbb} % the font for N,Z,Q,R,C \def\NN{{\NZQ N}} \def\QQ{{\NZQ Q}} \def\ZZ{{\NZQ Z}} \def\RR{{\NZQ R}} \def\CC{{\NZQ C}} \def\AA{{\NZQ A}} \def\PP{{\NZQ P}} \def\FFF{{\NZQ F}} \def\TT{{\NZQ T}} % %------------------------------------------------ % Symbols in "Fraktur" % \def\frk{\frak} % font for "Fraktur" \def\aa{{\frk a}} \def\pp{{\frk p}} \def\Pp{{\frk P}} \def\qq{{\frk q}} \def\Qq{{\frk Q}} \def\mm{{\frk m}} \def\Mm{{\frk M}} \def\nn{{\frk n}} \def\Nn{{\frk N}} % %------------------------------------------------ % Small letters in bold % \def\ab{{\bold a}} \def\bb{{\bold b}} \def\xb{{\bold x}} \def\yb{{\bold y}} \def\zb{{\bold z}} % \def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators %------------------------------------------------ % Numerical invariants of rings, ideals, and modules % \opn\chara{char} \opn\length{\ell} \opn\pd{pd} \opn\rk{rk} \opn\projdim{proj\,dim} \opn\injdim{inj\,dim} \opn\rank{rank} \opn\depth{depth} \opn\grade{grade} \opn\height{height} \opn\embdim{emb\,dim} \opn\codim{codim} \def\OO{{\cal O}} \opn\Tr{Tr} \opn\bigrank{big\,rank} \opn\superheight{superheight}\opn\lcm{lcm} \opn\trdeg{tr\,deg}% \opn\reg{reg} \opn\lreg{lreg} \opn\skel{skel} \opn\multideg{multideg} %------------------------------------------------ % Divisors % \opn\div{div} \opn\Div{Div} \opn\cl{cl} \opn\Cl{Cl} % %------------------------------------------------ % Subsets of the spectrum of a ring % \opn\Spec{Spec} \opn\Supp{Supp} \opn\supp{supp} \opn\Sing{Sing} \opn\Ass{Ass} % %------------------------------------------------ % Standard operations on ideals and modules % \opn\Ann{Ann} \opn\Rad{Rad} \opn\Soc{Soc} % %------------------------------------------------ % Linear algebra and homology, endo- and automorphisms % \opn\Ker{Ker} \opn\Coker{Coker} \opn\Im{Im} \opn\Hom{Hom} \opn\Tor{Tor} \opn\Ext{Ext} \opn\End{End} \opn\Aut{Aut} \opn\id{id} \def\Frob{{\cal F}} \opn\nat{nat} \opn\pff{pf}% \pf exists already \opn\Pf{Pf} \opn\GL{GL} \opn\SL{SL} \opn\mod{mod} \opn\ord{ord} % %------------------------------------------------ % Convexity % \opn\aff{aff} \opn\con{conv} \opn\relint{relint} \opn\st{st} \opn\lk{lk} \opn\cn{cn} \opn\core{core} \opn\vol{vol} \opn\link{link} \opn\star{star} \opn\skel{skel} \opn\Reg{Reg} %------------------------------------------------ % Graded rings and Rees algebras \opn\gr{gr} \def\Rees{{\cal R}} % %------------------------------------------------ % Polynomials and power series % \def\poly#1#2#3{#1[#2_1,\dots,#2_{#3}]} \def\pot#1#2{#1[\kern-0.28ex[#2]\kern-0.28ex]} \def\Pot#1#2#3{\pot{#1}{#2_1,\dots,#2_{#3}}} \def\konv#1#2{#1\langle #2\rangle} \def\Konv#1#2#3{\konv{#1}{#2_1,\dots,#2_{#3}}} % %------------------------------------------------ % Direct and inverse limits % \opn\dirlim{\underrightarrow{\lim}} \opn\inivlim{\underleftarrow{\lim}} % % % Names with a meaning % \let\union=\cup \let\sect=\cap \let\dirsum=\oplus \let\tensor=\otimes \let\iso=\cong \let\Union=\bigcup \let\Sect=\bigcap \let\Dirsum=\bigoplus \let\Tensor=\bigotimes % %------------------------------------------------ % \let\to=\rightarrow \let\To=\longrightarrow \def\Implies{\ifmmode\Longrightarrow \else \unskip${}\Longrightarrow{}$\ignorespaces\fi} \def\implies{\ifmmode\Rightarrow \else \unskip${}\Rightarrow{}$\ignorespaces\fi} \def\iff{\ifmmode\Longleftrightarrow \else \unskip${}\Longleftrightarrow{}$\ignorespaces\fi} \let\gets=\leftarrow \let\Gets=\longleftarrow \let\followsfrom=\Leftarrow \let\Followsfrom=\Longleftarrow \let\:=\colon % % % \newtheorem{thm}{Theorem}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{defn}[thm]{Definition} \newtheorem{exas}[thm]{Examples} \newtheorem{exam}[thm]{Example} \newtheorem{rem}[thm]{Remark} \newtheorem{ques}[thm]{Question} \newtheorem{lthm}[thm]{\underline{Theorem}} \newtheorem{ldefn}[thm]{\underline{Definition}} \newtheorem{lcor}[thm]{\underline{Corollary}} \newtheorem{lprop}[thm]{\underline{Proposition}} \numberwithin{equation}{section} \def\mapdown#1{\Big\downarrow\rlap {$\vcenter{\hbox{$\scriptstyle#1$}}$}} \begin{document} \bibliographystyle{amsplain} %\date{} \title{Binomial edge ideals of graphs } \author{Sara Saeedi Madani and Dariush Kiani } \thanks{2010 \textit{Mathematics Subject Classification.} 13C05, 16E05, 05E40.} \thanks{\textit{Key words and phrases.} Binomial edge ideals, Linear resolutions, Castelnuovo-Mumford regularity. } \address{Sara Saeedi Madani, Department of Pure Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran.} \email{sarasaeedi@aut.ac.ir} \address{Dariush Kiani, Department of Pure Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.} \email{dkiani@aut.ac.ir} \begin{abstract} We characterize all graphs whose binomial edge ideals have a linear resolution. Indeed, we show that complete graphs are the only graphs with this property. We also compute some graded components of the first Betti number of the binomial edge ideal of a graph with respect to the graphical terms. Finally, we give an upper bound for the Castelnuovo-Mumford regularity of the binomial edge ideal of a closed graph. \end{abstract} \maketitle \section*{ Introduction } \noindent Binomial edge ideals of graphs were introduced in \cite{HHHKR}. Let $G$ be a finite simple graph with vertex set $V(G)=\{v_1,\ldots,v_n\}$ and edge set $E(G)$. Also, let $S=k[x_1,\ldots,x_n,y_1,\ldots,y_n]$ be the polynomial ring over a field $k$. Then the \textbf{binomial edge ideal} of $G$ in $S$, denoted by $J_G$, is generated by binomials of the form $f_{ij}=x_iy_j-x_jy_i$, where $i \cdots >x_n>y_1>\cdots >y_n$. These graphs are called \textbf{closed} graphs. In \cite{EHH}, the authors studied the depth of classes of binomial edge ideals and classified all closed graphs whose binomial edge ideals are Cohen-Macaulay. Associated to the graph $G$ is a monomial ideal $I(G)=(x_{i}x_{j} : \{v_{i},v_{j}\}\in E(G)),$ in the polynomial ring $R=k[x_{1},\ldots ,x_{n}]$ over a field $k$, called the \textbf{edge ideal} of $G$. In \cite{F}, Fr\"oberg characterized all graphs whose edge ideals have a linear resolution. He showed that $I(G)$ has a linear resolution if and only if the complementary graph $\overline{G}$ is chordal. It is natural to ask a similar question about the binomial edge ideal of a graph. More precisely, one could ask wether there is a graphical characterization for binomial edge ideals to have a linear resolution or not. In this paper, we give the positive answer to this question. Actually, in Section $1$, we prove that $J_G$ has a linear resolution if and only if $J_G$ has linear relations if and only if $G$ is a complete graph. Moreover, it is well-known that if in$_<(J_G)$ has a linear resolution, then $J_G$ does too. Here, we show that the converse is also true. In addition, we show that these conditions are equivalent to the condition that $\mathrm{in}_<(J_G)$ is generated in degree $2$ and has linear quotients. Also, in this section, we determine some Betti numbers of the binomial edge ideal of a graph. Precisely, we show that $\beta_{1,3}(J_G)=2k_3(G)$, where $k_3(G)$ is the number of triangles of $G$. Moreover, we show that if $G$ is a non-complete connected graph, then $\beta_{1,4}(J_G)\neq 0$. In Section $2$ of this paper, we give an upper bound for the Castelnuovo-Mumford regularity of the binomial edge ideal of a closed graph, by using corresponding results for edge ideals. Indeed, we show that the regularity of the binomial edge ideal of a closed graph $G$ is less than or equal to $c(G)+1$, where $c(G)$ is the number of maximal cliques of $G$. Throughout the paper, we mean by a graph $G$, a simple graph with the vertex set $V(G)$ and edge set $E(G)$, with no isolated vertices. Also, by $<$, we mean the lexicographic order induced by $x_1> \cdots >x_n>y_1>\cdots >y_n$. \section{ Binomial edge ideals with linear resolutions } \noindent In this section, we study the graded Betti numbers $\beta_{1,3}(J_G)$ and $\beta_{1,4}(J_G)$, and we characterize all graphs whose binomial edge ideals have a linear resolution. The following theorem is the main theorem of this section. \begin{thm}\label{linear} Let $G$ be a graph. Then the following conditions are equivalent:\\ {\em{(a)}} $J_G$ has a linear resolution.\\ {\em{(b)}} $J_G$ has linear relations.\\ {\em{(c)}} $\mathrm{in}_<(J_G)$ is generated in degree 2 and has linear quotients.\\ {\em{(d)}} $\mathrm{in}_<(J_G)$ has a linear resolution.\\ {\em{(e)}} $G$ is a complete graph.\\ \end{thm} To prove this theorem, we need some facts that we will mention in the sequel. We denote the number of triangles (i.e. 3-cycles) of a graph $G$, by $k_3(G)$. In the next result, we determine the first initial Betti number of the binomial edge ideal of a graph: \begin{thm}\label{Betti} Let $G$ be a graph. Then we have\\ {\em{(a)}} $\beta_{1,3}(J_G)=2k_3(G)$.\\ {\em{(b)}} $\beta_{1,4}(J_G)\neq 0$, if $G$ is non-complete and connected.\\ {\em{(c)}} $\beta_{i,j}(J_G)= 0$, for $j>2i$, if $G$ is closed. In particular, $\beta_{1,j}(J_G)= 0$, for $j\neq 3,4$, if $G$ is closed.\\ {\em{(d)}} $\beta_{i,j}(J_G)= 0$, for $j>2n$. \end{thm} \begin{proof} (a) Suppose that $$\cdots \longrightarrow S^{|E(G)|}(-2)\stackrel{\psi}{\longrightarrow} S\longrightarrow S/J_G\longrightarrow 0$$ is the minimal graded free resolution of $S/J_G$, in which $\psi(e_{ij})=f_{ij}$. We first observe that $J_G$ is $\mathbb{Z}^n$-graded, if we set deg$(x_i)=$deg$(y_i)=\varepsilon_i$, where $\varepsilon_i$ denotes the $i$-th canonical basis vector of $\mathbb{Z}^n$. Thus, deg$e_{ij}=$deg$f_{ij}$. Let $Z_1$ be the relation module of $J_G$, and consider a relation $r=\sum g_{ij}e_{ij}$ of degree $3$ (in the standard grading), that is, an element in $Z_1'={(Z_1)}_{3}$. Since $J_G$ is $\mathbb{Z}^n$-graded, it follows that $Z_1'$ is also $\mathbb{Z}^n$-graded, and hence is generated by multihomogeous elements. Thus we may assume that $r$ is multihomogeneous, say of degree $a\in \mathbb{Z}^n$. Then all nonzero summands $g_{ij}e_{ij}$ are of degree $a$, in which $|a|=3$ (here $|a|$ is the sum of the components of $a$). Let $g_{ij}e_{ij} \neq 0$. Then $a=$deg$(g_{ij})+\varepsilon_i+\varepsilon_j$. Therefore, deg$(g_{ij})=\varepsilon_k$ for some $k$. If $k=i$ or $k=j$, then there is only one summand in $r$ with this multidregree and $r$ can not be a relation. If $k\neq i,j$, then $r$ has exactly three summands and hence $r=g_{ij}e_{ij}+g_{ik}e_{ik}+g_{jk}e_{jk}$. Thus $r$ is a relation of the ideal $(f_{ij},f_{ik},f_{jk})$, which is the ideal of $2$-minors of the matrix $\begin{bmatrix} x_i & x_j & x_k \\ y_i & y_j & y_k \end{bmatrix}$. So, the generating relations are $x_ke_{ij}-x_je_{ik}-x_ie_{jk}$ and $y_ke_{ij}-y_je_{ik}-y_ie_{jk}$, by Hilbert-Burch theorem.\\ (b) Since $G$ is not complete, it contains a path over three vertices, as an induced subgraph. Let $\{v_i,v_j,v_k\}$ be the vertices of this induced subgraph of $G$ with edges $\{v_i,v_j\}$ and $\{v_j,v_k\}$. We may assume that $i0$. Note that the relation $r$ has multidegree $\varepsilon_i+2\varepsilon_j+\varepsilon_k$. If it is not a minimal relation, it must be reduced by generating relations of degree $3$. Since their multidegree is of the form $\varepsilon_s+\varepsilon_t+\varepsilon_l$, only relations of multidegree $\varepsilon_i+\varepsilon_j+\varepsilon_k$ can be in expression of $r$. But, this is impossible, since the path with edges $\{v_i,v_j\}$ and $\{v_j,v_k\}$ is an induced subgraph of $G$, so that $\{v_i,v_k\}$ is not an edge of $G$. \\ (c) Notice that if $G$ is a closed graph, then we have $\mathrm{in}_{<}(J_G)=(x_iy_j~:~i2i$, by \cite[Lemma 2.2]{Ka}.\\ (d) By \cite[Theorem 2.1]{HHHKR}, in$_<(J_G)$ is a squarefree monomial ideal in $S$. Thus, the result follows by Hochster's formula, since $\beta_{i,j}(J_G)\leq \beta_{i,j}(\mathrm{in}_{<}(J_G))$. \end{proof} \begin{cor}\label{bipartite} If $k_3(G)=0$, then $\beta_{i,i+2}(J_G)=0$, for all $i$. In particular, for any bipartite graph $G$, one has $\beta_{i,i+2}(J_G)=0$, for all $i$. \end{cor} \begin{rem}\label{conj} {\em Whenever $G$ is a closed graph, we use \textbf{consecutive cancellations} to show that $\beta_{1,3}(J_G)=\beta_{1,3}(\mathrm{in}_<(J_G))=2k_3(G)$. Actually, we have $\beta_{0,3}(J_G)=\beta_{0,3}(\mathrm{in}_<(J_G))=0$ and $\beta_{2,3}(J_G)=\beta_{2,3}(\mathrm{in}_<(J_G))=0$, by minimality of the free resolutions. On the other hand, by \cite[Theorem 22.12]{P}, the sequence of graded Betti numbers of $J_G$ is obtained from the sequence of graded Betti numbers of $\mathrm{in}_{<}(J_G)$ by \textbf{consecutive cancellations}. So, we have $\beta_{1,3}(J_G)=\beta_{1,3}(\mathrm{in}_<(J_G))$. A sequence $q_{i,j}$ of numbers is said to be obtained from a sequence $p_{i,j}$ by a consecutive cancellation if there exist indices $s$ and $r$ such that $q_{s,r}=p_{s,r}-1$, $q_{s+1,r}=p_{s+1,r}-1$ and $q_{i,j}=p_{i,j}$ for all other values of $i,j$. Note that, more generally, in \cite{EHH}, the authors conjectured that for a closed graph $G$, all the graded Betti numbers of $J_G$ and in$_<(J_G)$ coincide.} \end{rem} \begin{rem}\label{Betti-nonclosed} {\em The third part of Theorem \ref{Betti} may not be true without the assumption that $G$ is closed. For example, consider the cycle over five vertices, $C_5$, which is not closed. One can see by \textit{CoCoA} that $\beta_{1,5}(J_{C_5})=4$. More generally, according to our computations by \textit{CoCoA}, it seems that $r=\sum_{i=1}^n(\frac{y_1\cdots y_n}{y_iy_{i+1}})e_{i,i+1}$ is a minimal relation of degree $n$ of $J_{C_n}$, for all $n$. So that $\beta_{1,n}(J_{C_n})\neq 0$, for all $n$. } \end{rem} Now, recall that a homogeneous ideal $I$ whose generators all have degree $d$ is said to have a \textbf{$d$-linear resolution} (or simply linear resolution) if for all $i\geq0$, $\beta_{i,j}(I)=0$ for all $j\neq{i+d}$. Also, a graded ideal $I$ is said to have \textbf{linear quotients}, if there exists a minimal system of homogeneous generators $g_1,g_2,\ldots,g_m$ of $I$ such that the colon ideal $(g_1,\ldots,g_{i-1}):g_i$ is generated by linear forms for all $i$. \\ Now, we are ready to prove Theorem \ref{linear}.\\ {\em Proof of Theorem \ref{linear}.} (a) $\Rightarrow$ (b) is trivial, (c) $\Rightarrow$ (d) follows by \cite[Proposition 8.2.1]{HH}, and (d) $\Rightarrow$ (a) follows by \cite[Corollary 3.3.3]{HH}.\\ (b) $\Rightarrow$ (e) Note that $G$ is a connected graph, since $J_G$ has linear relations. Now, suppose on the contrary that $G$ is not complete. Assume that $H$ is a maximal clique of $G$. So, $G$ has a vertex $v_k$ which is not in $H$ and is adjacent to a vertex $v_j$ of $H$, since $G$ is connected. Moreover, there is a vertex of $H$, say $v_i$, which is non-adjacent to $v_k$, because $H$ is a maximal clique. So, the induced subgraph of $G$ on $\{v_i,v_j,v_k\}$ is a path over $3$ vertices. Thus, by Theorem \ref{Betti}, we have $\beta_{1,4}(J_G)>0$, which is a contradiction, since $J_G$ has linear relations. Therefore, $G$ is a complete graph.\\ (e) $\Rightarrow$ (c) Suppose that $G$ is complete. Then $\mathrm{in}_{<}(J_G)$ has ${n\choose 2}$ quadratic square-free minimal generators, more precisely, we have $$\mathrm{in}_{<}(J_G)=(x_sy_{m_s}~:~1\leq s\leq n-1~,~s+1\leq m_s\leq n),$$ since $G$ is closed. We order the generators by the lexicographic order with $x_1>x_2>\cdots >x_n>y_1>y_2>\cdots >y_n$. So, we have $$x_1y_2>x_1y_3>\cdots >x_1y_n>x_2y_3>x_2y_4>\cdots >x_2y_n>\cdots >x_{n-1}y_n.$$ We consider $u_1,\ldots,u_{{n\choose 2}}$, the generators of in$_<(J_G)$, as above, that is $u_1>\ldots>u_{{n\choose 2}}$. We should show that for each $i$, the ideal $(u_1,\ldots,u_{i-1}):u_i$ is generated by a set of variables. Note that the set $\{\frac{u_j}{\mathrm{gcd}(u_j,u_i)}~:~1\leq j\leq i-1\}$ is a set of monomial generators of $(u_1\ldots,u_{i-1}):u_i$. It is enough to consider two following cases. For each $1\leq l\leq n-2$, the ideal $(x_1y_2,\ldots,x_1y_n,x_2y_3\ldots,x_2y_n,\ldots,x_ly_{l+1},\ldots, x_ly_n):x_{l+1}y_{l+2}$ is generated by the set $\{x_1,\ldots,x_l\}$. Also, for each $1< l\leq n-2$ and $l\le t\leq n$, the ideal $(x_1y_2,\ldots,x_1y_n,x_2y_3\ldots,x_2y_n,\ldots,x_ly_{l+1},\ldots, x_ly_t):x_{l}y_{t+1}$ is generated by the set $\{x_1,\ldots,x_{l-1},y_{l+1},\ldots,y_t\}$. Thus, $J_G$ has linear quotients. $~~~\Box$ \section{ The castelnuovo-mumford regularity of binomial edge ideals } \noindent In this section, we focus on the Castelnuovo-Mumford regularity of the binomial edge ideals of graphs. Actually, we give an upper bound for the regularity of the binomial edge ideal of a connected closed graph. In order to prove the main theorem of this section, we need some facts which we will mention in the following. A graph $G$ is \textbf{chordal} if every induced cycle in $G$ has length $3$, and $G$ is \textbf{co-chordal} if the complement graph $\overline{G}$ is chordal. The \textbf{co-chordal cover number} of a graph $G$, denoted by cochord$(G)$, is the minimum number of subgraphs $H_1,\ldots,H_s$ of $G$ such that every $H_i$ is cochordal and $\bigcup_{i=1}^s E(H_i)=E(G)$. In \cite{W}, Woodroofe gave an upper bound for the regularity of the edge ideal of a graph. Indeed, he showed: \begin{thm}\label{cochord} \cite[Theorem 11]{W} For any graph $G$, we have $\mathrm{reg}(I(G))\leq \mathrm{cochord}(G)+1$. \end{thm} We denote by $c(G)$, the number of maximal cliques of the graph $G$. We mean by a maximal clique of $G$, an induced subgraph of $G$ which is a complete graph and is also maximal with this property. Now, we are ready for the main theorem of this section: \begin{thm}\label{reg-closed} For any closed graph $G$, we have $\mathrm{reg}(J_G)\leq c(G)+1$. \end{thm} \begin{proof} Note that, by \cite[Corollary 3.3.4]{HH}, we have $\mathrm{reg}(J_G)\leq \mathrm{reg}(\mathrm{in}_{<}(J_G))=\mathrm{reg}(I(\mathrm{in}_{<}(G)))$. So, it is enough to show that $\mathrm{reg}(I(\mathrm{in}_{<}(G)))\leq c(G)+1$. By Theorem \ref{cochord}, we have $\mathrm{reg}(I(\mathrm{in}_{<}(G)))\leq \mathrm{cochord}(\mathrm{in}_{<}(G))+1$. Now, we show that $\mathrm{cochord}(\mathrm{in}_{<}(G))\leq c(G)$. Let $H$ be a maximal clique of $G$. Then $\mathrm{in}_{<}(H)$ is an induced subgraph of $\mathrm{in}_{<}(G)$. By Theorem \ref{linear}, $I(\mathrm{in}_{<}(H))$ has a linear resolution. Hence, by Fr\"oberg's theorem, \cite[Theorem 1]{F}, the complement graph of $\mathrm{in}_{<}(H)$ is chordal. On the other hand, all maximal cliques of $G$, say $H_1,\ldots,H_{c(G)}$, cover all edges of $G$. So, clearly, $\mathrm{in}_{<}(H_1),\ldots,\mathrm{in}_{<}(H_{c(G)})$ cover all edges of $\mathrm{in}_{<}(G)$. Thus, by definition, we have $\mathrm{cochord}(\mathrm{in}_{<}(G))\leq c(G)$. \end{proof} \begin{rem}\label{generalization} \em{Theorem \ref{reg-closed} could be seen as a generalization of the fact that if $G$ is a complete graph, then it has a linear resolution. In this case, we have $c(G)=1$ and hence $\mathrm{reg}(J_G)=2$. So, clearly, in Theorem \ref{reg-closed}, equality holds for complete graphs. There are some other classes of closed graphs with equality in Theorem \ref{reg-closed}. For example, let $P_n$ be the path over $n$ vertices. Then we have reg$(J_{P_n})={\mathrm{reg}}({\mathrm{in}}_<(J_{P_n}))=c(P_n)+1=n$, since $S/J_{P_n}$ is Cohen-Macaulay and ${\mathrm{in}}_<(J_{P_n})$ is the edge ideal of $n-1$ disjoint edges, (see \cite[Corollary 1.2]{EHH} and \cite[Proposition 3.2]{EHH}). As an other example with this property, consider any closed graph $G$ which has exactly two maximal cliques. Then we have reg$(J_G)=3$. } \end{rem} \begin{rem}\label{example} \em{The inequality of Theorem \ref{reg-closed} might be strict. For example, consider the graph $G$ with vertex set $V=\{v_1,\ldots,v_6\}$ and edges $\{v_1,v_2\}$, $\{v_1,v_3\}$, $\{v_2,v_3\}$, $\{v_2,v_4\}$, $\{v_3,v_4\}$, $\{v_3,v_5\}$, $\{v_4,v_5\}$, $\{v_4,v_6\}$, $\{v_5,v_6\}$. We have $G$ is closed and $c(G)=4$. But, one can see, by \textit{CoCoA}, that reg$(J_G)=4$. } \end{rem} \textbf{Acknowledgments:} We thank Professor J\"urgen Herzog for initiating us to look at these problems and many useful discussions. Moreover, the research of the second author was in part supported by a grant from IPM (No. 90050115). \providecommand{\byame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \begin{thebibliography}{10} \bibitem{EHH} V. Ene, J. Herzog and T. Hibi, {\em Cohen-Macaulay binomial edge ideals.} To appear in Nagoya Math. J. 204 (2011). \bibitem{F} R.~Fr\"{o}berg, {\em On Stanley-Reisner rings.} Topics in algebra, Banarch Center Publications, 26 (2) (1990), 57-70. \bibitem{HH} J. Herzog and T. Hibi, {\em Monomial ideals.} Springer, (2010). \bibitem{HHHKR} J. Herzog, T. Hibi, F. Hreinsdotir, T. Kahle and J. Rauh, {\em Binomial edge ideals and conditional independence statements.} Adv. Appl. Math. 45 (2010), 317-333. \bibitem{Ka} M. Katzman, {\em Characteristic-independence of Betti numbers of graph ideals.} J. Combin. Theory Ser. A 113 (2006), 435-454. \bibitem{P} I. Peeva, {\em Graded syzygies.} Springer, (2010). \bibitem{W} R. Woodroofe, {\em Matching, coverings, and Castelnuovo-Mumford regularity.} Preprint, (2011), arXiv:1009.2756v2. \end{thebibliography} \end{document}