Combinatorial Bounds of the Regularity of Elimination Ideals

Junjua, Muhammad; Shabbir, Khurram; Naseem, Asim

doi:10.61091/ars156-3

Abstract

1. Introduction
2. Background
3. Main Results
Acknowledgement
Conflict of Interest

References

Ars Combinatoria

Volume 156
Pages: 25-34

Research article

Combinatorial Bounds of the Regularity of Elimination Ideals

^¹, ^¹, ^¹

¹Govt. College University, Lahore, Pakistan.

Received: 10/05/2019
Accepted: 13/12/2019
Published: 22/07/2023

Copyright Link
License

Abstract

Elimination ideals are monomial ideals associated to simple graphs, not necessarily square–free, was introduced by Anwar and Khalid. These ideals are Borel type. In this paper, we obtain sharp combinatorial upper bounds of the Castelnuovo–Mumford regularity of elimination ideals corresponding to certain family of graphs.

Keywords: Primary decomposition, Castelnuovo–Mumford regularity, Stable ideal, Strongly stable ideals

1. Introduction

Let $S = k [x_{1}, \dots, x_{n}]$ be a polynomial ring in $n$ –variables over an infinite field $k$ . We say that a monomial ideal $I \subset S$ is of Borel type, see [1], if it satisfies the following condition: $(I : x_{j}^{\infty}) = (I : (x_{1}, \dots, x_{j})^{\infty})$ for all $1 \leq j \leq n .$ The Castelnuovo–Mumford regularity of $I$ is the number $r e g (I) = max {j - i | β_{i j} (I) \neq 0},$ where $β_{i j} (I)$ are the graded Betti numbers of $I$ . The regularity of monomial ideals of Borel type is extensively studied, see for instance [2,3,4,5].

Let $G$ be a simple connected graph on the vertex–set $V (G) = {x_{1}, \dots, x_{n}}$ and edge–set $E (G)$ . There are a number of ways to study the algebraic properties of the graph by associating a monomial ideal to it, well known among all are edge–ideals. Recently, Anwar and Khalid in [3] introduced a new class of monomial ideals, namely; elimination ideals $I_{D} (G)$ , associated to $G$ . They showed that the elimination ideals are monomial ideals of Borel type. They gave the description of Graphical Degree Stability of graph $G$ denoted by ${Stab}_{d} (G)$ ; a combinatorial measure associated to $G$ . They gave a systematic procedure to compute the graphical degree stability, namely Dominating Vertex Elimination Method (DVE method). They computed the upper bound of the Castelnuovo–Mumford regularity of elimination ideals for complete graph, star graph, line graph, cyclic graph, fan graph, friendship graph and wheel graph.
Motivated from [3], we further extended this study to other family of graphs. We succeeded to obtain a sharp combinatorial bound for the Castelnuovo–Mumford regularity of elimination ideals associated to regular Harary graphs $H_{n - 2, n}$ (see theorem 3). We obtain similar result for the join of complete graph and Path Graph; $K_{n} \lor P_{m}$ (see theorem 3) and for complete bipartite graph; $K_{m, n}$ (see theorem 4)

2. Background

Throughout in this paper, we consider $G$ as a finite simple connected graph with vertex set $V (G) = {x_{1}, \dots, x_{n}}$ and $S = k [x_{1}, \dots, x_{n}]$ be the associated polynomial ring over an infinite field $k$ , also the edge set of $G$ will be denoted by $E (G)$ . As $| V (G) |$ is finite, we may use the set $[n] = {1, 2, \dots, n}$ instead of $V (G)$ and we shall always use $[n]$ to label the vertices in figures.
Let $x_{i} \in V (G),$ then the number of edges incident to $x_{i}$ is called the degree of $x_{i}$ and is denoted by $\deg (x_{i})$ , if $\deg (x_{i}) \geq \deg (x_{j})$ for all $x_{j} \in V (G),$ then $x_{i}$ is called dominating vertex of $G,$ and the set of all dominating vertices of $G$ is called the dominating set of $G,$ denoted as $D (G) .$ A vertex $x_{i} \in V (G)$ with $\deg (x_{i}) = 0$ is called an isolated vertex of $G .$ We call $G$ a scattered graph, if it has at least one isolated vertex, otherwise, non-scattered graph. A finite sequence of nonnegative integers is called graphical degree sequence if it is a degree sequence of some graph. Throughout in this paper, we assume that $\deg (x_{1}) \geq \deg (x_{2}) \geq \dots \geq \deg (x_{n})$ in $G$ . Now, we recall important definitions from [3].

Definition 1. Let $G_{i}$ be a graph and pick a vertex $x$ in $D (G_{i})$ such that $G_{i + 1} := G_{i} - {x}$ is an induced, non-scattered subgraph of $G_{i}$ . This method of obtaining an induced, non-scattered subgraph $G_{i + 1}$ from $G_{i}$ by eliminating a vertex from the dominating set $D (G_{i})$ is called the dominating vertex elimination method, the method is known as DVE method. See [3] for more details.

Let $G := G_{0}$ be a graph with vertex set $[n]$ , then the length of the maximum chain of induced, non scattered subgraphs of $G$ obtained by successively using DVE method is called the graphical degree stability of $G,$ and it is formally denoted by ${Stab}_{d} (G) .$ In other words, if $G := G_{0} \supset G_{1} \supset \dots \supset G_{k}$ is the maximum chain of induced, non scattered subgraphs of $G$ then ${Stab}_{d} (G) = k .$ Note that $G_{k}$ is a subgraph of $G$ with vertex set $[n - k] .$

Definition 2. Let $G_{i}$ be a graph with vertex set $V (G_{i}) = {x_{1}, x_{2}, \dots, x_{i}}$ and having the degree sequence $(d_{1}, d_{2}, \dots, d_{i})$ , then the ideal $Q_{i} := ⟨ x_{1}^{d_{1}}, x_{2}^{d_{2}}, \dots, x_{i}^{d_{i}} ⟩$ is called the sequential ideal of $G_{i}$ . Let $G := G_{0} \supset G_{1} \supset \dots \supset G_{k}$ be the maximum chain of induced, non scattered subgraphs of $G$ obtained by DVE method with ${Stab}_{d} (G) = k,$ then $I_{D} (G) := ⋂_{j = 0}^{k} Q_{j}$ is called the elimination ideal of $G .$

Now, we recall some definitions from graph theory.

Definition 3. Let $G$ and $H$ be two graphs with mutually disjoint vertex sets $V (G) = {u_{1}, u_{2} \dots, u_{n}}$ and $V (H) = {w_{1}, w_{2}, \dots, w_{m}} .$ A graph, denoted by $G \lor H$ , is called the join of $G$ and $H$ if $V (G \lor H) = V (G) \cup V (H)$ and $E (G \lor H) = E (G) \cup E (H) \cup {u_{i} w_{j} | u_{i} \in V (G), w_{j} \in V (H)}$ .

Definition 4. Let $G$ be a graph with vertex set $V (G) .$ A subset $X$ of $V (G)$ is called an independent set if no two vertices of $X$ are adjacent. A k-partite graph is a graph whose vertex set $V (G)$ can be partitioned into k distinct independent sets. A complete k-partite graph is a k-partite graph with every two vertices from distinct independent sets are adjacent. If k=2, then graph is bipartite.

We conclude this section by recalling some important definitions and results regarding stable properties of ideals.
Let $I \subset S = k [x_{1}, \dots, x_{n}]$ be a monomial ideal. For any monomial $u \in S$ set $m (u) := max {j | x_{j} | u}$ and $m (I) = max {m (u) | u \in G (I)}$ , where $G (I)$ denotes the set of minimal monomial generators of $I .$ The highest degree of monomial in $G (I)$ is denoted by $\deg (I)$ . Also, $I_{\geq t}$ is the monomial ideal generated by monomials of $I$ of degree $\geq$ t. A monomial ideal $I$ is stable if for each monomial $u \in I$ we have $x_{j} . \frac{u}{x_{m (u)}} \in I$ for all $1 \leq j < m (u)$ . We set $q (I) = m (I) (\deg (I) - 1) + 1$ .
Eisenbud, Reeves and Totaro proved the following result in [6].

Theorem 1. Let $I$ be a monomial ideal with $\deg (I) = d$ and $e \geq d$ be an integer such that $I_{\geq e}$ is stable, then $r e g (I) \leq e$ .

In [2], the authors gave the following bound for the regularity of Borel type ideals.

Proposition 1. Let $I$ be a Borel type ideal, then $r e g (I) \leq q (I)$ .

Remark 1. As $A s s (S / I_{D} (G))$ is totally ordered under inclusion, therefore $I_{D} (G)$ is a Borel type ideal by [2].

In [2], the authors proved the following:

Proposition 2. If $I$ and $J$ are two monomial ideals with $s \geq \deg (I)$ and $t \geq \deg (J)$ be two integers such that $I_{\geq s}$ and $J_{\geq t}$ are stable ideals, then $(I \cap J)_{\geq max {s, t}}$ is stable ideal.

3. Main Results

In this section, we give our main results regarding the Castelnuovo–Mumford regularity of elimination ideals for different classes of graphs.

3.1. Regularity of Regular Harary Graph $H_{n - 2, n}$

First, we recall the definition of Harary graph.

Definition 5.

Harary graph $H_{k, n}$ is the smallest $k$ -connected graph with $n$ vertices. Let us have a set $V = {x_{1}, x_{2}, \dots, x_{n}}$ of $n$ vertices, then the construction of Harary graphs are as follows:
Case I: If $k = 2 m < n$ $(n m a y b e e v e n o r o d d),$ then place all $n$ vertices in a circle and join each vertex $x_{i}$ to its $m$ consecutive left vertices and to its $m$ consecutive right vertices by drawing edges.
Case II: Let $n$ is even. If $k = 2 m + 1 < n,$ then first construct $H_{2 m, n}$ and then join each vertex $x_{i}, 1 \leq i \leq \frac{n}{2},$ to its diametrically opposite vertex.
Case III: If both $k$ and $n$ are odd then first construct $H_{k - 1, n}$ , then join each vertex $x_{i}, 1 \leq i \leq \frac{n - 1}{2} + 1,$ with vertex $x_{i + \frac{n - 1}{2}} .$

Note that the graphs in Case I and Case II are regular. Also note that if $k = n - 1$ then Case I and Case II suggest that $H_{k, n}$ is a complete graph $K_{n}$ . When $n$ is even, the diametrically opposite vertex of $x_{i}$ is given by: ${\begin{cases} x_{i} \leftrightarrow x_{i + \frac{n}{2}} & i f 1 \leq i \leq \frac{n}{2} \\ x_{i} \leftrightarrow x_{i - \frac{n}{2}} & i f \frac{n}{2} + 1 \leq i \leq n \end{cases}$

We are interested in computing the regularity of elimination ideal associated to $H_{n - 2, n}$ when $n$ is even and degree $k = n - 2.$ We begin by computing the graphical degree stability of $H_{n - 2, n}$ .

Lemma 1. Let $H_{n - 2, n}$ be a regular Harary graph with even vertices $n = 2 r \geq 4$ and degree of each vertex is $n - 2$ , then ${Stab}_{d} (H_{n - 2, n}) = n - 3$ .

Proof. We prove it by induction on $r$ for $n = 2 r \geq 4.$ For $r = 2$ , $G_{0} := H_{2, 4}$ is a regular graph with degree sequence $(2, 2, 2, 2)$ , so its dominating set will be $D (G_{0}) = {x_{1}, x_{2}, x_{3}, x_{4}}$ . Now, pick vertex $x_{1} \in D (G_{0})$ , after removing $x_{1}$ we get $G_{1}$ with degree sequence $(2, 1, 1)$ . The process will stop at $G_{1}$ and ${Stab}_{d} (H_{2, 4}) = 1.$

Consider the result is true for $r = p$ , i.e. ${Stab}_{d} (H_{2 p - 2, 2 p}) = 2 p - 3.$

Now take $r = p + 1$ , and let $G_{0} := H_{2 p, 2 p + 2}$ . The degree sequence of $G_{0}$ is $\underset{(2p+2)-tuple}{\underset{⏟}{(2 p, \dots, 2 p)}}$ with dominating set is $D (G_{0}) = {x_{1}, x_{2}, \dots, x_{2 p + 2}}$ . Choose vertex $x_{1}$ from $D (G_{0})$ and apply DVE method, we get $G_{1}$ with $D (G_{1})$ solely consists of diametrically opposite vertex (see Definition 1) of $x_{1}$ of degree $2 p$ . All other vertices are of degree $p - 1$ . The degree sequence of $G_{1}$ will be $\underset{(2p+1)-tuple}{\underset{⏟}{(2 p, 2 p - 1, \dots, 2 p - 1)}}$ . On removing $x_{1}$ (after relabeling of the vertices) we get $G_{2} := H_{2 p - 2, 2 p}$ . Now ${Stab}_{d} (H_{2 p - 2, 2 p}) = 2 p - 3$ $\Rightarrow {Stab}_{d} (H_{2 p, 2 p + 2}) = 2 + {Stab}_{d} (H_{2 p - 2, 2 p}) = (2 p + 2) - 3$ which is required.

Example 1. 1] Consider $H_{4, 6}$ , here $n = 6$ and $k = 4$ , see Figure $1$ .

Corollary 2. Let $H_{n - 2, n}$ be a regular Harary graph with even vertices $n \geq 4$ and degree of each vertex is $n - 2$ , then its sequential ideal is given as follows: $Q_{i} = {\begin{cases} ⟨ x_{1}^{n - i - 2}, x_{2}^{n - i - 2}, \dots, x_{n - i}^{n - i - 2} ⟩ & i f i i s e v e n \\ ⟨ x_{1}^{n - i - 1}, x_{2}^{n - i - 2}, \dots, x_{n - i}^{n - i - 2} ⟩ & i f i i s o d d \end{cases}$ where $0 \leq i \leq n - 3$ .

Proof. The proof follows from the definition of elimination ideal and lemma 1.

Theorem 2. Let $H_{n - 2, n}$ be a regular Harary graph with even vertices $n \geq 4$ and degree of each vertex is $n - 2$ , then $r e g (I_{D} (H_{n - 2, n})) \leq (n - 1) (n - 2) - 1$ .

Proof. We shall discuss the two cases of corollary 2 separately.

Case 1. When $i \in {0, 2, 4, \dots, n - 4}$ , the sequential ideal is given as $Q_{i} = ⟨ x_{1}^{a_{1}}, \dots, x_{n - i}^{a_{n - i}} ⟩$ where $a_{j} = n - i - 2$ for all $1 \leq j \leq n - i$ . Let $γ (i) = a_{i} (a_{i} + 1) - 1$ for all $i \in {0, 2, 4, \dots, n - 4}$ . We shall show that $Q_{i_{\geq γ (i)}}$ is a stable ideal. Take $u \in Q_{i_{\geq γ (i)}}$ , then $u = v x_{k}^{a_{k}}$ for some $1 \leq k \leq n - i$ where $v \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ (i) - a_{k}}$ .

If $m (u) > k,$ then $\frac{x_{l} u}{x_{m (u)}} = \frac{x_{l} v}{x_{m (u)}} x_{k}^{a_{k}} \in Q_{i_{\geq γ (i)}}$ for all $l < m (u)$ . So, $Q_{i_{\geq γ (i)}}$ is stable.

If $m (u) = k,$ then clearly $u \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ (i)}$ which is a stable ideal and $Q_{i_{\geq γ (i)}} \subseteq ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ (i)}$ . It remains to show that $⟨ x_{1}, \dots, x_{n - i} ⟩^{γ (i)} \subseteq Q_{i_{\geq γ (i)}}$ . Let $w \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ (i)}$ then $w = x_{1}^{β_{1}} x_{2}^{β_{2}} \dots x_{n - i}^{β_{n - i}}$ with $β_{s} \geq 0$ for all $1 \leq s \leq n - i$ and $Σ_{s = 1}^{n - i} β_{s} \geq γ (i)$ . Therefore, there exist at least one $r \in {1, \dots, n - i}$ such that $β_{r} \geq a_{r}$ and $w = (x_{1}^{β_{1}} \dots x_{r}^{β_{r} - a_{r}} \dots x_{n - i}^{β_{n - i}}) x_{r}^{a_{r}} \in Q_{i_{\geq γ (i)}}$ , hence the result follows.

Case 2. When $i \in {1, 3, 5, \dots, n - 3}$ , the sequential ideal then is given as $Q_{i} = ⟨ x_{1}^{a_{1}}, \dots, x_{n - i}^{a_{n - i}} ⟩$ where $a_{j} = {\begin{cases} n - i - 1 & i f j = 1 \\ n - i - 2 & i f 2 \leq j \leq n - i \end{cases}$ Let $γ^{'} (i) = a_{i} (a_{i} + 1)$ for all $i \in {1, 3, 5, \dots, n - 3}$ , then we shall show that $Q_{i_{\geq γ^{'} (i)}}$ is a stable ideal. Take $u \in Q_{i_{\geq γ^{'} (i)}}$ , then $u = v x_{k}^{a_{k}}$ for some $1 \leq k \leq n - i$ where $v \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ^{'} (i) - a_{k}}$ .

If $m (u) > k,$ then $\frac{x_{l} u}{x_{m (u)}} = \frac{x_{l} v}{x_{m (u)}} x_{k}^{a_{k}} \in Q_{i_{\geq γ^{'} (i)}}$ for all $l < m (u)$ . So, $Q_{i_{\geq γ^{'} (i)}}$ is stable.

If $m (u) = k,$ then clearly $u \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ^{'} (i)}$ which is stable ideal and $Q_{i_{\geq γ^{'} (i)}} \subseteq ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ^{'} (i)}$ . We are to show that $⟨ x_{1}, \dots, x_{n - i} ⟩^{γ^{'} (i)} \subseteq Q_{i_{\geq γ^{'} (i)}}$ . Let $w \in ⟨ x_{1}, \dots, x_{n - i} ⟩^{γ^{'} (i)}$ then $w = x_{1}^{β_{1}} x_{2}^{β_{2}} \dots x_{n - i}^{β_{n - i}}$ with $β_{s} \geq 0$ for all $1 \leq s \leq n - i$ and $Σ_{s = 1}^{n - i} β_{s} \geq γ^{'} (i)$ . Therefore, there exist at least one $r \in {1, \dots, n - i}$ such that $β_{r} \geq a_{r}$ and $w = (x_{1}^{β_{1}} \dots x_{r}^{β_{r} - a_{r}} \dots x_{n - i}^{β_{n - i}}) x_{r}^{a_{r}} \in Q_{i_{\geq γ^{'} (i)}}$ and the result follows.

By lemma 1, ${Stab}_{d} (H_{n - 2, n}) = n - 3$ , so the corresponding elimination ideal is given as $I_{D} (H_{n - 2, n}) = ⋂_{i = 0}^{n - 3} Q_{i}$ . By proposition 1, $I_{D} (H_{n - 2, n})$ is stable for $γ_{0}$ , where $γ_{0} = max {γ (i), γ^{'} (j) | i \in {0, 2, \dots, n - 4}, j \in {1, 3, \dots, n - 3}} = (n - 1) (n - 2) - 1$ and by theorem 1 $r e g (I_{D} (H_{n - 2, n})) \leq (n - 1) (n - 2) - 1.$

Remark 2. In Example 1,
$D (G_{0}) = {x_{1}, x_{2}, \dots, x_{6}}$ with $Q_{0} = ⟨ x_{1}^{4}, x_{2}^{4}, \dots, x_{6}^{4} ⟩$ and $r e g (Q_{0}) = 19$ .

$D (G_{1}) = {x_{1}}$ with $Q_{1} = ⟨ x_{1}^{4}, x_{2}^{3}, \dots, x_{5}^{3} ⟩$ and $r e g (Q_{1}) = 12$

$D (G_{2}) = {x_{1}, x_{2}, x_{3}, x_{4}}$ with $Q_{2} = ⟨ x_{1}^{2}, x_{2}^{2}, x_{3}^{2}, x_{4}^{2} ⟩$ and $r e g (Q_{2}) = 5$

$D (G_{3}) = {x_{1}}$ with $Q_{3} = ⟨ x_{1}^{2}, x_{2}, x_{3} ⟩$ and $r e g (Q_{3}) = 2$

3.2. Regularity of $K_{n} \lor P_{m}$

In [3], following formula is given to compute the graphical degree stability of path graph:

Proposition 3. Let $P_{m}, m \geq 3$ , be a path graph then: ${Stab}_{d} (P_{m}) = {\begin{cases} \frac{m - 3}{3} & i f m \equiv 0 (m o d 3) \\ \frac{m - 4}{3} & i f m \equiv 1 (m o d 3) \\ \frac{m - 2}{3} & i f m \equiv 2 (m o d 3) \end{cases}$

Lemma 1. Let $K_{n}, n \geq 2$ be a complete graph and $P_{m}, m \geq 4$ be a path graph then: ${Stab}_{d} (K_{n} \lor P_{m}) = n + {Stab}_{d} (P_{m})$

Proof. We shall prove it by induction on $n$ . Let $n = 2$ and $m = 4$ , then $G_{0} := K_{2} \lor P_{4}$ with degree sequence $(5, 5, 4, 4, 3, 3)$ and $D (G_{0}) = {x_{1}, x_{2}} .$ Without loss of generality, remove $x_{1} \in D (G_{0})$ to get $G_{1}$ with the degree sequence $(4, 3, 3, 2, 2)$ . So, $D (G_{1}) = {x_{1}}$ and on removing $x_{1} \in D (G_{1})$ , we get $G_{2} = P_{4} .$ $⟹ {Stab}_{d} (K_{2} \lor P_{4}) = 2 + {Stab}_{d} (P_{4})$ Suppose that result is true for $n = q$ and $m = r$ , then ${Stab}_{d} (K_{q} \lor P_{r}) = q + {Stab}_{d} (P_{r})$ .

Consider $n = q + 1$ and $m = r$ then $G_{0} := K_{q + 1} \lor P_{r}$ with degree sequence $(\underset{(q+1)-tuple}{\underset{⏟}{q + r, \dots, q + r}}, \underset{(r-2)-tuple}{\underset{⏟}{q + 3, \dots, q + 3}}, q + 2, q + 2)$ and $| V (G_{0} | = q + r + 1$ . Since $r \geq 4$ , $D (G_{0}) = {x_{1}, \dots, x_{q + 1}}$ which are precisely the vertices that were initially belonged to $K_{q + 1} .$ As removing any vertex from $K_{q + 1}$ gives $K_{q},$ So without loss of generality pick $x_{1} \in D (G_{0})$ and on removing it, we get $G_{1} = K_{q} \lor P_{r} .$ $⟹ {Stab}_{d} (K_{q + 1} \lor P_{r}) = 1 + {Stab}_{d} (K_{q} \lor P_{r}) = 1 + q + {Stab}_{d} (P_{r})$ which completes the proof.

Corollary 3. Let $K_{n}, n \geq 2$ be a complete graph and $P_{m}, m \geq 4$ be a path graph, then the sequential ideal of $K_{n} \lor P_{m}$ is given as follows: $Q_{i} = {\begin{cases} ⟨ x_{1}^{m + n - i - 1}, \dots, x_{n - i}^{m + n - i - 1}, x_{n - i + 1}^{n - i + 2}, \dots, x_{m + n - i - 2}^{n - i + 2}, x_{m + n - i - 1}^{n - i + 1}, x_{m + n - i}^{n - i + 1} ⟩ & i f 0 \leq i \leq n - 1 \\ ⟨ x_{1}^{2}, x_{2}^{2}, \dots, x_{m - 3 (i - n) - 2}^{2}, x_{m - 3 (i - n) - 1}, \dots, x_{m + n - i} ⟩ & i f n \leq i \leq n + p \end{cases}$ where $p = {Stab}_{d} (P_{m})$

Proof. The proof follows immediately from lemma 1 and [3].

Theorem 3. Let $K_{n}, n \geq 2$ be a complete graph and $P_{m}, m \geq 4$ be a path graph then $r e g (I_{D} (K_{n} \lor P_{m})) \leq n^{2} + 2 n (m - 1) + m - 1.$

Proof. We shall discuss the two cases of corollary 3 separately.

Case 1. When $0 \leq i \leq n - 1$ , the sequential ideal is given as $Q_{i} = ⟨ x_{1}^{a_{1}}, \dots, x_{m + n - i}^{a_{m + n - i}} ⟩$ where $a_{j} = {\begin{cases} m + n - i + 1 & i f 1 \leq j \leq n - i \\ n - i + 2 & i f n - i + 1 \leq j \leq m + n - i - 2 \\ n - i + 1 & i f n - i + 1 \leq j \leq m + n - i . \end{cases}$

Let $γ (i) = (n - i)^{2} + 2 (m - 1) (n - i) + m - 1$ for all $0 \leq i \leq n - 1$ . We shall show that $Q_{i_{\geq γ (i)}}$ is a stable ideal. Take $u \in Q_{i_{\geq γ (i)}}$ , then $u = v x_{k}^{a_{k}}$ for some $1 \leq k \leq m + n - i$ where $v \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i) - a_{k}}$ .

If $m (u) > k,$ then $\frac{x_{l} u}{x_{m (u)}} = \frac{x_{l} v}{x_{m (u)}} x_{k}^{a_{k}} \in Q_{i_{\geq γ (i)}}$ for all $l < m (u)$ . So, $Q_{i_{\geq γ (i)}}$ is stable.

If $m (u) = k,$ then clearly $u \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i)}$ and $Q_{i_{\geq γ (i)}} \subseteq ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i)}$ . We are to show that $⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i)} \subseteq Q_{i_{\geq γ (i)}}$ . Let $w \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i)}$ then $w = x_{1}^{β_{1}} x_{2}^{β_{2}} \dots x_{m + n - i}^{β_{m + n - i}}$ with $β_{s} \geq 0$ for all $1 \leq s \leq m + n - i$ and $Σ_{s = 1}^{m + n - i} β_{s} \geq γ (i)$ . Therefore, there exist at least one $r \in {1, \dots, m + n - i}$ such that $β_{r} \geq a_{r}$ and $w = (x_{1}^{β_{1}} \dots x_{r}^{β_{r} - a_{r}} \dots x_{m + n - i}^{β_{m + n - i}}) x_{r}^{a_{r}} \in Q_{i_{\geq γ (i)}}$ and the result follows.

Case 2. When $n \leq i \leq n + p$ , the sequential ideal is given as $Q_{i} = ⟨ x_{1}^{a_{1}}, \dots, x_{m + n - i}^{a_{m + n - i}} ⟩$ where $a_{j} = {\begin{cases} 2 & i f 1 \leq j \leq m - 3 (i - n) - 2 \\ 1 & i f m - 3 (i - n) - 1 \leq j \leq m + n - i . \end{cases}$

Let $γ^{'} (i) = m - 3 (i - n) - 1$ for all $n \leq i \leq n + p$ , then we shall show that $Q_{i_{\geq γ^{'} (i)}}$ is a stable ideal. Take $u \in Q_{i_{\geq γ^{'} (i)}}$ , then $u = v x_{k}^{a_{k}}$ for some $1 \leq k \leq m + n - i$ where $v \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ^{'} (i) - a_{k}}$ .

If $m (u) > k,$ then $\frac{x_{l} u}{x_{m (u)}} = \frac{x_{l} v}{x_{m (u)}} x_{k}^{a_{k}} \in Q_{i_{\geq γ^{'} (i)}}$ for all $l < m (u)$ . So, $Q_{i_{\geq γ^{'} (i)}}$ is stable.

If $m (u) = k,$ then clearly $u \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ^{'} (i)}$ and $Q_{i_{\geq γ^{'} (i)}} \subseteq ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ^{'} (i)}$ . We are to show that $⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ^{'} (i)} \subseteq Q_{i_{\geq γ^{'} (i)}}$ . Let $w \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ^{'} (i)}$ then $w = x_{1}^{β_{1}} x_{2}^{β_{2}} \dots x_{m + n - i}^{β_{m + n - i}}$ with $β_{s} \geq 0$ for all $1 \leq s \leq m + n - i$ and $Σ_{s = 1}^{m + n - i} β_{s} \geq γ^{'} (i)$ . Therefore, there exist at least one $r \in {1, \dots, m + n - i}$ such that $β_{r} \geq a_{r}$ and $w = (x_{1}^{β_{1}} \dots x_{r}^{β_{r} - a_{r}} \dots x_{m + n - i}^{β_{m + n - i}}) x_{r}^{a_{r}} \in Q_{i_{\geq γ^{'} (i)}}$ and the result follows.

By lemma 1, ${Stab}_{d} (K_{n} \lor P_{m}) = n + p$ , so the corresponding elimination ideal is given as $I_{D} (K_{n} \lor P_{m}) = ⋂_{i = 0}^{n + p} Q_{i}$ , by proposition 1, $I_{D} (K_{n} \lor P_{m})$ is stable for $γ_{0}$ , where $γ_{0} = max {γ (i), γ^{'} (j) | 0 \leq i \leq n - 1 and n \leq j \leq n + p} = n^{2} + 2 n (m - 1) + m - 1$ and by theorem 1, $r e g (I_{D} (K_{n} \lor P_{m})) \leq n^{2} + 2 n (m - 1) + m - 1.$

Example 2. Consider $K_{3} \lor P_{4},$ here $n = 3$ and $m = 4.$

$D (G_{0}) = {x_{1}, x_{2}, x_{3}}$ , $Q_{0} = ⟨ x_{1}^{6}, x_{2}^{6}, x_{3}^{6}, x_{4}^{5}, x_{5}^{5}, x_{6}^{4}, x_{7}^{4} ⟩$ and $r e g (Q_{0}) = 30$ , see Figure $2$ .

$D (G_{1}) = {x_{1}, x_{2}}$ , $Q_{1} = ⟨ x_{1}^{5}, x_{2}^{5}, x_{3}^{4}, x_{4}^{4}, x_{5}^{3}, x_{6}^{3} ⟩$ and $r e g (Q_{1}) = 19$ , see Figure $3$ .

$D (G_{2}) = {x_{1}}$ , $Q_{2} = ⟨ x_{1}^{4}, x_{2}^{3}, x_{3}^{3}, x_{4}^{2}, x_{5}^{2} ⟩$ and $r e g (Q_{2}) = 10$ , see Figure $4$ .

$D (G_{3}) = {x_{1}, x_{2}}$ , $Q_{3} = ⟨ x_{1}^{2}, x_{2}^{2}, x_{3}, x_{4} ⟩$ and $r e g (Q_{3}) = 3$ , see Figure $5$ .

3.3. Regularity of complete bipartite graph $K_{m, n}$

We recall the result about graphical degree stability of complete bipartite graph from [3]:

Proposition 4. Let $K_{m, n}$ be a complete bipartite graph with $m \geq n$ then: ${Stab}_{d} (K_{m, n}) = n - 1$

We generalize this result for complete $n$ -partite graphs.

Lemma 1. Let $K_{m_{1}, \dots, m_{n}}$ be a complete n-partite graph with $m_{i} \geq m_{j}$ for $1 \leq i < j \leq n$ , then ${Stab}_{d} (K_{m_{1}, \dots, m_{n}}) = m_{n} + m_{n - 1} + \dots + m_{2} - 1$

Proof. We prove it by induction. For $n = 2$ , we have $K_{m_{1}, m_{2}}$ with $m_{1} \geq m_{2}$ then by proposition 4: ${Stab}_{d} (K_{m_{1}, m_{2}}) = m_{2} - 1$ Let the result is true for $n = k - 1$ , i.e. ${Stab}_{d} (K_{m_{1}, \dots, m_{k - 1}}) = m_{k - 1} + m_{k - 2} + \dots + m_{2} - 1$ with $m_{i} \geq m_{j}$ if $1 \leq i < j \leq k - 1$ .

Consider $G_{0} := K_{m_{1}, \dots, m_{k}}$ , be the complete $k -$ partite graph and $V (G_{0}) = X_{1} \cup X_{2} \cup \dots \cup X_{k}$ , where each $X_{r} = {x_{r_{1}}, x_{r_{2}}, \dots, x_{r_{m_{r}}}}$ is an independent set with $| X_{r} | = m_{r}, 1 \leq r \leq k$ . Further $m_{i} \geq m_{j}$ if $1 \leq i < j \leq k$ .

If $x \in X_{r}, 1 \leq r \leq k$ then degree of $x$ would be $m_{1} + \dots + m_{r - 1} + m_{r + 1} + \dots + m_{k} .$ As $m_{k} \leq m_{j}$ for all $1 \leq j \leq k - 1,$ hence $X_{k} \subseteq D (G_{0})$ . So, without loss of generality we pick the vertex $x_{k_{m_{k}}} \in X_{k}$ , removing it will give us a new graph $G_{1}$ with dominating set $D (G_{1}) = X_{k} - {x_{k_{m_{k}}}}$ with degree of each vertex of $D (G_{1})$ is still $m_{1} + \dots + m_{k - 1}$ . If $x \in X_{r}, 1 \leq r \leq k - 1$ then degree of $x$ in $G_{1}$ would be $m_{1} + \dots + m_{r - 1} + m_{r + 1} + \dots + m_{k} - 1$ . Now pick $x_{k_{m_{k - 1}}}$ from $D (G_{1})$ and remove it so that we get new graph $G_{2}$ with dominating set $D (G_{2}) = X_{k} - {x_{k_{m_{k}}}, x_{k_{m_{k - 1}}}}$ with degree of each vertex of $D (G_{2})$ is still $m_{1} + \dots + m_{k - 1} .$ If $x \in X_{r}, 1 \leq r \leq k - 1$ then degree of $x$ in $G_{2}$ would be $m_{1} + \dots + m_{r - 1} + m_{r + 1} + \dots + m_{k} - 2.$ Continue in this way we get $G_{m_{k}} := K_{m_{1}, \dots, m_{k - 1}}$ . So, ${Stab}_{d} (K_{m_{1}, \dots, m_{k}}) = m_{k} + {Stab}_{d} (K_{m_{1}, \dots, m_{k - 1}}) = m_{k} + m_{k - 1} + \dots + m_{2} - 1$ which completes the proof.

Corollary 1. Let $K_{m, n}$ be a complete bipartite graph with $m \geq n$ , then the sequential ideal is given as follows: $Q_{i} = ⟨ x_{1}^{m}, \dots, x_{n - i}^{m}, x_{n - i + 1}^{n - i}, \dots, x_{m + n - i}^{n - i} ⟩$ where $0 \leq i \leq n - 1$ .

Proof. The proof follows immediately from lemma 1.

Theorem 4. Let $K_{m, n}$ be a complete bipartite graph with $m \geq n$ , then $r e g (I_{D} (K_{m, n})) \leq m + (2 m - 1) (n - 1) .$

Proof. By proposition 4, ${Stab}_{d} (K_{m, n}) = n - 1$ . The sequential ideal is given as $Q_{i} = ⟨ x_{1}^{a_{1}}, \dots, x_{m + n - i}^{a_{m + n - i}} ⟩$ for all $0 \leq i \leq n - 1$ where $a_{j} = {\begin{cases} m & i f 1 \leq j \leq n - i \\ n - i & i f n - i + 1 \leq j \leq m + n - i . \end{cases}$ Let $γ (i) = m + (2 m - 1) (n - i - 1)$ for all $0 \leq i \leq n - 1$ , then we shall show that $Q_{i_{\geq γ (i)}}$ is a stable ideal. Take $u \in Q_{i_{\geq γ (i)}}$ , then $u = v x_{k}^{a_{k}}$ for some $1 \leq k \leq m + n - i$ where $v \in ⟨ x_{1}, \dots, x_{m + n - i} ⟩^{γ (i) - a_{k}}$ .

If $m (u) > k,$ then $\frac{x_{l} u}{x_{m (u)}} = \frac{x_{l} v}{x_{m (u)}} x_{k}^{a_{k}} \in Q_{i_{\geq γ (i)}}$ for all $l < m (u)$ . So, $Q_{i_{\geq γ (i)}}$ is stable.

By proposition 1, $I_{D} (K_{m, n}) = ⋂_{i = 0}^{n - 1} Q_{i}$ is stable for $γ_{0}$ , where $γ_{0} = max {γ (i) | 0 \leq i \leq n - 1} = m + (2 m - 1) (n - 1)$ and by theorem 1, $r e g (I_{D} (K_{m, n})) \leq m + (2 m - 1) (n - 1) .$

Example 3. Consider $K_{4, 3},$ here $m = 4$ and $n = 3.$
$D (G_{0}) = {x_{1}, x_{2}, x_{3}}$ , $Q_{0} = ⟨ x_{1}^{4}, x_{2}^{4}, x_{3}^{4}, x_{4}^{3}, x_{5}^{3}, x_{6}^{3}, x_{7}^{3} ⟩$ and $r e g (Q_{0}) = 18$ , see Figure $6$ .

$D (G_{1}) = {x_{1}, x_{2}}$ , $Q_{1} = ⟨ x_{1}^{4}, x_{2}^{4}, x_{3}^{2}, x_{4}^{2}, x_{5}^{2}, x_{6}^{2} ⟩$ and $r e g (Q_{1}) = 11$ ,see Figure $7$ .

$D (G_{2}) = {x_{1}}$ , $Q_{2} = ⟨ x_{1}^{4}, x_{2}, x_{3}, x_{4}, x_{5} ⟩$ and $r e g (Q_{2}) = 4$ , see Figure $8$ .

Remark 3. As elimination ideals are of Borel type ideals and an upper bound for Borel type ideal were discussed in [2] and [1]. It is worthy to note that our given bounds are sharper than the one given in [2] and [7].

Acknowledgement

The first and second authors were supported by the Higher Education Commission (Islamabad) through the National Research Program for Universities, Grant No.7359/Punjab/NRPU/R $&$ D/ HEC/ 2017.

Conflict of Interest

The author declares no conflict of interests.

References:

Herzog, J., Popescu, D. and Vladoiu, M., 2003. On the Ext-modules of ideals of Borel type. Contemporary Mathematics, 331, pp.171-186. [Google Scholor]
Ahmad, S. and Anwar, I., 2008. An upper bound for the regularity of ideals of Borel type. Communications in Algebra, 36(2), pp.670-673.[Google Scholor]
Anwar, I. and Khalid, A., 2019. Algebraic characterization of graphical degree stability. Communications of the Korean Mathematical Society, 34(1), pp.113-125. [Google Scholor]
Bayer, D. and Mumford, D., 1993. What can be computed in Algebraic Geometry? in Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica XXXIV, 1 – 48. [Google Scholor]
Cimpoeas, M., 2008. A stable property of Borel type ideals. Communications in Algebra, 36(2), pp.674-677. [Google Scholor]
Eisenbud, D., Reeves, A. and Totaro, B., 1994. Initial ideals, Veronese subrings, and rates of algebras. Advances in Mathematics, 109(2), pp.168-187. [Google Scholor]
Cimpoeas, M., 2007. Contributions in combinatorics in commutative algebra, Ph.D. Thesis, University of Bucharest. [Google Scholor]

[1] Herzog, J., Popescu, D. and Vladoiu, M., 2003. On the Ext-modules of ideals of Borel type. Contemporary Mathematics, 331, pp.171-186. [Google Scholor]

[2] Ahmad, S. and Anwar, I., 2008. An upper bound for the regularity of ideals of Borel type. Communications in Algebra, 36(2), pp.670-673.[Google Scholor]

[3] Anwar, I. and Khalid, A., 2019. Algebraic characterization of graphical degree stability. Communications of the Korean Mathematical Society, 34(1), pp.113-125. [Google Scholor]

[4] Bayer, D. and Mumford, D., 1993. What can be computed in Algebraic Geometry? in Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica XXXIV, 1 – 48. [Google Scholor]

[5] Cimpoeas, M., 2008. A stable property of Borel type ideals. Communications in Algebra, 36(2), pp.674-677. [Google Scholor]

[6] Eisenbud, D., Reeves, A. and Totaro, B., 1994. Initial ideals, Veronese subrings, and rates of algebras. Advances in Mathematics, 109(2), pp.168-187. [Google Scholor]

[7] Cimpoeas, M., 2007. Contributions in combinatorics in commutative algebra, Ph.D. Thesis, University of Bucharest. [Google Scholor]

Contents

Ars Combinatoria