Proof Let $k\geq 1$ be an integer. For any element $h=f_{i_1}\dots f_{i_k}\in A_k$ , we set $h^{*}=y_{i_1}\dots y_{i_k}$ . Let $\{h_1^{*},\ldots ,h_{d}^*\}$ be the set of all standard monomials of bidegree $(*,k)$ in T which are of the form $h^*$ . Then by [Reference Herzog, Hibi and Moradi7, Lemma 3.2], $h_1,\ldots ,h_d$ is a system of generators of $A_k$ . We show that this is indeed a minimal system of generators of $A_k$ . Since $f_1,\ldots ,f_m$ is a minimal generating set of $A_1$ , there is nothing to prove for $k=1$ . Now, let $k>1$ . By contradiction suppose that there exists an integer j such that ${h_j=\sum _{\ell \neq j}p_{\ell }h_{\ell }}$ for some homogeneous polynomials $p_{\ell }\in S$ . Then $q=h_j^*-\sum _{\ell \neq j}p_{\ell }h_{\ell }^*\in J$ . Without loss of generality, assume that q has the least initial term among all the expressions of the form $h_j^*-\sum _{\ell \neq j}p^{\prime }_{\ell }h_{\ell }^*\in J$ . Since $h_j^*$ is a standard monomial, we have $\operatorname {in}_<(q)=\operatorname {in}_<(p_i)h_i^*\in \operatorname {in}_{<}(J)$ for some $i\neq j$ with $p_i\neq 1$ . By assumption, there exists an element g in the Gröbner basis of J such that $\operatorname {in}_<(g)$ has degree two and $\operatorname {in}_<(g)$ divides $\operatorname {in}_<(p_i)h_i^*$ . If $\operatorname {in}_<(g)=y_ry_t$ for some r and t, then $y_ry_t$ divides $h_i^*$ , which implies that $h_i^*\in \operatorname {in}_<(J)$ , a contradiction. So $\operatorname {in}_<(g)=x_ry_t$ for some r and t and then $x_r$ divides $\operatorname {in}_<(p_i)$ and $y_t$ divides $h_i^*$ . Let $g=x_ry_t-\sum _{\ell =1}^s c_{\ell }u_{\ell }y_{j_{\ell }}$ for some $c_{\ell }\in K$ and monomials $u_{\ell }\in S$ . Then

(2) $$ \begin{align} x_rf_t=\sum_{\ell=1}^s c_{\ell}u_{\ell}f_{j_{\ell}}. \end{align} $$

We have $u_{\ell }\neq 1$ for all $\ell $ . Indeed, if $u_{\lambda }=1$ for some $\lambda $ , then

(3) $$ \begin{align} f_{j_{\lambda}}=c_{\lambda}^{-1}x_rf_t-\sum_{\ell\neq\lambda} c_{\lambda}^{-1}c_{\ell}u_{\ell}f_{j_{\ell}}. \end{align} $$

This is a contradiction, since $f_1,\ldots ,f_m$ is a minimal generating set of $A_1$ . Thus $u_{\ell }\neq 1$ for all $\ell $ . We have

$$ \begin{align*} \operatorname{in}_<(p_i)h_i=(\operatorname{in}_<(p_i)/x_r)x_rf_t(h_i/f_t)= \\ (\operatorname{in}_<(p_i)/x_r)(\sum_{\ell=1}^s c_{\ell}u_{\ell}f_{j_{\ell}}) (h_i/f_t). \end{align*} $$

Hence $\operatorname {in}_<(p_i)h_i=\sum _{\ell =1}^s c_{\ell }w_{\ell }h^{\prime }_{\ell }$ , for the monomials $w_{\ell }=(\operatorname {in}_<(p_i)/x_r)u_{\ell }\neq 1$ and elements $h^{\prime }_{\ell }=f_{j_{\ell }}(h_i/f_t)\in A_k$ . Let $p^{\prime }_i=p_i-\operatorname {in}_<(p_i)$ . Then

(4) $$ \begin{align} h_j=(\operatorname{in}_<(p_i)+p^{\prime}_i)h_i+\sum_{\ell\neq i,j}p_{\ell}h_{\ell}=\sum_{\ell=1}^s c_{\ell}w_{\ell}h^{\prime}_{\ell}+p^{\prime}_ih_i+\sum_{\ell\neq i,j}p_{\ell}h_{\ell}. \end{align} $$

We show that $h^{\prime }_{\ell }\neq h_j$ for all $1\leq \ell \leq s$ . Indeed, by the equality (2) and that $u_{\ell }\neq 1$ , we have $\deg (f_t)\geq \deg (f_{j_{\ell }})$ . Hence $\deg (h^{\prime }_{\ell })\leq \deg (h_i)$ . While $\deg (h_j)=\deg (p_i)+\deg (h_i)>\deg (h_i)$ . Hence $\deg (h_j)>\deg (h^{\prime }_{\ell })$ which implies that $h^{\prime }_{\ell }\neq h_j$ . Also ${y_{j_{\ell }}<'y_t}$ implies that $(h^{\prime }_{\ell })^*<'h_i^*$ . By (4), we have

(5) $$ \begin{align} q'=h_j^*-\sum_{\ell=1}^s c_{\ell}w_{\ell}(h^{\prime}_{\ell})^*-p^{\prime}_ih_i^*-\sum_{\ell\neq i, j}p_{\ell}h_{\ell}^*\in J. \end{align} $$

Since $(h^{\prime }_{\ell })^*\neq h_j^*$ for all $\ell $ and $\operatorname {in}_<(q')<\operatorname {in}_<(q)$ , by the assumption on q, we conclude that there exists at least one integer $1\leq \ell \leq s$ such that the monomial $(h^{\prime }_{\ell })^*$ is not standard. By [Reference Herzog, Hibi and Moradi7, Lemma 2.2], for any such $\ell $ , there exist standard monomials $h_{t_{\ell ,1}}^*,\ldots ,h_{t_{\ell ,b}}^*$ with $h_{t_{\ell ,1}}^*<\cdots <h_{t_{\ell ,b}}^*<(h^{\prime }_{\ell })^*$ and homogeneous polynomials $v_{\ell ,\lambda }$ such that

(6) $$ \begin{align} (h^{\prime}_{\ell})^*-\sum_{\lambda=1}^b v_{\ell,\lambda}h_{t_{\ell,\lambda}}^*\in J. \end{align} $$

Again notice that $j\notin \{t_{\ell ,1},\ldots ,t_{\ell ,b}\}$ , since $\deg (h_j)>\deg (h^{\prime }_\ell )\geq \deg (h_{t_{\ell ,\lambda }})$ for any ${1\leq \lambda \leq b}$ . Set $I_1=\{\ell : 1\leq \ell \leq s, \ (h^{\prime }_{\ell })^*\ \textrm {is not standard}\}$ and $I_2=[s]\backslash I_1$ . By (5) and (6), we obtain an expression

$$ \begin{align*}q"=h_j^*-\sum_{\ell\in I_1}\sum_{\lambda=1}^b c_{\ell}w_{\ell}v_{\ell,d}\ h_{t_{\ell,d}}^*-\sum_{\ell\in I_2}c_{\ell}w_{\ell}(h^{\prime}_{\ell})^*-p^{\prime}_ih_i^*-\sum_{\ell\neq i, j}p_{\ell}h_{\ell}^*\in J\end{align*} $$

in terms of standard monomials. Since $\operatorname {in}_<(q")<\operatorname {in}_<(q)$ , we get a contradiction.

Thus, $h_1,\ldots ,h_d$ is a minimal system of generators of $A_k$ . Now, using [Reference Herzog, Hibi and Moradi7, Theorem 2.3], we conclude that for each k, $A_k$ has linear quotients with respect to its minimal set of generators. Thus, it follows from [Reference Herzog and Hibi6, Theorem 8.2.15] that $A_k$ is componentwise linear.

Proof Let $S = K[x_1, \ldots , x_n, z^{(1)}_1, \ldots , z^{(n)}_{r_n} ]$ denote the polynomial ring in $n + r_1 + \cdots + r_n$ variables over a field K. Let $C^{(i)}_1, \ldots , C^{(i)}_{s_i}$ denote the minimal vertex covers of $H_i$ . Given a vertex cover C of G, we introduce a subset $C' = C \cup C^{(i)} \cup \cdots \cup C^{(n)}$ of $V(G) \cup V(H_1) \cup \cdots \cup V(H_n)$ for which

$$\begin{align*}C^{(i)} = \left\{ \begin{array}{@{}lll} V(H_i), & \text{if} & x_i \not\in C, \\ C^{(i)}_j, & \text{if} & x_i \in C, \end{array} \right. \end{align*}$$

where $1 \leq j \leq s_i$ is arbitrary. It follows that $C'$ is a minimal vertex cover of G and that every minimal vertex cover of G is of the form $C'$ .

Let $<_{\mathrm {lex}}$ denote the pure lexicographic order on S with respect to the above ordering $z^{(1)}_1> \cdots > x_n$ . Let $C_1, \ldots , C_q$ denote the minimal vertex covers of $G(H_1, \ldots , H_n)$ and suppose that $u_{C_q} <_{\mathrm {lex}} \cdots <_{\mathrm {lex}} u_{C_1}$ .

Let $T_i = K[z^{(i)}_1, \ldots , z^{(i)}_{r_i}, y^{(i)}_1, \ldots , y^{(i)}_{s_i}]$ denote the polynomial ring in $r_i + s_i$ variables over K and $J_{H_i} \subset T_i$ the toric ideal of ${\mathcal R}(I_{H_i})$ which is the kernel of $\pi _i : T_i \to {\mathcal R}(I_{H_i})$ . Let $w = z^{(i)}_j w"$ be a monomial belonging to the minimal system of monomial generators of $\mathrm {in}_{<^\sharp }(J_{H_i})$ , where $w"$ is a monomial in $y^{(i)}_1, \ldots , y^{(i)}_{s_i}$ . Let $\pi _i(w) = z^{(i)}_j u_{C^{(i)}_{\xi _1}}t \dots u_{C^{(i)}_{\xi _a}}t$ . Let $C_{\zeta _{i'}}$ be a minimal vertex covers of $G(H_1, \ldots , H_n)$ with $C_{\zeta _{i'}} \cap V(H_i) = C^{(i)}_{\xi _{i'}}$ for each $1 \leq i' \leq a$ . It follows that $z^{(i)}_j y_{\zeta _1} \dots y_{\zeta _a}$ belongs to $\mathrm {in}_{<^\sharp }(J_{G(H_1, \ldots , H_n)}) \subset T = S[y_1, \ldots , y_q]$ .

Let C be a minimal vertex cover of $G(H_1, \ldots , H_n)$ with $x_i \not \in C$ and

$$\begin{align*}C' = ((C \cup \{x_i\}) \backslash V(H_i) ) \cup C^{(i)}_j, \end{align*}$$

where $1 \leq j \leq s_i$ is arbitrary. Then $C'$ is a minimal vertex cover of $G(H_1, \ldots , H_n)$ with $u_{C'} <_{\mathrm {lex}} u_{C}$ . Let $C = C_e$ and $C' = C_f$ . Then $e < f$ and

$$ \begin{align*}x_i y_e - \prod_{z^{(i)}_{j'} \not\in C^{(i)}_j} z^{(i)}_{j'} y_f \in J_{G(H_1, \ldots, H_n)}\end{align*} $$

whose initial monomial is $x_i y_e$ .

Let ${\mathcal {A}}$ denote the set of monomials of the form either $z^{(i)}_j y_{\zeta _1} \dots y_{\zeta _a}$ or $x_i y_e$ constructed above. Let ${\mathcal {B}}$ denote the set of monomials in $y_1, \ldots , y_q$ belonging to the minimal system of monomial generators of $\mathrm {in}_{<^\sharp }(J_{G(H_1, \ldots , H_n)})$ .

Let $({\mathcal {A}}, {\mathcal {B}})$ denote the monomial ideal of T generated by ${\mathcal {A}} \cup {\mathcal {B}}$ . One claims that $\mathrm {in}_{<^\sharp }(J_{G(H_1, \ldots , H_n)}) = ({\mathcal {A}}, {\mathcal {B}})$ . One must prove that, for monomials u and v of T not belonging to $({\mathcal {A}}, {\mathcal {B}})$ with $u \neq v$ , one has $\pi (u) \neq \pi (v)$ , see [Reference Herzog, Hibi and Ohsugi9, Theorem 3.11]. Let ${u = u_x u_z u_y}$ and $v = v_x v_z v_y$ with $u \neq v$ , where $u_x, v_x$ are monomials in $x_1, \ldots , x_n$ , where $u_z, v_z$ are monomials in $z^{(i)}_j, 1 \leq i \leq n, 1 \leq j \leq r_i$ , and where $u_y, v_y$ are monomials in $y_1, \ldots , y_s$ . Suppose that u and v are relatively prime and that $\pi (u) = \pi (v)$ .

Let, say, $u_x \neq 1$ and $x_i$ divide $u_x$ . Since $x_i$ does not divide $v_x$ and since $\deg u_y = \deg v_y$ , it follows that there is $y_a$ which divides $u_y$ for which $x_i \not \in C_a$ . Hence, $x_i y_a \in {\mathcal {A}}$ , a contradiction. Thus, $u_x = v_x = 1$ .

Let $\pi (u) = u_z \cdot u_{C_{a_1}}t \dots u_{C_{a_p}}t$ and $\pi (v) = v_z \cdot u_{C_{a^{\prime }_1}}t \dots u_{C_{a^{\prime }_p}}t$ . Let, say, $u_z \neq 1$ and $z^{(i)}_j$ divide $u_z$ . In each of $\pi (u)$ and $\pi (v)$ , replace each of $x_{1}, \ldots , x_n$ with $1$ and replace $z^{(i')}_j$ with $1$ for each $i' \neq i$ and for each $1 \leq j \leq r_i$ . Then $\pi (u)$ comes to

$$ \begin{align*}u^{\prime}_z \cdot u_{C^{(i)}_{c_1}}t \dots u_{C^{(i)}_{c_{p'}}}t\,\left(\prod_{j=1}^{r_i}z_j^{(i)}\right)^{p-p'}\end{align*} $$

and $\pi (v)$ comes to

$$ \begin{align*}v^{\prime}_z \cdot u_{C^{(i)}_{c^{\prime}_1}}t \dots u_{C^{(i)}_{c^{\prime}_{p'}}}t\,\left(\prod_{j=1}^{r_i}z_j^{(i)}\right)^{p-p'},\end{align*} $$

where each of $u^{\prime }_z$ and $v^{\prime }_z$ is a monomial in $z_{1}^{(i)}, \ldots , z_{r_i}^{(i)}$ . One has $p'> 0$ and

$$ \begin{align*}u^{\prime}_z \cdot y^{(i)}_{c_1} \dots y^{(i)}_{c_{p'}} - v^{\prime}_z \cdot y^{(i)}_{c^{\prime}_1} \dots y^{(i)}_{c^{\prime}_{p'}} \in J_{H_i}.\end{align*} $$

Since $z^{(i)}_j$ divides $u^{\prime }_z$ , one has $u^{\prime }_z \cdot y^{(i)}_{c_1} \dots y^{(i)}_{c_{p'}} - v^{\prime }_z \cdot y^{(i)}_{c^{\prime }_1} \dots y^{(i)}_{c^{\prime }_{p'}} \neq 0$ and its initial monomial belongs to $\mathrm {in}_{<^\sharp }(J_{H_i})$ . Since $J_{H_i}$ satisfies the x-condition, it follows that either $u \in ({\mathcal {A}}, {\mathcal {B}})$ or $v \in ({\mathcal {A}}, {\mathcal {B}})$ , a contradiction. Thus $u_z = v_z = 1$ .

Since $u = u_y, v = v_y, u - v \neq 0$ and $\pi (u) = \pi (v)$ , one has either $u \in ({\mathcal {B}})$ or $v \in ({\mathcal {B}})$ , a contradiction.

Proof We keep the notation used in the proof of Theorem 3.1. Suppose that $J_{H_i}$ has a quadratic Gröbner basis with respect to $z^{(i)}_1> \cdots > z^{(i)}_{r_i}$ for each i. By Theorem 3.1, the ideal $J=J_{G(H_1, \ldots , H_n)}$ satisfies the x-condition with respect to the order $<$ induced by the orders $z^{(i)}_1> \cdots > z^{(i)}_{r_i}$ . Hence by the proof of [Reference Herzog, Hibi and Moradi7, Theorem 3.3], for any positive integer k, the ideal $(I_{G(H_1, \ldots , H_n)})^k$ has a system of generators $h_1,\ldots ,h_s$ , each of them of the form $h_i=u_{C_{i_1}}\dots u_{C_{i_k}}$ , which possess an order of linear quotients $h_1<\cdots <h_s$ and such that $h_i^*=y_{i_1}\dots y_{i_k}$ is a standard monomial of T with respect to $<^\sharp $ and J. We prove that $\{h_1,\ldots ,h_s\}$ is the minimal generating set of monomials of $(I_{G(H_1, \ldots , H_n)})^k$ .

Suppose that $h_j=wh_i$ for some integers i and j and a monomial $w\in S$ . We should show that $w=1$ and $i=j$ . Let $h_i=u_{C_{i_1}}\dots u_{C_{i_k}}$ and $h_j=u_{C_{j_1}}\dots u_{C_{j_k}}$ . If $w=1$ and ${i\neq j}$ , then $h_j^*-h_i^*\in J$ . So either $h_i^*$ or $h_j^*$ belongs to $\operatorname {in}_{<^\sharp }(J)$ , a contradiction. Hence $i=j$ and we are done.

Now, assume that $w\neq 1$ . Let $w=w_xw_z$ , where $w_x$ is a monomial in $x_1, \ldots , x_n$ and $w_z$ is a monomial in $z^{(i)}_j, 1 \leq i \leq n, 1 \leq j \leq r_i$ . Assume that $w_x\neq 1$ and $x_t|w$ for some integer t. So we have $x_t\notin C_{i_{a}}$ for some $1\leq a\leq k$ . The set

$$\begin{align*}C' = ((C_{i_{a}} \cup \{x_t\}) \backslash V(H_t) ) \cup C^{(t)}_\ell, \end{align*}$$

where $1 \leq \ell \leq s_t$ is arbitrary, is a minimal vertex cover of $G(H_1, \ldots , H_n)$ with ${u_{C'} <_{\mathrm {lex}} u_{C}}$ . Let $C' = C_b$ . Then $i_a< b$ and

$$ \begin{align*}x_t y_{i_{a}} - \prod_{z^{(t)}_{j'} \not\in C^{(t)}_\ell} z^{(t)}_{j'} y_b \in J_{G(H_1, \ldots, H_n)}\end{align*} $$

whose initial monomial is $x_t y_{i_{a}}$ . Since $x_t| w$ and $u_{C_{i_a}}|h_i$ , we may write $wh_i=w'h'$ , where $w'=(w/x_t)\prod _{z^{(t)}_{j'} \not \in C^{(t)}_\ell } z^{(t)}_{j'}$ and $h'=(h_i/u_{C_{i_a}})u_{C_b}$ . Therefore $h_j=w'h'$ with $\deg (w^{\prime }_x)<\deg (w_x)$ . Repeating this procedure, we obtain $h_j=uf$ , where u is a monomial with $u_x=1$ and $u_z\neq 1$ and $f=u_{C_{\ell _1}}\dots u_{C_{\ell _k}}$ for some $\ell _1,\ldots ,\ell _k$ . Let $w"(h")^*$ be the unique standard monomial in T with respect to $<^\sharp $ and J such that ${\pi (w"(h")^*)=f}$ , where $w"$ is a monomial in S.

Then $h_j=uf=uw"h"$ . Let $h"=u_{C_{s_1}}\dots u_{C_{s_k}}$ If $x_t|w"$ for some integer t, then we have $x_t\notin C_{s_{a}}$ for some a and then $x_t y_{s_{a}}\in \operatorname {in}_{<^\sharp }(J)$ . Since $x_ty_{s_{a}}$ divides $w"(h")^*$ , this implies that $w"(h")^*\in \operatorname {in}_{<^\sharp }(J)$ , a contradiction. Hence $w^{\prime \prime }_x=1$ . Note that $(h")^*$ is a standard monomial as well. So the equality $h_j=uf=u_zw^{\prime \prime }_zh"$ shows that we may reduce to the case that $w_x=1$ . Hence $w=w_z$ with $w_z\neq 1$ and $h_j=w_zh_i$ .

Let, say, $z^{(i)}_j$ divides $w_z$ . In each of $h_j$ , $h_i$ and w, replace each of $x_{1}, \ldots , x_n$ with $1$ and replace $z^{(i')}_j$ with $1$ for each $i' \neq i$ and for each $1 \leq j \leq r_{i'}$ . Then $h_j$ comes to

$$ \begin{align*}u_{C^{(i)}_{c_1}}t \dots u_{C^{(i)}_{c_{p'}}}t\,\left(\prod_{j=1}^{r_i}z_j^{(i)}\right)^{p-p'} \end{align*} $$

and $h_i$ comes to

$$ \begin{align*}u_{C^{(i)}_{c^{\prime}_1}}t \dots u_{C^{(i)}_{c^{\prime}_{p'}}}t\,\left(\prod_{j=1}^{r_i}z_j^{(i)}\right)^{p-p'},\end{align*} $$

and w comes to v, where v is a monomial in $z_{1}^{(i)}, \ldots , z_{r_i}^{(i)}$ . One has $p'> 0$ and

(7) $$ \begin{align} y^{(i)}_{c_1} \dots y^{(i)}_{c_{p'}} - v \cdot y^{(i)}_{c^{\prime}_1} \dots y^{(i)}_{c^{\prime}_{p'}} \in J_{H_i}. \end{align} $$

Moreover, since $h_i^*$ and $h_j^*$ are standard monomials in T, $y^{(i)}_{c_1} \dots y^{(i)}_{c_{p'}}$ and $y^{(i)}_{c^{\prime }_1} \dots y^{(i)}_{c^{\prime }_{p'}}$ are standard monomials in $T_i$ , i.e., they do not belong to $\operatorname {in}_<(J_{H_i})$ . Since $J_{H_i}$ has a quadratic Gröbner basis with respect to $z^{(i)}_1> \cdots > z^{(i)}_{r_i}$ , as was shown in the proof of [Reference Herzog, Hibi and Moradi7, Theorem 3.6], the monomials $u_{C^{(i)}_{c_1}} \dots u_{C^{(i)}_{c_{p'}}}$ and $u_{C^{(i)}_{c^{\prime }_1}}\dots u_{C^{(i)}_{c^{\prime }_{p'}}}$ belong to the minimal set of monomial generators of $(I_{H_i})^{p'}$ . This contradicts to equation (7).

Proof For any graph $H_i$ belonging to one of the families (a) to (d), the defining ideal of ${\mathcal R}(I_{H_i})$ has a quadratic Gröbner basis, see [Reference Herzog and Hibi5], [Reference Herzog, Hibi and Moradi7, Corollary 4.7], and [Reference Herzog, Hibi, Ohsugi, Fløystad, Johnsen and Knutsen8, Theorem 2.7]. Hence, the desired result follows from Theorem 3.2.