Vertex decomposable graphs and obstructions to shellability. (English) Zbl 1180.13031
Let \(G=(V,E)\) be a graph on the vertex set \(V=\{x_1,\ldots,x_n\}.\) The independent complex of \(G\) is the simplicial complex with vertex set \(V\) whose facets are the independent sets of \(G.\) In this paper, the vertex decomposability of independence complexes of graphs is considered. In the third section it is proved geometrically that the only cyclic graphs whose independence complex is vertex decomposable, shellable and/or sequentially Cohen-Macaulay are \(C_3\) and \(C_5.\) The main theorem states that if \(G\) is a graph with no chordless cycles of length other than \(3\) or \(5\), then the independence complex of \(G\) is vertex decomposable (hence shellable and sequentially Cohen-Mcaulay). This result is used to characterize the obstructions to shellability in flag complexes. It is also shown that certain graph constructions preserve shellability.
Reviewer: Viviana Ene (Constanta)
MSC:
| 13F55 | Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes |
| 05C38 | Paths and cycles |
| 05E99 | Algebraic combinatorics |
Keywords:
independence complex; edge ideals; chordal graphs; vertex decomposable complex; shellable complex; sequentially Cohen-MacaulayReferences:
| [1] | R. Aharoni, E. Berger, and R. Meshulam, Eigenvalues and homology of flag complexes and vector representations of graphs, Geom. Funct. Anal. 15 (2005), no. 3, 555 – 566. · Zbl 1074.05058 · doi:10.1007/s00039-005-0516-9 |
| [2] | Louis J. Billera and Amy N. Myers, Shellability of interval orders, Order 15 (1998/99), no. 2, 113 – 117. · Zbl 0930.06003 · doi:10.1023/A:1006196114698 |
| [3] | A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819 – 1872. · Zbl 0851.52016 |
| [4] | Anders Björner, Michelle Wachs, and Volkmar Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math. 169 (2009), 295 – 316. · Zbl 1247.05270 · doi:10.1007/s11856-009-0012-2 |
| [5] | Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945 – 3975. · Zbl 0886.05126 |
| [6] | Romain Boulet, Etienne Fieux, and Bertrand Jouve, Simplicial simple-homotopy of flag complexes in terms of graphs, arXiv:0809.1751. To appear in European Journal of Combinatorics. · Zbl 1191.57002 |
| [7] | Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. · Zbl 0919.05001 |
| [8] | Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. · Zbl 0788.13005 |
| [9] | Vašek Chvátal, Irena Rusu, and R. Sritharan, Dirac-type characterizations of graphs without long chordless cycles, Discrete Math. 256 (2002), no. 1-2, 445 – 448. · Zbl 1011.05050 · doi:10.1016/S0012-365X(01)00166-2 |
| [10] | Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. · Zbl 1074.05001 |
| [11] | Anton Dochtermann and Alexander Engström, Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin. 16 (2009), no. 2, Research Paper 2, approx. 24 pp. (electronic). · Zbl 1161.13013 |
| [12] | Christopher A. Francisco and Huy Tài Hà, Whiskers and sequentially Cohen-Macaulay graphs, J. Combin. Theory Ser. A 115 (2008), no. 2, 304 – 316. · Zbl 1142.13021 · doi:10.1016/j.jcta.2007.06.004 |
| [13] | Christopher A. Francisco and Adam Van Tuyl, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc. 135 (2007), no. 8, 2327 – 2337. · Zbl 1128.13013 |
| [14] | T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar 18 (1967), 25 – 66 (German). · Zbl 0153.26002 · doi:10.1007/BF02020961 |
| [15] | John Ginsburg, Dismantlability revisited for ordered sets and graphs and the fixed-clique property, Canad. Math. Bull. 37 (1994), no. 4, 473 – 481. · Zbl 0824.05057 · doi:10.4153/CMB-1994-069-6 |
| [16] | Jürgen Herzog, Takayuki Hibi, and Xinxian Zheng, Cohen-Macaulay chordal graphs, J. Combin. Theory Ser. A 113 (2006), no. 5, 911 – 916. · Zbl 1172.13307 · doi:10.1016/j.jcta.2005.08.007 |
| [17] | Caroline J. Klivans, Threshold graphs, shifted complexes, and graphical complexes, Discrete Math. 307 (2007), no. 21, 2591 – 2597. · Zbl 1127.05086 · doi:10.1016/j.disc.2006.11.018 |
| [18] | Dmitry N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88 (1999), no. 1, 112 – 122. · Zbl 0934.05041 · doi:10.1006/jcta.1999.2984 |
| [19] | Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321 – 330. · Zbl 1030.05086 · doi:10.1016/S0097-3165(03)00045-1 |
| [20] | J. Scott Provan and Louis J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576 – 594. · Zbl 0457.52005 · doi:10.1287/moor.5.4.576 |
| [21] | Jorge L. Ramírez Alfonsín and Bruce A. Reed , Perfect graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 2001. · Zbl 0972.00015 |
| [22] | Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. · Zbl 0838.13008 |
| [23] | William T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. Dimension theory. · Zbl 0764.05001 |
| [24] | Adam Van Tuyl and Rafael H. Villarreal, Shellable graphs and sequentially Cohen-Macaulay bipartite graphs, J. Combin. Theory Ser. A 115 (2008), no. 5, 799 – 814. · Zbl 1154.05054 · doi:10.1016/j.jcta.2007.11.001 |
| [25] | Rafael H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990), no. 3, 277 – 293. · Zbl 0737.13003 · doi:10.1007/BF02568497 |
| [26] | Rafael H. Villarreal, Monomial algebras, Monographs and Textbooks in Pure and Applied Mathematics, vol. 238, Marcel Dekker, Inc., New York, 2001. · Zbl 1002.13010 |
| [27] | M. L. Wachs, Obstructions to shellability, Discrete Comput. Geom. 22 (1999), no. 1, 95 – 103. · Zbl 0939.06003 · doi:10.1007/PL00009450 |
| [28] | Michelle L. Wachs, Poset topology: tools and applications, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 497 – 615. · Zbl 1135.06001 |
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.
