The Greedy Algorithm and the Cohen-Macaulay property of rings, graphs and toric projective curves

The Greedy Algorithm and the Cohen-Macaulay property of rings, graphs and toric projective curves Argimiro Arratia Abstract It is shown in this paper how a solution for a combinatorial problem obtained from applying the greedy algorithm is guaranteed to be optimal for those instances of the problem that, under an appropriate algebraic representation, satisfy the Cohen-Macaulay property known for rings and modules in Commutative Algebra. The choice of representation for the instances of a given combinatorial problem is fundamental for recognizing the Cohen-Macaulay property. Departing from an exposition of the general framework of simplicial complexes and their associated Stanley-Reisner ideals, wherein the Cohen-Macaulay property is formally defined, a review of other equivalent frameworks more suitable for graphs or arithmetical problems will follow. In the case of graph problems a better framework to use is the edge ideal of Rafael Villarreal. For arithmetic problems it is appropriate to work within the semigroup viewpoint of toric geometry developed by Antonio Campillo and collaborators. 1 Introduction A greedy algorithm is one of the simplest strategies to solve an optimization problem. It is based on a step-by-step selection of a candidate solution that seems best at the moment, that is a local optimal solution, in the hope that in the end this process leads to a global optimal solution. Greedy algorithms do not always output (global) optimal solutions, but for many optimization problems they do. For Antonio Campillo and Miguel Angel Revilla. Argimiro Arratia Dept. Computer Science & Barcelona Graduate School of Mathematics, Universitat Polit` ecnica de Catalunya, Spain, e-mail: [email protected] To appear in the Festshrift volume for Antonio Campillo on the occasion of his 65th birthday (Springer 2018). 1 2 Argimiro Arratia A seminal result of Jack Edmonds [Edmonds, 1971], states that for a greedy algorithm to output optimal solutions it is necessary and sufficient that the input is a matroid, regardless of the weight function associated to the optimization problem. A matroid is a simplicial complex with the additional exchange property. Korte and Lovazs have extended Edmonds result to cover other type of weight functions and weaker combinatorial objects as input. Specifically they have slimmed the matroid by removing the subclusiveness property and named the new object a greedoid [Korte & Lov´ asz, 1984]. The intuition behind Edmonds result is to view the problem of determining the correctness of the greedy algorithm as a localization problem: in order to know if greedy works for some set H, it suffices to look at some discrete partition of H and check if greedy works for each of the parts then it should work for H. This is a classical working paradigm for the algebraic geometer (see, e.g., [Kunz, 1985]), namely to solve problems locally and translate solutions globally, and vice versa. Matroids fit in very well this local–global pattern, which is best viewed in the realm of Commutative Algebra as follows: As a simplicial complex ∆over some ground set S, a matroid is such that for every subset Wof S, the induced subcomplex ∆W:={F∈∆:F⊆W}has an associated ideal in some ring of polynomials which is Cohen-Macaulay. By extension we say then that each ∆Wis Cohen-Macaulay [Stanley, 1996]. This suggests that in order to guarantee optimal solutions from the greedy algorithm we should start with those instances of the input that are Cohen-Macaulay or piece– wise Cohen-Macaulay (as matroids). Now, a related question is how to recognize those Cohen-Macaulay instances for a given combinatorial problem. This is a question about the choice of representation, since there is more than one way to associate to a simplicial complex some module that encodes its algebraic properties, like being Cohen-Macaulay. It also has to do with the chosen ground set of the simplicial complexes. The selection of the type of simplicial complex and associated module should be determined by the type of combinatorial problem to which we apply some form of greedy algorithm. For a general ground set Sidentified with an initial segment of the natural numbers, the standard module to associate is the Stanley-Reisner ring over some ring of polynomials [Stanley, 1996]. However, for problems on graphs there is a natural ideal to associate, which is the edge ideal [Villarreal, 1990], equivalent to a Stanley-Reisner ideal over a particular simplicial complex whose faces correspond to the independent sets of the graph. For arithmetic problems, an alternative framework is given by the numeric semigroups viewpoint of Toric Geometry [Campillo & Pis´ on, 2001, Campillo & Gimenez, 2000], which serves as a bridge between affine and projective toric varieties to and from polytopes and simplicial complexes. We will illustrate in the following sections the usefulness of these algebraic ideas for ascertaining the correctness of greedy algorithms. Greedy Algorithm and the Cohen-Macaulay property 3 2 Greedy algorithms and simplicial complexes Let Sbe a finite set and ∆a collection of subsets of S. We say that (S,∆)is a simplicial complex if it verifies the following two conditions: (S1) For all s∈S,{s} ∈ ∆. (S2) F⊆G∈∆implies F∈∆. Sis called the ground set and is usually identified with [n]:={1,...,n}, in which case one refers to the simplicial complex as ∆. The elements of ∆are called faces, and the maximal elements of ∆, with respect to ⊆, are called facets (or ∆-maximal sets). The dimension of the simplicial complex ∆, denoted dim(∆), is the maximum dimension of its faces, where the dimension of face Fis dim(F) = |F| − 1, where |F|denotes the cardinality of F. Given a simplicial complex ∆over the ground set S, and given a linear weight function f:S→R≥0, we can extend fto 2S(the set of subsets of S) by defining for each A⊆S,f(A) = ∑ a∈A f(a). We state the general form of an optimization problem as a maximization problem. Definition 1. The Optimization Problem for (S,∆)and weight function f:S→R≥0, denoted f-OPT(∆), is the following: To find a set A∈∆with maximum f-weight. Observe that if fis linear, or at least monotone (i.e. A⊆Bimplies f(A)≤f(B)), then the optimization problem f-OPT(∆) reads: To find a facet of ∆with maximum f-weight. From now on we assume that fis linear. Definition 2. The greedy algorithm associated to Optimization Problem for (S,∆) and weight f, denoted GREEDY, is presented in Figure 1. GREEDY Input: (S,∆)and f:S→R≥0 1. A←/0 2. sort Sin nonincreasing order by weight f 3. while S6=/0 do 4. choose a∈Sin the nonincreasing order by f 5. S←S−{a} 6. if A∪{a} ∈ ∆then A←A∪{a} 7. end while 8. end Output: A. Fig. 1 Algorithm GREEDY. 4 Argimiro Arratia Remark 1. Monotonicity (or positive linearity) of fis needed for inducing a partial order in Sand sorting makes sense. The algorithm always terminates because Sis finite, and it will always output a non empty set Awhich is contained in a facet. The complexity of GREEDY will mostly depend on the membership test in line 6. Note that fcan be a positive constant function. In this case we can select the elements in Sin any order, and the correctness of GREEDY have to be determined for any of the possible orders of selecting the equally weighted elements. Apart from this difficulty, the consideration of constant fis useful to treat under the GREEDY scheme optimization problems where instances are not explicitly weighted and we turn them into weighted problems by assigning equal constant weight to every element. This we will do in Section 4. Definition 3. We say that the algorithm GREEDY for (S,∆)and f correctly solves the associated optimization problem if it gives as output a set Asuch that: (i)Ais ∆-maximal (a facet) and (ii) for all B∈∆(f(A)≥f(B)). We begin by showing that we need no extra assumptions about ∆(other than to be a simplicial complex) to guarantee that the output of GREEDY is a ∆-maximal set. Proposition 1. The output of GREEDY is a ∆-maximal set. Proof. Let Abe the output and suppose Ais not maximal. Then there is a C∈∆ such that A⊂C. Let x∈C−A, then A∪{x} ⊆ C∈∆, and hence A∪ {x} ∈ ∆. But this xmust have been considered at some step in the algorithm and should have been placed in A, so x∈A, a contradiction. ut Since the previous result holds regardless of the weight function f, what then we really need to guarantee is that GREEDY outputs an Aof maximum f-weight For some weight functions (e.g., constant functions), one way to achieve this is to impose on ∆the stronger condition of being pure, that is all ∆-maximal elements have same dimension For a more ample spectrum of weight functions (e.g. linear), GREEDY achieves optimal solutions for inputs where the pureness condition can be localized. This is the point of matroids, and by extension of Cohen-Macaulay complexes. 3 Matroids and Cohen-Macaulay complexes Amatroid is a simplicial complex (S,∆)which, in addition, verifies the following principle: Greedy Algorithm and the Cohen-Macaulay property 5 Principle of Exchange (PE): If A,B∈∆and |A|<|B| then there exists x∈B−Asuch that A∪{x} ∈ ∆. The Principle of Exchange is equivalent to a localization of the property of being pure1: PE ⇐⇒ ∀W⊆S,∆W:={F∈∆:F⊆W}is pure Moreover, the Principle of Exchange is equivalent to the correctness of GREEDY. This is Edmond’s result on matroids and the greedy algorithm [Edmonds, 1971], but see [Papadimitriou & Steiglitz, 1998, Theorem 12.5, p. 285] for a textbook exposition of this important result in optimization. We collect all these facts in the following theorem (and using an updated notation and terminology from Commutative Algebra). Theorem 1 ([Edmonds, 1971]). Given a simplicial complex ∆over a ground set S, the following statements are equivalent: (i) GREEDY correctly solves the optimization problem for (S,∆)and any (linear) weight function. (ii) The Principle of Exchange (i.e. (S,∆)is a matroid). (iii) ∀W⊆S, the induced subcomplex ∆Wis pure. ut We shall see next that the localization of pureness is equivalent to a localization of the Cohen-Macaulay property. Thus, matroids are locally Cohen-Macaulay complexes, and we can view the correctness of GREEDY in the world of Cohen- Macaulay rings, and extensions, which we argue here to be an appropriate algebraic framework (if not the correct one) to understand the workings of GREEDY. 3.1 Greedy on locally Cohen-Macaulay complexes Given a simplicial complex ∆over the ground set [n]:={1,...,n}, and given K:=k[x1,...,xn], the polynomial ring in nvariables over some field k, the Stanley– Reisner ideal of ∆is the square free monomial ideal I∆=hxA:A6∈ ∆i ⊆ K, where xA:=xi1xi2···xirwith A={i1,...,ir} ⊆ [n]. The Stanley-Reisner ring (or face ring) is the quotient R∆=K/I∆. From the correspondence between ∆and I∆, the latter can be characterized as I∆=\ F∈∆ Fa facet MFc(1) where MFcis the monomial prime ideal corresponding to the non-face Fc= [n]\F; in other words, MFc=hxi:i6∈ Fi. Equation (1) gives an irreducible decomposition of I∆; as MFc, for Fa facet (a maximal face), is an irreducible component provided it is not redundant (i.e. cannot be deleted). 1The reader is encouraged to prove this equivalence. 6 Argimiro Arratia The dimension of the face ring, dim(R∆), can be defined as dim(R∆) = dim(∆)+ 1, and therefore2 dim(R∆) = max[|F|:F∈∆](2) The codimension of R∆, codim(R∆), can be defined as the smallest number of generators of any irreducible component of I∆(see [Miller & Sturmfels, 2005, §5.5]). Other two useful measures of dimension are: 1) the projective dimension of R∆, pd(R∆), as the length of a minimal resolution of R∆; and 2) the depth of R∆, depth(R∆), as the maximal length of a regular sequence on R∆. All these forms of dimension are related as follows: pd(R∆)≥codim(R∆)and dim(R∆)≥depth(R∆). Now, the ideal I∆(or equivalently the ring R∆) is Cohen-Macaulay if and only if pd(R∆) = codim(R∆)if and only if depth(R∆) = dim(R∆). The simplicial complex ∆is Cohen-Macaulay if its face ring R∆is Cohen- Macaulay. Remark 2. Technically the Cohen-Macaulay property depends on the choice of the field k, because computing regular sequences involves finding non zero divisors of certain quotient modules, and being a divisor or not depends on the characteristic of the field. Hence, we will always assume that our field kis of characteristic 0. For further simplicity the reader can assume that kis the field of real numbers. A consequence of the above definitions and facts about the Stanley-Reisner ring R∆is the following result (cf. [Bruns & Herzog, 1993, Corollary 5.1.5] or [Miller & Sturmfels, 2005, p. 114]): Proposition 2. If the face ring K/I∆is Cohen-Macaulay then all irreducible components of I∆have equal cardinality. ut It follows from the above result that a Cohen-Macaulay simplicial complex is pure. The converse is true locally, that is, a locally pure complex (i.e. a matroid) is locally Cohen-Macaulay [Stanley, 1996, Proposition 3.1]. We then have the following characterization of the correctness of the greedy algorithm in terms of the Cohen-Macaulay property: Theorem 2. Given a simplicial complex ∆over a ground set S, the following statements are equivalent: (i) GREEDY correctly solves the optimization problem for (S,∆)and any (linear) weight function. (ii) ∀W⊆S, ∆Wis pure (i.e. (S,∆)is a matroid). (iii) ∀W⊆S, ∆Wis Cohen-Macaulay. Proof. The equivalence of (i)and (ii)is Theorem 1, and the equivalence of (ii)and (iii)is Proposition 3.1 of [Stanley, 1996]. ut 2The dimension of a finitely generated ring is the maximum cardinality of an algebraically independent set. This is equivalent in R∆to dim(∆)+1 and Eq. (2). Greedy Algorithm and the Cohen-Macaulay property 7 4 Maximum Independent Set and Cohen-Macaulay graphs The Maximum Independent Set problem (or MIS) is the optimization problem that asks for a largest subset of vertices in a graph which are pairwise non-adjacent. A dual problem to MIS is the Minimum Vertex Cover (or MVC), which asks for the smallest subset of vertices in a graph where all the edges have at least one endpoint. Both problems are related to each other by the following equivalence: a set of vertices is a vertex cover if, and only if, its complement is an independent set. The MIS (and the MVC) problem is NP-complete [Garey & Johnson, 1979], and in view of its general intractability various greedy algorithms have been proposed for obtaining approximate solutions. A common feature of many of these greedy strategies for finding solutions to the MIS is to select vertices in some order with respect to their degrees (i.e. number of incident edges) and remove them and their adjacent vertices at each step. Although, in general, these strategies based on vertex selection have a poor approximation ratio under a worst case analysis (cf. [Papadimitriou & Steiglitz, 1998, §17.1] or [Dinur & Safra, 2005]), some of these work for some classes of graphs, meaning that they do provide us with the optimal solution (an independent set of maximum possible cardinality). We shall see that these vertex selection greedy strategies (dependable on the order of selecting the vertices) work in general for Cohen-Macaulay graphs. First we shall fix some notation and terminology on graphs. Definition 4. We denote graphs as G=hV(G),E(G)ior h[n],E(G)i, where the vertex set V(G)of cardinality nis identified with the labelling set [n]:={1,2,...,n}, and E(G)⊆ {{i,j}:i,j∈V(G)}is the set of edges. The complement of G, denoted Gc, is a graph with same set of vertices as Gand edge set E(Gc):={{i,j}:{i,j} 6∈ E(G)}. Given a vertex a∈V(G), the neighbourhood of ais the set NG(a) = {b: {a,b} ∈ E(G)}, and its degree is denoted deg(a). For a subset of vertices W⊆V(G), the graph induced by Whas as vertices the set Wand as edges all those in E(G) among pairs of vertices in W. The graph induced by Wis formally denoted GW. All throughout this paper a graph is always simple and undirected. Given a graph G, a subset Cof V(G)is a clique if for all distinct pairs i,j∈C,{i,j} ∈ E(G). An independent set of Gis a subset M⊆V(G)such that for all i,j∈M,{i,j} 6∈ E(G). The independent set Mis maximal if no extension of Mis an independent set. A maximum independent set (MIS) is a (maximal) independent set of greatest possible cardinality. A vertex cover of Gis a subset C⊆V(G)such that for all {i,j} ∈ E(G), C∩ {i,j} 6=/0. Cis minimal if no proper subset of Cis a vertex cover of G, and is aminimum vertex cover (MVC) if it has smallest possible cardinality. It is usually said that Gis unmixed if all of its minimal vertex covers have the same size. Next, we shall denote the vertex selection strategy following the rule ωfor selecting vertices as VERTEXSELECT[ω], and which proceeds as follows: VERTEXSELECT[ω]: select a vertex in the order established by the rule ω, remove its neighbours and repeat the selection procedure in the reduced graph. The output is the set of selected vertices. 8 Argimiro Arratia By construction the output of VERTEXSELECT[ω]is a maximal independent set. We shall first deal with two simple rules for selecting vertices: ωL: choose the vertex with largest degree first; ωS: choose the vertex with smallest degree first. Note that for both rules, selection of vertices is always possible, so both variants of the VERTEXSELECT[ω]algorithm terminate. Also, under these rules, vertices are sorted in the order given by their degrees, breaking ties at each step of the algorithm by using the implicit order given initially by the numeric labelling of the vertices. An example where the algorithm VERTEXSELECT[ω]outputs an optimal solution, regardless of ω, is the graph in Figure 2. For this graph an optimal output obtained using the rule ωSof the smallest degree first is the pair {5,1}but it could also be: {2,5}, or {3,4}, where the last two pairs can also be obtained with the rule ωLof the largest degree first. Fig. 2 A graph for which VERTEXSELECT[ω]gives optimal solution for ω∈ {ωS,ωL}. • 1• 3 • 2   J J J J J J •4   •5 """""""""""" On the other hand, Figure 3 shows a graph where VERTEXSELECT[ωS]gives the optimal solution {1,4,6}, whilst VERTEXSELECT[ωL]gives {3,4}, an independent set which is not maximum. Fig. 3 A graph for which VERTEXSELECT[ωS]gives optimal solution, but VERTEXSELECT[ωL] does not. • 1• 3 • 2   J J J J J J •6 @@ @    •4 •5 We will see next how to associate a suitable simplicial complex to a graph in order to analyze the correctness of VERTEXSELECT[ω]through the lens of Commutative Algebra. Greedy Algorithm and the Cohen-Macaulay property 9 4.1 The Edge Ideal and correctness of VERTEXSELECT Let Gbe a graph on [n]and edge set E(G); let K=k[x1,...,xn], with ka field. To Gone can associate the edge ideal I(G)⊆K, which is generated by all square–free monomials xixjwith (i,j)∈E(G). This edge ideal seems to have been first defined by Rafael Villarreal in [Villarreal, 1990]. To the complementary graph of G,Gc, one can associate the clique complex κ(Gc)where a face of dimension dis a clique of Gcof size d+1; that is, any subset A⊆[n]is in κ(Gc)iff ∀i∀j(i,j∈A→(i,j)∈E(Gc)). Hence, the Stanley–Reisner monomial ideal associated to κ(Gc), namely Iκ(Gc), is exactly the edge ideal I(G), and the following definition is sound: Definition 5. A graph G=h[n],E(G)iis Cohen-Macaulay over a field k, if the edge ideal I(G) = hxixj:(i,j)∈E(G)i(and equivalently, the ideal Iκ(Gc)) is Cohen-Macaulay over K=k[x1,...,xn], that is, K/I(G)(or K/Iκ(Gc)) is Cohen- Macaulay ring. Cohen-Macaulay graphs are extensively studied in [Villarreal, 1990]. For example, the only cycles that are Cohen-Macaulay are those of three or five vertices. Now, if F⊂[n]is a maximal clique in Gcthen Fis a maximal independent set in Gand Fc:= [n]\Fis a minimal vertex cover in Gof cardinality n−|F|, and vice versa. From this combinatorial equivalence we can derive the following facts: Fact 1: Given a graph G, another simplicial complex often associated to Gis ∆(G) consisting of all independent sets of G. By the previous equivalence one sees that ∆(G) = κ(Gc). Thus, the edge ideal I(G) = I∆(G). Fact 2: By Equation (1) the irreducible components of the edge ideal I(G)are obtained from the intersection of monomial prime ideals of the form hxi:i∈Ci such that Cis a minimal vertex cover of G. Fact 3: Using Equation (2), we get that the dimension of the face ring of ∆(G), dim(R∆(G)) = dim(K/I(G)), is equal to the maximum cardinality of a clique in the complementary graph Gc, or equivalently, the maximum cardinality of an independent set in G. On the other hand, codim(R∆(G))is equal to the minimum cardinality of a vertex cover in G. This is by definition of codimension and simply noting that (max. cardinality of independent set in G) + (min. cardinality of vertex cover in G) = n. Theorem 3. If the graph G is Cohen-Macaulay then, for any of the degree-based rules ω∈ {ωS,ωL}, the algorithm VERTEXSELECT[ω]outputs an optimal solution on input G. Proof. By Proposition 3 all irreducible components of I(G) = I∆(G)have same cardinality, which by Fact 2 means that Gis unmixed, and since VERTEXSELECT[ω] always output a maximal solution, this solution is optimal. ut 16 Argimiro Arratia To find an effective way for checking that the greedy algorithm outputs an optimal solution for any given coin system, the idea is to actually check for those values where the greedy algorithm does not give optimal solutions, for it happens that the set of witness where greedy fails for a given coin system is finite. This remarkable and useful result was obtained by Kozen and Zaks in [Kozen & Zaks, 1994] through combinatorial arguments, but we shall derive it using the algebraic tools of Campillo and Revilla laid out in the previous section. Theorem 9 ([Kozen & Zaks, 1994]). Given a system of coins Mh={1=e1<e2< ... < eh}. If for some B, greed(B)>opt(B), then the smallest such B satisfies e3+1<B<eh+eh−1. Proof. If B<e3, we only need the subset {1,e2}of the coin system and for this greed(B) = opt(B). For B=e3,e3+1, greed(B) = opt(B) = 1,2. For the other bound, let B≥eh+eh−1, and assume that for all x<B, greed(x) = opt(x). Let i<ehsuch that B=teh+i, for some integer t(i.e. B≡imod eh). Let cibe the least integer in S0such that ci≡eh−imod eh. Then (i,ci)∈Sand opt(i) = (i+ci)/eh. Also (B,ci)∈Sand opt(B)·eh=B+ci=teh+i+ci, hence opt(B) = t+i+ci eh =t+opt(i) Now, by assumption and the fact that i<ehwe conclude that opt(B) = t+opt(i) = t+greed(i) = greed(teh+i) = greed(B). Next, in order to avoid computing opt(B), Kozen and Zaks use the previous theorem to characterize greedy optimally solely in terms of greed(x). Again we give a proof of this fact using the algebraic setting for the Coin-Exchange problem: Corollary 1 ([Kozen & Zaks, 1994]). Given a system of coins Mh={1=e1<e2< ... < eh},the greedy algorithm is correct for Mhif and only if ∀B∈(e3+1,eh+eh−1),∀c∈ {e3,...,eh}(c<B−→ greed(B)≤greed(B−c)+1). Proof. (⇒)Consider B∈(e3+1,eh+eh−1)and ej, for j∈ {3,...,h}, such that ej<B. By hypothesis, Theorem 8 (i), Proposition 4 and Equation (4), greed(B) = opt(B) = opt(B−ej)+1≤greed(B−ej)+1 (⇐)If there is a Bsuch that greed(B)>opt(B), by Theorem 9 the smallest such B lies in (e3+1,eh+eh−1). Let ejbe a coin used in the minimal representation of B. Then opt(B−ej) = opt(B)−1<greed(B)−1≤greed(B−ej) contradicting that Bis smallest witness of the failure of the greedy algorithm. ut Greedy Algorithm and the Cohen-Macaulay property 17 Using Corollary 1 one can effectively check that for the following coin systems the greedy algorithm always output optimal solutions: 1. US coin system. 2. Eurozone coin system. 3. Fibonacci coin system {1,2,3,5,8,13,21,44}. On the other hand, the toric projective curves associated to each of these systems are examples of Cohen-Macaulay curves. Acknowledgements The author acknowledges the support of the Ministerio de Econom´ ıa, Industria y Competitividad, Spain, project MACDA [TIN2017-89244-R] and of the Generalitat de Catalunya, project MACDA [SGR2014-890] References [Bj¨ orner & Wachs, 1996] Bj¨ orner, A. and Wachs, M. Shellable nonpure complexes and posets I, Trans. Amer. Math. Soc. 348 (4), 1299-1327, 1996. [Bruns & Herzog, 1993] Bruns, W. and Herzog, J. Cohen-Macaulay Rings, Cambridge Univ. Press, 1993. [Campillo & Gimenez, 2000] Campillo, A. and Gimenez, P. Syzygies of affine toric varieties. J. Algebra, 225, 142-161, 2000. [Campillo & Pis´ on, 2001] Campillo, A. and Pis´ on, P. Toric mathematics from semigroup viewpoint. In: Granja, A. et al (eds.), Ring Theory and Algebraic Geometry. Lecture Notes in Pure and Applied Math., 221, 95-112, 2001. [Campillo & Revilla, 2001] Campilllo, A. and Revilla, M. A. Coin exchange algorithms and toric projective curves, Communications in Algebra, 29 (7), 2985–2989, 2001. [Dinur & Safra, 2005] Dinur, I. and Safra, S. On the hardness of approximating Minimum Vertex- Cover. Annals of Mathematics,162 (1), 439-485, 2005. [Edmonds, 1971] Edmonds, J., Matroids and the greedy algorithm, Math. Programming 1, 127– 136, 1971. [Fr¨ oberg, 1990] Fr¨ oberg, R. On Stanley-Reisner rings. In: Topics in Algebra, Banach Center Publications 26 (2), 57–70, 1990. [Fulkerson & Gross, 1965] Fulkerson, D. R. and Gross, O. A. Incidence matrices and interval graphs, Pacific J. Math., 15: 835–855, 1965. [Garey & Johnson, 1979] Garey, M. R. and Johnson, D. S. Computers and Intractability. Freeman, San Francisco, 1979. [Guo, Shen & Wu, 2016] Guo, J., Shen, Y. H., and Wu, T. Strong shellability of simplicial complexes. arXiv preprint arXiv:1604.05412, 2016. [Guo, Shen & Wu, 2017] Guo, J., Shen, Y. H., and Wu, T. Edgewise strongly shellable clutters. J. of Algebra and Its Applications, 2017. [Korte & Lov´ asz, 1984] Korte, B. and Lov´ asz, L., Greedoids and linear objective functions, SIAM J. Alg. Disc. Meth.,5(2), 229–238, 1984. [Kozen & Zaks, 1994] Kozen, D. and Zaks, S. Optimal bounds for the change-making problem. Theoret. Comput. Sci. 123, 377–388, 1994. [Kunz, 1985] Kunz, E. Introduction to Commutative Algebra and Algebraic Geometry. Springer, 1985. [Miller & Sturmfels, 2005] Miller, E. and Sturmfels, B. Combinatorial Commutative Algebra, Springer, 2005. [Papadimitriou & Steiglitz, 1998] Papadimitriou, C. and Steiglitz, K. Combinatorial Optimization, Algorithms and Complexity, Dover, 1998. 18 Argimiro Arratia [Stanley, 1996] Stanley, R. Combinatorics and Commutative Algebra, 2nd. ed., Birkh¨ auser, 1996. [van Tuyl & Villarreal, 2008] van Tuyl, A. and Villarreal, R. Shellable graphs and sequentially Cohen–Macaulay bipartite graphs, J. of Combinatorial Theory Series A 115 (5), 799-814, 2008. [Villarreal, 1990] Villarreal, R. Cohen-Macaulay graphs, Manuscripta Math. 66 (3): 277–293, 1990.