October 01, 2025
We introduce the abstract notion of squarefree-power-like functions, which unify the sequences of squarefree ordinary and symbolic powers of squarefree monomial ideals. By employing the Tor-vanishing criteria for mixed sums of ideals, we establish sharp lower bounds for their Castelnuovo–Mumford regularity in terms of what we call the admissible set of the associated hypergraph. As an application, we derive the first general combinatorial lower bound for the regularity of squarefree symbolic powers of monomial ideals. In the setting of edge ideals, by exploiting the special combinatorial structures of block graphs and Cohen-Macaulay chordal graphs, we show that this bound turns into an exact formula for all squarefree symbolic powers of block graphs, as well as for the second squarefree symbolic powers of edge ideals of Cohen–Macaulay chordal graphs.
The study of various powers of ideals, such as ordinary powers, symbolic powers, integral closure powers, etc. has long been a central theme in commutative algebra. Much of the work in this area focuses on homological invariants of these powers and seeks to understand their asymptotic behavior. A classical result in this direction is Brodmann’s theorem [1], which establishes the stability of the associated primes of powers of ideals. Cutkosky, Herzog, and Trung [2], and independently Kodiyalam [3], proved that the regularity of powers of a homogeneous ideal eventually becomes a linear function; similar results hold in greater generality [4], and in particular for symbolic powers of ideals [5], [6]. In contrast, the study of specific small powers of a given class of ideals is much more challenging, as many invariants tend to behave unpredictably for lower powers (see, for instance, [7], [8]).
Squarefree powers were introduced very recently in [9] and have since been investigated extensively by several authors (see, for example, [10]–[17], and the references therein). There are two important motivations to study squarefree powers. First, they are closely connected to matching theory, providing an algebraic framework to study matchings in a graph. Secondly, the minimal free resolution of a squarefree power of an ideal appears as a subcomplex of the minimal free resolution of the corresponding ordinary power; hence, squarefree powers of an ideal provide valuable information about the ordinary powers. Interestingly, from the definition of squarefree powers, it follows that for any given squarefree monomial ideal \(I\), there exists an integer \(k>0\) such that \(I^{[n]}=0\) for all \(n \geq k\). Thus, unlike ordinary powers, square-free powers do not admit an asymptotic behavior, making the study of their homological invariants significantly different.
Recently, Fakhari introduced a symbolic analogue of this new notion in [18], referring to it as the squarefree part of symbolic powers. In this article, we refer to these simply as squarefree symbolic powers (defined in 2). The sequences of squarefree (ordinary) powers and squarefree symbolic powers of squarefree monomial ideals exhibit similar behaviors, for instance, both are decreasing and satisfy certain Tor-vanishing conditions (see 2 for details). A central motivation for this work is to explore and unify these two sequences within a broader framework, with the aim of studying their Castelnuovo–Mumford regularity. This leads us to the following guiding question:
Question 1. Let \(\mathcal{I} = \{I_i\}_{i \geq 0}\) be a decreasing sequence of squarefree monomial ideals arising from various powers of a monomial ideal in a polynomial ring. Is there an effective way to provide a combinatorial bound for the Castelnuovo–Mumford regularity for all such ideals?
To address this question, we introduce the notion of squarefree-power-like function \(\mathtt{F}\) along with an associated combinatorial invariant, which we call the \(k\)-admissible \(\mathtt{F}\)-number. Let \(I\) be a squarefree monomial ideal and \(\mathcal{G}(I)\) be the set of minimal monomial generators of \(I\). We can consider \(I\) as the edge ideal \(I=I(\mathcal{H})\), where \(\mathcal{H}\) is the hypergraph corresponding to the ideal \(I\). For each positive integer \(k\geq 1\), we define the function \(\mathtt{F}(\mathcal{H}, k)\) to be a squarefree monomial ideal, which satisfies some desired properties (see 1). This, in particular, provides a shared platform to study both the notions of squarefree powers \(I^{[k]}\) and squarefree symbolic powers \(I^{\{k\}}\). We further introduce the concept of a \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\) and define the associated combinatorial invariant, the \(k\)-admissible \(\mathtt{F}\)-number, denoted by \(\mathrm{adm}^{\mathtt{F}}(\mathcal{H},k)\). This invariant plays a key role in establishing one of the main results of the paper described below.
Let \(\mathcal{H}\) be a hypergraph and \(\mathtt{F}\) a squarefree-power-like function. Then, for any \(1 \le k \le \nu_{\mathtt{F}}(\mathcal{H})\), we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H},k) \right) \geq \mathrm{adm}^{\mathtt{F}}(\mathcal{H},k) + k.\]
We note that this bound is sharp when \(I(\mathcal{H})\) is a complete intersection, that is, when \(\mathcal{H}\) is a disjoint union of edges (see 5). Furthermore, we show that both squarefree powers and squarefree symbolic powers fit into this framework (see 4 and 7). In particular, the lower bound in 4 recovers the bound established for squarefree powers in [19].
For squarefree symbolic powers \(I(\mathcal{H})^{\{k\}}\), we refine the concept of \(k\)-admissible \(\mathtt{F}\)-sets by incorporating combinatorial invariants of the underlying hypergraph. This leads to the definition of \(k\)-admissible independence number of \(\mathcal{H}\), denoted by \(\mathrm{ind}(\mathcal{H}, k)\) (see 3). It follows from the definition of squarefree symbolic powers that \(I(\mathcal{H})^{\{k\}}=0\) whenever \(k> \mathrm{ht}(I(\mathcal{H}))\) and using 4 we establish that for all \(1\leq k\leq \mathrm{ht}(I(\mathcal{H}))\), \(\mathrm{reg}(I(\mathcal{H})^{\{k\}}) \geq \mathrm{ind}(\mathcal{H},k)+k\) (2). It is worthwhile to mention that the only known lower bound for the regularity of squarefree symbolic powers is provided by Fakhari in [18] for a graph \(G\), and the power \(k\) is always bounded above by the induced matching number \(\nu(G)\) in this case. Note that, in general, \(\nu(G)\le \mathrm{ht}(I(G))\) for an arbitrary graph \(G\). Moreover, the difference can be arbitrarily large (for instance, complete graphs). Thus, 2 substantially extends the only known lower bound for the regularity of squarefree symbolic powers to all squarefree symbolic powers of edge ideals of arbitrary hypergraphs.
We further investigate the sharpness and compatibility of our bounds with those from [10], [18]–[20]. For complete graphs, the lower bound is attained (see 11). In [10], Crupi, Ficarra, and Lax refined the earlier bound of [20] and derived an exact formula for the regularity of squarefree powers of forests in terms of the combinatorial invariant \(\mathrm{aim}(G,k)\). This result was later extended to block graphs in [19]. Since block graphs form a natural and important subclass of chordal graphs that generalizes forests, the comparison between these invariants becomes particularly meaningful. Notably, for the class of forests \(I(G)^{\{k\}}=I(G)^{[k]}\) and the notion \(\mathrm{ind}(G,k)\) coincides with \(\mathrm{aim}(G,k)\). However, for general block graphs, neither of these identities needs to hold, that is, \(I(G)^{\{k\}}\neq I(G^{[k]})\) and \(\mathrm{ind}(G,k) \neq \mathrm{aim}(G,k)\), in general. Our second main goal in this context is to find an exact formula for the regularity of squarefree symbolic powers of edge ideals of block graphs in the spirit of [19]. Interestingly, in this case, we are able to explicitly determine \(\mathrm{reg}(I(G)^{\{k\}})\) in terms of the combinatorial invariant \(\mathrm{ind}(G,k)\), and we do this by establishing several technical lemmas and combinatorial constructions to track \(\mathrm{ind}(G,k)\) and the minimal generators of \(I(G)^{\{k\}}\). In particular, this leads to our second main theorem, stated as follows:
Let \(G\) be a block graph. Then for each \(1 \le k \le \mathrm{ht}(I(G))\), we have \[\mathrm{reg}(I(G)^{\{k\}}) = \mathrm{ind}(G,k) + k.\]
Moreover, we show in 6 that a similar formula holds for the second squarefree symbolic power of Cohen-Macaulay chordal graphs, analogous to [19]. This paper is organized as follows. In 2, we recall some preliminary notions from combinatorics and commutative algebra. We also review homological properties of filtrations of monomial ideals and study how they can be adapted for the case of squarefree powers. The main section of this article is 3, where we introduce the abstract notion of squarefree-power-like function and establish a general lower bound for regularity. As an application, in 4, we relate this general lower bound to certain well-known graph-theoretic invariants, which yields a sharp combinatorial lower bound for the squarefree symbolic powers of monomial ideals. Furthermore, in 5 and 6, we show that this general lower bound is attained for all squarefree symbolic powers of block graphs, and for the second squarefree symbolic powers of Cohen-Macaulay chordal graphs, respectively.
In this section, we begin by recalling some preliminary notions from combinatorics and commutative algebra, and we refer to [21]–[23] for any undefined terminology. After setting up the necessary background, we proceed to derive results concerning the regularity of the mixed sum of eventually vanishing decreasing sequences of monomial ideals. These results will play a central role in the latter part of the article.
A (simple) hypergraph \(\mathcal{H}\) is an ordered pair \(\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H}))\), where \(V(\mathcal{H})\) is a finite set, called the vertex set, and \(E(\mathcal{H})\) is a family of subsets of \(V(\mathcal{H})\), called the edge set, such that no two elements contain one another. The elements of \(V(\mathcal{H})\) are referred to as vertices, and the elements of \(E(\mathcal{H})\) as edges. For \(W\subseteq V(\mathcal{H})\), the induced sub-hypergraph of \(\mathcal{H}\) on \(W\), denoted by \(\mathcal{H}[W]\), is defined by \(V(\mathcal{H}[W])=W \, \text{and} \, E(\mathcal{H}[W])=\{\mathcal{E}\in E(\mathcal{H})\mid \mathcal{E}\subseteq W\}\). The hypergraph \(\mathcal{H}[V(\mathcal{H})\setminus W]\) is also denoted by \(\mathcal{H}\setminus W\). If \(W=\{x\}\) for some \(x\in V(\mathcal{H})\), then we simply write \(\mathcal{H}\setminus x\). A matching of \(\mathcal{H}\) is a collection of edges \(M\subseteq E(\mathcal{H})\) such that \(\mathcal{E}\cap \mathcal{E}'=\emptyset\) for any distinct \(\mathcal{E},\mathcal{E}'\in M\). A matching \(M\) is called an induced matching if \(E\big(\mathcal{H}\big[\cup_{\mathcal{E}\in M}\mathcal{E}\big]\big)=M\). The induced matching number of \(\mathcal{H}\), denoted by \(\nu_1(\mathcal{H})\), is the maximum cardinality of an induced matching in \(\mathcal{H}\).
A (simple) graph \(G\) is a hypergraph whose edges all have cardinality two. For \(A\subseteq V(G)\), the set of closed neighbors of \(A\) is defined by \(N_{G}[A]\mathrel{\vcenter{:}}= A\cup \{x\in V(G)\mid \{x,y\}\in E(G)\;\text{for some } y\in A\}\). The set of open neighbors of \(A\) is \(N_{G}(A)\mathrel{\vcenter{:}}= N_{G}[A]\setminus A\). If \(A=\{x\}\), then we simply write \(N_G(x)\) for \(N_G(\{x\})\). For \(x\in V(G)\), the number \(|N_G(x)|\) is called the degree of \(x\) and is denoted by \(\deg(x)\). If \(\deg(x)=1\), then the unique edge adjacent to \(x\) is called a whisker of \(G\). Given two vertices \(x,y\in V(G)\), an induced path of length \(n\) between \(x\) and \(y\) is a sequence of vertices \(P: a_1,\ldots,a_n\) such that \(a_1=x\), \(a_n=y\), and \(\{a_i,a_j\}\in E(G)\) if and only if \(j=i-1\) or \(j=i+1\). A complete graph on \(n\) vertices, denoted \(K_n\), is a graph in which every pair of vertices is joined by an edge. A clique of a graph \(G\) is a complete induced subgraph of \(G\). A maximal clique in \(G\) is called a block. A vertex \(x\in V(G)\) is called a free vertex (or a simplicial vertex) of \(G\) if \(G[N_{G}(x)]\) is complete. Two edges \(e,e'\in E(G)\) are said to form a gap in \(G\) if \(\{e,e'\}\) is an induced matching in \(G\). The complement of a graph \(G\), denoted \(G^c\), is the graph with \(V(G^c)=V(G) \, \text{and}\, E(G^c)=\{\{x,y\}\mid \{x,y\}\notin E(G)\}\).
A cycle of length \(m\), denoted \(C_m\), is the graph with \(V(C_m)=\{x_1,\ldots,x_m\}, \, E(C_m)=\{\{x_1,x_m\}\}\cup\{\{x_i,x_{i+1}\}\mid 1\le i\le m-1\}\). The cycle \(C_3\) is also sometimes called a triangle. A graph \(G\) is called a forest if it contains no cycle. A connected forest is called a tree. A graph \(G\) is called chordal if it has no induced cycle \(C_n\) with \(n\geq 4\). A graph is said to be weakly chordal if both \(G\) and \(G^c\) contain no induced cycle \(C_n\) with \(n\geq 5\). Note that every chordal graph is weakly chordal. A block graph \(G\) is a chordal graph such that any two blocks in \(G\) intersect in at most one common vertex. A graph \(G\) is said to be a whisker graph if every vertex of \(G\) is either of degree \(1\) or is a neighbor of a degree \(1\) vertex.
For a graded ideal \(I\subseteq R\), the graded minimal free resolution of \(I\) is an exact sequence \[\mathcal{F}_{\cdot}: \quad 0 \longrightarrow F_t \xrightarrow{\partial_{t}} \cdots \xrightarrow{\partial_{2}} F_1 \xrightarrow{\partial_1} F_0 \xrightarrow{\partial_0} I \longrightarrow 0,\] where \(F_i=\bigoplus_{j\in\mathbb{N}} R(-j)^{\beta_{i,j}(I)}\) is a free \(R\)-module for each \(i\ge 0\), and \(R(-j)\) is the polynomial ring \(R\) with grading shifted by \(j\). The integers \(\beta_{i,j}(I)\) are called the \(i^{\text{th}}\) \(\mathbb{N}\)-graded Betti numbers of \(I\) in degree \(j\). The Castelnuovo–Mumford regularity (or simply, regularity) of \(I\), denoted by \(\mathrm{reg}(I)\), is defined as \(\mathrm{reg}(I)\mathrel{\vcenter{:}}= \max\{\, j-i \mid \beta_{i,j}(I)\neq 0 \,\}\). If \(I\) is the zero ideal, we adopt the convention \(\mathrm{reg}(I)=0\). Moreover, we define \(\mathrm{reg}(R)\mathrel{\vcenter{:}}= 0\). The following two well-known results on the regularity of graded ideals will be used frequently in subsequent sections.
Lemma 1. [24]Let \(I \subseteq R=\mathbb{K}[x_1,\ldots,x_n]\) be a monomial ideal, \(m\) a monomial of degree \(d\) in \(R\), and \(x\) an indeterminate in \(R\). Then:
\(\mathrm{reg}(I+( x))\le \mathrm{reg}(I)\),
\(\mathrm{reg}(I:x)\le \mathrm{reg}(I)\),
\(\mathrm{reg}(I) \le \max\{\mathrm{reg}(I:m) + d,\;\mathrm{reg}(I+( m))\}\).
Lemma 2. [23]Let \(I_1\subseteq R_1=\mathbb{K}[x_1,\ldots,x_m]\) and \(I_2\subseteq R_2=\mathbb{K}[x_{m+1},\ldots,x_n]\) be graded ideals. Consider the ideal \(I=I_1R+I_2R \subseteq R=\mathbb{K}[x_1,\ldots,x_n]\). Then \[\mathrm{reg}(I)=\mathrm{reg}(I_1)+\mathrm{reg}(I_2)-1.\]
Let \(\mathcal{H}\) be a hypergraph on the vertex set \(V(\mathcal{H})=\{x_1,\ldots,x_n\}\). Identifying the vertices of \(\mathcal{H}\) as indeterminates, we consider the polynomial ring \(R=\mathbb{K}[x_1,\ldots,x_n]\) over a field \(\mathbb{K}\). Corresponding to any \(F\subseteq \{x_1,\ldots,x_n\}\), we denote the square-free monomial \(\prod_{x_i\in F}x_i\) of \(R\) by \(\mathbf{x}_{F}\). The edge ideal of \(\mathcal{H}\), denoted by \(I(\mathcal{H})\), is a square-free monomial ideal of \(R\) defined as \[I(\mathcal{H})\mathrel{\vcenter{:}}= \left ( \mathbf{x}_{\mathcal{E}}\mid \mathcal{E}\in E(\mathcal{H})\right ).\] Note that any square-free monomial ideal can be seen as the edge ideal of a hypergraph. In general, for a monomial ideal \(I\), we denote by \(\mathrm{Ass}_I\) the set of its minimal prime ideals. Given an integer \(k \geq 1\), the \(s^{\text{th}}\) symbolic power of \(I\), written as \(I^{(k)}\), is defined by \[I^{(k)} \mathrel{\vcenter{:}}= \bigcap\limits_{\mathfrak p \in \mathrm{Ass}_I} \ker\!\left(R \longrightarrow (R/I^k)_{\mathfrak p}\right).\] Suppose now that \(I\) is a squarefree monomial ideal in \(R\), and let \(I = \mathfrak p_1 \cap \cdots \cap \mathfrak p_r\) be its irredundant primary decomposition, where each \(\mathfrak p_i\) is generated by a subset of the variables of \(S\). Then, by [25], for every \(k \geq 1\) we have \[I^{(k)} = \mathfrak p_1^k \cap \cdots \cap \mathfrak p_r^k.\] The ideal generated by the square-free monomials in \(\mathcal{G}(I^{(k})\) is denoted by \(I^{\{k\}}\), and is called as the \(k^{\text{th}}\) squarefree symbolic power of \(I\). Thus, by definition, we obtain the following.
Lemma 3. (cf. [18])Let \(I\subseteq R\) be a squarefree monomial ideal, and \(I=P_1\cap\cdots \cap P_r\) be an irredundant primary decomposition, where every \(P_i\) is generated by a subset of the variables in \(R\). Then \[I^{\{k\}}=P_1^{\{k\}}\cap \cdots \cap P_r^{\{k\}}.\]
By convention, \(I^{\{k\}}=R\) for all \(k\le 0\). The following two lemmas on the squarefree symbolic powers of edge ideals of graphs will be heavily used in the subsequent sections.
Lemma 4. [18]Let \(G\) be a graph and \(x_1\) is a simplicial vertex of \(G\) with \(N_G[x_1]=\{x_1,\ldots , x_d\}\), for some integer \(d\geq 2\). Then for every integer \(k\geq 1\), \[(I(G)^{\{k\}}:x_1x_2\cdots x_d)=I(G\setminus N_G[x_1])^{\{k-d+1\}}.\]
Lemma 5. [18]Let \(G\) be a graph and suppose that \(W = \{x_1,\ldots , x_d\}\) is a nonempty subset of vertices of \(G\). Then for every integer \(k \geq 1\), \[\mathrm{reg}(I(G)^{\{k\}}:x_1)\leq \max \{\mathrm{reg}(I(G\setminus U_1)^{\{k\}}: \mathbf{x}_{U_2})+|U_2|-1\mid x_1\in U_2, U_1\cap U_2=\emptyset, U_1\cup U_2=W\}.\]
In this subsection, we consider the regularity of the mixed sum of a filtration of ideals in a polynomial ring. A sequence \(\mathcal{I}=\{I_i\}_{i\geq 0}\) of ideals in a polynomial ring \(A=\mathbb{K}[x_1,\dots, x_r]\) is said to be a filtration if it satisfies the following three conditions:
\(I_0=A\);
\(I_1\) is a non-zero proper ideal in \(A\);
\(I_i\supseteq I_{i+1}\) for all \(i\ge 0\).
Let \(\mathcal{I}=\{I_i\}_{i\geq 0}\) (resp, \(\mathcal{J}=\{J_j\}_{j\geq 0}\)) be a filtration of monomial ideals of \(A=\mathbb{K}[x_1,\dots, x_r]\) (resp, \(B=\mathbb{K}[y_1,\dots, y_s]\)). For each \(n\geq 0\), \[Q_n=\sum_{i+j=n}(I_iR)(J_jR),\] is an ideal of \(R=A\otimes_\mathbb{K}B\). The ideal \(Q_n\) is sometimes referred to as a mixed sum of \(\mathcal{I}\) and \(\mathcal{J}\). Homological invariants of \(Q_n\) are computable directly from those of ideals of \(\mathcal{I}\) and \(\mathcal{J}\) in special cases. Recall that \(\mathcal{I}\) is called Tor-vanishing if for each \(i\geq 1\), the inclusion map \(I_i\to I_{i-1}\) is Tor-vanishing, i.e., the map \(\operatorname{Tor}_n^A(\mathbb{K}, I_i)\to \operatorname{Tor}_n^A(\mathbb{K}, I_{i-1})\) is the zero map for all \(n\geq 0\).
Theorem 1. If \(\mathcal{I}\) and \(\mathcal{J}\) are Tor-vanishing, then \[\mathrm{reg}(Q_n) = \max_{\substack{i\in [1,n-1]\\ j\in [1,n]}} \{ \mathrm{reg}(I_{n-i}) + \mathrm{reg}(J_i) , \quad \mathrm{reg}(I_{n-j+1}) + \mathrm{reg}(J_j) - 1 \}\] for any \(n\geq 0\).
In the sequel, we often encounter filtration that is eventually \(0\). For this reason, for a filtration of monomial ideal \(\mathcal{I}=\{I_i\}_{\geq 0}\), we define \[\nu (\mathcal{I}) = \sup \{n\geq 0\colon I_n\neq 0 \}.\] With this invariant one can optimize 1, as for any \(n\geq 0\), we have \[Q_n = \sum_{ \max \{ 0,n-\nu(\mathcal{I}) \} \leq i\leq \min \{n,\nu(\mathcal{J})\}} I_{n-i} J_{i}.\] As the arguments are almost line-by-line as those of the proof of [26], we state our result and give only a sketch of the proof.
Theorem 2. If \(\mathcal{I}\) and \(\mathcal{J}\) are Tor-vanishing, then \[\begin{align} \mathrm{reg}(Q_n) &=\begin{multlined}[t] \max_{\substack{i\in [\max\{0,n-\nu(\mathcal{I)}\},\;\min\{n,\nu(\mathcal{J})]\\j\in [\max\{0,n-\nu(\mathcal{I)}\}+1,\;\min\{n,\nu(\mathcal{J})]}} \{\mathrm{reg}(I_{n-i}) + \mathrm{reg}(J_i) , \quad \mathrm{reg}( I_{n-j+1}) + \mathrm{reg}(J_j) -1 \} \end{multlined} \\ &=\begin{multlined}[t] \max_{\substack{i\in [\max\{1,n-\nu(\mathcal{I})\},\;\min\{n-1,\nu(\mathcal{J})\} ]\\j\in [\max\{0,n-\nu(\mathcal{I)}\}+1,\;\min\{n,\nu(\mathcal{J})]}} \{\mathrm{reg}(I_{n-i}) + \mathrm{reg}(J_i) , \quad \mathrm{reg}( I_{n-j+1}) + \mathrm{reg}(J_j) -1 \} \end{multlined} \end{align}\] for any \(n\in [0,\nu(\mathcal{I})+\nu(\mathcal{J})]\).
Sketch of the proof. Set \[a\mathrel{\vcenter{:}}=\max\{0,n-\nu(\mathcal{I)}\}, \quad b= \min\{n,\nu(\mathcal{J})\}, \quad a'\mathrel{\vcenter{:}}= \max\{1,n-\nu(\mathcal{I})\}, \quad \text{and}\quad b'\mathrel{\vcenter{:}}= \min\{n-1,\nu(\mathcal{J})\}.\] For each \(t\in [a,b]\), set \[P_{n,t} = \sum_{ i =a }^t I_{n-i} J_{i}.\] Then \(P_{n,t}=P_{n,t-1}+I_{n-t}J_{t}\) is a Betti splitting (cf. [27]), due to the fact that \(\mathcal{I}\) and \(\mathcal{J}\) are Tor-vanishing filtration of monomial ideals generated in distinct sets of variables, and \(P_{n,t-1}\cap I_{n-t}J_{t}=I_{n-t+1}J_{t}\). Therefore, we have \[\mathrm{reg}P_{n,t} = \max\{ \mathrm{reg}P_{n,t-1}, \quad \mathrm{reg}I_{n-t} + \mathrm{reg}J_{t}, \quad \mathrm{reg}I_{n-t+1} + \mathrm{reg}J_{t}-1 \}.\] Using induction on \(t\), remarking that \(Q_n=P_{n,b}\), with the base case \(\mathrm{reg}P_{n,a} =\mathrm{reg}(I_{n-a}J_{a}) = \mathrm{reg}I_{n-a}+ \mathrm{reg}J_{a}\), we obtain \[\begin{align} \mathrm{reg}\;Q_n = \begin{multlined}[t] \max_{\substack{i\in [a,b]\\j\in [a+1,b]}} \{\mathrm{reg}\;I_{n-i} + \mathrm{reg}\;J_i , \quad \mathrm{reg}\;I_{n-j+1} + \mathrm{reg}\;J_j -1 \}, \end{multlined} \end{align}\] which proves the first equality. There are potentially a few numbers in the above set that can be ignored without changing the maximum. We have \[\begin{align} \mathrm{reg}\;I_0 + \mathrm{reg}\;J_n &= 0 + \mathrm{reg}\;J_n \leq \mathrm{reg}\;I_{1} + \mathrm{reg}\; J_n -1,\\ \mathrm{reg}\;I_n + \mathrm{reg}\;J_0 &= \mathrm{reg}\;I_n + 0 \leq \mathrm{reg}\;I_{n} + \mathrm{reg}\; J_1 -1 \end{align}\] as \(I_1\) and \(J_1\) are non-zero proper ideals. Thus, we can put new bounds on \(i\) without changing the equality, as follows: \[\begin{align} i&\geq \max \{a,1\} = \max\{0,n-\nu(\mathcal{I}),1\} = a',\\ i&\leq \min \{ b,n-1 \} = \min \{n, \nu(\mathcal{J}), n-1\} = b'. \end{align}\] The second equality then follows. ◻
We recall a sufficient condition for an inclusion of monomial ideals to be Tor-vanishing. For a monomial \(m\), let \(\mathrm{supp}(m)\), called the support of \(m\), denote the set of variables that divide \(m\). For a monomial ideal \(I\), let \(\partial^*(I)\) denote the monomial ideal generated by \(m/x\), where \(m\in \mathcal{G}(I)\) and \(x\in \mathrm{supp}(m)\).
Lemma 6. If \(I\subseteq I'\) are two nonzero monomial ideals such that \(\partial^*(I)\subseteq I'\), then the inclusion \(I\hookrightarrow I'\) is Tor-vanishing.
For a monomial ideal \(I\), the ordinary powers \(\{I^n\}_{n\geq 0}\) and symbolic powers \(\{I^{(n)}\}_{n\geq 0}\) are among known examples that satisfy the condition in 6 ([28] and [26]), and thus in particular, are Tor-vanishing. We will show a new way to obtain Tor-vanishing filtration. For a monomial ideal \(I\), let \(\mathrm{sqf}(I)\) be the ideal generated by the squarefree monomials belonging to \(I\); if \(I\) does not contain any squarefree monomial, then \(\mathrm{sqf}(I)=( 0 )\). By convention, \(\mathrm{sqf}(R)=R\).
Lemma 7. Let \(\{I_i\}_{i\geq 0}\) be a filtration of monomial ideal and \(k\geq 1\) a positive integer. If \(\partial^*(I_k)\subseteq I_{k-1}\), then \(\partial^*(\mathrm{sqf}(I_k))\subseteq \mathrm{sqf}(I_{k-1})\).
Proof. We have \[\partial^*(\mathrm{sqf}(I_k))\subseteq \partial^*(I_k)\subseteq I_{k-1}.\] The result then follows from taking the squarefree part of both sides, remarking that \(\mathrm{sqf}\left(\partial^*(\mathrm{sqf}(I_k))\right)=\partial^*(\mathrm{sqf}(I_k))\) as the latter is squarefree. ◻
Two filtration of monomial ideals that are known to satisfy the condition in 7 are \(\{I^n\}_{n\geq 0}\) and \(\{I^{(n)}\}_{n\geq 0}\) where \(I\) is a monomial ideal ([28] and [26]). Now assume that \(I\) is a squarefree monomial ideal. Then by taking the squarefree part, we obtain the two filtrations \(\{I^{[n]}\}_{n\geq 0}\) and \(\{I^{\{n\}}\}_{n\geq 0}\). Note that \(\nu\left(\{I^{[n]}\}_{n\geq 0}\right)\) is exactly the matching number of the associated hypergraph, and \(\nu\left(\{I^{\{n\}}\}_{n\geq 0}\right)\) is exactly \(\mathrm{ht}(I)\). The following follows directly from 6 and 7.
Corollary 1. Let \(I\) be a squarefree monomial ideal. Then \(\{I^{[n]}\}_{n\geq 0}\) and \(\{I^{\{n\}}\}_{n\geq 0}\) are Tor-vanishing.
Before going to the next section, we set up some notations and terminologies that we will use in the subsequent sections. For \(A\subseteq \{x_1,\ldots,x_n\}\), \((A)\) denote the monomial ideal \((x\mid x\in A)\) in the polynomial ring \(R=\mathbb{K}[x_1,\ldots,x_n]\). If \(\mathfrak p\) is a prime ideal in \(R\) generated by monomials \(\{x_i\mid x_i\in B\subseteq\{x_1,\ldots,x_n\}\}\), then we sometimes identify the set \(B\) with the ideal \(\mathfrak p\), and write \(\mathfrak p\) as \(\mathfrak p_B\).
In this section, we define the notion of a squarefree-power-like function. The idea is to create a common framework for squarefree powers and squarefree symbolic powers of squarefree monomial ideals. The goal is to give a sharp combinatorial lower bound on their regularity.
For a monomial ideal \(I\) and a monomial \(m\), let \(I^{\leq m}\) denote the monomial ideal generated by monomials in \(I\) that divide \(m\). This action is often referred to as restriction (with respect to \(m\)).
Definition 1 (Squarefree-power-like function). Fix a set of variables \(V\). Let \(\mathtt{F}\) be a function that maps a pair \((\mathcal{H},k)\) of a hypergraph \(\mathcal{H}\) with \(V(\mathcal{H})\subseteq V\) and a non-negative integer \(k\) to a squarefree monomial ideal \(\mathtt{F}(\mathcal{H},k)\) in \(S=\mathbb{K}[V]\), satisfying the following property:
\(\mathtt{F}(\mathcal{H},0)=S\), \(\mathtt{F}(\mathcal{H},1)=I(\mathcal{H})\), and \(\mathtt{F}(\mathcal{H},k)\) is generated by monomials in \(\mathbb{K}[V(\mathcal{H})]\).
\(\partial^{\ast}\,\mathtt{F}(\mathcal{H},k)\subseteq \mathtt{F}(\mathcal{H},k-1)\) for any positive integer \(k\).
For any hypergraph \(\mathcal{H}\), an induced sub-hypergraph \(\mathcal{H}_1\) of \(\mathcal{H}\), and any integer \(k\), we have \[\mathtt{F}(\mathcal{H},k)^{\leq\mathbf{x}_{V(\mathcal{H}_1)}} = \mathtt{F}(\mathcal{H}_1,k).\]
For any hypergraphs \(\mathcal{H}_1\) and \(\mathcal{H}_2\) in disjoint sets of vertices, and any integer \(k\geq 1\), we have \[\mathtt{F}(\mathcal{H}_1+ \mathcal{H}_2,k) = \sum_{i=0}^k \mathtt{F}(\mathcal{H}_1,i)\mathtt{F}(\mathcal{H}_2,k-i),\] where \(\mathcal{H}_1+\mathcal{H}_2\) denotes the hypergraph whose vertex and edge sets are exactly the union of the vertex and edge sets of \(\mathcal{H}_1\) and \(\mathcal{H}_2\), respectively.
We call this function \(\mathtt{F}\) a squarefree-power-like function (on \(V\)).
For the remainder of the section, \(\mathtt{F}\) denotes a squarefree-power-like function. We remark that there are a few properties that can be further deduced from our definition. For a monomial ideal \(I\), set \(\delta(I)\mathrel{\vcenter{:}}= \inf\{\deg(m)\colon m\in I\}\). For a hypergraph \(\mathcal{H}\), the sequence \(\{\mathtt{F}(\mathcal{H},i)\}_{i\geq 0}\) is a filtration of monomial ideals, and it eventually terminates at the zero ideal. Indeed, if \(m\) is a monomial in \(\mathtt{F}(\mathcal{H},n)\) for some integer \(n\), then \(m/x\in \partial^* \mathtt{F}(\mathcal{H},n)\subseteq \mathtt{F}(\mathcal{H},n-1)\). This implies that \(\delta(\mathtt{F}(\mathcal{H},n))>\delta(\mathtt{F}(\mathcal{H},n-1))\) for any \(n\geq 1\). Moreover, since \(\mathtt{F}(\mathcal{H},n)\) is an ideal generated by squarefree monomials in \(\mathbb{K}[V(\mathcal{H})]\) (1(a)), we have \(\delta(\mathtt{F}(\mathcal{H},n))\leq |V(\mathcal{H})|\) if \(\mathtt{F}(\mathcal{H},n)\neq 0\). Therefore, \(\delta(\mathtt{F}(\mathcal{H},n))=\infty\), or equivalently, \(\mathtt{F}(\mathcal{H},n)=0\), for any \(n> |V(\mathcal{H})|\). The smallest \(k_0\) for which \(\mathtt{F}(\mathcal{H},k)=0\) for all \(k>k_0\) is said to be the \(\mathtt{F}\)-number of \(\mathcal{H}\), and we will denote it by \(\nu_\mathtt{F}(H)\). We obtain some basic results on \(\mathtt{F}\)-numbers below.
Lemma 8.
For any two hypergraphs \(\mathcal{H}_1\) and \(\mathcal{H}_2\) in disjoint set of vertices, \[\nu_\mathtt{F}(\mathcal{H}_1\sqcup \mathcal{H}_2)=\nu_\mathtt{F}(\mathcal{H}_1)+\nu_\mathtt{F}(\mathcal{H}_2).\]
For any hypergraph \(\mathcal{H}\), if \(\mathtt{F}(\mathcal{H},k)=\left(\prod_{x\in V(\mathcal{H})} x \right)\), then \(\nu_\mathtt{F}(\mathcal{H})=k\).
Proof. (1) follows immediately from 1(d). As for (2), assume that \(\mathtt{F}(\mathcal{H},k+1)\neq 0\). Then \[|V(\mathcal{H})|=\delta(\mathtt{F}(\mathcal{H},k))< \delta(\mathtt{F}(\mathcal{H},k+1)) \leq |V(\mathcal{H})|,\] a contradiction. Thus, \(\mathtt{F}(\mathcal{H},k+1)=0\). Since \(\mathtt{F}(\mathcal{H},k)\neq 0\), the result follows. ◻
The next result justifies our name choice.
Proposition 2. If \(\mathcal{H}\) is a disjoint union of edges, then \(\mathtt{F}(\mathcal{H},k)=I(\mathcal{H})^{[k]}\) for any integer \(k\).
Proof. Set \(\mathcal{H}=\mathcal{H}_1+\cdots+\mathcal{H}_q\) where the hypergraphs \(\mathcal{H}_1,\dots, \mathcal{H}_q\) have one edge each. We will prove our statement by induction on \(q\).
If \(q=1\) then by 1(b) and 8 (2), \(\mathtt{F}(\mathcal{H},k)\) is nonzero if and only if \(k\leq 1\). The result then follows from 1 (a). Now assume \(q\geq 2\). By induction, we can assume that \[\mathtt{F}(\mathcal{H}_1+\cdots+\mathcal{H}_{q'},k)=I(\mathcal{H}_1+\cdots+\mathcal{H}_{q'})^{[k]}\] whenever \(q'<q\). By 8 (2) and 1 (a), we have \(\nu_\mathtt{F}(\mathcal{H}_i)=1\) for any \(i\in [q]\). Using 1 (d), we obtain \[\begin{align} \mathtt{F}(\mathcal{H},k) &= \sum_{i=0}^k \mathtt{F}(\mathcal{H}_1+\cdots + \mathcal{H}_{q-1},i)\mathtt{F}(\mathcal{H}_q,k-i) \\ &= I(\mathcal{H}_1+\cdots + \mathcal{H}_{q-1})^{[k]} + I(\mathcal{H}_1+\cdots + \mathcal{H}_{q-1})^{[k-1]}I(\mathcal{H}_q)\\ &= I(\mathcal{H}_1+\cdots + \mathcal{H}_{q})^{[k]}, \end{align}\] as desired. ◻
Next, we introduce an invariant that will help us bound the regularity of \(\mathtt{F}(\mathcal{H},k)\).
Definition 2. Let \(\mathcal{H}\) be a hypergraph. Then for any \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\), a vertex set \(C\subseteq V(\mathcal{H})\) is called a \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\) if there is a partition \(C=\sqcup_{i=1}^rC_i\) such that the following holds:
for any \(i\in [r]\), we have \(E(\mathcal{H}[C_i])\neq \emptyset\);
for any edge \(\mathcal{E}\) of \(\mathcal{H}[C]\), we have \(\mathcal{E}\in E(\mathcal{H}[C_i])\) for some \(i\in [r]\);
\(k\leq \sum_{i=1}^r \nu_\mathtt{F}(\mathcal{H}[C_i]) \leq r+k-1\);
\(\mathtt{F}(\mathcal{H}[C_i], \nu_\mathtt{F}(\mathcal{H}[C_i]))\) equals the principal ideal \(\left(\mathbf{x}_{C_i} \right)\) for any \(i\in [r]\).
For each such \(C\), we compute the value of \(|C|-\sum_{i=1}^r \nu_\mathtt{F}(\mathcal{H}[C_i])\). We call the largest value among those the \(k\)-admissible \(\mathtt{F}\)-number of \(\mathcal{H}\), and denote it by \(\mathrm{adm}^{\mathtt{F}}(\mathcal{H},k)\).
Proposition 3. Let \(\mathcal{H}\) be a hypergraph. Then for any \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\), there exists a \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\). Consequently, \(\mathrm{adm}^{\mathtt{F}}(\mathcal{H},k)\) is well-defined for any hypergraph \(\mathcal{H}\) and any integer \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\).
Proof. As \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\), the ideal \(\mathtt{F}(\mathcal{H},k)\) is a nonzero proper squarefree monomial ideal. Consider a minimal squarefree generator \(m\) of \(\mathtt{F}(\mathcal{H},k)\), and set \(C\coloneq \mathrm{supp}(m)\). Using 1(a),(b), we see that conditions (1)-(2) of Definition 2 are satisfied for the partition \(C=C_1\). Moreover, by 1(c), \[\mathtt{F}(\mathcal{H}[C],k) = \mathtt{F}(\mathcal{H},k)^{\leq m} = (m) = \left(\prod_{x\in \mathrm{supp}(m)}x\right).\] In particular, this implies that Condition (4) of Definition 2 holds, and that \(\nu_\mathtt{F}(\mathcal{H}[C])=k\), which implies Condition (3) of Definition 2. To sum up, \(C=C_1\) is indeed a \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\). ◻
Assume that \(\mathcal{H}\) is a hypergraph, \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\) an integer, and \(C\subseteq V(\mathcal{H})\) a \(k\)-admissable \(\mathtt{F}\)-set of \(\mathcal{H}\). By 1 (c), we have \(\mathtt{F}(\mathcal{H},k)^{\leq \mathbf{x}_C} = \mathtt{F}(\mathcal{H}[C],k)\). By the Restriction Lemma ([29]), \(\mathrm{reg}\, \mathtt{F}(\mathcal{H}[C],k)\) is a lower bound of \(\mathrm{reg}\, \mathtt{F}(\mathcal{H},k)\). Computationally, even with the many conditions on \(C\), the number \(\mathrm{reg}\, \mathtt{F}(\mathcal{H}[C],k)\) is still not easy to determine. The number \(|C|-\sum_{i=1}^r \nu_\mathtt{F}(\mathcal{H}[C_i])\), on the other hand, is easier to compute, and it turns out that this number is a lower bound for \(\mathrm{reg}\, \mathtt{F}(\mathcal{H}[C],k)\). This is the main result of this section. Before proving it, we need a weaker version of 2.
Theorem 3. Given two hypergraphs \(\mathcal{H}_1\) and \(\mathcal{H}_2\) with disjoint vertex sets, and a positive integer \(\nu_\mathtt{F}(\mathcal{H}_1)\leq k\leq \nu_\mathtt{F}(\mathcal{H}_1+\mathcal{H}_2)\), we have \[\begin{align} \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1+\mathcal{H}_2,k) \geq \begin{multlined}[t] \max \{ \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,\nu_\mathtt{F}(\mathcal{H}_1)) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,k-\nu_\mathtt{F}(\mathcal{H}_1)), \\ \; \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,\nu_\mathtt{F}(\mathcal{H}_1)) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,k+1-\nu_\mathtt{F}(\mathcal{H}_1)) -1 \}. \end{multlined} \end{align}\]
Proof. Due to 1(b) and 6, the filtration \(\{\mathtt{F}(\mathcal{H}_1,i)\}_{i\geq 0}\) and \(\{\mathtt{F}(\mathcal{H}_2,j)\}_{j\geq 0}\) are Tor-vanishing. Thus we can apply 2: \[\begin{align} \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1+\mathcal{H}_2,k) = \begin{multlined}[t] \max_{\substack{i\in [a,b]\\j\in [a+1,b]}} \{ \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,k-i) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,i) , \\ \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,k-j+1) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,j) -1 \} \end{multlined} \end{align}\] for any \(k\geq 0\), where \[a=\max\{0,k-\nu_\mathtt{F}(\mathcal{H}_1)\} \quad \text{and} \quad b= \min\{k,\nu_\mathtt{F}(\mathcal{H}_2)\}.\] Note that \(\nu_\mathtt{F}(\mathcal{H}_1+\mathcal{H}_2)= \nu_\mathtt{F}(\mathcal{H}_1)+\nu_\mathtt{F}(\mathcal{H}_2)\). We thus can pick \(i=k-\nu_\mathtt{F}(\mathcal{H}_1)\in [a,b]\) and obtain \[\label{eq:reg-1} \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1+\mathcal{H}_2,k) \geq \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,\nu_\mathtt{F}(\mathcal{H}_1)) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,k-\nu_\mathtt{F}(\mathcal{H}_1)).\tag{1}\] It now suffices to show that \[\label{eq:reg-2} \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1+\mathcal{H}_2,k) \geq \mathrm{reg}\, \mathtt{F}(\mathcal{H}_1,\nu_\mathtt{F}(\mathcal{H}_1)) + \mathrm{reg}\, \mathtt{F}(\mathcal{H}_2,k+1-\nu_\mathtt{F}(\mathcal{H}_1)) -1.\tag{2}\] Indeed, if \(k=\nu_\mathtt{F}(\mathcal{H}_1+\mathcal{H}_2)= \nu_\mathtt{F}(\mathcal{H}_1)+ \nu_\mathtt{F}(\mathcal{H}_2)\), then \(\mathtt{F}(\mathcal{H}_2,k+1-\nu_\mathtt{F}(\mathcal{H}_1))=0\), and (2 ) follows from (1 ). Now we can assume that \(k\leq \nu_\mathtt{F}(\mathcal{H}_1)+ \nu_\mathtt{F}(\mathcal{H}_2)-1\). We can now pick \(j=k+1-\nu_\mathtt{F}(\mathcal{H}_1)\in [a+1,b]\), and obtain (2 ), as desired. ◻
We are now ready to prove the main result of this section.
Theorem 4. Let \(\mathcal{H}\) be a hypergraph and \(k\) an integer where \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\). Then for any \(k\)-admissible \(\mathtt{F}\)-set \(C=\sqcup_{i=1}^r C_i\) of \(\mathcal{H}\), we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H},k) \right) \geq |C|-\sum_{i=1}^r \nu_\mathtt{F}(\mathcal{H}[C_i])+k.\] Consequently, we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H},k) \right) \geq \mathrm{adm}^{\mathtt{F}}(\mathcal{H},k)+k.\]
Proof. We induct on \(k\) and \(|E(\mathcal{H})|\). If \(k=1\), then we have \(\nu_\mathtt{F}(\mathcal{H}[C_i])=1\) for any \(i\in [r]\) by 2 (1) and (3). By 2 (4), we have \(\mathrm{reg}(\mathtt{F}(\mathcal{H}[C_i]),1) = |C_i|\) for any \(i\in [r]\). By 2 (2), 2, and the Restriction Lemma ([29]), we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H},1) \right)\geq \mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C],1) \right) = \mathrm{reg}\left( \sum_{i=1}^r \mathtt{F}(\mathcal{H}[C_i],1) \right) = \sum_{i=1}^r|C_i| -r+1,\] as desired. If \(|E(\mathcal{H})|=1\), then we must have \(r=1\) due to 2 (1). By 2 (3), we have \(k\leq \nu_\mathtt{F}(\mathcal{H}[C_1]) \leq k\), and thus \(\nu_\mathtt{F}(\mathcal{H}[C_1])=k\). Using 2 (4), we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H},k \right)\geq \mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C_1], k ) \right) = |C_1| = \left(|C| -\nu_\mathtt{F}(\mathcal{H}[C]) \right)+k,\] as desired.
By induction, we can assume that \(k\geq 2\) and whenever \(k'<k\) or \(|E(\mathcal{H}')|< |E(\mathcal{H})|\), we have \[\mathrm{reg}\left( I(\mathcal{H}')^{\{k'\}} \right) \geq |C'|-\sum_{i=1}^{r'} \nu_\mathtt{F}(\mathcal{H}[C_i'])+k,\] where \(C'=\sqcup_{i=1}^{r'} C_i'\) is any \(k'\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}'\). Now assume that \(C=\sqcup_{i=1}^r C_i\) is a \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\) where the conditions in 2 hold. Set \(a=|C|-\sum_{i=1}^r \nu_\mathtt{F}(\mathcal{H}[C_i])\), and \(a_i=\nu_\mathtt{F}(\mathcal{H}[C_i])\) for each \(i\in [r]\). By the Restriction Lemma ([29]), it suffices to show that \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C],k) \right) \geq a+k.\]
Suppose that \(r=1\). Then \(k\leq \nu_\mathtt{F}(\mathcal{H}[C])=a_1\leq k\), and thus \(\nu_\mathtt{F}(\mathcal{H}[C])=a_1=k\). By 2 (4), the ideal \(\mathtt{F}(\mathcal{H}[C],k)\) is generated by a monomial of degree \(|C|\), and thus we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C],k) \right) = |C|= \left(|C| - \nu_\mathtt{F}(\mathcal{H}[C])\right)+ \nu_\mathtt{F}(\mathcal{H}[C]) = a+k,\] as desired. Now we can assume that \(r\geq 2\). Due to condition (2) of 2, the graph \(\mathcal{H}[C]\) is exactly the disjoint union of the hypergraphs \(\mathcal{H}[C_i]\) where \(i\) ranges in \([r]\). Set \(\mathcal{H}_1\mathrel{\vcenter{:}}= \mathcal{H}[C_1]\), and \(\mathcal{H}_2=\sqcup_{i=2}^r \mathcal{H}[C_i]\). Then \(\mathcal{H}_1\) and \(\mathcal{H}_2\) share no vertex. Moreover, we have \[k-\nu_\mathtt{F}(\mathcal{H}_1)=k-\nu_\mathtt{F}(\mathcal{H}[C_1])=k-a_1\geq \sum_{i=2}^r a_i - (r-1)\geq 0\] and \[k\leq a_1+ \sum_{i=2}^ra_i=\nu_\mathtt{F}(\mathcal{H}_1)+\nu_\mathtt{F}(\mathcal{H}_2),\] by conditions (2) and (3) of 2. Thus, by 3, we have \[\label{equ:regularity-betti-F} \mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C],k) \right) \geq \max \{ |C_1| + \mathrm{reg}\big( \mathtt{F}(\mathcal{H}_2,k-a_1) \big), \quad |C_1| + \mathrm{reg}\big( \mathtt{F}(\mathcal{H}_2,k-a_1+1) \big) -1 \},\tag{3}\] where we used the fact that \(\mathrm{reg}\left( \mathtt{F}(\mathcal{H}_1,a_1) \right)\) is the principal ideal generated by a monomial of degree \(|C_1|\), from condition (4) of 2. Recall that we have \(\nu_\mathtt{F}(\mathcal{H}[C])=\sum_{i=1}^r a_i \leq r+k-1\). If \(\sum_{i=1}^r a_i<r+k-1\), then \[\nu_\mathtt{F}(\mathcal{H}_2)=\sum_{i=2}^r \nu_\mathtt{F}(\mathcal{H}[C_i]) = \sum_{i=2}^r a_i = \sum_{i=1}^r a_i-a_1 < (r+k-1)-a_1 = (r-1)+ (k-a_1),\] and hence \[k-a_1\le\nu_\mathtt{F}(\mathcal{H}_2) = \sum_{i=2}^r \nu_\mathtt{F}(\mathcal{H}[C_i]) \leq (r-1) + (k-a_1) - 1.\] Thus, \(\sqcup_{i=2}^r C_i\) is a \((k-a_1)\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}_2\). By induction, we have \[\begin{align} \mathrm{reg}\left( \mathtt{F}(\mathcal{H}_2,k-a_1) \right) \geq (|\sqcup_{i=2}^r C_i| - \sum_{i=2}^r a_i ) + (k-a_1) &= (a-|C_1| + a_1) + (k-a_1) \\ &= a -|C_1|+ k. \end{align}\] Thus, by (3 ), we have \[\mathrm{reg}\left( \mathtt{F}(\mathcal{H}[C],k) \right) \geq |C_1| + \mathrm{reg}\left( \mathtt{F}(\mathcal{H}_2,k-a_1) \right) \geq |C_1| + \left(a -|C_1|+ k\right)= a+k,\] as desired. Now we can assume that \(\sum_{i=1}^r a_i=r+k-1\). By 2 (2) and 8 (1), we have \[\nu_\mathtt{F}(H_2) =\sum_{i=2}^r \nu_\mathtt{F}(H[C_i]) = \sum_{i=1}^r a_i -a_1 = (r+k-1)-a_1 = (r-1)+ (k-a_1+1)-1.\] Since \(r\geq 2\), we have \[k-a_1+1\leq (r-2) + (k-a_1+1) = \nu_\mathtt{F}(H_2) = (r-1)+ (k-a_1+1)-1.\] Thus, \(\sqcup_{i=2}^r C_i\) is a \((k-a_1+1)\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}_2\). By induction, we have \[\begin{align} \mathrm{reg}\left( \mathtt{F}(\mathcal{H}_2,k-a_1+1) \right) &\geq \left(|\sqcup_{i=2}^r C_i| -\sum_{i=2}^{r} \nu_\mathtt{F}(\mathcal{H}[C_i]) \right) + (k-a_1+1)\\ &= (a-|C_1| + a_1) + (k-a_1+1) \\ &= a-|C_1|+k+1. \end{align}\] Thus, by (3 ), we have \[\begin{align} \mathrm{reg}\left(\mathtt{F}(\mathcal{H}[C],k) \right) &\geq |C_1| + \mathrm{reg}\left( \mathtt{F}(\mathcal{H}_2,k-a_1+1) \right) -1\\ &\geq |C_1| + \left(a-|C_1|+k+1 \right)-1 \\ &= a+k, \end{align}\] as desired. This concludes the proof. ◻
Remark 4. The (ordinary) squarefree powers \(\mathtt F:(\mathcal{H},k)\mapsto I(\mathcal{H})^{[k]}\) is an example of a squarefree-power-like function. Indeed, it is easy to see that \(I(\mathcal{H})^{[k]}\) satisfies all the conditions in 1 (see also [19]). Moreover, in this situation any \(k\)-admissible \(\mathtt F\)-set \(C=\sqcup_{i=1}^rC_i\) of \(\mathcal{H}\) can be realized as a generalized \(k\)-admissible matching \(M=\sqcup_{i=1}^rM_i\) of \(\mathcal{H}\), in the sense of [19]. Thus, by 4, \[\mathrm{reg}(I(\mathcal{H})^{[k]})\ge\max\{|V(M)|-|M|\mid M\text{ is a generalized }k\text{-admissible matching of }\mathcal{H}\}+k.\] This fact was also established in [19].
Remark 5. Given a squarefree-power-like function \(\mathtt{F}\). Let \(\mathcal{H}\) be the union of pairwise disjoint edges. Then by 2, we may as well assume that \(\mathtt{F}\) is the action of taking squarefree powers. Then as shown in [19], we have \(\mathrm{reg}(\mathtt{F}(\mathcal{H},k))=\mathrm{adm}^{\mathtt{F}}(\mathcal{H},k)+k\) for any \(1\leq k\leq \nu_\mathtt{F}(\mathcal{H})\). In other words, our lower bound in 4 is sharp.
Remark 6. An analogue of 3 can be obtained for \({\rm depth}\, \mathtt{F}(\mathcal{H}_1+\mathcal{H}_2,k)\) by applying [26]. On the other hand, deriving a combinatorial estimate for \({\rm depth}\, \mathtt{F}(\mathcal{H},k)\), in the spirit of 4 appears to be a considerably more challenging problem. In particular, it remains an interesting direction to establish a combinatorial lower bound for \({\rm depth}\, \mathtt{F}(\mathcal{H},k)\) for all \(1 \leq k \leq \nu_\mathtt{F}(\mathcal{H})\), where \(\mathtt{F}\) denotes a squarefree-power-like function.
Immediate applications of squarefree-power-like functions include squarefree powers \((\mathcal{H},k)\mapsto I(\mathcal{H})^{[k]}\) and squarefree symbolic powers \((\mathcal{H},k)\mapsto I(\mathcal{H})^{\{k\}}\). In fact, in the case of squarefree powers, our definition coincides with that of Erey and Hibi [20], and \(\mathrm{adm}^{\mathtt{F}}\) in this case can be phrased using matchings from graph theory. In a different article [19], we have explored how sharp this bound is for various squarefree powers of edge ideals. For the rest of the article, we explore this for squarefree symbolic powers and see how our invariants can be related to concepts in combinatorics. First, we provide a proof for why \((\mathcal{H},k)\mapsto I(\mathcal{H})^{\{k\}}\) is a squarefree-power-like function. We start with a small lemma, which is a generalization of [30]. However, as the proof works line-by-line, we refer to that of [30].
Lemma 9. Let \(\mathcal{H}\) be a hypergraph and \(\mathcal{H}_1\) an induced sub-hypergraph of \(\mathcal{H}\). Then \[\left(I(\mathcal{H})^{(k)}\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x} = I(\mathcal{H}_1)^{(k)}. \qedhere\]
Proposition 7. Let \(\mathtt{F}(\mathcal{H},k)=I(\mathcal{H})^{\{k\}}\) for any hypergraph \(\mathcal{H}\) and integer \(k\). Then \(\mathtt{F}\) is a squarefree-power-like function.
Proof. The condition (a) of 1 follows directly from the definition of squarefree symbolic powers. The condition (b) is due to [26] and 7. The condition (d) is obtained by taking the squarefree part of the equation in [26]. As for condition (c), consider a hypergraph \(\mathcal{H}\), an induced sub-hypergraph \(\mathcal{H}_1\) of \(\mathcal{H}\), and any integer \(k\). By 9, we have \[\left(I(\mathcal{H})^{(k)}\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x} = I(\mathcal{H}_1)^{(k)}.\] Taking the squarefree part of both sides of the above equality, we obtain \[\mathrm{sqf}\left(\left(I(\mathcal{H})^{(k)}\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x}\right) = I(\mathcal{H}_1)^{\{k\}}.\] Note that taking the squarefree part is the same as restriction with respect to the product of all variables, and restriction commutes with each other. Thus, \[I(\mathcal{H}_1)^{\{k\}}=\mathrm{sqf}\left(I(\mathcal{H})^{(k)}\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x}=\left(\mathrm{sqf}(I(\mathcal{H})^{(k)})\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x}=\left(I(\mathcal{H})^{\{k\}}\right)^{\leq \prod_{x\in V(\mathcal{H}_1)} x},\] as desired. ◻
Our next goal is to specialize our concepts for squarefree-power-like functions to the case of taking squarefree symbolic powers of the edge ideal of hypergraphs. We will relate them to the combinatorial objects that are known to be linked with symbolic powers namely, independent sets and vertex covers.
Let \(\mathcal{H}\) be a hypergraph. Recall that the independent number of \(\mathcal{H}\), denoted by \(\alpha(\mathcal{H})\), is the maximum cardinality of an independent set of \(\mathcal{H}\). On the other hand, the vertex covering number of \(\mathcal{H}\), denoted by \(\beta(\mathcal{H})\), is the minimum cardinality of a vertex cover of \(\mathcal{H}\). These two graph-theoretic invariants are instrumental in the study of symbolic powers of edge ideals (see, for instance, [31]). For the squarefree symbolic power, the invariant \(\beta(\mathcal{H})\) plays a pivotal role as seen in [18] since \(I(\mathcal{H})^{\{k\}}\neq ( 0)\) if and only if \(1\le k\le \beta(\mathcal{H})\).
In the following definition, we make use of \(\alpha(\mathcal{H})\) to define a certain combinatorial invariant which we call as the \(k\)-admissible independence number and it turns out that for squarefree symbolic powers of block graphs and certain squarefree symbolic powers of Cohen-Macaulay bipartite graphs the \(k\)-admissible independence number is same as the regularity of these ideals (see 5 and Section 6).
Definition 3. Let \(\mathcal{H}\) be a hypergraph. Then for any \(1\leq k\leq \beta(\mathcal{H})\), a vertex set \(C\subseteq V(\mathcal{H})\) is called a \(k\)-admissible set of \(\mathcal{H}\) if there is a partition \(C=\sqcup_{i=1}^rC_i\) such that such that the following holds:
for any \(i\in [r]\), we have \(E(\mathcal{H}[C_i])\neq \emptyset\);
for any edge \(e\in E(\mathcal{H}[C])\), we have \(e\in E(\mathcal{H}[C_i])\) for some \(i\in [r]\);
\(k\leq \sum_{i=1}^r \beta(\mathcal{H}[C_i]) \leq r+k-1\);
for each \(i\in[r]\), \(I(\mathcal{H}[C_i])^{\{\beta(\mathcal{H}[C_i])\}}=\left( \mathbf{x}_{C_i} \right )\).
For every such \(C\), we compute the value of \(\alpha(\mathcal{H}[C])\). We call the largest value among those, denoted by \(\mathrm{ind}(\mathcal{H},k)\), the \(k\)-admissible independence number of \(\mathcal{H}\), i.e., \[\mathrm{ind}(\mathcal{H},k)=\max\{\alpha(\mathcal{H}[C]): C\text{ is a k-admissible set of }\mathcal{H}\}\]
Remark 8. For any \(k\)-admissible set of \(\mathcal{H}\), we have \[\alpha(\mathcal{H}[C])=\sum_{i=1}^r\alpha(\mathcal{H}[C_i])=\sum_{i=1}^r (|C_i|- \beta(\mathcal{H}[C_i]))= |C|-\sum_{i=1}^r \beta(\mathcal{H}[C_i]).\]
Remark 9. For any hypergraph \(\mathcal{H}\), the \(1\)-admissible independence number of \(\mathcal{H}\) is the induced matching number of \(\mathcal{H}\). In other words, \(\mathrm{ind}(\mathcal{H},1)=\nu(\mathcal{H})\). To see this, consider \(C\subseteq V(\mathcal{H})\) with a partition \(C=\sqcup_{i=1}^r C_i\) such that \(\alpha(\mathcal{H}[C])=\mathrm{ind}(\mathcal{H},1)\). Since \(k=1\), from conditions (2) and (3) of 3, we have \(\beta(\mathcal{H}[C_i])=1\) for all \(1\leq i\leq r\). Then, it follows from condition (4) of 3 that \(|E(\mathcal{H}[C_i])|=1\). Thus, \(\mathcal{H}[C]\) is an induced subgraph of \(\mathcal{H}\) consisting of disjoint edges of \(\mathcal{H}\), and hence is an induced matching of \(\mathcal{H}\). On the other hand, the vertex set of any induced matching of \(\mathcal{H}\) can be regarded as a \(1\)-admissible set of \(\mathcal{H}\).
Lemma 10. Let \(\mathcal{H}\) be a hypergraph and let \(\mathcal{H}'\) be an induced sub-hypergraph of \(\mathcal{H}\). Then for any \(k\geq 1\), \(\mathrm{ind}(\mathcal{H}',k)\leq \mathrm{ind}(\mathcal{H},k)\).
Proof. Let \(C=\sqcup_{i=1}^rC_i\subseteq V(\mathcal{H}')\) be such that \(\mathrm{ind}(\mathcal{H}',k)=\alpha(\mathcal{H}'[C])\). Since \(\mathcal{H}'\) is an induced subgraph of \(\mathcal{H}\), it follows that \(\mathcal{H}[C]=\mathcal{H}'[C]\), and therefore \(\mathcal{H}[C_i]=\mathcal{H}'[C_i]\) for all \(i\in [r]\). Hence, \(C\subseteq V(\mathcal{H})\) is a \(k\)-admissible set of \(\mathcal{H}\) and the assertion follows. ◻
We then obtain an application of Theorem 4.
Corollary 2. Let \(\mathcal{H}\) be a hypergraph and \(1\leq k\leq \mathrm{ht}I(\mathcal{H})\). Let \(C=\sqcup_{i=1}^r C_i\) be an \(k\)-admissible \(\mathtt{F}\)-set of \(\mathcal{H}\). Then \[\mathrm{reg}(I(\mathcal{H})^{\{k\}} )\geq |C| - \beta(\mathcal{H}[C]) + k = \alpha(H[C]) +k.\] Consequently, we have \[\mathrm{reg}(I(\mathcal{H})^{\{k\}}) \geq \mathrm{ind}(\mathcal{H},k)+k.\]
The following lemma provides an effective way to check the condition (4) of 3 for a squarefree monomial ideal.
Lemma 11. Let \(\mathcal{H}\) be a hypergraph, and let \(k\geq 1\) be an integer such that \(I(\mathcal{H})^{\{k\}}\neq ( 0)\). Then \(I(\mathcal{H})^{\{k\}} =\left ( \mathbf{x}_{V(\mathcal{H})} \right )\) if and only if for each \(x\in V(\mathcal{H})\), there is a minimal vertex cover \(\mathcal{C}\) of \(\mathcal{H}\) such that \(x\in \mathcal{C}\) and \(|\mathcal{C}|=k\). Moreover, if \(I(\mathcal{H})^{\{k\}}=\left ( \mathbf{x}_{V(\mathcal{H})} \right )\), then \(k=\beta(\mathcal{H})\).
Proof. To prove the ‘if’ part, assume that \(I(\mathcal{H})^{\{k\}} \neq\left (\mathbf{x}_{V(\mathcal{H})} \right )\). Then there is some \(x\in V(\mathcal{H})\) and \(f\in I(\mathcal{H})^{\{k\}}\) such that \(x\nmid f\). Since there is a minimal vertex cover \(\mathcal{C}\) of \(\mathcal{H}\) such that \(x\in \mathcal{C}\) and \(|\mathcal{C}|=k\), it follows that \(f\notin \mathfrak p_{\mathcal{C}}^{\{k\}}\), as \(|\mathrm{supp}(f)\cap C|\leq k-1\). Hence, \(f\notin I(\mathcal{H})^{\{k\}}\), a contradiction. Conversely, assume that \(f=\mathbf{x}_{V(\mathcal{H})}\) is a minimal monomial generator of \(I(\mathcal{H})^{\{k\}}\). Then \(f\in \mathfrak p_{\mathcal{C}}^{\{k\}}\) for every minimal vertex cover \(\mathcal{C}\) of \(\mathcal{H}\). By way of contradiction, let there be a vertex \(x\in V(\mathcal{H})\) such that every minimal vertex cover \(\mathcal{C}\) of \(\mathcal{H}\) with \(x\in \mathcal{C}\) has \(|\mathcal{C}|\geq k+1\). Now, consider \(g=\frac{f}{x}\). Then observe that, for any minimal vertex cover \(\mathcal{C}\) of \(\mathcal{H}\) such that \(x\notin \mathcal{C}\), \(|\mathrm{supp}(g)\cap \mathcal{C}|\geq k\). Moreover, if \(\mathcal{C}'\) is a minimal vertex cover with \(x\in \mathcal{C}'\), we also have \(|\mathrm{supp}(g)\cap \mathcal{C}'|=|\mathrm{supp}(g)\cap (\mathcal{C}'\setminus \{x\})|\geq k\). This shows that \(g\in I(\mathcal{H})^{\{k\}}\), which is again a contradiction.
The last statement follows from the ‘only if’ part of the above arguments and the fact that \(I(\mathcal{H})^{\{l\}}\neq(0)\) if and only if \(l\le\beta(\mathcal{H})\). ◻
In this section, we show that the regularity of the \(k^{\text{th}}\) squarefree symbolic powers of edge ideals of block graphs can be expressed in terms of the \(k\)-admissible independence number of the graph. The proof of this result relies heavily on the analysis of the \(k\)-admissible independence number of block graphs. To begin with, we present several applications of 11 that are necessary for the proof of our main theorem in this section.
Lemma 12. Let \(G\) be a graph and \(S\subseteq V(G)\). Let \(K_n\) be the complete graph on the vertex set \(\{x_1, x_2, \dots , x_n\}\), where \(n\ge 2\). Consider the graph \(\Gamma\) constructed from \(G\) and \(K_n\) as follows: \[\begin{align} V(\Gamma)&=V(G)\sqcup V(K_n),\\ E(\Gamma)&=E(G)\sqcup E(K_n)\sqcup \{\{u,x_n\}\mid u\in S\}. \end{align}\] Then
\(\beta(\Gamma)=\beta(G)+n-1\).
If \(I(\Gamma)^{\{\beta(\Gamma)\}}=\left(\mathbf{x}_{V(\Gamma)}\right)\), then \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\). For \(n\ge 3\), the converse of this statement is also true in the case \(n\geq 3\).
Proof. \((1)\) For \(i\in[n-1]\), we set \(A_i=\{x_1,\ldots,\widehat{x_i},\ldots,x_n\}\). We claim that, if \(\mathcal{C}\) is a minimal vertex cover of \(G\), then for any \(i\in [n-1]\), \(\mathcal{C}\cup A_i\) is a minimal vertex cover of \(\Gamma\). Indeed, it is easy to see that \(\mathcal{C}\cup A_i\) is a vertex cover of \(\Gamma\). Now, let \(\mathcal{C}'\subseteq \mathcal{C}\cup A_i\) be a minimal vertex cover of \(\Gamma\). Observe that \(A_i\subseteq \mathcal{C}'\) since \(\{x_j,x_i\}\in E(\Gamma)\) for each \(x_j\in A_i\). Now, suppose \(y\in\mathcal{C}\). Then there exists some \(z\in N_G(y)\) such that \(z\notin\mathcal{C}\) since \(\mathcal{C}\) is a minimal vertex cover of \(G\). Consequently, \(z\notin\mathcal{C}'\) and since \(\{y,z\}\in E(\Gamma)\), we must have \(y\in\mathcal{C}'\). Thus \(\mathcal{C}'=\mathcal{C}\cup A_i\) is a minimal vertex cover of \(\Gamma\), and hence \(\beta(\Gamma)\le \beta(G)+n-1\). Next, suppose that \(\mathcal{C}''\) is a minimal vertex cover of \(\Gamma\) such that \(|\mathcal{C}''|=\beta(\Gamma)\). Then by the structure of \(\Gamma\) we find that \(|\mathcal{C}''\cap\{x_1,\ldots,x_n\}|=n-1\). On the other hand, \(\mathcal{C}''\cap V(G)\) is a vertex cover of \(G\). Thus, \(|\mathcal{C}''\cap V(G)|\ge \beta(G)\). Consequently, \(|\mathcal{C}''|=|\mathcal{C}''\cap V(G)|+|\mathcal{C}''\cap \{x_1,\ldots,x_n\}|\ge \beta(G)+(n-1)\). This completes the proof.
\((2)\) Assume that \(I(\Gamma)^{\{\beta(G)+n-1\}}=\left(\mathbf{x}_{V(\Gamma)}\right)\). Choose some \(y\in V(G)\). Then by 11, there exists a minimal vertex cover \(\mathcal{C}'\) of \(\Gamma\) such that \(|\mathcal{C}'|=\beta(G)+n-1\). Proceeding as in the previous paragraph, we see that \(\mathcal{C}''\) is a vertex cover of \(G\) such that \(y\in\mathcal{C}''\) with \(|\mathcal{C}''|=\beta(G)\), where \(\mathcal{C}''=\mathcal{C}\cap V(G)\). Thus, \(\mathcal{C}''\) is a minimal vertex cover of \(G\). Therefore, by 11, we have \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\), as desired.
For the converse part, let us assume that \(n\geq 3\) and \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\). Choose some \(y\in V(G)\). Then by 11, there is a minimal vertex cover \(\mathcal{C}\) of \(G\) such that \(y\in \mathcal{C}\) and \(|\mathcal{C}|=|\beta(G)|\). From part \((1)\), we have that both \(\mathcal{C}\cup A_1=\mathcal{C}\cup \{x_2,\ldots,x_n\}\) and \(\mathcal{C}\cup A_2=\mathcal{C}\cup\{x_1,x_3,\ldots,x_n\}\) are minimal vertex covers of \(\Gamma\) such that \(|\mathcal{C}\cup A_1|=|\mathcal{C}\cup A_2|=\beta(G)+n-1\). Note that \(y,x_2,\ldots,x_n\in \mathcal{C}\cup A_1\) and \(x_1\in \mathcal{C}\cup A_2\). Thus, by 11, \(I(\Gamma)^{\{\beta(G)+n-1\}}=\left(\mathbf{x}_{V(\Gamma)}\right)\). ◻
Remark 10. The converse part of the assertion \((2)\) of 12 is not necessarily true if we assume \(n=2\). For instance, take \(G=K_3\) with \(S=V(G)=\{y_1,y_2,y_3\}\) and \(V(K_2)=\{x_1,x_2\}\). It is easy to see that \(\beta(G)=2\) and \(I(G)^{\{2\}}=\left(y_1y_2y_3\right)\). On the other hand, since \(\Gamma\) is nothing but \(K_4\) with a whisker attached to one of the vertices, we see that \(\beta(\Gamma)=3\) and consequently, \(y_1y_2y_3x_2\in I(\Gamma)^{\{3\}}\). Thus, \(I(\Gamma)^{\{3\}}\neq \left(\mathbf{x}_{V(\Gamma)}\right)\).
Lemma 13. Let \(G\) be a graph and fix a vertex \(v\in V(G)\). Let \(W(K_n)\) denote the whiskered graph on the complete graph \(K_n, n\geq 1\). Let \(\Gamma\) be a graph obtained from \(G\) and \(W(K_n)\), where \[\begin{align} V(\Gamma)&=V(G)\sqcup V(W(K_n)),\\ E(\Gamma)&=E(G)\sqcup E(W(K_n))\sqcup \{\{v,x\}\mid x\in V(K_n)\}. \end{align}\] Then
\(\beta(\Gamma)=\beta(G)+n\).
\(I(\Gamma)^{\{\beta(\Gamma)\}}=\left(\mathbf{x}_{V(\Gamma)}\right)\) if and only if \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\).
Proof. Let \(V(K_n)=\{x_1,x_2, \dots , x_n\}\) and \(V(W(K_n))=V(K_n)\cup \{y_1,y_2, \dots , y_n\}\) with \(E(W(K_n))=E(K_n)\cup \{\{x_i,y_i\}\mid i\in [n]\}\).
\((1)\) Let \(\mathcal{C}\) be a minimal vertex cover of \(G\). Then, proceeding as in 12, it is easy to see that \(\mathcal{C}\cup V(K_n)\) is a minimal vertex cover of \(\Gamma\). Thus, \(\beta(\Gamma)\leq \beta(G)+n\). Next, suppose \(C\) is a minimal vertex cover of \(\Gamma\) such that \(|\mathcal{C}|<\beta(G)+n\). Observe that \(n\ge |\mathcal{C}\cap V(K_n)|\geq n-1\). If \(\mathcal{C}\cap V(K_n)= V(K_n)\), then \(\mathcal{C}\setminus V(K_n)\) is a vertex cover of \(G\), where \(|\mathcal{C}\setminus V(K_n)|< \beta(G)\), a contradiction. If \(|\mathcal{C}\cap V(K_n)|= n-1\), then without loss of generality, we can assume that \(x_1\notin \mathcal{C}\). In this case, \(y_1\in \mathcal{C}\) and hence, \(\mathcal{C}'= \mathcal{C}\setminus (V(K_n)\cup \{y_1\})\) is a vertex cover of \(G\) such that \(|\mathcal{C}'|<\beta(G)\), again a contradiction. Thus we must have \(\beta(\Gamma)=\beta(G)+n\), as desired.
\((2)\) First, let us assume that \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)} \right )\). Then by 11, for any \(u\in V(G)\), there is a vertex cover \(\mathcal{C}\) of \(G\) such that \(u\in \mathcal{C}\) and \(|\mathcal{C}|=\beta(G)\). Consequently, \(\mathcal{C}'=\mathcal{C}\cup \{x_1, \dots , x_n\}\) is a minimal vertex cover of \(\Gamma\) with \(u\in \mathcal{C}'\) and \(|\mathcal{C}'|=\beta(G)+n=\beta(\Gamma)\). Note that \(x_i\in \mathcal{C}'\) for each \(i\in [n]\). Now take any \(y_i\in V(\Gamma)\). From our assumption and by 11, there is a minimal vertex cover \(\mathcal{C}_1\) of \(G\) such that \(v\in \mathcal{C}_1\) and \(|\mathcal{C}_1|=\beta(G)\). Then one can see that \(\mathcal{C}_1'=\mathcal{C}_1\cup \{x_1, \dots , x_{i-1}, y_i, x_{i+1}, \dots , x_n\}\) is a vertex cover of \(\Gamma\) such that \(|\mathcal{C}_1'|=|\mathcal{C}_1|+n=\beta(G)+n=\beta(\Gamma)\). Hence, \(\mathcal{C}_1'\) is a minimal vertex cover of \(\Gamma\) where \(y_i\in \mathcal{C}_1'\) and \(|\mathcal{C}_1'|=\beta(\Gamma)\). Thus, using 11 we have that \(I(\Gamma)^{\{\beta(\Gamma)\}}=\left(\mathbf{x}_{V(\Gamma)} \right )\). The converse part follows from the repeated use of 12. ◻
Lemma 14. Let \(G\) be a graph and \(\{x,y_1\},\{x,y_2\}\in E(G)\) with \(\deg_G(y_1)=\deg_G(y_2)=1\). Then \(I(G)^{\{\beta(G)\}}\neq \left(\mathbf{x}_{V(G)}\right)\).
Proof. On the contrary, let us assume that \(I(G)^{\{\beta(G)\}}= \left(\mathbf{x}_{V(G)}\right)\). Then by 11, there is a minimal vertex cover \(C\) of \(G\) such that \(y_1\in C\) and \(|C|=\beta(G)\). Note that \(x\notin C\), and hence \(y_2\in C\). Now, \(C'=(C\setminus \{y_1,y_2\})\cup \{x\}\) is a vertex cover of \(G\) of cardinality \(|C'|=\beta(G)-1\), which is a contradiction. ◻
The following lemma is again an application of 11, and the proof of this is similar.
Lemma 15. The following results hold for the graph classes constructed from the complete graph.
If \(G=K_n\) with \(n\geq 2\), then \(\beta(G)=n-1\) and \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\).
If \(G=W(K_n)\) with \(n\geq 2\), then \(I(G)^{\{\beta(G)\}}=\left(\mathbf{x}_{V(G)}\right)\).
Let \(n\ge 2\) and \(r<n\) be two positive integers. Let \(G\) be a graph on \(n+r\) vertices with \(V(G)=V(K_n)\sqcup \{y_1,\dots , y_r\}\), and \(E(G)=E(K_n)\sqcup \{\{u_1,y_1\},\dots , \{u_r, y_r\}\}\), where \(u_i\in V(K_n)\) are distinct vertices for \(i\in [r]\). Then \(I(G)^{\{\beta(G)\}}\neq \left(\mathbf{x}_{V(G)}\right)\).
We now recall the notion of a special block in a block graph \(G\). Let \(\mathcal{B}_G\) denote the set of all blocks in \(G\). Following [19], for \(B\in\mathcal{B}_G\) and \(u\in V(B)\), we define \(\mathcal{N}_G(B,u)\mathrel{\vcenter{:}}=\{D\in\mathcal{B}_G\mid V(D)\cap V(B)=\{u\}\}\). Using these notations, a special block is defined in the following way.
Definition 4. Let \(G\) be a block graph, and \(L\) a block of \(G\) with \(V(L)=\{u_1,\ldots,u_d\}\). We say that \(L\) is a special32block of \(G\) if \(L\) is one of the following types.
\(d\le 2\), and \(\mathcal{N}_G(L,u_i)=\emptyset\) for each \(i\in[d]\).
\(d\ge 3\), and \(\mathcal{N}_G(L,u_i)=\emptyset\) for each \(i\in[d-1]\).
\(d\ge 2\), and there exists some \(i\in[d-1]\) such that \(\mathcal{N}_G(L,u_i)\neq\emptyset\). Moreover, if \(\mathcal{N}_G(L,u_i)\neq\emptyset\) for some \(i\in[d-1]\), then for each \(D\in \mathcal{N}_G(L,u_i)\), \(D\cong K_2\).
Lemma 16. [19] Let \(G\) be a block graph. Then, \(G\) contains at least one special block.
The inequalities concerning the \(k\)-independence number described in the next two lemmas are heavily used in the proof of the main theorem (5) of this section.
Lemma 17. Let \(G\) be a block graph and let \(L\) be a special block of \(G\) with \(V(L)=\{u_1,\dots , u_d\}\). Assume that \(L\) is a special block of either Type I with \(d\ge 2\) or Type III with \(d\geq 3\), or Type II. Then for any \(1\leq s\leq d\) and \(k\geq s\), \[\mathrm{ind}(G\setminus L, k-s+1)\leq \mathrm{ind}(G,k)-1,\] where \(G\setminus L\) is the induced subgraph of \(G\) on the vertex set \(V(G)\setminus V(L)\).
Proof. Let \(C = \bigsqcup_{i=1}^r C_i\) be a \((k - s + 1)\)-admissible set of \(G \setminus L\) such that \[\mathrm{ind}(G \setminus L, k - s + 1) = \alpha(G[C]).\] Then by Condition (3) of 3, \(k - s + 1 \leq \sum_{i=1}^{r} \beta(G[C_i]) \leq r + k - s.\) We divide the proof in two cases.
Case I: Assume that \(L\) is a special block of Type I with \(d= 2\). In this case, \(s\in \{1,2\}\). We sketch the proof for the \(s=1\) case only, as the case \(s=2\) can be proved by similar arguments. Take \(C_{r+1}=\{u_1,u_{2}\}\) and set \(C'=\bigsqcup_{i=1}^{r+1} C_i\). Then from the structure of \(G\) we have \(E(G[C_{r+1}])\neq\emptyset\), and if \(e\in E(G[C'])\), then \(e\in E(G[C_i])\) for some \(i\in [r+1]\). Moreover, \(G[C_{r+1}]\) is a connected component of \(G\) with \(\beta(G[C_{r+1}])=1\) and hence, \[I(G[C_{r+1}])^{\{\beta(G[C_{r+1}])\}} =(\mathbf{x}_{C_{r+1}}).\] Observe that \[\beta(G[C']) = \sum_{i=1}^{r+1} \beta(G[C_i]) = \beta(G[C]) + 1,\] and thus, \[k+1 \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq r + k.\] From this, it follows that \[k \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq (r+1) + k - 1.\] Therefore, \(C'\) is a \(k\)-admissible set of \(G\). Note that \[\alpha(G[C']) = |C'| - \beta(G[C']) = |C| + 2 - \beta(G[C]) + 1 = \alpha(G[C]) + 1.\] This proves the inequality \(\mathrm{ind}(G\setminus L,k) \leq \mathrm{ind}(G,k) - 1\). Case II: Assume that \(L\) is a special block of Type III with \(d\geq 3\) or Type II. Then we have the following two subcases.
Case IIA: Let us assume first that \(s<d\). In this case we take \(C_{r+1} \subseteq \{u_1, \dots, u_{d-1}\}\) such that \(|C_{r+1}| = s\) and set \(C'=\bigsqcup_{i=1}^{r+1} C_i\). Again, by the structure of \(G\) we have \(E(G[C_{r+1}])\neq\emptyset\), and if \(e\in E(G[C'])\), then \(e\in E(G[C_i])\) for some \(i\in [r+1]\). Note that \(G[C_{r+1}]\) is a complete graph with \(\beta(G[C_{r+1}]) = s - 1,\) and by 15, \(I(G[C_{r+1}])^{\{s - 1\}} = (\mathbf{x}_{C_{r+1}})\). Further, observe that \[k \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq r + k - 1 < (r + 1) + k - 1.\] Thus, \(C' = \bigsqcup_{i=1}^{r+1} C_i\) is a \(k\)-admissible set of \(G\). Now, \[\begin{align} \alpha(G[C'])=|C'|-\beta(G[C'])=|C|-\beta(G[C])+1=\alpha(G[C])+1=\mathrm{ind}(G\setminus W,k-s+1)+1 \end{align}\] This shows that whenever \(s\neq d\), we have \(\mathrm{ind}(G\setminus W,k-s+1)\leq \mathrm{ind}(G,k)-1\).
Case IIB: Consider the remaining part, i.e., \(s = d\). Then we have \[k - d + 1 \leq \sum_{i=1}^{r} \beta(G[C_i]) \leq r + k - d.\] Now, if \(\sum_{i=1}^{r} \beta(G[C_i]) \geq k - d + 2\), then we can take \(C_{r+1} = \{u_1, \dots, u_{d-1}\}\) and set \(C'=\bigsqcup_{i=1}^{r+1} C_i\). As before, by the structure of \(G\) we have \(E(G[C_{r+1}])\neq\emptyset\), and if \(e\in E(G[C'])\), then \(e\in E(G[C_i])\) for some \(i\in [r+1]\). Moreover, since \(G[C_{r+1}]\) is a complete graph with \(\beta(G[C_{r+1}]) = d - 2\), using 15 we have \(I(G[C_{r+1}])^{\{d-2\}} = (\mathbf{x}_{C_{r+1}})\). Furthermore, we have the inequalities \[k \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq r + k - 2 < (r + 1) + k - 1.\] Thus, \(C' = \bigsqcup_{i=1}^{r+1} C_i\) is a \(k\)-admissible set of \(G\), and consequently, \(\alpha(G[C'])=\alpha(G[C]) + 1\). This, in turn, implies that \(\mathrm{ind}(G \setminus W, k - d + 1) \leq \mathrm{ind}(G, k) - 1\).
Finally, assume that \(\sum_{i=1}^{r} \beta(G[C_i]) = k - d + 1\). In this case, we take \(C'=\widetilde{C}\) as a single partition, where \(\widetilde{C}=C\cup\{u_1,\ldots,u_d\}\). Thus, Conditions (1) and (2) of 3 are automatically satisfied for \(C'\). Observe that \(I(G[C])^{\{\beta(G[C])\}}=(\mathbf{x}_{C})\) because of Conditions (2) and (4) in 3. Now, since \(d\ge 3\), using 12, we obtain \(\beta(G[C']) = \beta(G[C]) + d - 1\) and \(I(G[C'])^{\{\beta(G[C'])\}} =(\mathbf{x}_{C'})\). Thus, in order to show that \(C'\) is a \(k\)-admissible set, it remains to check Condition (4) in 3. However, since \(C'\) is a single partition and \(\beta(G[C']) = \beta(G[C]) + d - 1=k\), we have what we desired. Thus, \(C'\) is a \(k\)-admissible set and \[\alpha(G[C']) = |C'| - \beta(G[C']) = |C| + d - (\beta(G[C]) + d - 1)= \alpha(G[C]) + 1.\] Consequently, \(\mathrm{ind}(G\setminus W,k-d+1)\leq \mathrm{ind}(G,k)-1\), in this case too. This completes the proof of the lemma. ◻
Lemma 18. Let \(G\) be a block graph and \(L=\{u_1,\dots , u_d\}\) is a special block of Type III such that for each \(i\in [d-1]\), \(N_G[u_i]=V(L)\cup \{v_{i,1},\dots , v_{i,t_i}\}\), where \(t_i\) is a positive integer. Then for all \(i\in [d-1]\) and \(k\geq 2\), \[\mathrm{ind}(G\setminus u_i,k-1)=\mathrm{ind}(G\setminus \{u_i,v_{i,1},\dots , v_{i,t_i}\},k-1)\leq \mathrm{ind}(G,k)-1.\]
Proof. Without loss of generality, we may assume that \(i=1\). To simplify notations, we set \(G' = G \setminus \{u_1, v_{1,1}, \dots, v_{1,t_1} \}\). It is easy to see that \(\mathrm{ind}(G\setminus u_1,k-1)= \mathrm{ind}(G',k-1)\). Thus it remains to show that \(\mathrm{ind}(G',k-1)\le \mathrm{ind}(G,k)-1\). Let \(C = \bigsqcup_{i=1}^r C_i\) be a \((k-1)\)-admissible set of \(G'\) such that \(\mathrm{ind}(G', k-1) = \alpha(G[C])\). Then \[\begin{align} \label{ineq321} k - 1 \leq \sum_{i=1}^{r} \beta(G[C_i]) \leq r + (k - 1) - 1. \end{align}\tag{4}\] If \(N_G(u_1) \cap C = \emptyset\), then take \(C_{r+1} = \{u_1, v_{1,1}\}\) and set \(C' = \bigsqcup_{i=1}^{r+1} C_i\). Then it follows from the structure of \(G\) that \(E(G[C_{r+1}])\neq\emptyset\), and if \(e\in E(G[C'])\), then \(e\in E(G[C_i])\) for some \(i\in [r+1]\). Observe that \(\beta(G[C_{r+1}]) =1\). Therefore, \[k \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq r + k - 1 < (r+1) + k - 1.\] Thus, \(C' = \bigsqcup_{i=1}^{r+1} C_i\) is a \(k\)-admissible set of \(G\). Note that \(\alpha(G[C']) = \alpha(G[C]) + 1\), and therefore, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case.
Next, we assume \(N_G(u_1) \cap C \neq \emptyset\). Since \(G[\{u_1,\ldots,u_d\}]\) is a complete graph, using Condition (2) of 3, we can say that there exists some \(\ell \in [r]\) such that \[N_G(u_1) \cap C_\ell \neq \emptyset \quad \text{and} \quad N_G(u_1) \cap C_j = \emptyset \text{ for all } j \in [r], j \neq \ell.\] We first fix some notations for the rest of the proof. Let \(T=\{u_2,u_3,\dots , u_d\}\). For \(j\in [d-1]\), we set \(S_j:= N_G(u_j)\setminus V(L)= \{v_{j,1}, \dots , v_{j,{t_j}}\}\). Note that for each \(j\in [d-1]\), by our choice of \(L\), \(v_{j, q}, 1\leq q\leq t_j\) are leaf vertices for each \(q\in [t_j]\). Further, we set \(S=\cup_{j=1}^{d-1}S_j\), and \(\Lambda =S\cup T\). Then consider the following two cases:
Case A. First we assume that \(C_{\ell}\cap S=\emptyset\). Then \(\Lambda \cap C_\ell\subseteq T\). We have the following two subcases to consider.
Subcase A.1. \(u_d\notin C_{\ell}\). Then using the given hypothesis \(C_{\ell}\cap S=\emptyset\) and \(I(G[C_{\ell}])^{\beta(G[C_{\ell}])}=\left(\mathbf{x}_{C_{\ell}} \right )\), we can write \(N_G(u_1) \cap C_\ell=\{u_{i_1},\dots , u_{i_s}\}\), where \(s\ge 2\) and \(d\notin\{i_1,,\ldots,i_s\}\). Now, take \(C_{\ell}'=C_{\ell}\cup \{v_{i_1,1}, v_{i_2, 1},\dots , v_{i_{s},1}\}\) and set \[C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}'.\] Observe that we can write \(C_{\ell}=A_1\sqcup A_2\), where \(A_1=N_G(u_1)\cap C_{\ell}\) and \(A_2\subseteq V(G)\setminus (\cup_{i=1}^{d-1}N_G[u_i])\). Moreover, \(\beta(G[C_{\ell}])=\beta(G[A_1])+\beta(G[A_2])\), \(I(G[A_2])^{\{\beta(A_2)\}}=(\mathbf{x}_{A_2})\) whenever \(A_2\neq\emptyset\), and \(I(G[A_1])^{\{\beta(A_1)\}}=(\mathbf{x}_{A_1})\). Let us take \(A_1'=A_1\cup\{v_{i_1,1}, v_{i_2, 1},\dots , v_{i_{s},1}\}\). Then \(G[A_1']\) is a whisker graph, and thus by 15, \(\beta(G[A_1'])=s\) and \(I(G[A_1'])^{\{\beta(A_1')\}}=(\mathbf{x}_{A_1'})\). Consequently, \(I(G[C_{\ell}'])^{\beta(G[C_{\ell}'])}=\left(\mathbf{x}_{C_{\ell}'} \right )\). Also, it follows that \(e\in E(G[C''])\) implies either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}'])\). Moreover, since \(\beta(G[A_1'])=s=\beta(G[A_1])+1\), from 4 we have \[k \leq \left( \sum_{i \in [r], i \neq \ell} \beta(G[C_i]) \right) + \beta(G[C_\ell']) \leq r + k - 1.\] Thus, \(C''\) is a \(k\)-admissible set of \(G\) such that \(\alpha(G[C'']) = \alpha(G[C]) + s-1\). In particular, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case too.
Subcase A.2. \(u_d\in C_{\ell}\).
Subcase A.2.1. \(N_G(u_1) \cap C_\ell=\{u_d\}\). In this case we take \(C_{\ell}'=C_{\ell}\cup \{u_1, v_{1,1}\}\), and it follows from 13 that \(I(G[C_{\ell}'])^{\beta(G[C_{\ell}'])}=(\mathbf{x}_{C_{\ell}'} )\), where \(\beta(G[C_{\ell}'])=\beta(G[C_{\ell}])+1\). Now, if we set \[C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}',\] then by the construction we see that \(e\in E(G[C''])\) implies either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}'])\). Furthermore, from 4 we have \[k \leq \left( \sum_{i \in [r], i \neq \ell} \beta(G[C_i]) \right) + \beta(G[C_\ell']) \leq r + k - 1.\] Therefore, \(C''\) is a \(k\)-admissible set of \(G\) such that \(\alpha(G[C'']) = \alpha(G[C]) + 1\). Hence, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case also.
Subcase A.2.2. \(N_G(u_1) \cap C_\ell=\{u_{i_1},\dots , u_{i_s}, u_d\}\) for some \(s\ge 1\). In this case, we proceed to show that \(s\) must be \(1\). Indeed, if \(s\ge 2\), then take \(C_{\ell}'=(C_{\ell}\setminus \{u_d\}) \cup \{v_{i_1,1}, v_{i_2, 1},\dots , v_{i_{s},1}\}\) and set \[C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}'.\] Since \(I(G[C_{\ell}])^{\beta(G[C_{\ell}])}=(\mathbf{x}_{C_{\ell}})\), using 12 and 15 we have \(I(G[C_{\ell}'])^{\beta(G[C_{\ell}'])}=(\mathbf{x}_{C_{\ell}'})\), where \(\beta(G[C_{\ell}'])=\beta(G[C_{\ell}])\). It is easy to see that \(e\in E(G[C''])\) implies either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}'])\). Thus, \(C''\) is a \((k-1)\)-admissible set of \(G''\) such that \[\alpha(G[C'']) = \alpha(G[C]) + s-1> \alpha(G[C]),\] a contradiction to the fact that \(\mathrm{ind}(G', k-1) = \alpha(G[C])\). Thus, we have \(s=1\). In this case we take \(C_{\ell}'=(C_{\ell}\setminus \{u_d\}) \cup \{v_{i_1, 1}, u_1, v_{1,1}\}\), and set \[C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}'.\] Then, proceeding as before we see that \(C''\) is a \(k\)-admissible set of \(G\) such that \(\alpha(G[C'']) = \alpha(G[C]) + 1\), and consequently, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case.
Subcase B. Assume that \(C_{\ell}\cap S\neq \emptyset\). In this case, by 14 we find that \(|C_{\ell}\cap S_j|\le 1\) for each \(j\in[d-1]\). Based on this observation, we have the following two subcases to consider.
Subcase B.1. \(u_d\notin C_{\ell}\). Then by 15(3) and the fact that \(C_{\ell}\cap S\neq \emptyset\), we find that \(G[C_{\ell}\cap \Gamma]\) is a complete whisker graph. Thus if we take \(C_{\ell}'=C_{\ell} \cup \{u_1, v_{1,1}\}\), and set \[C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}',\] then from 15(2) we have \(\beta(G[C_{\ell}'])=\beta(G[C_{\ell}])+1\) and \(I(G[C_{\ell}'])^{\beta(G[C_{\ell}'])}= (\mathbf{x}_{C_{\ell}'} )\). Hence, \[k \leq \left( \sum_{i \in [r], i \neq \ell} \beta(G[C_i]) \right) + \beta(G[C_\ell']) \leq r + k - 1.\] Also, observe that \(e\in E(G[C''])\) implies either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}'])\). Thus, \(C''\) is a \(k\)-admissible set of \(G\) such that \(\alpha(G[C'']) = \alpha(G[C]) + 1\), and consequently, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case also.
Subcase B.2. \(u_d\in C_{\ell}\). In this case, without loss of generality, we can assume that \(\Lambda \cap C_{\ell}= \{ u_2, \dots , u_s, v_{2,1}, \dots , v_{t,1}, u_d\}\), where \(2\leq t\leq s\le d-1\).
Subcase B.2.1. \(t=s\). Take \(C_{\ell}'=C_{\ell} \setminus \{ u_2, \dots , u_s, v_{2,1}, \dots , v_{s,1}\}\). By repeated applications of 12(2) with \(n=2\), we get \(\beta(G[C_{\ell}'])=\beta(G[C_{\ell}])-(s-1)\) and \(I(G[C_{\ell}'])^{\{\beta(G[C_{\ell}'])\}}= (\mathbf{x}_{C_{\ell}'} )\). Moreover \(\alpha(G[C_{\ell}']) = \alpha(G[C]) -(s-1).\) Now, we set \(C_{\ell}''=C_{\ell}'\cup \{ u_1, u_2, \dots , u_s, v_{1,1}, v_{2,1}, \dots , v_{s,1}\}\). Then by 13, we have \(\beta(G[C_{\ell}''])=\beta(G[C_{\ell}])+1\) and \(I(G[C_{\ell}''])^{\{\beta(G[C_{\ell}''])\}}=(\mathbf{x}_{C_{\ell}''} )\). Moreover, \(\alpha(G[C_{\ell}'']) = \alpha(G[C]) +1\). Taking \(C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}''\), we see that \(e\in E(G[C''])\) implies either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}''])\). Furthermore, from 4 we get \[k \leq \left( \sum_{i \in [r], i \neq \ell} \beta(G[C_i]) \right) + \beta(G[C_\ell'']) \leq r + k - 1.\] Thus, \(C''\) is a \(k\)-admissible set of \(G\) such that \(\alpha(G[C'']) = \alpha(G[C]) + 1\), and hence \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case.
Subcase B.2.2. \(t<s\). Take \(C_{\ell}^{1}=C_{\ell} \setminus \{ u_2, \dots , u_t, v_{2,1}, \dots , v_{t,1}\}\). By repeated applications of 12(2) with \(n=2\), we get \(\beta(G[C_{\ell}^{1}])=\beta(G[C_{\ell}])-(t-1)\) and \(I(G[C_{\ell}^{(1)}])^{\{\beta(G[C_{\ell}^{1}])\}}=(\mathbf{x}_{C_{\ell}^{1}} )\). Moreover \(\alpha(G[C_{\ell}^{(1)}]) = \alpha(G[C_{\ell}]) -(t-1)\). Next, we take \(C_{\ell}^{2}=C_{\ell}^{1} \setminus \{ u_{t+1}, \dots , u_s,u_d\}\). Then by 12(2) it follows that \[\beta(G[C_{\ell}^{2}])=\beta(G[C_{\ell}^{1}])-(s-t)=\beta(G[C_{\ell}])-s+1,\] and \(I(G[C_{\ell}^{2}])^{\beta(G[C_{\ell}^{2}])}=(\mathbf{x}_{C_{\ell}^{2}})\). Moreover, \[\alpha(G[C_{\ell}^{2}]) = \alpha(G[C_{\ell}^{1}]) -1=\alpha(G[C_{\ell}]) -t.\] Finally, we take \(C_{\ell}^{3}=C_{\ell}^{2}\sqcup \{ u_1, \dots , u_s, v_{1,1}, \dots , v_{s,1}\}\). Then it follows from 13 that \[\beta(G[C_{\ell}^{3}])=\beta(G[C_{\ell}^{2}])+s=\beta(G[C_{\ell}])+1,\] and \(I(G[C_{\ell}^{3}])^{\beta(G[C_{\ell}^{3}])}=(\mathbf{x}_{C_{\ell}^{3}} )\). Moreover, \[\alpha(G[C_{\ell}^{3}]) = \alpha(G[C_{\ell}^{2}])+s=\alpha(G[C_{\ell}])+ (s-t).\] Next, we take \(C''=(\sqcup_{i\in[r], i\neq \ell}C_i)\sqcup C_{\ell}^{3}\), then it follows that \[k \leq \left( \sum_{i \in [r], i \neq \ell} \beta(G[C_i]) \right) + \beta(G[C_\ell^{3}]) \leq r + k - 1.\] observe from the structure of \(G\) that if \(e\in E(G[C''])\), then either \(e\in E(G[C_i])\) for some \(i\in [r]\setminus\{\ell\}\) or \(e\in E(G[C_{\ell}^3])\). Thus, \(C''\) is a \(k\)-admissible set of \(G\) such that \[\alpha(G[C'']) = \alpha(G[C]) + (s-t)\geq \alpha(G[C])+1.\] Hence, \(\mathrm{ind}(G', k - 1)\le \mathrm{ind}(G, k) - 1\), in this case too. This completes the proof of the lemma. ◻
We are now in a position to prove the main theorem of this section.
Theorem 5. Let \(G\) be a block graph on \(n\) vertices and let \(L\) be a special block with \(V(L)=\{u_1,\dots , u_d\}\). Then, for each \(1\le k\le \nu(G)\), we have the following:
\(\mathrm{reg}(I(G)^{\{k\}})\le \mathrm{ind}(G,k)+k\).
If \(\mathcal{N}_G(L,u_i)= \emptyset\) for some \(i\in [d-1]\), then \(\mathrm{reg}(I(G)^{\{k\}}:u_i)\le \mathrm{ind}(G,k)+k-1\).
If \(\mathcal{N}_G(L,u_i)\neq \emptyset\) for all \(i\in [d-1]\), then \[\mathrm{reg}(I(G)^{\{k\}}:u_i)\le \mathrm{ind}(G,k)+k-1,\] for all \(i\in [d-1]\).
Consequently, \[\mathrm{reg}(I(G)^{\{k\}})=\mathrm{ind}(G,k)+k.\]
Proof. We first prove (1), (2), and (3) simultaneously by induction on \(n\). If \(n \leq 2\), then \(k = 1\) and thus by [32] \[\mathrm{reg}(I(G)^{\{1\}}) = \nu(G) + 1 = \mathrm{ind}(G,1) + 1.\] Moreover, (2) is trivially satisfied, and (3) is vacuously true. Therefore, we may assume that \(n \geq 3\). For such an \(n\), we first consider the case \(k = 1\). Then (1) follows directly from [32]. For (2) and (3), note that \(\mathrm{reg}((I(G)^{\{1\}}:u_i))=\mathrm{reg}(I(G\setminus V(L)))\). Thus the inequality \(\mathrm{reg}(I(G)^{\{1\}}:u_i)\le \mathrm{ind}(G,1)\) can be verified using 17, 18, and the induction hypothesis. So, we further assume that \(k \geq 2\). We now divide the proof into two cases.
Case A. Let \(L\) be a special block of Type I in \(G\). In this case, either \(L\) is an isolated vertex or \(L \cong K_2\). If \(L\) is an isolated vertex of \(G\), then by the induction hypothesis and by 10, we have \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}) &= \mathrm{reg}(I(G \setminus V(L))^{\{k\}}) \\ &\le \mathrm{ind}(G \setminus V(L),k) + k \\ &\le \mathrm{ind}(G,k) + k. \end{align}\] Thus, statement (1) is satisfied, and statements (2) and (3) are vacuously true.
Now, suppose \(L \cong K_2\) and \(V(L) = \{u_1, u_2\}\). Then, \(\mathcal{N}_G(B,u_i)= \emptyset\) for \(i=1,2\). Thus, statement (3) is vacuously true. For statement (2), we set \(W=\{u_1,u_2\}\). Then by 5, we get \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1)& \leq \max\{\mathrm{reg}(I(G\setminus u_{2})^{\{k\}}:u_1),\; \mathrm{reg}(I(G)^{\{k\}}:u_1u_2)+1 \}\\ &= \max\{\mathrm{reg}(I(G\setminus \{u_1,u_2\})^{\{k\}}),\; \mathrm{reg}(I(G\setminus \{u_1,u_2\})^{\{k-1\}})+1 \} \\ &\leq \max\{\mathrm{ind}(G\setminus \{u_1,u_2\}, k)+k,\; \mathrm{ind}(G\setminus \{u_1,u_2\}, k-1)+k \}, \end{align}\] where the second equality follows from 4, and the third inequality follows from the induction hypothesis of the statement (1). Finally, the assertion \(\mathrm{reg}(I(G)^{\{k\}}:u_1) \leq \mathrm{ind}(G,k) +k - 1\) follows from 17. This proves statement (2). For statement (1), observe that \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}+(u_1))&=\mathrm{reg}(I(G\setminus \{u_1,u_2\})^{\{k\}}+(u_1))\\ &\le\mathrm{reg}(I(G\setminus \{u_1,u_2\})^{\{k\}})\\ &\le \mathrm{ind}(G\setminus \{u_1,u_2\}, k)+k\\ &\le \mathrm{ind}(G, k)+k, \end{align}\] where the inequality in the second line follows from 1(i), the inequality in the third line follows from the induction hypothesis on statement (1), and the last inequality follows from 10. We can now use 1(iii) and statement (2) to conclude that \(\mathrm{reg}(I(G)^{\{k\}})\le \mathrm{ind}(G,k)+k\), which proves (1).
Case B. Let us assume that \(L\) is a special block of \(G\) which is either of Type II or of Type III. Let \(V(L)=\{u_1,\dots , u_d\}\), where \(d\geq 2\).
Proof of (2): Let us assume that there is a vertex \(u_i\in V(L)\) with \(i\in[d-1]\) such that \(\mathcal{N}_G(L, u_i)=\emptyset\). Then observe that we must have \(d\geq 3\). Without any loss of generality, assume that \(i=1\). We set \(W=\{u_1,\dots ,u_d\}\). Then by 5, we get \[\label{eqn:32simplicial32colon} \begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1)&\leq \max \{\mathrm{reg}(I(G\setminus U_1)^{\{k\}}: \mathbf{x}_{U_2})+|U_2|-1\mid u_1\in U_2, U_1\cap U_2=\emptyset, U_1\cup U_2=W\}\\ &\leq \max \{\mathrm{reg}(I(G\setminus W)^{\{k-|U_2|+1\}})+|U_2|-1\mid u_1\in U_2, U_2\subseteq W\}\\ &\leq \max \{\mathrm{ind}(G\setminus W, k-|U_2|+1) +k \mid u_1\in U_2, U_2\subseteq W\} \end{align}\tag{5}\] where the inequality in the second line follows from 4, and the inequality in the third line follows from the induction hypothesis of the statement (1). Finally, it follows from 17 that \(\mathrm{ind}(G\setminus W, k-|U_2|+1)\leq \mathrm{ind}(G,k)-1\), for any \(U_2\subseteq W\) with \(1\leq |U_2|\leq d\). Hence, 5 , implies that \(\mathrm{reg}(I(G)^{\{k\}}:u_1)\leq \mathrm{ind}(G,k)-1\). This completes the proof of (2).
Proof of (3): Assume that for every \(u_i\in V(L), 1\leq i\leq d-1\), \(\mathcal{N}_G(L, u_i)\neq \emptyset\). Then, \(L\) is a special block of Type III. First, we consider the case when \(d=2\). Then \(V(L)=\{u_1,u_2\}\), and assume that \(N_G(u_1)=\{u_2, v_{1,1},\dots , v_{1,s}\}, s\geq 1\). We set \(W=\{u_1, v_{1,1}\}\). Then by 5, we get \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1)& \leq \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1),\; \mathrm{reg}(I(G)^{\{k\}}:u_1v_{1,1})+1 \}\\ &= \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1),\; \mathrm{reg}(I(G\setminus \{u_1, v_{1,1}\})^{\{k-1\}})+1 \} \\ &= \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1),\; \mathrm{reg}(I(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\})^{\{k-1\}})+1 \} \;\;\; \\ &\leq \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1),\; \mathrm{ind}(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\},k-1)+k \} \end{align}\] where the equality in the second line follows from 4, and the inequality in the fourth line follows from the induction hypothesis of the statement (1).
Now, by 18, it follows that \(\mathrm{ind}(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\},k-1)\leq \mathrm{ind}(G,k)-1\). Thus, it suffices to show that \(\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1)\leq \mathrm{ind}(G,k)+k-1\). For this, we again consider \(W=\{u_1,v_{1,2}\}\subseteq V(G\setminus v_{1,1})\), and proceed similarly. After \(s\)-many steps, we finally obtain \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1) &\leq \max\{\mathrm{reg}(I(G\setminus \{v_{1,1}, \dots , v_{1,s}\})^{\{k\}}:u_1), \\ &\mathrm{ind}(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\},k-1)+k\}. \end{align}\] Thus, it is enough to show that \(\mathrm{reg}(I(G\setminus \{v_{1,1}, \dots , v_{1,s}\})^{\{k\}}:u_1)\leq \mathrm{ind}(G,k)+k-1\). Now, we set \(G'=G\setminus \{v_{1,1}, \dots , v_{1,s}\}\) and \(W=\{u_1,u_2\}\subseteq V(G')\). Then by applying 5 again, we get \[\begin{align} \mathrm{reg}(I(G')^{\{k\}}:u_1)& \leq \max\{\mathrm{reg}(I(G'\setminus u_{2})^{\{k\}}:u_1),\; \mathrm{reg}(I(G')^{\{k\}}:u_1u_2)+1 \}\\ &= \max\{\mathrm{reg}(I(G'\setminus \{u_1,u_2\})^{\{k\}}),\; \mathrm{reg}(I(G'\setminus \{u_1,u_2\})^{\{k-1\}})+1 \} \\ &\leq \max\{\mathrm{ind}(G'\setminus \{u_1,u_2\}, k)+k,\; \mathrm{ind}(G'\setminus \{u_1,u_2\}, k-1)+k \}\\ &= \max\{\mathrm{ind}(G\setminus \{u_1,u_2, v_{1,1}, \dots , v_{1,s}\}, k)+k,\; \\ &\mathrm{ind}(G\setminus \{u_1,u_2, v_{1,1}, \dots , v_{1,s}\}, k-1)+k \}. \end{align}\] where the second equality follows from 4, and the third inequality follows from the induction hypothesis of the statement (1).
Let us set \(G''=G\setminus \{u_1,u_2, v_{1,1}, \dots , v_{1,s}\}\). We claim that \(\mathrm{ind}(G'',k)\leq \mathrm{ind}(G,k)-1\). Let \(C=\bigsqcup_{i=1}^r C_i\) be a \(k\)-admissible set of \(G''\) such that \[\mathrm{ind}(G'',k)=\alpha(G[C]).\] Then we have \[k\leq \sum_{i=1}^{r} \beta(G[C_i])\leq r+k-1.\] Now take \(C_{r+1}=\{u_1,v_{1,1}\}\) and set \(C'=\bigsqcup_{i=1}^{r+1} C_i\). Then observe that there is no edge among vertices of \(G[C_i]\) and \(G[C_{r+1}]\) in \(G\), for any \(1\leq i\leq r\). Moreover, \(\beta(G[C_{r+1}])=1\) and so, \[I(G[C_{r+1}])^{\{\beta(G[C_{r+1}])\}} = I(G[C_{r+1}]) = (u_1v_{1,1}).\] Finally, \[\beta(G[C']) = \sum_{i=1}^{r+1} \beta(G[C_i]) = \beta(G[C]) + 1,\] and hence, \(k+1 \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq r + k\), which can be rewritten as \[k \leq \sum_{i=1}^{r+1} \beta(G[C_i]) \leq (r+1) + k - 1.\] Therefore, \(C'\) is a \(k\)-admissible set of \(G\). Note that \[\alpha(G[C']) = |C'| - \beta(G[C']) = |C| + 2 - \beta(G[C]) - 1 = \alpha(G[C]) + 1.\] This proves that \(\mathrm{ind}(G'',k) \leq \mathrm{ind}(G,k) - 1\). The inequality \(\mathrm{ind}(G'',k-1) \leq \mathrm{ind}(G,k) - 1\) can be obtained using 10 and 18. Therefore, in this case, we have \[\mathrm{reg}(I(G')^{\{k\}}:u_1) \leq \mathrm{ind}(G,k)+k - 1,\] and consequently, \[\mathrm{reg}(I(G)^{\{k\}}:u_1) \leq \mathrm{ind}(G,k)+k - 1.\]
It now remains to consider the case when \(d\geq 3\). For this, we first take \(W=\{u_1,v_{1,1}\}\). Then, by similar arguments as in the previous case, we have \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1)& \leq \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1),\; \mathrm{reg}(I(G)^{\{k\}}:u_1v_{1,1})+1 \}\\ &\leq \max\{\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1), \mathrm{ind}(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\},k-1)+k-1 \} \end{align}\] Again to find an upper bound for \(\mathrm{reg}(I(G\setminus v_{1,1})^{\{k\}}:u_1)\), we consider \(W=\{u_1,v_{1,2}\}\) and proceed similarly. After \(s\)-many steps, we finally obtain, \[\begin{align} \mathrm{reg}(I(G)^{\{k\}}:u_1) &\leq \max\{\mathrm{reg}(I(G\setminus \{v_{1,1}, \dots , v_{1,s}\})^{\{k\}}:u_1), \\ &\mathrm{ind}(G\setminus \{u_1,v_{1,1},\dots , v_{1,s}\},k-1)+k-1 \}. \end{align}\] Now, let us set \(G'=G\setminus \{v_{1,1}, \dots , v_{1,s}\}\). Note that in \(G'\), the block \(L'\) with \(V(L')=\{u_1,\dots, u_d\}\) is a special block and \(d\geq 3\). It follows that \(L\) is a special block of Type III in \(G'\) with \(\mathcal{N}_{G'}(L,u_1)=\emptyset\). Thus, by the induction hypothesis on (2), we have \[\mathrm{reg}(I(G')^{\{k\}}:u_1)\leq \mathrm{ind}(G,k)+k-1.\] So now, it remains to show that \[\mathrm{ind}(G \setminus \{u_1, v_{1,1}, \dots, v_{1,s}\}, k-1) \leq \mathrm{ind}(G, k)-1,\] and it directly follows from 18. This completes the proof of (3)
Proof of (1): Let \(L\) be a special block of \(G\) which is either of Type II, or of Type III. Let \(V(L)=\{u_1,\dots , u_d\}\). Then either \(\mathcal{N}_G(L,u_i)=\emptyset\) for some \(i\in [d-1]\), or \(\mathcal{N}_G(L,u_i)\neq \emptyset\) for each \(i\in [d-1]\). Thus, using (2) and (3), we can choose some \(i\in[d-1]\) such that \(\mathrm{reg}(I(G)^{\{k\}}:u_i)\leq \mathrm{ind}(G,k)+k-1\). On the other hand, \[\begin{align} \mathrm{reg}( I(G)^{\{k\}}+(u_i))&\le \mathrm{reg}(I(G\setminus u_i)^{\{k\}})\\ &\leq \mathrm{ind}(G\setminus u_i,k)+k\\ & \le \mathrm{ind}(G,k)+k. \end{align}\] where the inequality in the first line follows from 1 (i), the inequality in the second line follows from the by the induction hypothesis on (1), and the inequality in the last line follows from 10. Hence, the assertion \(\mathrm{reg}(I(G)^{\{k\}}) \leq \mathrm{ind}(G,k)+k\) follows from 1 (iii). This completes the proof of (1).
Finally, we have \(\mathrm{reg}(I(G)^{\{k\}})=\mathrm{ind}(G,k)+k\) using (1) and 2. This completes the proof of the theorem. ◻
Remark 11. Since the complete graph \(K_n\) is a block graph, it follows from 5 that \(\mathrm{reg}(I(K_n)^{\{k\}})=\mathrm{ind}(K_n,k)+k\) for all \(1\leq k\leq \beta(K_n)=n-1\). However, one can simply observe that \(\mathrm{ind}(K_n,k)=1\) for all such \(k\). Indeed, if we take \(C\subseteq V(K_n)\) with \(|C|\ge 2\) such that \(C=\sqcup_{i=1}^rC_i\) is a \(k\)-admissible set of \(K_n\), then the induced subgraph on \(C\) is a complete subgraph of \(K_n\), and hence by Condition (2) of 3, we must have \(r=1\). Also, \(E(G[C])\neq \emptyset\) as \(|C|\geq 2\). Moreover, condition (3) of 3 is satisfied if and only if \(|C|=k+1\). And finally, if \(|C|=k+1\) then \(I(G[C])^{\{\beta(G[C])\}}=I(G[C])^{\{k\}}= (\mathbf{x}_C)\). Therefore, a vertex set \(C\subseteq V(K_n)\) is a \(k\)-admissible set if and only if \(|C|=k+1\), and consequently, \(\mathrm{ind}(K_n,k)=\max\{\alpha(G[C]): |C|=k+1\}=1\).
In this section, we consider the class of Cohen-Macaulay chordal graphs and show that the general lower bound for the second squarefree symbolic power is attained. Recall the following combinatorial classification of the Cohen-Macaulay property of the edge ideal of a chordal graph by Herzog, Hibi, and Zheng in [33]. These graphs are simply called the Cohen-Macaulay chordal graph.
Definition 5. A graph \(G\) is said to be a Cohen-Macaulay chordal graph if \(G\) is chordal and \(V(G)\) can be partitioned into \(W_1,\ldots,W_m\) such that \(G[W_i]\) is a maximal clique containing a free vertex for each \(i\in[m]\).
To prove the regularity formula, we require some auxiliary lemmas regarding squarefree symbolic powers of edge ideals and their behavior with various colon operations.
Lemma 19. Let \(\{x,y\}\in E(G)\) be such that \(N_G[x]\subseteq N_G[y]\). Then for any \(1\leq k\leq \beta(G)\) \[(I(G\setminus y)^{\{k\}}:x)\subseteq (I(G\setminus x)^{\{k\}}:y).\]
Proof. Let \(f\) be a squarefree monomial such that \(xf\in I(G\setminus y)^{\{k\}}\). Then for all \(P\in \mathrm{Ass}(I(G\setminus y))\) we have \(|P\cap \mathrm{supp}(xf)|\geq k\). We may assume that \(x,y\notin \mathrm{supp}(f)\). To show \(f\in (I(G\setminus x)^{\{k\}}:y)\), it is enough to show that \(|Q\cap \mathrm{supp}(yf)|\geq k\) for any \(Q\in \mathrm{Ass}(I(G\setminus x))\). We now consider the following two cases:
Case I: Assume that \(y\in Q\). If we consider \(Q'=(Q\cup \{x\})\setminus \{y\}\), then observe that \(Q'\) is a vertex cover of \(G\setminus y\). Since \(xf\in I(G\setminus y)^{\{k\}}\), it follows that \(|Q'\cap \mathrm{supp}(xf)|\geq k\), which implies that \(|Q'\cap \mathrm{supp}(f)|\geq k-1\), and hence \(|Q\cap \mathrm{supp}(yf)|\geq k\).
Case II: Assume that \(y\notin Q\). Since \(N_G[x]\subseteq N_G[y]\), we see that \(Q\) is a vertex cover of \(G\setminus y\). Again, since \(xf\in I(G\setminus y)^{\{k\}}\), we have \(|Q\cap \mathrm{supp}(xf)|\geq k\). As \(x\notin Q\), we get \(|Q\cap \mathrm{supp}(f)|\geq k\), which implies that \(|Q\cap \mathrm{supp}(yf)|\geq k\).
Thus, for any \(Q\in \mathrm{Ass}(I(G\setminus x))\), we have \(|Q\cap \mathrm{supp}(yf)|\geq k\). Therefore, \(f\in (I(G\setminus x)^{\{k\}}:y)\). ◻
If \(G\) is any chordal graph, and \(\{x,y\}\in E(G)\), then \((I(G)^{[2]}:xy)\) is again a quadratic squarefree monomial ideal, and thus can be realized as an edge ideal of a graph \(H\). Indeed, by [19], we have \((I(G)^{[2]}:xy)=I(H)\), where \(H\) is a weakly chordal graph with the vertex set and edge set described as follows: \[\begin{align} V(H)&=V(G)\setminus\{x,y\}\text{ and } \\ E(H)&=E(G\setminus\{x,y\})\cup\{\{u,v\}\mid u\in N_G(x)\setminus\{y\},v\in N_G(y)\setminus\{x\},\text{ and }u\neq v\}. \end{align}\] On the other hand, it follows from the explicit expression of the second symbolic powers of edge ideals of simple graphs (see [31]) that \(I(G)^{\{2\}}=I(G)^{[2]}+J_3(G)\), where \(J_3(G)\) is the ideal generated by \(x_ix_jx_k\), where \(x_i,x_j,x_k\) forms a triangle in \(G\). Let \(\widetilde{G}\) denote the induced subgraph of \(H\) on the vertex set \(V(H)\setminus\{a\mid \{a,x,y\}\text{ forms a triangle in }G\}\). Then the following lemma follows from the above discussion.
Lemma 20. Let \(\{x,y\}\) be an edge of a chordal graph \(G\). Then \[(I(G)^{\{2\}}:xy)=I(\widetilde{G})+(a\mid a\in V(H)\setminus V(\widetilde{G})),\] where \(\widetilde{G}\) is a weakly chordal graph.
We now turn our attention to the relationship between the admissible independence numbers of \(G\) and \(\widetilde{G}\), when \(G\) is a Cohen-Macaulay chordal graph. These relationships will be helpful in the proof of the main theorem in this section.
Lemma 21. Let \(G\) be a Cohen-Macaulay chordal graph with the decomposition \(V(G)=W_1\sqcup W_2\sqcup \dots\sqcup W_m\) such that \(m\ge 2\) and for each \(i\in [m]\), \(G[W_i]\cong K_{t_i}\), where \(t_i\ge 2\).
Let \(x\in W_i\) such that \(W_i\setminus \{x\}\) contains at least one free vertex of \(G\). Let \(y\in N_G[x]\setminus W_i\) and \((I(G)^{\{2\}}:xy)=I(\widetilde{G})\). Then \(\nu_1(\widetilde{G})\le \mathrm{ind}(G,2)-1\).
Let \(x,y\in W_i\) be free vertices of \(G\). Then \((I(G)^{\{2\}}:xy)=I(G\setminus W_i)+( W_i\setminus \{x,y\} )\). Moreover, \(\nu_1(G\setminus W_i)\le \mathrm{ind}(G,2)-1\).
Proof. (1) Follows from [19], since \(\widetilde{G}\) is an induced subgraph of \(H\).
(2) The first assertion follows from 20. The last assertion follows from the fact that given an induced matching \(M\) of \(G\setminus W_i\), the set \(M\cup \{\{x,y\}\}\) is an induced matching of \(G\), and hence a \(2\)-admissible set of \(G\) with \(\mathrm{ind}(G[V(M)\cup \{x,y\}])=|M|+1\). ◻
Lemma 22. Let \(G\) be any graph and \(x,y\in V(G)\) such that \(N_G[x]\subseteq N_G[y]\). Then \(\mathrm{ind}(G\setminus N_G[y],k)\le\mathrm{ind}(G,k)-1\) for any \(1\le k\le \beta(G)\).
Proof. Set \(H=G\setminus N_G[y]\). Let \(C=\sqcup_{i=1}^rC_i\) be a \(k\)-admissible set of \(H\) such that \(\mathrm{ind}(H,k)= \alpha(H[C])\). Now, set \(C_{r+1}=\{x,y\}\) and \(C'=\sqcup_{i=1}^{r+1}C_i\). Note that \(G[C]=H[C]\), and hence there is no edge among vertices of \(G[C_{r+1}]\) and \(G[C]\), as \(N_G[x,y]=N_G[y]\) and \(N_G[y]\cap V(H)=\emptyset\). Moreover, \(\beta(G[C_{r+1}])=1\) and hence \(I(G[C_{r+1}])^{\{1\}}=( xy)\). Thus, \[k+1\leq \sum_{i=1}^{r+1}\beta(G[C_i])\leq r+k,\] which can be rewritten as \(k\leq \sum_{i=1}^{r+1}\beta(G[C_i])\leq (r+1)+k-1\). Therefore, \(C'\) is a \(k\)-admissible set of \(G\). Note that \(\alpha(G[C'])=\alpha(G[C])+\alpha(G[C_{r+1}])=\mathrm{ind}(H,k)+1\), and this completes the proof. ◻
We are now in the position to prove the main theorem of this section. The proof goes along similar lines as [19].
Theorem 6. Let \(G\) be a Cohen-Macaulay chordal graph with \(\beta(G)\geq 2\). Then \[\mathrm{reg}(I(G)^{\{2\}})= \mathrm{ind}(G,2)+2.\]
Proof. The inequality \(\mathrm{reg}(I(G)^{\{2\}})\ge \mathrm{ind}(G,2)+2\) follows from 2. To prove the upper bound \(\mathrm{reg}(I(G)^{\{2\}})\le \mathrm{ind}(G,2)+2\), we use induction on \(|V(G)|\). Since \(\beta(G)\geq 2\), we have \(|V(G)|\ge 3\). If \(|V(G)|=3\), then \(G=K_3\). Thus, \(I(G)^{\{2\}}\) is a principal ideal generated by all the vertices of \(G\), and hence, it is easy to see that \(\mathrm{reg}(I(G)^{\{2\}})=\mathrm{ind}(G,2)+2\).
Now, suppose \(|V(G)|\ge 4\). Since \(G\) is a Cohen-Macaulay chordal graph, we can write \(V(G)=W_1\sqcup W_2\sqcup \dots\sqcup W_m\) such that \(G[W_i]\cong K_{t_i}\) for each \(i\in [m]\), where \(t_i\ge 2\). Then we have the following two cases:
Case I: Suppose that \(G\) is not a disjoint union of complete graphs. Then there exists some \(i\in [m]\) and \(x\in W_i\) such that \(N_G(x)\setminus W_i\neq\emptyset\). Without loss of generality, let \(i=1\). Moreover, let \(W_1=\{x_1,\ldots,x_r\}\) for some \(r\ge 2\) such that \(x_r\) is a free vertex of \(G\), and \(N_G(x_1)\setminus W_1\neq\emptyset\). Suppose \(N_G(x_1)\setminus W_1=\{y_1,\ldots,y_s\}\).
Claim 1: For each \(l\in[s-1]\cup\{0\}\), \[\mathrm{reg}((I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_l)):x_1y_{l+1})\le\mathrm{ind}(G,2),\] where \(I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_l)=I(G)^{\{2\}}\) in case \(l=0\).
Proof of Claim 1: Let \(G_l=G\setminus\{y_1,\ldots,y_{l}\}\), where \(G_0=G\). Then, it is easy to see that \(G_l\) is again a Cohen-Macaulay chordal graph. Now, \[\begin{align} \mathrm{reg}((I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_l)):x_1y_{l+1})&=\mathrm{reg}((I(G_l)^{\{2\}}:x_1y_{l+1})+(y_1,\ldots,y_l))\\ &=\mathrm{reg}(I(\widetilde{G_l}))\\ & = \nu_1(\widetilde{G_l})+1\\ &\le \mathrm{ind}(G_l,2)\\ &\le \mathrm{ind}(G,2), \end{align}\] where \(\widetilde{G_l}\) is a weakly chordal graph (by 20); the equality in the third line follows from [34], the inequality in the fourth line follows from 21, and the inequality in the fifth line follows from 10. This completes the proof of Claim 1.
Claim 2: For each \(p\in[r-1]\), \[\mathrm{reg}((I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_p)):x_1x_{p+1})\le \mathrm{ind}(G,2),\] where \(I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_p)=I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_s)\) in case \(p=1\).
Proof of Claim 2: Let \(H_p=G\setminus\{y_1,\ldots,y_{s},x_2,\ldots,x_p\}\), where \(H_1=G\setminus\{y_1,\ldots,y_{s}\}\). Then again, it is easy to see that \(H_p\) is a Cohen-Macaulay chordal graph. Moreover, both \(x_{1}\) and \(x_{r}\) are free vertices of \(H_p\). Now, \[\begin{align} \mathrm{reg}((I(G)^{\{2\}}+( x_1y_1,&\ldots,x_1y_s,x_1x_2,\ldots,x_1x_p)):x_1x_{p+1})\\& =\mathrm{reg}((I(H_p)^{\{2\}}:x_1x_{p+1})+( y_1,\ldots,y_s,x_2,\ldots,x_p))\\ & =\mathrm{reg}(I(H_p\setminus \{x_1,x_{p+1},x_{p+2},\dots x_r\}))\\ &= \nu_1(H_p\setminus \{x_1,x_{p+1},x_{p+2},\dots x_r\})+1 \\ &\le \mathrm{ind}(H_p,2)\\ & \le \mathrm{ind}(G,2), \end{align}\] where the equality in the second line and the inequality in the fourth line follow from 21, the equality in the third line follows from [34], and the last inequality follows from 10. This completes the proof of Claim 2.
Let \(\Gamma=G\setminus N_G[x_1]\). Then \(\Gamma\) is a Cohen-Macaulay chordal graph. Moreover, \[\label{eq31} \begin{align} \mathrm{reg}((I(G)^{\{2\}}+( x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_r)):x_1)&=\mathrm{reg}(I(\Gamma)^{\{2\}}+(y_1,\ldots,y_s,x_2,\ldots,x_r))\\ &\le \mathrm{ind}(\Gamma,2)+2\\ &\le \mathrm{ind}(G,2)+1, \end{align}\tag{6}\] where the equality follows from [11], the first inequality follows from the induction hypothesis, and the second inequality follows from 22.
Next, we have \[\label{eq32} \begin{align} \mathrm{reg}(I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_r,x_1))&=\mathrm{reg}(I(G\setminus x_1)^{\{2\}})\\ &\le\mathrm{ind}(G\setminus x_1,2)+2\\ &\le \mathrm{ind}(G,2)+2, \end{align}\tag{7}\] where the first and second inequalities follow from the induction hypothesis and 10, respectively. Now, using the regularity lemma (1) along with inequalities (6 ) and (7 ), we get \[\mathrm{reg}(I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_r))\le\mathrm{ind}(G,2)+2.\] Applying the regularity lemma with the above inequality and the inequality proved in Claim 2, we get \[\mathrm{reg}(I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_s,x_1x_2,\ldots,x_1x_{r-1}))\le\mathrm{ind}(G,2)+2.\] By a repeated use of Claim 2 and the regularity lemma, we get \(\mathrm{reg}(I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_s))\le\mathrm{ind}(G,2)+2\). Now, from Claim 1 we have \(\mathrm{reg}((I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_{s-1})):x_1y_{s})\le\mathrm{ind}(G,2)\). Thus using the regularity lemma again we obtain \(\mathrm{reg}((I(G)^{\{2\}}+(x_1y_1,\ldots,x_1y_{s-1}))\le\mathrm{ind}(G,2)+2\). By a repeated use of Claim 1 and the regularity lemma this time, we finally get \(\mathrm{reg}(I(G)^{\{2\}}\le\mathrm{ind}(G,2)+2\), as desired.
Case II: \(G\) is a disjoint union of complete graphs. In this case, let \(W_1=\{x_1,\ldots,x_r\}\) for some \(r\ge 2\). Then, proceeding as in Case I above, we obtain the following:
For each \(p\in[r-1]\), \(\mathrm{reg}((I(G)^{\{2\}}+( x_1x_2,\ldots,x_1x_p)):x_1x_{p+1})\le\mathrm{ind}(G,2)\), where \(I(G)^{\{2\}}+( x_1x_2,\ldots,x_1x_p)=I(G)^{\{2\}}\) in case \(p=1\);
\(\mathrm{reg}((I(G)^{\{2\}}+( x_1x_2,\ldots,x_1x_r)):x_1)\le\mathrm{ind}(G,2)+1\);
\(\mathrm{reg}((I(G)^{\{2\}}+( x_1x_2,\ldots,x_1x_r,x_1))\le\mathrm{ind}(G,2)+2\).
Now, using the regularity lemma along with (ii) and (iii) above, we have \(\mathrm{reg}(I(G)^{\{2\}}+( x_1x_2,\ldots,x_1x_r))\le \mathrm{ind}(G,2)+2\). Thus, as before, by a repeated use of the regularity lemma and (i) above, we obtain \(\mathrm{reg}(I(G)^{\{2\}})\le\mathrm{ind}(G,2)+2\). This completes the proof of the theorem. ◻
Remark 12. As established in 5 and 6, one has an exact formula for \(\mathrm{reg}(I(G)^{\{k\}})\) for all \(k\) when \(G\) is a block graph, and for \(\mathrm{reg}(I(G)^{\{2\}})\) when \(G\) is a Cohen–Macaulay chordal graph. These constitute significant subclasses of chordal graphs. It is therefore natural to ask whether the equality \[\mathrm{reg}(I(G)^{\{k\}}) \;=\; \mathrm{ind}(G,k)+k\] holds for all chordal graphs and for all \(1 \leq k \leq \nu(G)\). Our computations verify that this formula is indeed valid for all chordal graphs on up to \(6\) vertices.
Chau, Das, and Roy are supported by Postdoctoral Fellowships at the Chennai Mathematical Institute and a grant from the Infosys Foundation.
Data sharing does not apply to this article as no new data were created or analyzed in this study.
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.