×

Chordality, \(d\)-collapsibility, and componentwise linear ideals. (English) Zbl 1439.13053

Let \(K\) be a field, \(S=K[x_1,\ldots,x_n]\) and \(\Gamma\) be a simplicial complex on \([n]=\{1,\ldots,n\}.\) It is a well-known theorem of Fröberg that the edge ideal of a graph \(G\) has a linear resolution if and only if the complement of \(G\) is a chordal graph. There are several generalizations of chordal graphs to higher dimensions, such that an statement similar to this theorem of Fröberg holds in higher dimensions, at least one-sided. One such generalization which is considered in this paper, was introduced in [M. Bigdeli et al., J. Comb. Theory, Ser. A 145, 129–149 (2017; Zbl 1355.05285)]. This concept was introduced in terms of clutters. In this paper, the authors change the perspective to simplicial complexes and reveal a strong relation between chordality and collapsibility of simplicial complexes and use this relation to study chordal complexes.
To be more concrete, the authors say the simplicial complex \(\Gamma\) is \(d\)-chordal, when the \((d+1)\)-uniform clutter consisting of all \(d\)-faces of \(\Gamma\), is chordal in the sense of the aforementioned paper. Also \(\Gamma\) is called chordal, when it is \(d\)-chordal for all \(d\geq 1\). They prove that if \(\Gamma\) is \(d\)-collapsible, then it is \(t\)-chordal for all \(t\geq d\). Now let \(\Delta_d(\Gamma)\) be the simplicial complex which contains all subsets of \([n]\) with size at most \(d\), also whose \(d\)-faces are exactly as \(d\)-faces of \(\Gamma\) and in which a subset of \([n]\) with size more than \(d+1\) is a face if and only if all of its subsets are faces. This complex is called the \(d\)-closure of \(\Gamma\) and if \(\Gamma=\Delta_d(\Gamma)\), then \(\Gamma\) is said to be a \(d\)-closure. It is shown that if \(\Gamma\) is a \(d\)-closure, then \(\Gamma\) is \(d\)-chordal if and only if it is \(d\)-collapsible if and only if it is chordal. The authors use this relation to show that all induced subcomplexes of a chordal complex are chordal.
A face \(E\) of \(\Gamma\) is called a free face, if it is contained in exactly one facet of \(\Gamma\). Free faces are key to the definitions of both \(d\)-chordal and \(d\)-collapsible complexes. Suppose that \(I=I_\Gamma\) is the Stanley-Reisner ideal of \(\Gamma\) and \(E\) is a free face of \(\Gamma\). Theorem 4.5 of the paper, shows that most of the graded Betti numbers of the ideals \(I+(x_E)\) and \(I\) are the same, where \(x_E=\prod_{i\in E} x_i\). Moreover, If all minimal generators of \(I\) have degree \(\leq |E|+1\), then most of the graded Betti numbers of \(I\) and \(I+(x_mx_E|m\in A)\), where \(A\) is a certain subset of \([n]\setminus E\), are the same. As a consequence, they deduce that if \(\Gamma\) is chordal, then \(I\) is componentwise linear. This was previously known only when \(I\) was equigenerated. At the end, the authors consider certain classes of componentwise linear ideals and show that they come from chordal complexes.

MSC:

13F55 Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes
05E45 Combinatorial aspects of simplicial complexes
13D02 Syzygies, resolutions, complexes and commutative rings
05E40 Combinatorial aspects of commutative algebra
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adiprasito, K.; Benedetti, B.; Lutz, F. H., Extremal examples of collapsible complexes and random discrete Morse theory, Discrete Comput. Geom., 57, 4, 824-853 (2017) · Zbl 1365.05305
[2] Adiprasito, K. A.; Nevo, E.; Samper, J. A., Higher chordality: from graphs to complexes, Proc. Am. Math. Soc., 144, 8, 3317-3329 (2016) · Zbl 1336.05149
[3] Aramova, A.; Herzog, J.; Hibi, T., Squarefree lexsegment ideals, Math. Z., 228, 2, 353-378 (1998) · Zbl 0914.13007
[4] E. Babson, A.A. Yazdan Pour, private communication, 2017.
[5] Bigdeli, M.; Herzog, J.; Yazdan Pour, A. A.; Zaare-Nahandi, R., Simplicial orders and chordality, J. Algebraic Comb., 45, 4, 1021-1039 (2017) · Zbl 1436.13028
[6] Bigdeli, M.; Yazdan Pour, A. A.; Zaare-Nahandi, R., Stability of Betti numbers under reduction processes: towards chordality of clutters, J. Comb. Theory, Ser. A, 145, 129-149 (2017) · Zbl 1355.05285
[7] M. Bigdeli, A.A. Yazdan Pour, Multigraded minimal resolution of simplicial subclutters, preprint, 2018. · Zbl 1457.13044
[8] Björner, A.; Wachs, M., Shellable nonpure complexes and posets I, Trans. Am. Math. Soc., 348, 4, 1299-1327 (1996) · Zbl 0857.05102
[9] Björner, A.; Wachs, M., Shellable nonpure complexes and posets II, Trans. Am. Math. Soc., 349, 10, 3945-3975 (1997) · Zbl 0886.05126
[10] Connon, E.; Faridi, S., Chorded complexes and a necessary condition for a monomial ideal to have a linear resolution, J. Comb. Theory, Ser. A, 120, 7, 1714-1731 (2013) · Zbl 1314.05240
[11] Connon, E.; Faridi, S., A criterion for a monomial ideal to have a linear resolution in characteristic 2, Electron. J. Comb., 22, 1, Article 1.63 pp. (2015) · Zbl 1308.05111
[12] Cordovil, R.; Lemos, M.; Sales, C., Dirac’s theorem on simplicial matroids, Ann. Comb., 13, 53-63 (2009) · Zbl 1229.05064
[13] Dirac, G. A., On rigid circuit graphs, Abh. Math. Semin. Univ. Hamb., 25, 71-76 (1961) · Zbl 0098.14703
[14] Duval, A., Algebraic shifting and sequentially Cohen-Macaulay simplicial complexes, Electron. J. Comb., 3, 1, Article 21 pp. (1996) · Zbl 0883.06003
[15] Eagon, J. A.; Reiner, V., Resolution of Stanley-Reisner rings and Alexander duality, J. Pure Appl. Algebra, 130, 3, 265-275 (1998) · Zbl 0941.13016
[16] Emtander, E., A class of hypergraphs that generalizes chordal graphs, Math. Scand., 106, 1, 50-66 (2010) · Zbl 1183.05053
[17] Faridi, S., Simplicial trees are sequentially Cohen-Macaulay, J. Pure Appl. Algebra, 190, 1-3, 121-136 (2004) · Zbl 1045.05029
[18] Fröberg, R., On Stanley-Reisner rings, (Topics in Algebra, Part 2. Topics in Algebra, Part 2, Banach Center Publications, vol. 26 (1990)), 57-70 · Zbl 0741.13006
[19] Helly, E., Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Dtsch. Math.-Ver., 32, 175-176 (1923) · JFM 49.0534.02
[20] Herzog, J.; Hibi, T., Componentwise linear ideals, Nagoya Math. J., 153, 141-153 (1999) · Zbl 0930.13018
[21] Herzog, J.; Hibi, T., Cohen-Macaulay polymatroidal ideals, Eur. J. Comb., 27, 4, 513-517 (2006) · Zbl 1095.13008
[22] Herzog, J.; Hibi, T., Monomial Ideals, GTM, vol. 260 (2011), Springer: Springer London · Zbl 1206.13001
[23] Herzog, J.; Sharifan, L.; Varbaro, M., The possible extremal Betti numbers of a homogeneous ideal, Proc. Am. Math. Soc., 142, 6, 1875-1891 (2014) · Zbl 1291.13022
[24] Herzog, J.; Takayama, Y., Resolutions by mapping cones, The Roos Festschrift, Vol. 2. The Roos Festschrift, Vol. 2, Homol. Homotopy Appl., 4, 2, 277-294 (2002) · Zbl 1028.13008
[25] Hochster, M., Cohen-Macaulay rings, combinatorics, and simplicial complexes, (Ring Theory, II, Proc. Second Conf., Univ. Ring Theory, II, Proc. Second Conf., Univ, Oklahoma, Norman, Okla., 1975. Ring Theory, II, Proc. Second Conf., Univ. Ring Theory, II, Proc. Second Conf., Univ, Oklahoma, Norman, Okla., 1975, Lecture Notes in Pure and Appl. Math., vol. 26 (1977), Dekker: Dekker New York), 171-223 · Zbl 0351.13009
[26] Hoefel, A., Hilbert Functions in Monomial Algebras (2011), Dalhousie University, available at
[27] Hoefel, A.; Mermin, J., Gotzmann squarefree ideals, Ill. J. Math., 56, 2, 397-414 (2012) · Zbl 1286.13021
[28] Kosolv, D., Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics, vol. 21 (2008), Springer: Springer Berlin · Zbl 1130.55001
[29] Lekerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fundam. Math., 51, 45-64 (1962) · Zbl 0105.17501
[30] Morales, M.; Nasrollah Nejad, A.; Yazdan Pour, A. A.; Zaare-Nahandi, R., Monomial ideals with 3-linear resolutions, Ann. Fac. Sci. Toulouse, Sér. 6, 23, 4, 877-891 (2014) · Zbl 1304.13027
[31] Nikseresht, A., Chordality of clutters with vertex decomposable dual and ascent of clutters, J. Comb. Theory, Ser. A, 168, 318-337 (2019) · Zbl 1421.05101
[32] Nikseresht, A.; Zaare-Nahandi, R., On generalization of cycles and chordality to clutters from an algebraic viewpoint, Algebra Colloq., 24, 611 (2017) · Zbl 1387.13046
[33] Provan, J. S.; Billera, L. J., Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res., 5, 4, 576-594 (1980) · Zbl 0457.52005
[34] Stanley, R., Combinatorics and Commutative Algebra, Progress in Mathematics, vol. 41 (1996), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA · Zbl 0838.13008
[35] Tancer, M., d-collapsibility is NP-complete for \(d \geq 4\), Chic. J. Theor. Comput. Sci., Article 3 pp. (2010) · Zbl 1286.68210
[36] Van Tuyl, A.; Villarreal, R. H., Shellable graphs and sequentially Cohen-Macaulay bipartite graphs, J. Comb. Theory, Ser. A, 115, 5, 799-814 (2008) · Zbl 1154.05054
[37] Wegner, G., d-collapsing and nerves of families of convex sets, Arch. Math., 26, 1, 317-321 (1975) · Zbl 0308.52005
[38] Woodroofe, R., Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Comb., 18, 1, Article 208 pp. (2011) · Zbl 1236.05213
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.