Vertex decomposable graphs and obstructions to shellability
HTML articles powered by AMS MathViewer
- by Russ Woodroofe PDF
- Proc. Amer. Math. Soc. 137 (2009), 3235-3246 Request permission
Abstract:
Inspired by several recent papers on the edge ideal of a graph $G$, we study the equivalent notion of the independence complex of $G$. Using the tool of vertex decomposability from geometric combinatorics, we show that $5$-chordal graphs with no chordless $4$-cycles are shellable and sequentially Cohen-Macaulay. We use this result to characterize the obstructions to shellability in flag complexes, extending work of Billera, Myers, and Wachs. We also show how vertex decomposability may be used to show that certain graph constructions preserve shellability.References
- 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. MR 2221142, DOI 10.1007/s00039-005-0516-9
- Louis J. Billera and Amy N. Myers, Shellability of interval orders, Order 15 (1998/99), no. 2, 113–117. MR 1695087, DOI 10.1023/A:1006196114698
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- Anders Björner, Michelle Wachs, and Volkmar Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math. 169 (2009), 295–316. MR 2460907, DOI 10.1007/s11856-009-0012-2
- Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945–3975. MR 1401765, DOI 10.1090/S0002-9947-97-01838-2
- 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.
- 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. MR 1686154, DOI 10.1137/1.9780898719796
- Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. MR 1251956
- 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. MR 1927566, DOI 10.1016/S0012-365X(01)00166-2
- Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
- 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).
- 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. MR 2382518, DOI 10.1016/j.jcta.2007.06.004
- Christopher A. Francisco and Adam Van Tuyl, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc. 135 (2007), no. 8, 2327–2337. MR 2302553, DOI 10.1090/S0002-9939-07-08841-7
- T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66 (German). MR 221974, DOI 10.1007/BF02020961
- John Ginsburg, Dismantlability revisited for ordered sets and graphs and the fixed-clique property, Canad. Math. Bull. 37 (1994), no. 4, 473–481. MR 1303674, DOI 10.4153/CMB-1994-069-6
- Jürgen Herzog, Takayuki Hibi, and Xinxian Zheng, Cohen-Macaulay chordal graphs, J. Combin. Theory Ser. A 113 (2006), no. 5, 911–916. MR 2231097, DOI 10.1016/j.jcta.2005.08.007
- Caroline J. Klivans, Threshold graphs, shifted complexes, and graphical complexes, Discrete Math. 307 (2007), no. 21, 2591–2597. MR 2359603, DOI 10.1016/j.disc.2006.11.018
- Dmitry N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88 (1999), no. 1, 112–122. MR 1713484, DOI 10.1006/jcta.1999.2984
- Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321–330. MR 1979537, DOI 10.1016/S0097-3165(03)00045-1
- 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. MR 593648, DOI 10.1287/moor.5.4.576
- Jorge L. Ramírez Alfonsín and Bruce A. Reed (eds.), Perfect graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 2001. MR 1858793
- Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. MR 1453579
- William T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. Dimension theory. MR 1169299
- 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. MR 2417022, DOI 10.1016/j.jcta.2007.11.001
- Rafael H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990), no. 3, 277–293. MR 1031197, DOI 10.1007/BF02568497
- Rafael H. Villarreal, Monomial algebras, Monographs and Textbooks in Pure and Applied Mathematics, vol. 238, Marcel Dekker, Inc., New York, 2001. MR 1800904
- M. L. Wachs, Obstructions to shellability, Discrete Comput. Geom. 22 (1999), no. 1, 95–103. MR 1692690, DOI 10.1007/PL00009450
- 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. MR 2383132, DOI 10.1090/pcms/013/09
Additional Information
- Russ Woodroofe
- Affiliation: Department of Mathematics, Washington University in St. Louis, St. Louis, Missouri 63130
- MR Author ID: 656572
- ORCID: 0000-0002-8199-3483
- Email: russw@math.wustl.edu
- Received by editor(s): January 8, 2009
- Published electronically: June 4, 2009
- Communicated by: Jim Haglund
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 137 (2009), 3235-3246
- MSC (2000): Primary 13F55, 05C38, 05E99
- DOI: https://doi.org/10.1090/S0002-9939-09-09981-X
- MathSciNet review: 2515394