Regularity of edge ideals of powers of graphs
My Hanh Pham, Thanh Vu · 2025
Read Regularity of edge ideals of powers of graphs by My Hanh Pham, Thanh Vu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05126.txt.
Introduction
My Hanh Pham and Thanh Vu present a short math paper from 2025. It deals with edge ideals, which are algebraic objects built from graphs. They study powers of these ideals for two kinds of graphs, forests and cycles. They ask how a measure called regularity changes as the power grows for each family.
Catalog record
| CREATOR | My Hanh Pham, Thanh Vu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-05126
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Regularity of edge ideals of powers of graphs My Hanh Pham, Thanh Vu Abstract . We prove that the regularity of edge ideals of powers of forests is weakly decreasing. We then compute the regularity of edge ideals of powers of cycles. † † footnotetext: *Corresponding Author: Thanh Vu 2000 Mathematics Subject Classification Primary: 05C70, 13D02 1. Introduction Let G be a simple graph on the vertex set V(G)=[n]=\{1,\ldots,n\} and the edge set E(G) . The distance \dist_{G}(u,v) between the vertices u and v of G is the number of edges in a shortest path connecting u and v . If no such path exists, \dist_{G}(u,v)=\infty . The diameter of G , denoted by \diam(G) , is the greatest distance between any two vertices of G . For a positive integer d , the d -th power of G , denoted by G^{d} , is a graph on the vertex set V(G) and \{u,v\} is an edge of G^{d} if and only if \dist_{G}(u,v)\leq d . In particular, G^{d} is a complete graph for any d\geq\diam(G) . Graph power is a classical concept in graph theory [ BM ] . It deeply connects to information theory, communication complexity, and Ramsey theory [ AL ] . Recently, it also appears in the work of Cooper, El Khoury, Faridi, Mayes-Tang, Morey, Sega, and Spiroff [ CEFMMSS ] where the authors studied free resolutions of powers of squarefree monomial ideals. In this work, we study the regularity of edge ideals of powers of graphs. Recall that the edge ideal of G over a field \Bbbk is defined by I(G)=(x_{i}x_{j}\mid\{i,j\}\in E(G))\subset R=\Bbbk[x_{1},\ldots,x_{n}]. We denote by \im(G) the induced matching number of G . In Lemma 2.5 , we prove that \im(G^{d+1})\leq\im(G^{d}) for any positive integer d . Although the induced matching number of G only gives a lower bound for the regularity of its edge ideal [ K , Lemma 2.2] , based on computations, we suggest the following. Conjecture 1.1 . Let G be a simple graph and d be a positive integer. Then \reg\left(R/I\left(G^{d}\right)\right)\geq\reg\left(R/I\left(G^{d+1}\right)\right), where \reg denotes the Castelnuovo-Mumford regularity. In the first main result of the paper, we prove that Conjecture 1.1 holds for forests. Theorem 1.2 . Let G be a forest and d be a positive integer. Then \reg\left(R/I\left(G^{d}\right)\right)\geq\reg\left(R/I\left(G^{d+1}\right)\right). If G=G_{1}\cup G_{2}\cup\cdots\cup G_{t} where G_{i} are the connected components of G then G^{d}=G_{1}^{d}\cup G_{2}^{d}\cup\cdots\cup G_{t}^{d} . By the results of Nguyen and Vu [ NV ] , we may assume that G is connected when studying the homological invariants of powers of I(G^{d}) . When d\geq 2 , G^{d} contains many triangles and is generally more complicated than G . Fortunately, when G is a tree, by the result of Laskar and Shier [ LS ] , G^{d} is chordal for all d\geq 1 . The conclusion then follows from Lemma 2.5 and [ W , Theorem 14] . On the other hand, the power operation preserves symmetries of G , e.g. if G is circulant then its powers are circulant. Our next result shows that Conjecture 1.1 also holds for cycles. Theorem 1.3 . Let n,d be positive integers such that n\geq 3 . Then \reg\left(R/I(C_{n}^{d})\right)=\begin{cases}1&\text{ if }n\leq 2d+2,\\ 2&\text{ if }n=2d+3,\\ \left\lfloor\frac{n}{d+2}\right\rfloor&\text{ otherwise},\end{cases} where C_{n} denotes a cycle on n vertices. This result confirms the computational experiments done by Romeo [ Ro ] . In the cases where n\leq 2d+3 the results are essentially known. In the cases where n=k(d+2)+r for 0\leq r\leq d , we drop the vertices 1,2,\ldots,d sequentially to get to the case of powers of paths. The critical case where n=k(d+2)+d+1 is much more subtle. The basic idea is simple, though. To establish the inequality \reg(J)\leq k+1 for a monomial ideal J , we use one of the following strategies. (1) Express J=K+xL for some variable x , then establish that \reg(K),\reg(K\cap L)\leq k+1 and \reg(L)\leq k . (2) Choose a sequence of variables y_{1},\ldots,y_{\ell} so that J+(y_{1},\ldots,y_{\ell}) is well understood and have regularity at most k+1 and (J+(y_{1},\ldots,y_{j-1})):y_{j} is well understood and have regularity at most k for all j=1,\ldots,\ell . We refer to Section 3 for more details. In Section 2 , we recall the notion of graph powers and prove that the induced matching numbers of powers of graphs are weakly decreasing. We then deduce Theorem 1.2 . In Section 3 , we establish Theorem 1.3 . 2. Powers of graphs 2.1. Graph Definition 2.1 . Let G be a simple graph with the vertex set V(G)=\{x_{1},\ldots,x_{n}\} and the edge set E(G) . (1) The neighborhood of a vertex x\in V(G) is N_{G}(x)=\{y\in V(G)\mid\{x,y\}\in E(G)\} . The closed neighborhood of x is N_{G}[x]=N_{G}(x)\cup\{x\} . (2) For a subset U\subset V(G) , the neighborhood and closed neighborhood of U in G are defined respectively by N_{G}(U)=\cup\left(N_{G}(x)\mid x\in U\right) and N_{G}[U]=\cup\left(N_{G}[x]\mid x\in U\right) . (3) A simple graph H is a subgraph of G if V(H)\subseteq V(G) and E(H)\subseteq E(G) . H is an induced subgraph of G if it is a subgraph of G and E(H)=E(G)\cap V(H)\times V(H) . (4) For a subset U\subset V(G) , G[U] and G\backslash U denote the induced subgraph of G on U and on V(G)\setminus U respectively. (5) A path P_{n} on n vertices is the graph on V(P_{n})=\{x_{1},\ldots,x_{n}\} with the edge set E(P_{n})=\{\{x_{1},x_{2}\},\ldots,\{x_{n-1},x_{n}\}\}. (6) A cycle C_{n} on n vertices is the graph on V(C_{n})=\{x_{1},\ldots,x_{n}\} with the edge set E(C_{n})=E(P_{n})\cup\{\{x_{1},x_{n}\}\} . (7) A forest is a graph without any cycles. A tree is a connected forest. (8) G is called chordal if it has no induced cycles of length at least four. (9) A subset M\subseteq E(G) is called a matching of G if no two edges in M share a common vertex. It is an induced matching if M forms an induced subgraph of G . Induced matching number of G , denoted by \im(G) , is the largest size of an induced matching of G . The induced matching number of the d -th power of an n -cycle was given in [ Ro , Corollary 3.4] . We now compute the induced matching number of the d -th power of a path on n vertices. Lemma 2.2 . Let n,d be positive integers such that n\geq 2 . Then \im(P_{n}^{d})=\left\lfloor\frac{n+d}{d+2}\right\rfloor. Proof. Fix d\geq 1 . When n\leq d+1 , P_{n}^{d} is a complete graph on n vertices. Hence, \im(P_{n}^{d})=1 . Now, assume that n\geq d+2 . Write n=k(d+2)+r for some k\geq 1 and 0\leq r\leq d+1 . Let \mathcal{M}=\{\{1,2\},\{(d+2)+1,(d+2)+2\},\ldots,\{(d+2)\ell+1,(d+2)\ell+2\}\}, where \ell=k-1 if r\leq 1 and \ell=k if r\geq 2 . Then \mathcal{M} is an induced matching of P_{n}^{d} . Hence, \im(P_{n}^{d})\geq|\mathcal{M}|=\lfloor\frac{n+d}{d+2}\rfloor . We now prove by induction on n that \im(P_{n}^{d})\leq\left\lfloor\frac{n+d}{d+2}\right\rfloor . The base case where n\leq d+1 is clear. Now, assume that n\geq d+2 . Let \mathcal{M} be a maximum induced matching of P_{n}^{d} . If 1\notin\mathcal{M} , then \mathcal{M} is an induced matching of P_{n-1}^{d} , and the conclusion follows from induction. Thus, we may assume that 1\in\mathcal{M} . Assume that \{1,i\}\in\mathcal{M} for some i\leq d+1 . Then dropping \{1,i\} from \mathcal{M} gives an induced matching of P_{n-i-d}^{d} . By induction, we deduce that \im(P_{n}^{d})\leq 1+\im(P_{n-i-d}^{d})\leq 1+\im(P_{n-d-2}^{d})=\left\lfloor\frac{n+d}{d+2}\right\rfloor. The conclusion follows. ∎ In order to prove that \im(G^{d+1})\leq\im(G^{d}) for an