# Graded Linearity of Stanley–Reisner Ring of Broken Circuit Complexes

Authors: Mohammad Reza-Rahmati; Gerardo Flores
Journal: Journal of Mathematics
 (2022)

---

## Abstract

This paper introduces two new notions of graded linear resolution and graded linear quotients, which generalize the concepts of linear resolution property and linear quotient for modules over the polynomial ringA=kx1,…,xn. Besides, we compare graded linearity with componentwise linearity in general. For modules minimally generated by a regular sequence in a maximal ideal of A, we show that graded linear quotients imply graded linear resolution property for the colon ideals. On the other hand, we provide specific characterizations of graded linear resolution property for the Stanley–Reisner ring of broken circuit complexes and generalize the results of Van Le and Römer, related to the decomposition of matroids into the direct sum of uniform matroids. Specifically, we show that the matroid can be stratified such that each stratum has a decomposition into uniform matroids. We also present analogs of our results for the Orlik–Terao ideal of hyperplane arrangements which are translations of the corresponding results on matroids.


---

## Body

## 1. Introduction

We consider finitely generated graded modules over the polynomial ring,A=kx1,…,xn, where k is an infinite field. One of the essential facts about the finitely generated rings over A is Hilbert’s syzygy theorem [1], stating that any such module has a graded minimal A-resolution by free modules as(1)⋯⟶⊕jA−jβp,j⟶⋯⟶⊕jA−jβ0j⟶M⟶0,where the graded Betti numbers βij of the graded module M are the exponents appearing in a graded minimal free resolution. Another way to express it is βij=dimkToriM,kj. One can arrange the Betti numbers in a table by assigning βi,i+j in the i,j entry, called the Betti table. The graded A-module M is said to have a linear resolution if its nonzero Betti numbers in minimal A-resolution appear just in one line of entries, successively in the table. In special cases, one can characterize this property by the combinatorial data associated with these modules. We generalize this concept by mentioning finitely generated graded modules where their nonzero Betti numbers appear successively in several lines. Then, an important question is the combinatorial identification of the above property. A parallel concept is that of having linear quotients. This notion is defined in terms of the colon ideals of module M. It is well known that having a linear quotient implies the linear resolution property for colon ideals [2].In this text, we also generalize the concept of quotient linearity, and we define the graded linear quotient property. We compare it with graded linear property and prove the analogous theorem in the graded case. Our proof uses a standard inductive technique of passing to the long exact Tor-sequence associated with short exact sequence on colon ideals ofM. This generalization aims to study the notion of componentwise linearity, which plays a crucial role in commutative algebra. We show that graded linearity is a weaker property than componentwise linearity.For Cohen–Macaulay graded idealsI in A, the property of having a linear resolution is characterized by the combinatorial data of the ideal such as its Hilbert polynomial. In this case, the Hilbert polynomial can be summarized in a single binomial coefficient. An interesting example is the Stanley–Reisner ideal I<X of the broken circuit complex of matroid X. The Stanley–Reisner ideal I<X is generated by monomials on the broken circuits of X. The broken circuit complex of an ordered matroid X is a shellable complex, where it shows the Stanley–Reisner ring A/I<X is Cohen–Macaulay [1]. The linearity property, in this case, can be translated into a combinatorial decomposition of the matroid in terms of uniform matroids (see [3]) in the form(2)X=Us,n−r+s⊕Ur−s,r−s,where matroid Up,n is the uniform matroid on n-element, whose independent sets are subsets having at most p element. The proof of the theorem uses the assertions of an external bound for the f-vectors of an r−1 dimensional shellable complex on the vector set S of size S=n in the form(3)fk−1≥∑i=0s−1n−r+i−1ir−ik−i,k=0,…,r,when all s-element subsets of S belong to Δ. The decomposition in (2) holds when the equality in (3) holds [4].A significant attempt in this work is to find analogous characterizations of graded linearity for these ideals. One also asks how the decomposition of the matroid can be extended. In other words, we investigate what the corresponding operation in the category of matroids is. To answer this question, we introduce the notion of stratification (filtration) of matroids by submatroids. Stratification of a matroidX is a decreasing filtration sequence,(4)X=X0⊃X1⊃⋯⊃Xd,Sj=Xj,Xj+1,by submatroids Xj, where we call Xj,Xj+1 the j-th strata of the stratification. If X is a rank r loopless matroid on n, we establish a new inequality(5)Ij−1≥∑i=0c−1∑l=1dclSn−r+l−1lr−ij−i,generalizing (3), and the equality holds if and only if the ideal I<X has graded linear resolution. In that case, we first establish that the Hilbert function of I<X has the form(6)HAI<X,s=c0s+q−1s+c1s+q−2s+⋯+cd−1s+q−ds,for some d. The coefficients ci=ciI<X can be easily calculated (called Hilbert coefficient of I<X). In this case, there exists a stratification as in (4) such that(7)Sj=Urj−sj,rj−sj⊕Usj,nj−rj+sj,where sj≤rj. We have n=∑jnj,r=∑jrj.To an arrangement of hyperplanes in a vector space, one can associate a matroid, where the independent sets correspond to the independent hyperplanes. In this way, some properties for matroids can be translated into the language of hyperplane arrangements. The properties above can be applied to certain graded ideals associated with a hyperplane arrangement. In particular, they apply to the Orlik–Solomon ideal and also the Orlik–Terao ideal of the arrangements. As an application, we provide similar assertions for graded linearity of the Orlik–Terao ideal of hyperplane arrangements, which translates the above results to this area. We discuss the Koszul property of the Stanley–Reisner ring of the broken circuit complex. We define an extension of Koszulness, namely, graded Koszulness, and characterize this concept via the decomposition of the associated matroid.Another important concept is the entire intersection property of Orlik–Solomon algebra and the Orlik–Terao ideal of hyperplane arrangements [3, 5–7]. There appear several characterizations of this property in [3] concerning the linearity of the corresponding ideals. We express the generalizations of these theorems to the graded linearity as a natural application to our results. We also present an application to graphs and their cycle matroids. Specifically, we discuss the entire intersection property of the facet ideal of r-cyclic graph Gn,r. We provide an alternative for the proof of the Cohen–Macaulayness of the facet ideal of Gn,r. The properties of the facet ideal IFΔ have been discussed in [8–12]. Our method gives a simple proof of the Cohen–Macaulayness of the facet ideal of Gn,r. This property was proved in [8] by direct methods. Our proof is based on the criteria characterizing the complete intersection properties on the cycle matroid of a graph.


### 1.1. Related Works

This work is based on the results of [3, 13] about several combinatorial characterizations of linear resolution property for the Stanley–Reisner ring of broken circuit complexes. The main theorem that is proven in that work is that of characterization for the decomposition of the broken circuit complex of a matroid when the associated Stanley–Reiner ring has a linear resolution. The authors also express the analogs theorems on the arrangement of hyperplanes. The results identify the linear resolution property for the Orlik–Solomon ideal of the arrangement and the complete intersection and Koszul property of their Orlik–Solomon and Orlik–Terao ideals.On the other hand, a comprehensive study of the combinatorics of the broken circuits of matroids is done [4]. In this regard, we have generalized a fundamental argument of [4] on the decomposition of matroids based on a lower bound for the components of the f-vectors of shellable complexes. The lower bound in its extreme case implies a decomposition of the complex of independent subsets of a matroid into the direct sum of two uniform matroids; see also [14]. Our approach in generalizing the above decomposition is through the stratification of a matroid by its submatroids. The concept has been explored in [15]; however, it has not worked out very much in the literature. Therefore, we have explained it through basic operations on matroids [15–18]. The stratification describes a decreasing filtration by submatroids and results in a kind of graded decomposition on the matroid, that is, decomposition on each stratum.A comprehensive exposition on Koszul algebras and the related conjectures is presented in [5]. The characterization of this property for Orlik–Terao ideals of arrangement of hyperplanes can be considered as a special case of having general linear resolution mentioned above. In this case, the Orlik–Terao ideal has a 2-linear resolution [3]. In this regard, the combinatorial identification of the Koszul property for algebras associated with matroids and hyperplane arrangements is one of the significant and crucial challenging problems in this area [5–7, 19, 20].


### 1.2. Organization of Text

Section2 contains the basic definitions and theorems that we use throughout the text. We have divided that into six subsections containing different notions in combinatorial algebra. Sections 3 and 4 consist of our main results and contributions. Specifically, Section 4 consists of the applications of the results in Section 3 to the hyperplane arrangements. In the end, we also prove a complete intersection property for the broken circuit complex of r-cyclic graph. Finally, in Section 5, we present some remarks and conclusions.


## 1.1. Related Works

This work is based on the results of [3, 13] about several combinatorial characterizations of linear resolution property for the Stanley–Reisner ring of broken circuit complexes. The main theorem that is proven in that work is that of characterization for the decomposition of the broken circuit complex of a matroid when the associated Stanley–Reiner ring has a linear resolution. The authors also express the analogs theorems on the arrangement of hyperplanes. The results identify the linear resolution property for the Orlik–Solomon ideal of the arrangement and the complete intersection and Koszul property of their Orlik–Solomon and Orlik–Terao ideals.On the other hand, a comprehensive study of the combinatorics of the broken circuits of matroids is done [4]. In this regard, we have generalized a fundamental argument of [4] on the decomposition of matroids based on a lower bound for the components of the f-vectors of shellable complexes. The lower bound in its extreme case implies a decomposition of the complex of independent subsets of a matroid into the direct sum of two uniform matroids; see also [14]. Our approach in generalizing the above decomposition is through the stratification of a matroid by its submatroids. The concept has been explored in [15]; however, it has not worked out very much in the literature. Therefore, we have explained it through basic operations on matroids [15–18]. The stratification describes a decreasing filtration by submatroids and results in a kind of graded decomposition on the matroid, that is, decomposition on each stratum.A comprehensive exposition on Koszul algebras and the related conjectures is presented in [5]. The characterization of this property for Orlik–Terao ideals of arrangement of hyperplanes can be considered as a special case of having general linear resolution mentioned above. In this case, the Orlik–Terao ideal has a 2-linear resolution [3]. In this regard, the combinatorial identification of the Koszul property for algebras associated with matroids and hyperplane arrangements is one of the significant and crucial challenging problems in this area [5–7, 19, 20].


## 1.2. Organization of Text

Section2 contains the basic definitions and theorems that we use throughout the text. We have divided that into six subsections containing different notions in combinatorial algebra. Sections 3 and 4 consist of our main results and contributions. Specifically, Section 4 consists of the applications of the results in Section 3 to the hyperplane arrangements. In the end, we also prove a complete intersection property for the broken circuit complex of r-cyclic graph. Finally, in Section 5, we present some remarks and conclusions.


## 2. Preliminaries

### 2.1. Linear Resolutions

LetA=Kx1,…,xn be the polynomial ring over an infinite field k and m=x1,…,xn the maximal ideal. A finitely generated graded A-module M is said to have s-linear resolution if the graded minimal free resolution of M is of the form(8)0⟶A−s−pβp⟶⋯⟶A−s−1β1⟶A−sβ0⟶M⟶0.In other words,M has s-linear resolution if βi,i+j=0 for j≠s; a relevant notion is that of s-linear quotient (see [2, 21]).Next, we give some definitions and nomenclature to set the conditions of Theorem1 presented in the following. First, let assume that < is a monomial order on A. Write a nonzero polynomial in A as f=∑vavv, where v∈A is a monomial. The initial monomial of f w.r.t. < is the biggest monomial w.r.t. < among the monomials belonging to suppf. We write in<f for the initial monomial of f with respect to <. The leading coefficient of f is the coefficient of in<f. If I is a nonzero ideal of A, the initial ideal of I w.r.t < is the monomial ideal of A, which is generated by in<f:f∈I. We write in<f for the initial ideal of I. Thus, we are ready to present the following theorem, which characterizes the linear resolution property.Theorem 1 (see [3]).
Assume thatI=⊕kIk is a graded Cohen–Macaulay ideal in A of codimension q and s is the smallest index where Is≠0. The following are equivalent:(i)
I has s-linear resolution(ii)
Ifa1,…,an−q is a maximal A/I-regular sequence of linear forms in A, we have I¯=ms¯ in A/a1,…,an−q(iii)
The Hilbert function ofI has the form HI,s=s+q−1s(iv)
Suppose< is a monomial order on A. If in<I (the initial ideal of I) is Cohen–Macaulay, then in<I has s-linear resolutionNow let us suppose thatI is a graded ideal of A and in<I is Cohen–Macaulay; then from the above theorem, it follows that I has linear resolution if and only if in<I has a linear resolution, cf. [3] loc. cit. A relevant definition is that of linear quotients as follows.Definition 1.
SayM has linear quotient, if there exists a minimal system of generators a1,…,am of M such that the colon ideals,(9)Jl=a1,…,al−1:al,are generated by linear forms of all l.On the other hand, the following result relative to linear quotients is also well known.Theorem 2 (see prop. 8.2.1 in [2]).
Suppose thatI is a graded ideal of A generated in degree s. If I has linear quotients, then it has a s-linear resolution.Another important concept related to linearity isthe componentwise linearity [2]. For that, we consider the following construction. Assume that M=⊕jMj is a finitely generated graded A-module and let F,d=Fn,dn:Fn⟶Fn−1 be the minimal graded free resolution of M. Define subcomplexes(10)Fi≔mi−nFn,dn.The linear part ofF is the complex(11)Flin=⊕iFiFi+1,grid.Also, we have an important definition and theorem regarding the graded moduleM=⊕jMj. These are presented next.Definition 2.
The graded moduleM=⊕jMj is said to be componentwise linear if Ms has linear resolution for all s, whereby definition Ms is the submodule generated by Ms.Theorem 3 (see [5, 13]).
The following are equivalent:(i)
M is componentwise linear(ii)
Mq has a linear resolution for every q(iii)
Flin is acyclicOne can choose a homogeneous basis for theA-graded modules Fi (for all i), so that matrices present the differentials with homogeneous entries. Then, the differential of the complex Flin is obtained by killing all the monomials of degrees bigger than one in the entries. The resulting matrix is called the linearization of differentials.


### 2.2. Broken Circuit Complexes

One can consider the above properties for certain ideals constructed from combinatorial data of a matroid. LetX,< be an ordered simple matroid of rank r on n. The minimal dependent subsets of X are called circuits. Denote by BC<X the broken circuit complex of X, that is, the collection of all subsets of M not containing any broken circuit. It is known that BC<X is an r−1-dimensional shellable complex. The Stanley–Reisner ideal of BC<X denoted by I<X is the ideal generated by all monomials on broken circuits. We denote a broken circuit by bc<C=C,min<C [3]. By definition,(12)I<X=xbc<C≔∏j∈bc<Cxj.The shellability ofBC<X implies that A/I<X is Cohen–Macaulay. Thus, the following theorem characterizes the linear resolution of the ideal I<X.Theorem 4 (see [3]).
The following are equivalent:(i)
I<X has s-linear resolution(ii)
X=Us,n−r+s⊕Ur−s,r−s(iii)
All powers ofI<X have linear resolutionsThe matroidUp,n is the uniform matroid on the n-element, whose independent sets are subsets having at most p elements. Up,n has rank p and its circuits have p+1 elements. In particular, Un,n has no dependent sets and is called free. The proof of Theorem 4 uses Theorem 7.5.2 of [4] on an external bound for the f-vectors; refer to [3]. For the sake of completeness, we briefly recall this fact from [4] in the following theorem.Theorem 5 (see [4]).
Let us consider the following:(1)
LetΔ be an r−1 dimensional shellable complex on the vector set S of size S=n. If, for some s∈ℕ, all s-element subsets of S belong to Δ, then the inequality,(13)fk−1≥∑i=0s−1n−r+i−1ir−ik−i,k=0,…,r,holds for thef-vector.(2)
Assume thatΔ=InX is the complex of independent subsets of a loopless matroid. Then, inequality (13) holds for fk replaced with Ik, the number of independent k-element subsets of X. The equality holds if and only if(14)X=Us,n−r+s⊕Ur−s,r−s,s+1=minC;Cis a circuit.We sketch some explanations related to the above theorem inspired from [4]. The condition that all s-element subsets of S are in Δ implies that fk=nk,k=0,1,2,3,…,s. By using formal combinatorial identities,(15)hk=∑i=0k−1i+kr−ik−ini=n−r+k−1k,k≤s.Therefore, the inequality in (13) follows by singling out the first s+1 terms in(16)fk=∑i=0khir−ik−i,k=1,…,r.In caseΔ=InX, let bX=Ir; then bX=n−r+ss is the number of bases of X. The h-vector is given by(17)h¯=1,n−r,…,n−r+s−1s,and the Tutte polynomial of X is(18)TXx,1=hΔx=xr+n−rxr−1+⋯+n−r+s−2s−1xr−s.The form of the Tutte polynomial shows thatX has exactly n−r+s coloops. This forces X=N⊕Ur−s,r−s where N is a matroid of rank s on n−r+s points. Now bN=bX=n−r+ss. This forces that N=Us,n−r+s. The equality in (13) holds, if hc=hc+1=⋯=0, cf. [4] loc. cit.


### 2.3. Complete Intersection Property

Later, in Section4, we need to decide whether a graded ideal is a complete intersection. For that, in this subsection, we present some definitions from commutative algebra. For a commutative Noetherian local ring A, the depth of A (the maximum length of a regular sequence in the maximal ideal of A) is at most the Krull dimension of A. The ring A is called Cohen–Macaulay if its depth is equal to its dimension. A regular sequence is a sequence a1,…,an of elements of m such that, for all i, element ai is not a zero divisor in A/a1,…,an. A local ring A is a Cohen–Macaulay ring if there exists a regular sequence a1,…,an such that the quotient ring A/a1,…,an is Artinian. In that case, n=dimA. More generally, a commutative ring is called Cohen–Macaulay if it is Noetherian, and all of its localizations at prime ideals are Cohen–Macaulay. Besides, we say that a ring A is a complete intersection if there exists some surjection R⟶A, with R a regular local ring, such that a regular sequence generates the kernel. Our goal is to identify the complete intersection property for the Stanley–Reisner ideal of broken circuit ideals of matroids. For that, let us present some definitions next.Let us assume thatX,< is an ordered matroid on n, and CX is the set of broken circuits of X. Let I<X be the Stanley–Reisner ideal of the broken circuit complex BC<X. A subset D∈CX is called generating set if xbc<C;C∈D generates I<X. It is clear from definition that D is a generating set of CX if bc<C for C∈D containing minimal broken circuits of X. Denote by LD the intersection graph of D; that is, the vertex set of LD is D and the edges are pairs C,C′ such that C∩C′=∅. Say D is simple if whenever C,C′∈D, either C∩C′=min<Cormin<C′; otherwise, C∩C′=∅.Theorem 6 (see [3]).
AssumeX,< is a simple ordered matroid The following are equivalent:(i)
I<X is complete intersection(ii)
The minimal broken circuits ofX are pairwise disjoint(iii)
There exists a simple subsetD⊂CX such that CX=LD′;D′⊂DTheorem6 gives concrete combinatorial criteria to check the entire intersection property of Stanley–Reisner ideal of broken circuit complex of matroids. It can also be applied to graph matroids; see [3].


### 2.4. Hyperplane Arrangements

To an arrangement of hyperplanesA, one naturally associates a matroid denoted by X=XA with the ground set to be the same as A and the independent sets to be the independent hyperplanes in A; that is, those whose corresponding reflections as said above are independent. Assume that the matroid XA is associated with an essential central hyperplane arrangement of n hyperplanes A=H1,…,Hn in a vector space V of dimension r over the infinite field k. When k=ℂ, the integral cohomology of the complement V,∪iHi is isomorphic to the Orlik–Solomon algebra of AA, which is the quotient of standard graded exterior algebra on ℂe1,…,en by the Orlik–Solomon ideal JA generated by the elements(19)∂ei1,…,ip=∑r−1r−1ei1,…,eir^,…,eip,when Hi1,…,Hip are dependent subsets of A; that is, the reflections αij through Hij are independent. Therefore,(20)AA=AJA=∧ℤe1,…,en∂ei1,…,ip=H∗V,∪iHi,ℤ.The Orlik–Terao algebra is a commutative analogue of Orlik–Solomon algebra. That is, instead of exterior algebra onn vectors, we work on A=kx1,…,xn and whenever we have a relation ∑jajαij=0, we assume a relation r=∑jajαij in a relation space FA. The Orlik–Terao ideal is generated by(21)∂r=∑j−1j−1ajxi1,…,xij^,…,xip⇐r=∑jajαij.The quotientCA=A/IA is called the Orlik–Terao algebra of the hyperplane arrangement. The Orlik–Solomon algebras and Orlik–Terao algebras of hyperplane arrangements are related to each other by an idea of deformation [2]. A relevant notion in this context is that of a Koszul algebra defined next.Definition 3 (see [3]).
Suppose thatL is either an exterior or a polynomial algebra over a field k. A graded algebra B=L/I is called Koszul if k has linear resolution over B.The characterization of the Koszulness of the Orlik–Solomon algebra of hyperplane arrangement is one of the essential questions in this area. In this regard, we mention the following theorem.Theorem 7 (see [3]).
LetA be an essential central arrangement of n hyperplanes in dimension r, and assume that IA is complete intersection. Then the following are equivalent:(1)
AA is Koszul(2)
CA is Koszul(3)
XA=U2,n−r+2⊕Ur−2,r−2(4)
A=A1×A2 where A1 is generic central arrangement of n−r+2 hyperplanes in dimension p and A2 is Boolean in dimension r−2(5)
IA has 2-linear resolution(6)
JA has 2-linear resolutionIt is well known that ifB is Koszul, then I is generated by quadrics. Unfortunately, the converse is not true in general. The following consequence is immediate from the above theorem.Theorem 8 (see [3]).
The Orlik–Terao idealIA of an essential central arrangement has 2-linear resolution if A is obtained by successively coning a central arrangement of lines in the plane. In this case, the Orlik–Terao algebra is Koszul.


### 2.5. Basic Operations on Matroids

Assume thatX is a matroid with an element set E and that S is a subset of E. The restriction of X to S, written as X|S, is the matroid on set S whose independent sets are the independent sets of X that are contained in S. Its circuits are the circuits of X contained in S, and its rank function is that of X restricted to subsets of S. In linear algebra, this corresponds to restricting to the subspace generated by the vectors in S. If T=X−S, this is equivalent to the deletion of T, written as X,T. The submatroids of X are precisely the results of a sequence of deletions (the order is irrelevant). The dual operation of restriction is contraction. If T is a subset of E, the contraction of X by T, written as X/T, is the matroid on the underlying set E−T whose rank function is r′A=rA∪T−rT. In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in T, together with the images of the vectors in E−T. Then, the Tutte polynomial is defined by the recurrence relation TA=TA∪T−TT [16–18]. Given a matroid n,I, and if X⊂n, the deletion n,X is the matroid with ground set n,X and independent sets J⊂n,X:J∈I. The matroid dual X∗ of X is the matroid on n, where I is a basis of X if Ic is a basis of X∗. If X⊂n, then the contraction can be defined as N/X=N∗╲X∗.Now, letX and Y be matroids on the same ground set E. We say that Y is a quotient of X if one of the following equivalent statements holds:(i)
Every circuit ofX is a union of circuits of Y(ii)
IfX′⊂Y′⊂E, then rMY′−rMX′≥rNY′−rNX′ (r is the rank function; see [15])(iii)
There exists a matroidR and a subset X′ of ER such that X=R,X′ and Y=R/X′(iv)
For all basesB of X and x∈B, there is a basis B0 of Y, with B0⊂B, such that y:B0−y∪x∈BN⊂y:B−y∪x∈BXFor the equivalences, we refer to Proposition 7.3.6 in [22]. If Y is a quotient of X, it follows that(i)
Every basis ofY is contained in a basis of X, and every basis of X contains a basis of Y(ii)
rkY≤rkX and, in case of equality, Y=X. cf. [15] loc. citDefinition 4.
A stratification of a matroidX is a decreasing filtration sequence X=M0⊃X1⊃⋯⊃Xd by submatroids Xj, where we call Xj,Xj+1 the j-th strata of the stratification.The Tutte polynomial ofX becomes the sum of the Tutte polynomials on each of the strata Sj=Xj,Xj+1 (see [16–18]).


### 2.6. Cycle Matroid and the R-Cyclic Graph

LetG,V,E be a graph, V the vertices, and E the edges. Set C as the edge set of cycles in G. Then C is the set of circuits of the matroid MG on E. We call MG the cycle matroid (or graphic matroid) of G. This matroid is simple if G is a simple graph. We will assume in the text that graph G and this matroid are simple; that is, every circuit has at least three vertices. In [8], the Cohen–Macaulayness of the facet ideal of r-cyclic graph Gn,r has been shown. We will present an alternative proof of this fact based on our results in Section 3. First, let us recall the precise definitions of facet ideal and the r-cyclic graph.Definition 5 (see [10]).
Assume thatΔ is a simplicial complex over n vertices labeled v1,…,vn. Let k be a field, let x1,…,xn be indeterminates, and A=kx1,…,xn. We define IFΔ as the ideal of A generated by square-free monomials xi1,…,xis, where vi1,…,vis is a facet of Δ. We call IFΔ the facet ideal of Δ.The so-called Stanley–Reisner ideal is the ideal generated by monomials corresponding to nonfaces of the complexΔ.Definition 6 (see [8]).
LetΔ be a simplicial complex over n. Let IFΔ be the monomial ideal minimally generated by square-free monomials fF1,…,fFs such that(22)fFi=xi1xi2,…,xir⇔Fi=i1,…,iris a facet ofΔ,for alli,is the facet ideal of complex Δ and is denoted by IFΔ. Graph Gn,r has n edges and r distinct cycles. One naturally associates a simplicial complex ΔGn,r=E,ei1,…,eir to Gn,r, where Ci=e11,…,e1i is the i-th cycle [8].The following provides an example of anr-cyclic graph when r=2, together with its facet ideal. In Section 4, we propose applying the criteria of Theorem 6 to r-cyclic graphs. The criteria are more general and can be applied to a wide area of graphs (see the argument after Theorem 13 and its corollary).Example 1.
GraphG in Figure 1 is a 2-cyclic graph with edge set 1,2,…,7. Let M be the cycle matroid of G. The set of circuits of M is ℭM=1,2,5,3,4,7. Let Δ be the broken circuit complex of M with respect to the ordering 7<6<⋯<1. The facet ideal of Δ is IFΔ=x1x2,x3x4.
The theory of matroids and their broken circuit complexes is very much tied with the theory of graphs [23–27]. Assume that G is a simple graph on l vertices. For each positive integer t, let χG,t be the number of colorings of G with t colors. This function is a polynomial, called the chromatic polynomial of G. Let MG be the cycle matroid of G and let < be an ordering of the edge set of G. A classical theorem of Whitney [28] says that(23)χG,t=tl−a1tl−1+a2tl−2−⋯+−1l−1a−1t,where a1,…,ar=f0,…,fr−1 is the f-vector of the broken circuit complex BC<MG (r is the rank of MG) and ai=0 for i>r. One can write χG,t as follows:(24)χG,t=tlπAMG,−t−1,where πAM,t stands for the Poincaré polynomial of the Orlik–Solomon algebra of matroid M [3].Figure 1
A2− cyclic graph with 7 edges.


## 2.1. Linear Resolutions

LetA=Kx1,…,xn be the polynomial ring over an infinite field k and m=x1,…,xn the maximal ideal. A finitely generated graded A-module M is said to have s-linear resolution if the graded minimal free resolution of M is of the form(8)0⟶A−s−pβp⟶⋯⟶A−s−1β1⟶A−sβ0⟶M⟶0.In other words,M has s-linear resolution if βi,i+j=0 for j≠s; a relevant notion is that of s-linear quotient (see [2, 21]).Next, we give some definitions and nomenclature to set the conditions of Theorem1 presented in the following. First, let assume that < is a monomial order on A. Write a nonzero polynomial in A as f=∑vavv, where v∈A is a monomial. The initial monomial of f w.r.t. < is the biggest monomial w.r.t. < among the monomials belonging to suppf. We write in<f for the initial monomial of f with respect to <. The leading coefficient of f is the coefficient of in<f. If I is a nonzero ideal of A, the initial ideal of I w.r.t < is the monomial ideal of A, which is generated by in<f:f∈I. We write in<f for the initial ideal of I. Thus, we are ready to present the following theorem, which characterizes the linear resolution property.Theorem 1 (see [3]).
Assume thatI=⊕kIk is a graded Cohen–Macaulay ideal in A of codimension q and s is the smallest index where Is≠0. The following are equivalent:(i)
I has s-linear resolution(ii)
Ifa1,…,an−q is a maximal A/I-regular sequence of linear forms in A, we have I¯=ms¯ in A/a1,…,an−q(iii)
The Hilbert function ofI has the form HI,s=s+q−1s(iv)
Suppose< is a monomial order on A. If in<I (the initial ideal of I) is Cohen–Macaulay, then in<I has s-linear resolutionNow let us suppose thatI is a graded ideal of A and in<I is Cohen–Macaulay; then from the above theorem, it follows that I has linear resolution if and only if in<I has a linear resolution, cf. [3] loc. cit. A relevant definition is that of linear quotients as follows.Definition 1.
SayM has linear quotient, if there exists a minimal system of generators a1,…,am of M such that the colon ideals,(9)Jl=a1,…,al−1:al,are generated by linear forms of all l.On the other hand, the following result relative to linear quotients is also well known.Theorem 2 (see prop. 8.2.1 in [2]).
Suppose thatI is a graded ideal of A generated in degree s. If I has linear quotients, then it has a s-linear resolution.Another important concept related to linearity isthe componentwise linearity [2]. For that, we consider the following construction. Assume that M=⊕jMj is a finitely generated graded A-module and let F,d=Fn,dn:Fn⟶Fn−1 be the minimal graded free resolution of M. Define subcomplexes(10)Fi≔mi−nFn,dn.The linear part ofF is the complex(11)Flin=⊕iFiFi+1,grid.Also, we have an important definition and theorem regarding the graded moduleM=⊕jMj. These are presented next.Definition 2.
The graded moduleM=⊕jMj is said to be componentwise linear if Ms has linear resolution for all s, whereby definition Ms is the submodule generated by Ms.Theorem 3 (see [5, 13]).
The following are equivalent:(i)
M is componentwise linear(ii)
Mq has a linear resolution for every q(iii)
Flin is acyclicOne can choose a homogeneous basis for theA-graded modules Fi (for all i), so that matrices present the differentials with homogeneous entries. Then, the differential of the complex Flin is obtained by killing all the monomials of degrees bigger than one in the entries. The resulting matrix is called the linearization of differentials.


## 2.2. Broken Circuit Complexes

One can consider the above properties for certain ideals constructed from combinatorial data of a matroid. LetX,< be an ordered simple matroid of rank r on n. The minimal dependent subsets of X are called circuits. Denote by BC<X the broken circuit complex of X, that is, the collection of all subsets of M not containing any broken circuit. It is known that BC<X is an r−1-dimensional shellable complex. The Stanley–Reisner ideal of BC<X denoted by I<X is the ideal generated by all monomials on broken circuits. We denote a broken circuit by bc<C=C,min<C [3]. By definition,(12)I<X=xbc<C≔∏j∈bc<Cxj.The shellability ofBC<X implies that A/I<X is Cohen–Macaulay. Thus, the following theorem characterizes the linear resolution of the ideal I<X.Theorem 4 (see [3]).
The following are equivalent:(i)
I<X has s-linear resolution(ii)
X=Us,n−r+s⊕Ur−s,r−s(iii)
All powers ofI<X have linear resolutionsThe matroidUp,n is the uniform matroid on the n-element, whose independent sets are subsets having at most p elements. Up,n has rank p and its circuits have p+1 elements. In particular, Un,n has no dependent sets and is called free. The proof of Theorem 4 uses Theorem 7.5.2 of [4] on an external bound for the f-vectors; refer to [3]. For the sake of completeness, we briefly recall this fact from [4] in the following theorem.Theorem 5 (see [4]).
Let us consider the following:(1)
LetΔ be an r−1 dimensional shellable complex on the vector set S of size S=n. If, for some s∈ℕ, all s-element subsets of S belong to Δ, then the inequality,(13)fk−1≥∑i=0s−1n−r+i−1ir−ik−i,k=0,…,r,holds for thef-vector.(2)
Assume thatΔ=InX is the complex of independent subsets of a loopless matroid. Then, inequality (13) holds for fk replaced with Ik, the number of independent k-element subsets of X. The equality holds if and only if(14)X=Us,n−r+s⊕Ur−s,r−s,s+1=minC;Cis a circuit.We sketch some explanations related to the above theorem inspired from [4]. The condition that all s-element subsets of S are in Δ implies that fk=nk,k=0,1,2,3,…,s. By using formal combinatorial identities,(15)hk=∑i=0k−1i+kr−ik−ini=n−r+k−1k,k≤s.Therefore, the inequality in (13) follows by singling out the first s+1 terms in(16)fk=∑i=0khir−ik−i,k=1,…,r.In caseΔ=InX, let bX=Ir; then bX=n−r+ss is the number of bases of X. The h-vector is given by(17)h¯=1,n−r,…,n−r+s−1s,and the Tutte polynomial of X is(18)TXx,1=hΔx=xr+n−rxr−1+⋯+n−r+s−2s−1xr−s.The form of the Tutte polynomial shows thatX has exactly n−r+s coloops. This forces X=N⊕Ur−s,r−s where N is a matroid of rank s on n−r+s points. Now bN=bX=n−r+ss. This forces that N=Us,n−r+s. The equality in (13) holds, if hc=hc+1=⋯=0, cf. [4] loc. cit.


## 2.3. Complete Intersection Property

Later, in Section4, we need to decide whether a graded ideal is a complete intersection. For that, in this subsection, we present some definitions from commutative algebra. For a commutative Noetherian local ring A, the depth of A (the maximum length of a regular sequence in the maximal ideal of A) is at most the Krull dimension of A. The ring A is called Cohen–Macaulay if its depth is equal to its dimension. A regular sequence is a sequence a1,…,an of elements of m such that, for all i, element ai is not a zero divisor in A/a1,…,an. A local ring A is a Cohen–Macaulay ring if there exists a regular sequence a1,…,an such that the quotient ring A/a1,…,an is Artinian. In that case, n=dimA. More generally, a commutative ring is called Cohen–Macaulay if it is Noetherian, and all of its localizations at prime ideals are Cohen–Macaulay. Besides, we say that a ring A is a complete intersection if there exists some surjection R⟶A, with R a regular local ring, such that a regular sequence generates the kernel. Our goal is to identify the complete intersection property for the Stanley–Reisner ideal of broken circuit ideals of matroids. For that, let us present some definitions next.Let us assume thatX,< is an ordered matroid on n, and CX is the set of broken circuits of X. Let I<X be the Stanley–Reisner ideal of the broken circuit complex BC<X. A subset D∈CX is called generating set if xbc<C;C∈D generates I<X. It is clear from definition that D is a generating set of CX if bc<C for C∈D containing minimal broken circuits of X. Denote by LD the intersection graph of D; that is, the vertex set of LD is D and the edges are pairs C,C′ such that C∩C′=∅. Say D is simple if whenever C,C′∈D, either C∩C′=min<Cormin<C′; otherwise, C∩C′=∅.Theorem 6 (see [3]).
AssumeX,< is a simple ordered matroid The following are equivalent:(i)
I<X is complete intersection(ii)
The minimal broken circuits ofX are pairwise disjoint(iii)
There exists a simple subsetD⊂CX such that CX=LD′;D′⊂DTheorem6 gives concrete combinatorial criteria to check the entire intersection property of Stanley–Reisner ideal of broken circuit complex of matroids. It can also be applied to graph matroids; see [3].


## 2.4. Hyperplane Arrangements

To an arrangement of hyperplanesA, one naturally associates a matroid denoted by X=XA with the ground set to be the same as A and the independent sets to be the independent hyperplanes in A; that is, those whose corresponding reflections as said above are independent. Assume that the matroid XA is associated with an essential central hyperplane arrangement of n hyperplanes A=H1,…,Hn in a vector space V of dimension r over the infinite field k. When k=ℂ, the integral cohomology of the complement V,∪iHi is isomorphic to the Orlik–Solomon algebra of AA, which is the quotient of standard graded exterior algebra on ℂe1,…,en by the Orlik–Solomon ideal JA generated by the elements(19)∂ei1,…,ip=∑r−1r−1ei1,…,eir^,…,eip,when Hi1,…,Hip are dependent subsets of A; that is, the reflections αij through Hij are independent. Therefore,(20)AA=AJA=∧ℤe1,…,en∂ei1,…,ip=H∗V,∪iHi,ℤ.The Orlik–Terao algebra is a commutative analogue of Orlik–Solomon algebra. That is, instead of exterior algebra onn vectors, we work on A=kx1,…,xn and whenever we have a relation ∑jajαij=0, we assume a relation r=∑jajαij in a relation space FA. The Orlik–Terao ideal is generated by(21)∂r=∑j−1j−1ajxi1,…,xij^,…,xip⇐r=∑jajαij.The quotientCA=A/IA is called the Orlik–Terao algebra of the hyperplane arrangement. The Orlik–Solomon algebras and Orlik–Terao algebras of hyperplane arrangements are related to each other by an idea of deformation [2]. A relevant notion in this context is that of a Koszul algebra defined next.Definition 3 (see [3]).
Suppose thatL is either an exterior or a polynomial algebra over a field k. A graded algebra B=L/I is called Koszul if k has linear resolution over B.The characterization of the Koszulness of the Orlik–Solomon algebra of hyperplane arrangement is one of the essential questions in this area. In this regard, we mention the following theorem.Theorem 7 (see [3]).
LetA be an essential central arrangement of n hyperplanes in dimension r, and assume that IA is complete intersection. Then the following are equivalent:(1)
AA is Koszul(2)
CA is Koszul(3)
XA=U2,n−r+2⊕Ur−2,r−2(4)
A=A1×A2 where A1 is generic central arrangement of n−r+2 hyperplanes in dimension p and A2 is Boolean in dimension r−2(5)
IA has 2-linear resolution(6)
JA has 2-linear resolutionIt is well known that ifB is Koszul, then I is generated by quadrics. Unfortunately, the converse is not true in general. The following consequence is immediate from the above theorem.Theorem 8 (see [3]).
The Orlik–Terao idealIA of an essential central arrangement has 2-linear resolution if A is obtained by successively coning a central arrangement of lines in the plane. In this case, the Orlik–Terao algebra is Koszul.


## 2.5. Basic Operations on Matroids

Assume thatX is a matroid with an element set E and that S is a subset of E. The restriction of X to S, written as X|S, is the matroid on set S whose independent sets are the independent sets of X that are contained in S. Its circuits are the circuits of X contained in S, and its rank function is that of X restricted to subsets of S. In linear algebra, this corresponds to restricting to the subspace generated by the vectors in S. If T=X−S, this is equivalent to the deletion of T, written as X,T. The submatroids of X are precisely the results of a sequence of deletions (the order is irrelevant). The dual operation of restriction is contraction. If T is a subset of E, the contraction of X by T, written as X/T, is the matroid on the underlying set E−T whose rank function is r′A=rA∪T−rT. In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in T, together with the images of the vectors in E−T. Then, the Tutte polynomial is defined by the recurrence relation TA=TA∪T−TT [16–18]. Given a matroid n,I, and if X⊂n, the deletion n,X is the matroid with ground set n,X and independent sets J⊂n,X:J∈I. The matroid dual X∗ of X is the matroid on n, where I is a basis of X if Ic is a basis of X∗. If X⊂n, then the contraction can be defined as N/X=N∗╲X∗.Now, letX and Y be matroids on the same ground set E. We say that Y is a quotient of X if one of the following equivalent statements holds:(i)
Every circuit ofX is a union of circuits of Y(ii)
IfX′⊂Y′⊂E, then rMY′−rMX′≥rNY′−rNX′ (r is the rank function; see [15])(iii)
There exists a matroidR and a subset X′ of ER such that X=R,X′ and Y=R/X′(iv)
For all basesB of X and x∈B, there is a basis B0 of Y, with B0⊂B, such that y:B0−y∪x∈BN⊂y:B−y∪x∈BXFor the equivalences, we refer to Proposition 7.3.6 in [22]. If Y is a quotient of X, it follows that(i)
Every basis ofY is contained in a basis of X, and every basis of X contains a basis of Y(ii)
rkY≤rkX and, in case of equality, Y=X. cf. [15] loc. citDefinition 4.
A stratification of a matroidX is a decreasing filtration sequence X=M0⊃X1⊃⋯⊃Xd by submatroids Xj, where we call Xj,Xj+1 the j-th strata of the stratification.The Tutte polynomial ofX becomes the sum of the Tutte polynomials on each of the strata Sj=Xj,Xj+1 (see [16–18]).


## 2.6. Cycle Matroid and the R-Cyclic Graph

LetG,V,E be a graph, V the vertices, and E the edges. Set C as the edge set of cycles in G. Then C is the set of circuits of the matroid MG on E. We call MG the cycle matroid (or graphic matroid) of G. This matroid is simple if G is a simple graph. We will assume in the text that graph G and this matroid are simple; that is, every circuit has at least three vertices. In [8], the Cohen–Macaulayness of the facet ideal of r-cyclic graph Gn,r has been shown. We will present an alternative proof of this fact based on our results in Section 3. First, let us recall the precise definitions of facet ideal and the r-cyclic graph.Definition 5 (see [10]).
Assume thatΔ is a simplicial complex over n vertices labeled v1,…,vn. Let k be a field, let x1,…,xn be indeterminates, and A=kx1,…,xn. We define IFΔ as the ideal of A generated by square-free monomials xi1,…,xis, where vi1,…,vis is a facet of Δ. We call IFΔ the facet ideal of Δ.The so-called Stanley–Reisner ideal is the ideal generated by monomials corresponding to nonfaces of the complexΔ.Definition 6 (see [8]).
LetΔ be a simplicial complex over n. Let IFΔ be the monomial ideal minimally generated by square-free monomials fF1,…,fFs such that(22)fFi=xi1xi2,…,xir⇔Fi=i1,…,iris a facet ofΔ,for alli,is the facet ideal of complex Δ and is denoted by IFΔ. Graph Gn,r has n edges and r distinct cycles. One naturally associates a simplicial complex ΔGn,r=E,ei1,…,eir to Gn,r, where Ci=e11,…,e1i is the i-th cycle [8].The following provides an example of anr-cyclic graph when r=2, together with its facet ideal. In Section 4, we propose applying the criteria of Theorem 6 to r-cyclic graphs. The criteria are more general and can be applied to a wide area of graphs (see the argument after Theorem 13 and its corollary).Example 1.
GraphG in Figure 1 is a 2-cyclic graph with edge set 1,2,…,7. Let M be the cycle matroid of G. The set of circuits of M is ℭM=1,2,5,3,4,7. Let Δ be the broken circuit complex of M with respect to the ordering 7<6<⋯<1. The facet ideal of Δ is IFΔ=x1x2,x3x4.
The theory of matroids and their broken circuit complexes is very much tied with the theory of graphs [23–27]. Assume that G is a simple graph on l vertices. For each positive integer t, let χG,t be the number of colorings of G with t colors. This function is a polynomial, called the chromatic polynomial of G. Let MG be the cycle matroid of G and let < be an ordering of the edge set of G. A classical theorem of Whitney [28] says that(23)χG,t=tl−a1tl−1+a2tl−2−⋯+−1l−1a−1t,where a1,…,ar=f0,…,fr−1 is the f-vector of the broken circuit complex BC<MG (r is the rank of MG) and ai=0 for i>r. One can write χG,t as follows:(24)χG,t=tlπAMG,−t−1,where πAM,t stands for the Poincaré polynomial of the Orlik–Solomon algebra of matroid M [3].Figure 1
A2− cyclic graph with 7 edges.


## 3. Main Results

In this section, we extend some main results presented in [3] to the corresponding graded notions. All the definitions and theorems in this section are new results. We prove three kinds of results: (a) The first is the definition of the graded linearity and graded linear quotient property. We compare the two notions of graded linearity and graded linear quotients on graded A-modules, and then we also compare graded linearity with componentwise linearity. (b) The second is to identify the graded linearity of the Stanley–Reisner ring of broken circuit complexes in terms of the Hilbert polynomial. (c) The third is a stratified decomposition property of the matroid when the Stanley–Reisner ideal of broken circuit complex has graded linear resolution.


### 3.1. Graded Linear Resolutions

We introduce the two following definitions. Next, we prove a theorem that compares the two definitions.Definition 7.
We say thatM has graded linear quotient, if there exists a minimal system of generators a1,…,am of M such that the colon ideals satisfy in degJl=1 (we call the least degree of a homogeneous generator of a graded A-module M the initial degree of M, denoted by in degM).Definition 8.
Say thatM has graded linear resolution if the graded Betti numbers in the graded Betti table appear in a finite number of horizontal lines, with finitely many nonzero entries in each line and successively.An example of having graded linear resolution is that of having linear resolution. However, the graded linearity is more general. We stress that having linear property for the graded modules under consideration is a strictly special case. Then, we present our next main result.Theorem 9 (main result).
Assume thatM is a graded A-module minimally generated by a regular sequence a1,…,an in m; and Jl is defined as in Definition 1. If M has graded linear quotients, then Jl has graded linear resolution for any l.Proof.
We use induction onl. Consider the short exact sequence:(25)0⟶AJl:zl+1⟶×zl+1AJl⟶AJl+1⟶0.
The first and the last modules have quasi-linear resolutions by induction assumption. Now, consider the associated long graded Tor exact sequence:(26)⟶ToriAJl:zl+1,kj⟶×zl+1ToriAJl,kj+d⟶ToriAJl+1,kj+d⟶Tori−1AJl:zl+1,kj+d−1⟶×zl+1Tori−1AJl,kj+d−1⟶,where d=degal+1. One notes that multiplication by zl+1 is in the annihilator of k. This implies that the sequence,(27)0⟶ToriAJl,kj+d⟶ToriAJl+1,kj+d⟶Tori−1AJl:al+1,kj+d−1⟶0,is short exact. We note that ToriA/Jl,kj+d embeds into ToriA/Jl+1,kj+d. Therefore, the nontriviality of the first one implies the nontriviality of the second. Therefore, in order to check the induction step, it suffices to prove(28)ToriAJl+1,kj+d≠0⇔Tori−1AJl:al+1,kj+d−1≠0.
The last assertion is true for the implication(29)Tori−1AJl:al+1,kj+d−1=0⇒ToriAJl,kj+d=0.
Now, the assertion follows by induction, and the proof is complete.In the following theorem, we compare the graded linearity with the componentwise linearity defined in the previous section. As a result, the graded linear property is weaker than componentwise linearity. Therefore, our definition can be regarded as a more general approximation to the concept of componentwise linear resolution.Theorem 10 (main result).
Assume thatM is a finitely generated graded A-module. Consider the following statements:(1)
M has graded linear resolution(2)
Ms have graded linear resolutions for all s(3)
M is componentwise linear
Then, we have3⇒2⇔1.Proof.
The implications3⇒2⇒1 are evident by Theorem 3. Therefore, we check out 1⇒2. This follows from the fact that a graded resolution of Ms can be included (is a subresolution) in a graded resolution of M.


### 3.2. Graded Linearity and Broken Circuit Complexes

We want to characterize the graded linear resolution property for the Stanley–Reisner rings of broken circuit complexes. The following result generalizes Theorem4 presented in the previous section and conforms to part of our main results.Theorem 11.
LetX,< be an ordered simple matroid of rank r on n. The following are equivalent:(1)
I<X has graded linear resolution.(2)
Ifa1,…,an−q is a maximal A/I<X-regular sequence of linear forms in A, we have(30)A¯I<X¯=⊕i=0dm¯sim¯si+1,inA/a1,…,an−s.(3)
The Hilbert function ofI<X has the form(31)HAI<X,s=c0s+q−1s+c1s+q−2s+⋯+cd−1s+q−ds,for somed.(4)
If≺ is a monomial order on A and if in≺I<X is Cohen–Macaulay, in≺I<X has graded linear resolution.Proof.
(3) follows from (2), and also (4) follows from (3) and the equality of the Hilbert functions(32)HAI<X,s=HAI<X¯,s,where the bar means the image in A/a1,…,an−q. Also, one has the stronger statement(33)HAI<X,s=HAI<X¯,s≤H⊕i=0dm¯sim¯si+1,s=∑i=0d−1cis+q−i−1s,with equality when (30) holds. In fact, by factoring out the regular sequence a1,…,an−q, one can assume that A is Artinian. Then, it is easy to establish that it has the form in (30) (see also [3], Proposition 3.1). This also proves (2).Remark 1.
The coefficientsci=ciI<X can be easily calculated (called Hilbert coefficient of I<X). The sum in the Hilbert polynomial is the sum of the Hilbert functions of all summands where calculation can be by hand.The following lemma is a generalization of Proposition 7.5.2 in [4] and forms part of our main result.Lemma 1.
Assume thatX is a rank r loopless matroid on n such that the Stanley–Reisner ideal of the broken circuits of X has graded linear resolution. Then,(34)Ij−1≥∑i=0c−1∑l=1dclSn−r+l−1lr−ij−i,and the equality holds if and only if there exists a stratification X=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that, on each stratum,(35)Xj╲Xj+1=Urj−sj,rj−sj⊕Usj,nj−rj+sj,where sj≤rj are positive integers and Ul,k denotes the uniform matroid. Also, we have n=∑jnj,r=∑jrj.Proof.
Following the argument of Theorem5 of the previous section (or Theorem 7.2.5 in [4]) and letting Δ=InX, we have(36)hk=HAI<X,k=∑lclk+q−l−1k,k=0,1,2,…,c−1,where cl are Hilbert coefficients of I<X. Then,(37)bX=∑lclq−l+pp,is the number of bases of X. Besides, the h-vector is given by(38)h¯=1,∑lclq−l1,…,∑lclc−1+q−l−1c−1,and the Tutte polynomial of X is TXx,1=hΔx=xr+h1xr−1+⋯+hpxr−p. The form of the Tutte polynomial shows the existence of stratification X=X0⊃X1⊃⋯⊃Xd by submatroids Xj such that(39)Xj╲Xj+1=Urj−sj,rj−sj⊕Nj,holds, where Nj is a matroid of rank sj on nj−rj+sj points. In fact, the h¯-vector of submatroids Xj is given by the truncations of the sums appearing in the h¯-vector of X. Thus,(40)bNj=bXj╲Xj+1=cjc−j+q−lc−1,holds, and this shows that Nj has the desired form. The equality in (34) holds when hc=hc+1=⋯=0.We can now formulate the graded linearity of the Stanley–Reisner ideal of the broken circuits in terms of the combinatorics ofM. Theorem 11 and the Lemma 1 can be used together to obtain the following decomposition property, expressed in the following result.Theorem 12 (main result).
LetX,< be an ordered simple matroid of rank r on n, and let I<X be the Stanley–Reisner ideal of broken circuit complex of X. Then, the following are equivalent:(1)
I<X has graded linear resolution.(2)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd for some d such that, on each stratum,(41)Xj╲Xj+1=Urj−sj,rj−sj⊕Usj,nj−rj+sj,holds, wheresj≤rj are positive integers. Besides, we have n=∑jnj,r=∑jrj.Proof.
We first show that2⇒1. First, assume that (2) holds. Then, by rearrangement of variables, we can assume that(42)I<X=xj1,…,xjs1,…,xl1,…,xlp|j1<⋯<js1<n−r+s1,…,l1<⋯<lp<n−r+p.
This ideal has graded linear resolution.
Next, we show1⇒2. For that, let us assume that (1) holds; that is, assume that I<X has graded linear resolution. Then, according to properties (2) and (3) of Theorem 11, if a=a1,…,ar is a maximal S/I<X-regular sequence of linear forms, then(43)S=AI<X+a=⊕j=0dm¯sjm¯sj+1,m0=A.
Thus, the Hilbert function ofA/I<X is given by(44)HAI<X,t=HS,t∏i1−tsi.
So thef-vector of Stanley–Reisner ring is given by(45)fj−1=∑i=0rcir−ij−i=∑i=0r∑l=1dcln−r+l−1lr−ij−i,where d=degHS,t and cl=clS are the coefficients of HS,t. Thus, Lemma 1 implies the decomposition in item (2).Remark 2.
We highlight three main points:(i)
There are modules over the polynomial ring which are not componentwise linear but satisfy the conditions for being graded linear. A simple example is a direct sum of a noncomponentwise linear module with one componentwise linear module, where the resolutions are just direct sums of the two resolutions of the modules. Being “graded linear” is a relatively weak property compared to being componentwise linear.(ii)
LetX be the graphic matroid of parallel connection of a 3-circuit with a 4-circuit. Then, X is a nonuniform 2-connected matroid and therefore cannot be a direct sum of uniform matroids. We can order the elements of X from 1 to 6 in a way that the Stanley–Reisner ideal of the broken circuit complex of M gets equal to IX=x5x6,x2x3x6,x2x3x4x5. Then, IX has a linear quotient and is, therefore, componentwise linear. This example shows that the stratification mentioned in the above theorem is essential.(iii)
There exist componentwise (matroidal) ideals, which are not generated by the regular sequence. For instance, letM be the same as the previous item, the parallel connection of a 3-circuit and a 4-circuit; then IX is componentwise linear and has linear quotients, but a regular sequence does not generate it.


## 3.1. Graded Linear Resolutions

We introduce the two following definitions. Next, we prove a theorem that compares the two definitions.Definition 7.
We say thatM has graded linear quotient, if there exists a minimal system of generators a1,…,am of M such that the colon ideals satisfy in degJl=1 (we call the least degree of a homogeneous generator of a graded A-module M the initial degree of M, denoted by in degM).Definition 8.
Say thatM has graded linear resolution if the graded Betti numbers in the graded Betti table appear in a finite number of horizontal lines, with finitely many nonzero entries in each line and successively.An example of having graded linear resolution is that of having linear resolution. However, the graded linearity is more general. We stress that having linear property for the graded modules under consideration is a strictly special case. Then, we present our next main result.Theorem 9 (main result).
Assume thatM is a graded A-module minimally generated by a regular sequence a1,…,an in m; and Jl is defined as in Definition 1. If M has graded linear quotients, then Jl has graded linear resolution for any l.Proof.
We use induction onl. Consider the short exact sequence:(25)0⟶AJl:zl+1⟶×zl+1AJl⟶AJl+1⟶0.
The first and the last modules have quasi-linear resolutions by induction assumption. Now, consider the associated long graded Tor exact sequence:(26)⟶ToriAJl:zl+1,kj⟶×zl+1ToriAJl,kj+d⟶ToriAJl+1,kj+d⟶Tori−1AJl:zl+1,kj+d−1⟶×zl+1Tori−1AJl,kj+d−1⟶,where d=degal+1. One notes that multiplication by zl+1 is in the annihilator of k. This implies that the sequence,(27)0⟶ToriAJl,kj+d⟶ToriAJl+1,kj+d⟶Tori−1AJl:al+1,kj+d−1⟶0,is short exact. We note that ToriA/Jl,kj+d embeds into ToriA/Jl+1,kj+d. Therefore, the nontriviality of the first one implies the nontriviality of the second. Therefore, in order to check the induction step, it suffices to prove(28)ToriAJl+1,kj+d≠0⇔Tori−1AJl:al+1,kj+d−1≠0.
The last assertion is true for the implication(29)Tori−1AJl:al+1,kj+d−1=0⇒ToriAJl,kj+d=0.
Now, the assertion follows by induction, and the proof is complete.In the following theorem, we compare the graded linearity with the componentwise linearity defined in the previous section. As a result, the graded linear property is weaker than componentwise linearity. Therefore, our definition can be regarded as a more general approximation to the concept of componentwise linear resolution.Theorem 10 (main result).
Assume thatM is a finitely generated graded A-module. Consider the following statements:(1)
M has graded linear resolution(2)
Ms have graded linear resolutions for all s(3)
M is componentwise linear
Then, we have3⇒2⇔1.Proof.
The implications3⇒2⇒1 are evident by Theorem 3. Therefore, we check out 1⇒2. This follows from the fact that a graded resolution of Ms can be included (is a subresolution) in a graded resolution of M.


## 3.2. Graded Linearity and Broken Circuit Complexes

We want to characterize the graded linear resolution property for the Stanley–Reisner rings of broken circuit complexes. The following result generalizes Theorem4 presented in the previous section and conforms to part of our main results.Theorem 11.
LetX,< be an ordered simple matroid of rank r on n. The following are equivalent:(1)
I<X has graded linear resolution.(2)
Ifa1,…,an−q is a maximal A/I<X-regular sequence of linear forms in A, we have(30)A¯I<X¯=⊕i=0dm¯sim¯si+1,inA/a1,…,an−s.(3)
The Hilbert function ofI<X has the form(31)HAI<X,s=c0s+q−1s+c1s+q−2s+⋯+cd−1s+q−ds,for somed.(4)
If≺ is a monomial order on A and if in≺I<X is Cohen–Macaulay, in≺I<X has graded linear resolution.Proof.
(3) follows from (2), and also (4) follows from (3) and the equality of the Hilbert functions(32)HAI<X,s=HAI<X¯,s,where the bar means the image in A/a1,…,an−q. Also, one has the stronger statement(33)HAI<X,s=HAI<X¯,s≤H⊕i=0dm¯sim¯si+1,s=∑i=0d−1cis+q−i−1s,with equality when (30) holds. In fact, by factoring out the regular sequence a1,…,an−q, one can assume that A is Artinian. Then, it is easy to establish that it has the form in (30) (see also [3], Proposition 3.1). This also proves (2).Remark 1.
The coefficientsci=ciI<X can be easily calculated (called Hilbert coefficient of I<X). The sum in the Hilbert polynomial is the sum of the Hilbert functions of all summands where calculation can be by hand.The following lemma is a generalization of Proposition 7.5.2 in [4] and forms part of our main result.Lemma 1.
Assume thatX is a rank r loopless matroid on n such that the Stanley–Reisner ideal of the broken circuits of X has graded linear resolution. Then,(34)Ij−1≥∑i=0c−1∑l=1dclSn−r+l−1lr−ij−i,and the equality holds if and only if there exists a stratification X=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that, on each stratum,(35)Xj╲Xj+1=Urj−sj,rj−sj⊕Usj,nj−rj+sj,where sj≤rj are positive integers and Ul,k denotes the uniform matroid. Also, we have n=∑jnj,r=∑jrj.Proof.
Following the argument of Theorem5 of the previous section (or Theorem 7.2.5 in [4]) and letting Δ=InX, we have(36)hk=HAI<X,k=∑lclk+q−l−1k,k=0,1,2,…,c−1,where cl are Hilbert coefficients of I<X. Then,(37)bX=∑lclq−l+pp,is the number of bases of X. Besides, the h-vector is given by(38)h¯=1,∑lclq−l1,…,∑lclc−1+q−l−1c−1,and the Tutte polynomial of X is TXx,1=hΔx=xr+h1xr−1+⋯+hpxr−p. The form of the Tutte polynomial shows the existence of stratification X=X0⊃X1⊃⋯⊃Xd by submatroids Xj such that(39)Xj╲Xj+1=Urj−sj,rj−sj⊕Nj,holds, where Nj is a matroid of rank sj on nj−rj+sj points. In fact, the h¯-vector of submatroids Xj is given by the truncations of the sums appearing in the h¯-vector of X. Thus,(40)bNj=bXj╲Xj+1=cjc−j+q−lc−1,holds, and this shows that Nj has the desired form. The equality in (34) holds when hc=hc+1=⋯=0.We can now formulate the graded linearity of the Stanley–Reisner ideal of the broken circuits in terms of the combinatorics ofM. Theorem 11 and the Lemma 1 can be used together to obtain the following decomposition property, expressed in the following result.Theorem 12 (main result).
LetX,< be an ordered simple matroid of rank r on n, and let I<X be the Stanley–Reisner ideal of broken circuit complex of X. Then, the following are equivalent:(1)
I<X has graded linear resolution.(2)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd for some d such that, on each stratum,(41)Xj╲Xj+1=Urj−sj,rj−sj⊕Usj,nj−rj+sj,holds, wheresj≤rj are positive integers. Besides, we have n=∑jnj,r=∑jrj.Proof.
We first show that2⇒1. First, assume that (2) holds. Then, by rearrangement of variables, we can assume that(42)I<X=xj1,…,xjs1,…,xl1,…,xlp|j1<⋯<js1<n−r+s1,…,l1<⋯<lp<n−r+p.
This ideal has graded linear resolution.
Next, we show1⇒2. For that, let us assume that (1) holds; that is, assume that I<X has graded linear resolution. Then, according to properties (2) and (3) of Theorem 11, if a=a1,…,ar is a maximal S/I<X-regular sequence of linear forms, then(43)S=AI<X+a=⊕j=0dm¯sjm¯sj+1,m0=A.
Thus, the Hilbert function ofA/I<X is given by(44)HAI<X,t=HS,t∏i1−tsi.
So thef-vector of Stanley–Reisner ring is given by(45)fj−1=∑i=0rcir−ij−i=∑i=0r∑l=1dcln−r+l−1lr−ij−i,where d=degHS,t and cl=clS are the coefficients of HS,t. Thus, Lemma 1 implies the decomposition in item (2).Remark 2.
We highlight three main points:(i)
There are modules over the polynomial ring which are not componentwise linear but satisfy the conditions for being graded linear. A simple example is a direct sum of a noncomponentwise linear module with one componentwise linear module, where the resolutions are just direct sums of the two resolutions of the modules. Being “graded linear” is a relatively weak property compared to being componentwise linear.(ii)
LetX be the graphic matroid of parallel connection of a 3-circuit with a 4-circuit. Then, X is a nonuniform 2-connected matroid and therefore cannot be a direct sum of uniform matroids. We can order the elements of X from 1 to 6 in a way that the Stanley–Reisner ideal of the broken circuit complex of M gets equal to IX=x5x6,x2x3x6,x2x3x4x5. Then, IX has a linear quotient and is, therefore, componentwise linear. This example shows that the stratification mentioned in the above theorem is essential.(iii)
There exist componentwise (matroidal) ideals, which are not generated by the regular sequence. For instance, letM be the same as the previous item, the parallel connection of a 3-circuit and a 4-circuit; then IX is componentwise linear and has linear quotients, but a regular sequence does not generate it.


## 4. Applications

This section applies the results of the previous section to the Orlik–Solomon ideal and the Orlik–Terao ideal of the arrangements of hyperplanes. Our results are direct interpretations of the theorems presented in Section3 but into the language of hyperplane arrangements. All the definitions and theorems of this section are new contributions to this text.


### 4.1. Application to Hyperplane Arrangements

We begin by the following theorem.Theorem 13.
For an essential central arrangement ofA of n hyperplanes, located in a vector space of dimension r, the following points are equivalent:(i)
IA has graded linear resolution.(ii)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that XjA╲Xj+1A=Urj−sj,rj−sj⊕Usj,nj−rj+sj, where sj≤rj are positive integers. Also, we have n=∑jnj,r=∑jrj.(iii)
A=A1×A2×⋯×Ak, where A1 is Boolean and the other factors Aj for j>1 are generic arrangements of nj−rj+sj hyperplanes in an sj-dimensional vector space.Proof.
The proof is analogous to the 2-decomposition case in [3] and is just an interpretation of the theorems in the previous section.In the following, we generalize the Koszul property to that of graded Koszul in a natural way. First, consider the following definition.Definition 9.
In the settings of Definition3, we call B graded Koszul if k has graded linear resolution.The following consequence is immediate from the above theorem.Theorem 14.
The Orlik–Terao idealIA has 2-graded linear resolution if A is obtained by successively coning central arrangements of lines in the plane. In this case, the Orlik–Terao algebra is graded Koszul.Proof.
The proof is a direct application of Theorem13.Theorem 15.
With the same setup of Theorem13, the following are equivalent:(1)
AA is graded Koszul.(2)
CA is graded Koszul.(3)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that XjA╲Xj+1A=Urj−sj,rj−sj⊕Usj,nj−rj+tj, where sj≤rj are positive integers. Also, we have n=∑jnj,r=∑jrj.(4)
A=A1×A2×⋯×Ak, where A1 is Boolean and the other factors Aj for j>1 are generic arrangement of nj−rj+sj hyperplanes in an sj-dimensional vector space.(5)
IA has 2-graded linear resolution.(6)
JA has 2-graded linear resolution.Proof.
The equivalence of (2)–(5) was already established above. The equivalence of (1)-(2) follows from Theorem13 and the argument in Theorem 12.The characterization of the Koszul property of Orlik–Solomon algebras of matroids (arrangements) is one of the essential problems in this area. It is a conjecture that a matroid (an arrangement) is supersolvable if and only if its Orlik–Solomon algebra is Koszul (see, e.g., [3, 5]).


### 4.2. Application on the Facet Ideal of ther-Cyclic Graph

Our last result is an application to prove the entire intersection property of the facet ideal of ther-cyclic graph (see Subsection 2.6).Proposition 1.
The facet idealIFΔGn,r is a complete intersection.Proof.
By definition,Gn,r is a graph on n edges with exactly r distinct cycles. Therefore, the broken circuits of the cycle matroid XGn,r are pairwise disjoint. On the other hand, the Stanley–Reisner ideal of the broken circuit complex of cycle matroid XGn,r is exactly the facet ideal of the complex ΔGn,r. Now, the theorem follows from Theorem 6.Corollary 1.
The facet idealIFΔGn,r is Cohen–Macaulay.The corollary has been proved in [8] by a direct computational method. We proved it as an immediate consequence of our result. A comprehensive analysis of the entire intersection property for graph matroids related to broken circuits is given in [3].Example 2.
LetG be the 2-cyclic graph in Figure 1, with the given numbering of the edges. Let M=MG be the cycle matroid of G. Consider, say, the ordering 7<6<⋯<1. Let Δ be the broken circuit complex of M. In this case, the minimal broken circuits of M are 1,2,3,4, and the ideal,(46)I<M=x1x2,x3x4=IFΔ,is a complete intersection.Theorem6 characterizes the entire intersection property in terms of the set of circuits. So the Stanley–Reisner ideal of the broken circuit complex of those ordered matroids whose minimal broken circuits are pairwise disjoint satisfies the entire intersection property. This result is applied to triangulations of simple polygons to show that the cycle matroid of such a graph admits a broken circuit complex with disjoint minimal broken circuits. Regarding the cycle matroids associated with arbitrary triangulation of simple polygons, the criteria which are given in Theorem 6 on complete intersection property always can be achieved by choosing a suitable ordering of the edges. That is, there always exists an ordering < of the edges of G such that the minimal broken circuits of the ordered matroid MG,< are pairwise disjoint (see Corollary 4.8 in [3]). The following conjecture was presented in [20].Conjecture 1 (see [3, 20]).
A matroid (an arrangement) is supersolvable if and only if its Orlik–Solomon algebra is Koszul.Conjecture1 holds for matroids whose minimal broken circuits are pairwise disjoint (cf. [3], Sec. 4). In conclusion, the above conjecture holds for the cycle matroid of an r-cyclic graph.


## 4.1. Application to Hyperplane Arrangements

We begin by the following theorem.Theorem 13.
For an essential central arrangement ofA of n hyperplanes, located in a vector space of dimension r, the following points are equivalent:(i)
IA has graded linear resolution.(ii)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that XjA╲Xj+1A=Urj−sj,rj−sj⊕Usj,nj−rj+sj, where sj≤rj are positive integers. Also, we have n=∑jnj,r=∑jrj.(iii)
A=A1×A2×⋯×Ak, where A1 is Boolean and the other factors Aj for j>1 are generic arrangements of nj−rj+sj hyperplanes in an sj-dimensional vector space.Proof.
The proof is analogous to the 2-decomposition case in [3] and is just an interpretation of the theorems in the previous section.In the following, we generalize the Koszul property to that of graded Koszul in a natural way. First, consider the following definition.Definition 9.
In the settings of Definition3, we call B graded Koszul if k has graded linear resolution.The following consequence is immediate from the above theorem.Theorem 14.
The Orlik–Terao idealIA has 2-graded linear resolution if A is obtained by successively coning central arrangements of lines in the plane. In this case, the Orlik–Terao algebra is graded Koszul.Proof.
The proof is a direct application of Theorem13.Theorem 15.
With the same setup of Theorem13, the following are equivalent:(1)
AA is graded Koszul.(2)
CA is graded Koszul.(3)
There exists a stratificationX=X0⊃X1⊃⋯⊃Xd by submatroids Xj for some d such that XjA╲Xj+1A=Urj−sj,rj−sj⊕Usj,nj−rj+tj, where sj≤rj are positive integers. Also, we have n=∑jnj,r=∑jrj.(4)
A=A1×A2×⋯×Ak, where A1 is Boolean and the other factors Aj for j>1 are generic arrangement of nj−rj+sj hyperplanes in an sj-dimensional vector space.(5)
IA has 2-graded linear resolution.(6)
JA has 2-graded linear resolution.Proof.
The equivalence of (2)–(5) was already established above. The equivalence of (1)-(2) follows from Theorem13 and the argument in Theorem 12.The characterization of the Koszul property of Orlik–Solomon algebras of matroids (arrangements) is one of the essential problems in this area. It is a conjecture that a matroid (an arrangement) is supersolvable if and only if its Orlik–Solomon algebra is Koszul (see, e.g., [3, 5]).


## 4.2. Application on the Facet Ideal of ther-Cyclic Graph

Our last result is an application to prove the entire intersection property of the facet ideal of ther-cyclic graph (see Subsection 2.6).Proposition 1.
The facet idealIFΔGn,r is a complete intersection.Proof.
By definition,Gn,r is a graph on n edges with exactly r distinct cycles. Therefore, the broken circuits of the cycle matroid XGn,r are pairwise disjoint. On the other hand, the Stanley–Reisner ideal of the broken circuit complex of cycle matroid XGn,r is exactly the facet ideal of the complex ΔGn,r. Now, the theorem follows from Theorem 6.Corollary 1.
The facet idealIFΔGn,r is Cohen–Macaulay.The corollary has been proved in [8] by a direct computational method. We proved it as an immediate consequence of our result. A comprehensive analysis of the entire intersection property for graph matroids related to broken circuits is given in [3].Example 2.
LetG be the 2-cyclic graph in Figure 1, with the given numbering of the edges. Let M=MG be the cycle matroid of G. Consider, say, the ordering 7<6<⋯<1. Let Δ be the broken circuit complex of M. In this case, the minimal broken circuits of M are 1,2,3,4, and the ideal,(46)I<M=x1x2,x3x4=IFΔ,is a complete intersection.Theorem6 characterizes the entire intersection property in terms of the set of circuits. So the Stanley–Reisner ideal of the broken circuit complex of those ordered matroids whose minimal broken circuits are pairwise disjoint satisfies the entire intersection property. This result is applied to triangulations of simple polygons to show that the cycle matroid of such a graph admits a broken circuit complex with disjoint minimal broken circuits. Regarding the cycle matroids associated with arbitrary triangulation of simple polygons, the criteria which are given in Theorem 6 on complete intersection property always can be achieved by choosing a suitable ordering of the edges. That is, there always exists an ordering < of the edges of G such that the minimal broken circuits of the ordered matroid MG,< are pairwise disjoint (see Corollary 4.8 in [3]). The following conjecture was presented in [20].Conjecture 1 (see [3, 20]).
A matroid (an arrangement) is supersolvable if and only if its Orlik–Solomon algebra is Koszul.Conjecture1 holds for matroids whose minimal broken circuits are pairwise disjoint (cf. [3], Sec. 4). In conclusion, the above conjecture holds for the cycle matroid of an r-cyclic graph.


## 5. Conclusion

The notion of graded linear resolution is introduced, and several characterizations of this property are shown for certain graded algebras associated with matroids. The notion is compared with that of graded linear quotions and componentwise linearity in general. Specifically, it is proved that the graded linearity of the Stanley–Reisner ideal of broken circuit complex of a simple matroid implies a mixed decomposition of a matroid into uniform matroids, along with a stratification. The translation of these results into the language of hyperplane arrangements is provided. Finally, an application to complete the intersection property of the facet ideal ofr-cyclic graph is given.


### 5.1. Further Directions

This work was an engagement from [3, 5, 13] with emphasis to find better criteria for componentwise linearity and Koszulness of Stanley–Reisner ideals. The result can be regarded as an approximate satisfaction toward the characterization of these two properties. Thus, future natural research could give a more straightforward explanation of these properties from the structure theory of commutative rings and the combinatorics of their matroids.Another motivation is the concept of flags and stratification of matroids (see [15]) and some applications of this concept in networks analysis and graph neural networks. Theorem 11 provides a fundamental insight into this direction, which can be used in kinds of algorithms for network programming, as well as neural networks [29]. The concept is very much tied with the theory of graphs, as well as its interrelation with graph theory [30]. The applications of matroid theory in computational algebra and networking are an attractive trend in current research for mathematicians and computer scientists. We will present several applications of flags on matroids toward algorithmic analysis of graph neural networks in future work.


## 5.1. Further Directions

This work was an engagement from [3, 5, 13] with emphasis to find better criteria for componentwise linearity and Koszulness of Stanley–Reisner ideals. The result can be regarded as an approximate satisfaction toward the characterization of these two properties. Thus, future natural research could give a more straightforward explanation of these properties from the structure theory of commutative rings and the combinatorics of their matroids.Another motivation is the concept of flags and stratification of matroids (see [15]) and some applications of this concept in networks analysis and graph neural networks. Theorem 11 provides a fundamental insight into this direction, which can be used in kinds of algorithms for network programming, as well as neural networks [29]. The concept is very much tied with the theory of graphs, as well as its interrelation with graph theory [30]. The applications of matroid theory in computational algebra and networking are an attractive trend in current research for mathematicians and computer scientists. We will present several applications of flags on matroids toward algorithmic analysis of graph neural networks in future work.



---

*Source: 1806967-2022-01-25.xml*