Abstract
Let \(I\subset K[x_1,\ldots ,x_n]\) be a squarefree monomial ideal generated in one degree. Let \(G_I\) be the graph whose nodes are the generators of I, and two vertices \(u_i\) and \(u_{ j}\) are adjacent if there exist variables x, y such that \(xu_i = yu_j\). We show that if I is generated in degree \(n-2\), then the following are equivalent:
- (i)
\(G_I\) is a connected graph;
- (ii)
I has a \((n-2)\)-linear resolution;
- (iii)
I has linear quotients;
- (iv)
I is a variable-decomposable ideal.
We also prove that if I has linear relations and \(\overline{G_I}\) is chordal, then I has linear quotients.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \(S = K[x_{1},\ldots , x_{n}] \) be the polynomial ring in n variables over a field K and I be a squarefree monomial ideal in S Fröberg [5, Theorem 1] proved that the edge ideal of a finite graph G has a 2-linear resolution if and only if the complement graph \(\overline{G}\) of G is a chordal graph. Emtander [4], Woodroofe [12], Van Tuyl and Villarreal [11] have partially generalized the Fröberg’s Theorem. It is known that monomial ideals with 2-linear resolution have linear quotients [7]. We denote by \(\varDelta ^{\vee }\) the Alexander dual of \(\varDelta \). Let I be the Stanley–Reisner ideal of \(\varDelta ^{\vee }\) which is generated in degree 2 and has a linear resolution. By a result of Eagon–Reiner [3], \(\varDelta \) is a Cohen–Macaulay of codimension 2. In [1], it is shown that if \(\varDelta \) is a Cohen–Macaulay simplicial complex of codimension 2, then \(\varDelta \) is vertex decomposable. Hence, by a result of [10], \(I=I_{\varDelta ^{\vee }}\) is a variable-decomposable monomial ideal generated in degree 2. Therefore, if I is a monomial ideal generated in degree 2, then
\((*)\; \; I\) is a variable-decomposable ideal\(\ \Leftrightarrow I \) has linear quotients \(\Leftrightarrow I \) has a linear resolution.
In [8], some other classes of squarefree monomial ideals with property \((*)\) were introduced. These three concepts are not equivalent in general, but we have the following implications:
I is a variable-decomposable ideal \(\Rightarrow I\) has linear quotients \(\Rightarrow I\) has a linear resolution.
In the present paper, we consider squarefree monomial ideals generated in degree d and try to find some other classes of squarefree monomial ideals with \((*)\) property. We show that if \(d=2\), \(d=n-2\), \(n\le 5\) or \(\overline{G_I}\) is a chordal graph, then the property \((*)\) holds for I. We also study squarefree monomial ideals with linear quotients and show that if I has linear relations and \(\overline{G_I} \) is chordal, then I has linear quotients.
The paper proceeds as follows. In Sect. 2, we recall some definitions and some known results which will be needed later. Let \(I=I(G)\) be an edge ideal of a simple graph G. In Sect. 3, we present a different proof of the well-known fact that property \((*)\) holds for I. Also we show that the concepts of linear relations, linear resolution, linear quotients and variable–decomposability are equivalent when I is a squarefree monomial ideal generated in degree \(n-2\). Consequently, if \(I\subset K[x_1,\ldots ,x_5]\) is a squarefree monomial ideal, then I has property \((*)\), see Corollary 1. We consider monomial ideal I, where \(\overline{G_I}\) is a chordal graph, in Sect. 4. If \(\overline{G_I}\) is a chordal graph and I has linear relations, then I has linear quotients as will be proved in Theorem 3. Hence, if \(\overline{G_I}\) is a chordal graph, then I has property \((*)\), see Corollary 2. In addition, another property of \(\overline{G_I}\) which implies that I has linear quotients is given in Theorem 4.
2 Preliminary
For a monomial ideal I in S, there is a minimal graded free resolution of the form
where \(F_i=\bigoplus _{j}S(-j)^{\beta _{i j}} \) and \( S(-j)\) denotes the free S-module obtained by shifting the degrees of S by j. The numbers \(\beta _{i j}=\beta _{i j} (I) \) are called the graded Betti numbers of I. Recall that I has a d-linear resolution over K if \(\beta _{i j} (I) = 0 \) for all \(j\ne i + d\). It follows that I is generated in degree d. Let \(\varphi : F_1 \longrightarrow I\) be the maps which send the basis element \(e_i\)s of \(F_1\) to the generators \(u_i\) of I. Recall that I has linear relations if the kernel of \(\varphi \) is generated by linear forms. Note that if the ideal I has linear relations, then all of its generators have the same degree.
The unique minimal monomial set of generators of a monomial ideal I is denoted by G(I). Monomial ideal I has linear quotients if there exists an order \(\sigma = u_1, \ldots , u_m\) of G(I) such that the colon ideal \(\langle u_1, \ldots , u_{i-1}\rangle : u_i\) is generated by a subset of variables for \(i = 2, \ldots , m\). Any order of the generators for which we have linear quotients will be called an admissible order. For a monomial \(u\in S\), set \( F(u_i) :={\,}\)Supp\((u)=\{i\; :\; x_i\mid u\} \). It is easy to see that if I is a squarefree monomial ideal, then I has linear quotients if and only if for all i and all \(j < i\) there exist \(l \in F(u_j) {\setminus } F(u_i)\) and an integer \(k < i\) such that \(F(u_k) {\setminus } F(u_i) =\{l\}\) (see [6, Corollary 8.2.4]).
Let \(u = x_1^{a_1} \ldots x_n^{a_n}\) be a monomial in S. For another monomial v, set \([u, v] = 1\) if \(x_i^{a_i} \not \mid v \) for all \(i \in F(u)\). Otherwise, set \([u, v] \ne 1\). For a monomial \(u \in S\) and a monomial ideal \(I \subseteq S\), set \(I_u=\langle u_i \in G(I) :\ [u, u_i] = 1\rangle \) and \(I^u = \langle u_j \in G(I) :\ [u, u_j] \ne 1\rangle>\).
In this paper, by the notation \(u_j:u_i=x_l\) we mean \(<u_j>:<u_i>=<x_l>.\)
Definition 1
Let I be a monomial ideal with the minimal system of generators \(\{u_1, \ldots , u_m \}\). A monomial \(u =x_1^{a_1} \cdots x_n^{a_n}\) is called shedding if \(I_u \ne 0\), and for each \(u_i \in G(I_u)\) and \(l \in F(u)\), there exists \(u_j \in G(I^u)\) such that \(u_j:u_i=x_l.\)
Definition 2
Let I be a monomial ideal minimally generated by \(\{u_1, \ldots , u_m \}\). Monomial ideal I is called a k-decomposable ideal if \(m= 1\) or else has a shedding monomial u with \(\mid \)Supp\((u)\mid \le k + 1\) such that the ideals \(I_u\) and \(I^u\) are k-decomposable. (Note that since the number of minimal generators of I is finite, the recursion procedure will stop.)
A monomial ideal is decomposable if it is k-decomposable for some \(k \ge 0\) . Also, a 0-decomposable ideal is called variable-decomposable. The concepts of shedding monomial and k-decomposable monomial ideals were first introduced by Rahmati and Yassemi in [10].
Let \(I\subset S\) be a squarefree monomial ideal which is generated in one degree. We associate with I a simple graph \(G_{I}\), called the first syzygies graph of I, whose vertices are the elements of G(I). Two vertices \(u_i\) and \(u_j\) are adjacent if there exist variables x and y such that \(xu_i=yu_j\). Since the generators of a monomial ideal form a Gröbner basis, hence the S-polynomials of each pair of its generators would give the generators of the first syzygies of the monomial ideal, that is, \(\frac{lcm(u_i,u_j)}{ u_i} e_i- \frac{lcm(u_i,u_j)}{ u_j} e_j\). So one can easily find nonlinear syzygies or, equivalently, linear syzygies.
Remark 1
Let I be a squarefree monomial ideal . If \(G_I\) is a complete graph, then I is a variable-decomposable ideal.
Let G be a finite graph on vertex set \(V=\{1,\ldots , n\}\). The edge ideal of G is defined by \(I(G) = \langle x_ix_j {:} \{i, j\} \text { is an edge in}\; G\rangle \subset S\). The induced subgraph \(G_W\) is the graph whose vertex set is \(W \subseteq V\) and the edge set consists of all the edges of G whose both endpoints are in W.
Definition 3
Let G be a graph on vertex set V and \(u \in V\). The set of all neighborhoods of u is denoted by N(u).
Definition 4
A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph.
The following fact will be used later.
Proposition 1
[2, Corollary 5.6] Every non-trivial connected graph contains at least two vertices that are not cut-vertices.
A finite graph G is called chordal if each of whose cycles of length \(> 3\) has a chord. It is clear that every induced subgraph of a chordal graph is again chordal. A perfect elimination ordering of G is an ordering \( i_{n}, \ldots , i_{2}, i_{1} \) of the vertices \(1, 2, \ldots , n\) of G such that, for each \( 1 < j \le n,\) the induced graph on \(C_{i_{j}}=\{i_j\} \cup \lbrace i_{k} \in [n] : 1 \le k < j, \lbrace i_{k}, i_{j} \rbrace \in E(G) \rbrace \) is a clique of G. In 1961, G. A. Dirac proved that a graph G is chordal if and only if it has a perfect elimination ordering.
Remark 2
Let \(\overline{G} \) be the complementary graph of G and let the ordering \( n, n-1, \ldots ,1 \) be a perfect elimination ordering of \( \overline{G} \). If \(k> i,j\) and \(\{ i , k \} , \{j , k \} \in E( \overline{G}) \), then \( \{ i , j \} \in E( \overline{G}) \). In other words, if \(\{ i, k \}, \{ j, k \} \notin E( G) \), then \( \{ i, j \} \notin E(G) \). Hence, if \( \{ i, j \} \in E(G)\) and \(k> i,j \), then \( \{ i, k\} \in E(G) \) or \( \{j , k \} \in E(G) \).
3 Resolution of Monomial Ideals of Degree 2 and \(n-2\)
Let G be a finite graph and I be the edge ideal of G. Fröberg [5] showed that I has a linear resolution if and only if \(\overline{G}\) is a chordal graph. As it is mentioned in the introduction, for monomial ideals generated in degree 2 the following conditions are equivalent:
- (a)
I has a linear resolution;
- (b)
I has linear quotients;
- (c)
I is a variable-decomposable ideal.
We could not find a direct proof for equivalence of these three statements, but we conclude it from known results in [1, 3, 7, 10]. For convenience of reader, a direct proof of this fact is provided in the following.
Theorem 1
Let I be the edge ideal of a finite graph G. Then the following conditions are equivalent:
- (a)
The complementary graph \(\overline{G}\) of G has a perfect elimination ordering;
- (b)
I is variable-decomposable ideal;
- (c)
I has a linear resolution;
- (d)
I has linear quotients.
Proof
\((a) \Rightarrow (b)\): We proceed by induction on \(\mid V(\overline{G})\mid \). The assertion is trivial if \( \mid V(\overline{G})\mid =2\). If \(\mid V(\overline{G})\mid >2\), then without loss of generality, we may assume that \(n, n-1, \ldots , 1 \) is a perfect elimination ordering of \( \overline{G} \) and \(I_{x_n}=I(G_1)\). It is clear that \(\overline{G_1}\) is an induced subgraph of \(\overline{G}\), so \(\overline{G_1}\) is a chordal graph. Since \(\mid V(\overline{G_1})\mid <\mid V(\overline{G}) \mid \), by induction hypothesis, \(I_{x_n}\) is a variable-decomposable ideal. It is not difficult to see that \(G_{I^{x_n}}\) is a complete graph; hence, \(I^{x_n}\) is a variable-decomposable ideal. So it is enough to show that \(x_n\) is a shedding variable. If \(u=x_ix_j \in I_{x_n}\), then by Remark 2, \(x_ix_n \in G(I)\) or \(x_jx_n \in G(I) \). Therefore, \(x_n\) is a shedding monomial.
\((b) \Rightarrow (c)\): This proof is down by induction on \(k=\mid G(I)\mid \). The assertion is obvious for \(k = 1\). Now suppose \(k>1\) and x is a shedding. Since \(\mid G(I^x)\mid \) and \(\mid G(I_x)\mid \) are less than \(\mid G(I)\mid \), by induction hypothesis, \(I^x\) and \(I_x\) have linear resolution. The short exact sequence
yields the long exact sequence
If \(j \ne d\), then both ends in this exact sequence vanish. Hence, the middle term vanishes too.
\((c) \Rightarrow (a)\): It follows from Fröberg’s Theorem that \(\overline{G}\) is chordal. It is well known that a graph is chordal if and only if it has a perfect elimination ordering.
\((b) \Rightarrow (d)\): Let I be a variable-decomposable ideal. Without loss of generality, assume that \(x_1\) is a shedding where \(I^{x_1}=\langle u_1, \ldots , u_{t-1}\rangle \) and \(I_{x_1}=\langle u_t, \ldots , u_m\rangle \) are variable-decomposable. Arguing by induction on \(\mid G(I)\mid \) yields that \(I^{x_1}\) and \(I_{x_1}\) have linear quotients. It can be assumed that \(u_1, \ldots , u_{t-1}\) and \(u_t, \ldots , u_m\) are admissible order for \(I^{x_1}\) and \(I_{x_1}\), respectively. It will be shown that \(u_1, \ldots , u_{t-1}, u_t, \ldots , u_m\) is an admissible order for I. Let \(u_i\in I_{x_1}\) and \(u_j\in I^{x_1}\), then, by definition of shedding, there exists \(u_k\in I^{x_1}\) such that \(F(u_k) {\setminus } F(u_i)=\{1\}\). Since \(u_j\in I^{x_1}\), one has \(1 \in F(u_k){\setminus } F(u_i)\).
\((d) \Rightarrow (c)\): Follows from [6, Proposition 8.2.1]. \(\square \)
Now we consider squarefree monomial ideals generated in degree \(n-2\).
Remark 3
Let \(I \subset S\) be a squarefree monomial ideal generated in degree \( n-2 \). If there exists l, \(1\le l\le n\), such that \(x_l \not \mid u\) for all \(u\in G(I)\), then \(G_I\) is a complete graph.
Remark 4
Let \( S=K[x_{1},\ldots ,x_{n}] \) and I be a squarefree monomial ideal generated in degree \( n-2 \). If \(u_i, u_j \in G(I)\) are not adjacent in \(G_I\), then \(F(u_i) \cup F(u_j)=[n]\).
Theorem 2
Let \( S=K[x_{1},\ldots ,x_{n}] \) and \( I =\langle u_1,\ldots , u_m\rangle \) be a squarefree monomial ideal generated in degree \( n-2 \). The following are equivalent:
- (a)
\( G_{I} \) is a connected graph;
- (b)
I has linear relations;
- (c)
I has a \((n-2)\)-linear resolution;
- (d)
I has linear quotients;
- (e)
I is a variable-decomposable ideal.
Proof
\((a) \Rightarrow (d)\): We order the vertices of \(G_I\) in a way that the induced subgraph on \(\{ u_1, \ldots , u_i \}\) is a connected graph for \( 2\le i\le m\). It will be shown that \(u_1, \ldots , u_m\) is an admissible order. If \( j < i\) and \(u_i, u_j\) are adjacent, take \(u_k=u_j\). Otherwise, by connectivity of the induced subgraph \(\{ u_1, \ldots , u_i \}\), there exist a vertex \(u_k\) such that \(u_i\) and \(u_k\) are adjacent. Set \(\{l\}=F(u_k) {\setminus } F(u_i)\). Then by Remark 4 one has \(l \in F(u_j) {\setminus } F(u_i)\).
\((d) \Rightarrow (c)\): It follows from [6, Proposition 8.2.1].
\((c) \Rightarrow (b)\): The implication is trivial.
\((b) \Rightarrow (a)\): See [8, Lemma 1.8].
\((a)\Rightarrow (e)\): We proceed by induction on \(\mid G(I)\mid \). If \(\mid G(I) \mid =1\) the assertion is trivial; hence, assume that \(\mid G(I)\mid \ge 2\). Let \(x_i\) be an arbitrary variable. By Remark 3, all elements in \(G_{I_{x_{i}}}\) are adjacent. If \(x_i\) is not a shedding, then there exist \(u \in I_{x_i} \) such that \(v: u \ne x_i\) for all \(v \in I^{x_i} \). Hence, u and v are not adjacent for all \(v \in I^{x_i}\). Assume that \(F(u)=[n] {\setminus } \{ i,j\}\). Now, we show that \(x_j\) is a shedding. If \(w \in I_{x_j}\), then u and w are adjacent which implies \(w \in I_{x_i} \), \(F(w)=[n] {\setminus } \{ i,j\}=F(u)\) and \( I_{x_j}=\langle u\rangle \). Since \( G_I\) is a connected graph, there exists \(v \in I^{x_j}\) such that u and v are adjacent and \(v:u=x_j\).
Now, it is enough to show that \(G_{I^{x_j}}\cong G_I {\setminus } \{u\} \) is a connected graph. If \(v ,w \in G(I){\setminus } \{u\}\), then there exists a path between v and w in \(G_I\). If u is not a vertex in this path, then v and w are connected in \(G_{I^{x_j}}\). Otherwise, we have a path \(v, \ldots , z, u, q, \ldots , w\). We know z, q are adjacent to u; hence, \(z, q \in I_{x_i}\) and z and q are adjacent. Therefore, v and w are connected in \(G_{I^{x_j}}\).
Now, we consider a case that every variable is a shedding for I. By Remark 3, it is enough to show that \(G_{I^{x_i}} \) is a connected graph for some \(1 \le i \le n\). Assume \(G_{I^{x_1}} \) is not a connected graph and \(C_1, \ldots , C_p\) are its connected components. Since \(G_I\) is a connected graph, \(C_i\) is connected to \(G_{ I_{x_1}}\), for \(i=1,\ldots ,p\). If \(u_1 \in C_1\) and \( l \notin F(u_1)\), then \(u_1 \in I_{x_l}\). Since \(G_{ I_{x_l}}\) is a complete graph and \(u \in C_i\), \(1 < i \le p\), is not adjacent to \(u_1\), we conclude that \(V(C_i)\subseteq G( I^{x_l})\). We claim that if \(u_t \in I_{x_1}\) and \(u_t\) is adjacent to \(u \in C_i\), for some \(1 < i \le p\), then \( u_t \in I^{x_l}\). Suppose on the contrary that \( u_t \in I_{x_l}\), then \(F(u_t)=[n] {\setminus } \{ 1, l\}\). On the other hand, \( u \in I^{x_1}\) and \( u \in I^{x_l}\). Hence, \(\{1, l\} \subseteq F(u)\); therefore, \( u_t\) and u are not adjacent, a contradiction.
Now we consider the following two cases:
Case 1 If for all \(u \in C_1\), then there exists \(u_t \in I_{x_1}\) such that \( u_t\) is adjacent to u, then \(G_{I^{x_l}} \) is a connected graph.
Case 2 There is a \(u \in C_1\) such that u is not adjacent to any \(u_t \in I_{x_1}\). Assume \(F(u)=[n] {\setminus } \{ 1, r\}\). If \(G_{I^{x_r}}\) is a connected graph, we are done. Otherwise, since u is not adjacent to any \(u_t \in I_{x_1}\) and \(G_{I_{x_r}}\) is a complete graph, one has \(G( I_{x_1}) \subseteq G(I^{x_r})\). It is clear that \(G_{I_{x_1}} \) and \(C_i\), for all \(2 \le i \le p\), form a connected component of \(G_{I^{x_r}}\). Hence, \(G_{I^{x_r}}\) has two connected components and since \( u \notin C_1^{'}\), its second connected component is \(C_1^{'}\subsetneq C_1\). Now repeat the above procedure for \(C_1^{'}\). Since the graph \(G_I\) is finite, after a finite number of steps we find \({x_r} \) for which \(G_{I^{x_r}}\) is a connected graph.
\((e) \Rightarrow (a)\): We proceed by induction on \(\mid G(I)\mid \). Since I is variable-decomposable, there exists a shedding x such that \(I_x\) and \(I^x\) are variable-decomposable. By induction hypothesis, \(G_{I_x}\) and \(G_{I^x}\) are connected graphs. Since x is a shedding, one has every vertex in \(G_{I_x}\) is adjacent to some vertex in \(G_{I^x}\). \(\square \)
Corollary 1
Let \(I \subseteq K[x_1,\ldots , x_n] \) be a squarefree monomial ideal. If \(n\le 5\), then the following are equivalent:
- (a)
I has a linear resolution;
- (b)
I has linear quotients;
- (c)
I is variable-decomposable ideal.
Proof
If I is generated in degree 2, then the assertion follows from Theorem 1. If I is generated in degree 3, then the assertion follows from Theorem 2. The assertion is trivial when I is generated in degree 1 or 4. \(\square \)
Notice that the following examples show that the condition \(n \le 5\) is the best possible.
Example 1
Consider monomial ideal \(I=\langle x_1x_2x_3, x_1x_3x_5, x_1x_5x_6, x_2x_5x_6, x_2x_3x_6,\)\( x_3x_4x_6, x_1x_4x_6, x_1x_2x_4, x_2x_4x_5, x_3x_4x_5\rangle \). This ideal is corresponding to triangulation of the projective plane and has a linear resolution in characteristics zero but has not a linear quotients (see [13]).
Example 2
Consider monomial ideal \(I=\langle x_1x_2x_3, x_1x_2x_6, x_1x_2x_5, x_2x_4x_5, x_3x_4x_5,\)\( x_1x_3x_4, x_1x_3x_6, x_2x_4x_6, x_3x_5x_6, x_4x_5x_6\rangle \). This ideal has linear quotients and is not a variable-decomposable (see [9]).
4 Linear Quotients of Monomial Ideals
It is shown in [8] that from any path between \(u_i\) and \(u_j\) in \(G_I\), one can find \(w_i\) and \(w_j\) in Mon(S) such that \(w_i e_i-w_je_j \in \ker (\varphi )\).
Remark 5
If there exist two paths \(u_i, v, u_j\) and \(u_i, w, u_j\) in \(G_I\) between \(u_i\) and \(u_j\), then the coefficients of \(e_i\) which comes from the first and the second paths are equal.
Lemma 1
Let \(I=\langle u_1, \ldots , u_m\rangle \) be a squarefree monomial ideal which has linear relations. If \(\overline{G_I}\) is a chordal graph, then there exists a t such that the monomial ideal J with \(G(J)=G(I){\setminus } \{u_t\}\) has linear relations.
Proof
By [8, Lemma 1.8], \(G_I\) is a connected graph; thus, the existence of non-cut-vertex \(u_t\) follows from Proposition 1. Let \(J=\langle u_1, \ldots ,u_{t-1}, u_{t+1}, \ldots , u_m\rangle \) and \(u_i\) and \(u_j\) be two arbitrary elements in \(G(J)= G(I){\setminus }\{u_t\}\). We have
Since I has linear relations, there exists a path \(L_1\) between \(u_i\) and \(u_j\) in \(G_I\) such that \(X_{F(u_j) {\setminus } F(u_i)}e_i-X_{F(u_i) {\setminus } F(u_j)}e_j\) is a linear combination of linear forms which comes from \(L_1\). If \(L_1\) is a subgraph of \(G_J\), then we are done. Otherwise, there exists a path \(L_2\) of minimum length between \(u_i\) and \(u_j\) in \(G_J\). Since \( \overline{G_I}\) is chordal, it is easy to see that \(G_I\) has no cycle of length greater than 4 without chord, and so by Remark 5 the linear combinations of linear forms which come from \(L_2\) are equal to \(X_{F(u_j) {\setminus } F(u_i)}e_i-X_{F(u_i) {\setminus } F(u_j)}e_j\). \(\square \)
Theorem 3
Let \(I=<u_1, \ldots , u_m>\) be a squarefree monomial ideal. If I has linear relations and \(\overline{G_I}\) is a chordal graph, then I has linear quotients.
Proof
We proceed by induction on \(|G(I)|=m\). The assertion is trivial for \(m=1\) and \(m=2\). If \(m>2\), then by Lemma 1 there exists a t (assume \(t=m\)) such that \(J=\langle u_1, \ldots ,u_{m-1} \rangle \) has linear relations. Induction hypothesis implies that J has linear quotients. Assume \(u_1, \ldots , u_{m-1}\) is an admissible order for J. We show \(u_1, \ldots , u_{m-1}, u_m\) is an admissible order for I. Let \(j<m\), then by [8, Proposition 1.22] there exists a path \(u_m=v_1, v_2, \ldots , v_r=u_j\) in \(G_I\) such that \(F(v_i) \subseteq F(u_m) \cup F(u_j)\) for all \(1 \le i \le r\). If \(\{l\}=F(v_2) {\setminus } F(u_m)\), then \(l \in F(u_j) {\setminus } F(u_m)\). \(\square \)
As an immediate consequence of Theorem 3, we have:
Corollary 2
Let \(I=\langle u_1, \ldots , u_m \rangle \) be a squarefree monomial ideal. If \(\overline{G_I}\) is a chordal graph, then the following are equivalent:
- (a)
I has linear relations;
- (b)
I has a linear resolution;
- (c)
I has linear quotients.
The following simple lemma is crucial for the proof of Theorem 4.
Lemma 2
Suppose I is a squarefree monomial ideal and \( \{u_{i},u_{r} \}\) and \( \{ u_{r},u_{j} \} \) are edges in \(G_{I}\). If \( \{u_{i},u_{j} \} \notin E(G_{I}) \) and \( F(u_{r}) {\setminus } F(u_{i}) =\{l\}\), then \( l \in F(u_{j}) {\setminus } F(u_{i}) \).
Proof
Since \( \{u_{i},u_{r} \} \in E(G_{I}) \), one has \( F(u_{r}) {\setminus } F(u_{i}) =\{l\}\). Assume \( F(u_{i})=A \cup \{t\} \) and \( F(u_{r})=A \cup \{l\}\). If \( l \notin F(u_{j}) \), then \( A \subseteq F(u_{j}) \). Hence, \( \{u_{i},u_{j} \} \in E(G_{I}) \), a contradiction. \(\square \)
Theorem 4
Assume that the ordering \( u_{m}, u_{m-1}, \ldots ,u_{1} \) is a perfect elimination ordering of \( \overline{G_{I}} \). Let \( u_{g_t}, u_{g_{t-1}},\ldots , u_{g_1} \) be the neighborhoods of \( u_{m}\) in \(\overline{G_I}\) and \(t>1\). Set \(V=\{u_{g_2-1},\ldots ,u_{g_1}, \ldots , u_{1} \} \). If \(N_{G^{'}}(u_{g_1}) \ne \emptyset \), where \(G^{'}\) is the induced subgraph of \(G_I\) on V, then I has linear quotients.
Proof
Let u be a neighborhood of \( u_{g_1} \). By Remark 2, u is a neighborhood of \( u_{g_i} \) for \( 2 \le i \le t\). We order the elements of G(I) as follows: \( u_{g_1}\), neighborhoods of \(u_{g_1}\), \(u_{g_2}\), neighborhoods of \(u_{g_2}\) which are not appeared before, ..., \( u_{g_t}\), neighborhoods of \(u_{g_t}\) which are not appeared before, \( u_{m} \), neighborhoods of \( u_{m} \) which are not appeared before.
Assume that \(v_{1}, \ldots , v_{m} \) come from the above ordering. In what follows, we show that this order is an admissible order. For \(j<i\), we must find \(k<i\) such that \(F(v_k){\setminus } F(v_i)=\{l\}\) and \(l\in F(v_j)\). Consider the following four cases:
- (i)
\( v_{i}=u_{g_{s}} \) and \( v_{j}=u_{g_{l}}\) with \(l<s\). Since u is a neighborhood of \( u_{g_s} \) and \( u_{g_l} \), if we set \(v_k=u\), then we are done by Lemma 2.
- (ii)
\( v_{i}=u_{g_{s}} \) and \( v_{j}\) is a neighborhood of \( u_{g_{l}} \) with \(l<s\). Remark 2 implies that \( v_{j}\) is a neighborhood of \( v_{i}\). Hence, take \(v_k=v_j\).
- (iii)
\( v_{i}\) is a neighborhood of \(u_{g_{s}} \) and \( v_{j}\) is a neighborhood of \( u_{g_{l}} \) with \(l \le s\). Remark 2 implies that \( v_{j}\) is a neighborhood of \( u_{g_{s}}\). If \( \{v_{i},v_{j} \} \in E(G_{I}) \), then we take \(v_k=v_j\). Otherwise, we take \(v_k= u_{g_{s}}\) and the assertion follows from Lemma 2.
- (iv)
\( v_{i}\) is a neighborhood of \(u_{g_{s}} \) and \( v_{j}= u_{g_{l}} \) with \(l \le s\). If \( l=s \), then take \(v_k=v_{j}\). So assume that \( l<s \). If \( \{v_i, u \} \in E(G_I) \), then take \(v_k=u\) and the assertion follows from Lemma 2. If \( \{v_i, u \} \notin E(G_I) \), then \( F(v_{i})= A \cup \{r_1, r_2\} \) and \( F(u)= A^{'} \cup \{r_3, r_4\} \). Remark 2 implies that \( v_{i}\) and u are neighborhoods of \( u_{m}\). It is easy to see that \( A=A^{'} \subseteq F(u_{m}) \). Hence, \( F(u_{m})= A\cup \{p,q\} \) such that \( p \in \{r_1, r_2\} \) and \( q \in \{r_3, r_4\}\). Without loss of generality, we may assume \( F(u_{m})= A \cup \{r_1, r_3\} \). Since \( v_{i}\) and u are neighborhoods of \(u_{g_{s}} \) and \( \{u_{m},u_{g_{s}} \} \notin E(G_{I}) \), one has \(F(u_{g_{s}})= A \cup \{r_2, r_4\} \). Take \( v_{k} =u_{g_{s}}\), then \( F(v_{k}){\setminus } F(v_{i}) =\{r_4\}\). If \( r_4 \notin F(v_{j}) \), since \( \lbrace u, v_{j} \rbrace \in E(G_{I}) \) , one has \( A \cup \lbrace r_3 \rbrace \subseteq F(v_{j})\). Therefore, \( \lbrace u_{m}, v_{j} \rbrace \in E(G_{I}) \), a contradiction.
\(\square \)
References
Ajdani, S.M., Jahan, A.S.: Vertex decomposability of \(2\)-CM and Gorenstein simplicial complexes of codimension \(3\). Bull. Malays. Math. Sci. Soc. 39, 609–617 (2016)
Chartrand, G., Zhang, P.: A First Course in Graph Theory. Courier Corporation (2013)
Eagon, J.A., Reiner, V.: Resolutions of Stanley–Reisner rings and Alexander duality. J. Pure Appl. Algebra 130, 265–275 (1998)
Emtander, E.: A class of hypergraphs that generalizes chordal graphs. Math. Scand. 106(1), 50–66 (2010)
Fröberg, R.: On Stanley–Reisner rings. Top. Algebra Banach Cent. Publ. 26, 57–70 (1990)
Herzog, J., Hibi, T.: Monomial Ideals, Graduate Texts in Mathematics, vol. 260. Springer, London (2011)
Herzog, J., Hibi, T., Zheng, X.: Monomial ideals whose powers have a linear resolution. Math. Scand. 95, 23–32 (2004)
Manouchehri, E., Jahan, A.S.: On Linear Resolution and Linear Quotients of Monomial Ideals. arXiv:1809.00133
Moriyama, S., Takeuchi, F.: Inccremental construction properties in dimension two: shellability, extendable shellability and vertex decomposability. Discrete Math. 263, 295–296 (2003)
Rahim Rahmati, A., Yassemi, S.: \(k\)-Decomposable monomial ideals. Algebra Colloq. 22, 745–756 (2015)
Tuyl, A., Villarreal, R.: Shellable graphs and sequentially Cohen–Macaulay bipartite graphs. J. Combin. Theory Ser. A. 115, 799–814 (2008)
Woodroofe, R.: Chordal and sequentially Cohen–Macaulay clutters. Electron. J. Combin. 18, P208 (2011)
Yazdan Pour, A.A.: Resolutions and Castelnuovo–Mumford Regularity, Differential Geometry [math.DG]. Université de Grenoble (2012)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Siamak Yassemi.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Manouchehri, E., Soleyman Jahan, A. On Linear Quotients of Squarefree Monomial Ideals. Bull. Malays. Math. Sci. Soc. 43, 1213–1221 (2020). https://doi.org/10.1007/s40840-019-00737-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40840-019-00737-5