Trees whose path ideals have linear quotients

Trung Chau, Kanoy Kumar Das, Animikha Dutta Dhar, Pranath S Karanth, Aniruda Suswaram · 2025

Read Trees whose path ideals have linear quotients by Trung Chau, Kanoy Kumar Das, Animikha Dutta Dhar, Pranath S Karanth, Aniruda Suswaram (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-2506-06209.txt.

Introduction

Trung Chau and co-authors classify trees by an algebraic property of their path ideals. For any chosen length n, each tree gives rise to an ideal built from its paths of that length, and the team asks exactly which trees yield ideals with linear quotients. Their 2025 paper gives a complete classification for every n. Results of this kind link the shape of a graph to the behavior of equations built from it, and they serve readers in commutative algebra and graph theory.

Catalog record

CREATORTrung Chau, Kanoy Kumar Das, Animikha Dutta Dhar, Pranath S Karanth, Aniruda Suswaram
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06209

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Trees whose path ideals have linear quotients Trung Chau, Kanoy Kumar Das, Animikha Dutta Dhar, Pranath S Karanth, Aniruda Suswaram Abstract . For any integer n n , we classify all trees whose n n -path ideals have linear quotients. 2020 Mathematics Subject Classification 13F55, 05E40, 05C05 1. Introduction A monomial ideal I\subseteq\Bbbk[x_{1},x_{2},\dots,x_{m}] is said to have linear quotients if there is an ordering of the monomials in \mingens(I)=\{f_{1},f_{2},\dots,f_{s}\} such that the successive colon ideals (f_{1},f_{2},\dots,f_{i}):f_{i+1} are generated by variables for all 1\leq i\leq s-1 . Ideals with linear quotients were introduced by Herzog and Takayama [ 17 ] and they have strong combinatorial implications. In the case of square-free monomial ideals, linear quotients and shellable simplicial complexes are dual concepts. This fact attracted many researchers to identify ideals with linear quotients and explore their properties [ 19 , 23 ] . In [ 24 ] , Villarreal introduced the class of edge ideals of graphs and studied their various algebraic properties which relate to the combinatorics of the corresponding graphs. Arguably the most celebrated result in this theme is that of Fröberg [ 12 ] , which states that a graph is co-chordal if and only if its edge ideal has linear resolution. Since then, an astounding amount of research has been carried out around edge ideals, as this class connects two different areas of mathematics, namely, graph theory and commutative algebra. Later on, several generalizations of edge ideals, such as path ideals, connected ideals, weighted oriented edge ideals, etc., have been introduced to carry forward this theme of research. A natural question one can ask is whether one can find an analog of the celebrated result of Fröberg [ 12 ] for these classes of ideals, that is, to classify ideals which have linear resolution. In this context, having linear quotients implies having linear resolution, and in fact, the converse holds for edge ideals. Conca and De Negri [ 7 ] were the first to consider path ideals of directed graphs to study M -sequences. Over the years, many algebraic properties and invariants of path ideals of directed graphs such as (Castelnuovo-Mumford) regularity, projective dimension, graded betti numbers, Cohen-Macaulayness, etc., have been intensively investigated [ 5 , 6 , 9 , 20 ] . In this work, we consider path ideals of simple undirected graphs. Let G be a simple graph with V(G)=\{x_{1},x_{2},\dots,x_{m}\} . The n -path ideal of G , denoted by J_{n}(G) , is defined to be the ideal of \Bbbk[x_{1},x_{2},\dots,x_{m}] given by J_{n}(G)\coloneqq\left(\prod_{j=1}^{n}x_{i_{j}}\mid x_{i_{1}},x_{i_{2}},\dots,x_{i_{n}}\text{ forms a }n\text{-path in }G\right). Alilooee and Faridi [ 1 , 2 ] considered n -path ideals of lines and cycles, and studied their Betti numbers. In [ 4 ] , it has been shown that if G is gap-free and claw free, then J_{n}(G) has linear resolution for n=3,4,5,6 ; and in addition, if G is whiskered K_{4} -free, then J_{n}(G) has linear resolution for all n\geq 3 . In [ 8 ] , 3 -path ideals of chordal graphs have been studied, and an exact formula for the regularity of n -path ideals of caterpillar graphs was given. Other related works in this direction are [ 13 , 21 ] . In these work, the authors use different techniques to determine the regularity of J_{n}(G) , obtaining instances of linear resolution as a corollary. In other words, their results do not imply that these ideals have linear quotients. Recently, in [ 3 ] , the authors considered connected ideals of graphs, which is another generalization of edge ideals, and as a consequence of their main result [ 3 , Theorem 5.1] , it follows that J_{3}(G) have linear quotients if and only if it has linear resolution if and only if G does not contain P_{3}+P_{3} , the disjoint union of two paths of length 2, as an induced subgraph, when G is a tree. Moreover, J_{2}(G) is the edge ideal of G , and thus a corollary of Fröberg theorem is: for a tree G , the ideal J_{2}(G) has linear quotients if and only if it has linear resolution if and only if G does not contain P_{2}+P_{2} , the disjoint union of two edges, as an induced subgraph. In this article, for n\geq 4 , we consider n -path ideals of trees and investigate when they have linear quotients (and linear resolution). The goal is to extend the aforementioned results for J_{2}(G) and J_{3}(G) . Any square-free monomial ideal can be treated as an edge ideal of a hypergraph. A necessary condition for a square-free monomial ideal to have linear resolution is that the induced matching number of the corresponding hypergraph to be one. This fact gives one of the obvious forbidden structures in case of path ideals of graphs: if J_{n}(G) has linear resolution, then G does not contain the disjoint union of two paths of length n , namely P_{n}+P_{n} , as an induced subgraph. However, for general n , this is not the only forbidden structure, even for trees. We show that, in the case of trees, there is a family of graphs, which we denote as L_{n,k} where n\geq 5,k\in[3,n-2] , are also forbidden to be an induced subgraph of G if J_{n}(G) has linear resolution. Indeed, to be more precise, we prove the following: Theorem 1.1 (Theorem 5.1 ) . Let G be a tree and n\geq 4 a positive integer. Then the following statements are equivalent: (1) J_{n}(G) has linear resolution; (2) J_{n}(G) has linear quotients; (3) either of the following holds: (i) n=4 , and G does not contain P_{4}+P_{4} or L_{5,3} as an induced subgraph; (ii) n\geq 5 , and G does not contain P_{n}+P_{n} or L_{n,k} as an induced subgraph for any k\in[3,\ (n+1)/2]. Some consider path ideals more complicated than other generalizations of edge ideals, e.g., connected ideals. One reason for this is the difficulty of determining J_{n}(G) for a given n and given G . For connected ideals (or edge ideals in particular), more edges in the graph almost always equal more generators for the ideals, a principle that does not hold for path ideals. For example, J_{4}(G)=(0) for any star graph G (a graph whose edges share a common vertex). The novelty in our approach is that for any n\geq 4 and any tree G such that J_{n}(G) has linear resolution, we can determine an induced subgraph H of G such that J_{n}(G)=J_{n}(H) and J_{n}(H) can be easily computed. We call the operation to obtain H from G trimming , which we shall explore in Section 4 . As a preview, let G be the following tree. x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7} x_{8} x_{9} Figure 1. The graph G Let H be the induced subgraph of G with the vertex set \{x_{1},x_{2},\dots,x_{8}\} . It can be verified straightforwardly that J_{7}(H)=J_{7}(G)=(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}x_{7}) . In fact, this is the smallest example where the trimming operation results in a proper subgraph of G . In other words, the effectiveness of this method can only be observed when one considers J_{n}(G) when n\geq 7 . This paper is organised as follows. In Section 2 , we recall preliminary notions from commutative algebra and graph theory, and prove

Read the complete text