Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Vertex decomposable graphs and obstructions to shellability


Author: Russ Woodroofe
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
Published electronically: June 4, 2009
MathSciNet review: 2515394
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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. MR 2221142 (2007b:05148)
  • 2. Louis J. Billera and Amy N. Myers, Shellability of interval orders, Order 15 (1998/99), no. 2, 113-117. MR 1695087 (2000b:06010)
  • 3. Anders Björner, Topological methods, Handbook of combinatorics, Vols. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819-1872. MR 1373690 (96m:52012)
  • 4. Anders Björner, Michelle Wachs, and Volkmar Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math. 169 (2009), 295-316. MR 2460907
  • 5. 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 (98b:06008)
  • 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.
  • 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. MR 1686154 (2001h:05001)
  • 8. Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. MR 1251956 (95h:13020)
  • 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. MR 1927566 (2003g:05106)
  • 10. Reinhard Diestel, Graph theory, third ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259 (2006e: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).
  • 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. MR 2382518 (2008j:13050)
  • 13. Christopher A. Francisco and Adam Van Tuyl, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc. 135 (2007), no. 8, 2327-2337 (electronic). MR 2302553 (2008a:13030)
  • 14. T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66. MR 0221974 (36:5026)
  • 15. 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 (95k:05151)
  • 16. 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 (2007b:13042)
  • 17. Caroline J. Klivans, Threshold graphs, shifted complexes, and graphical complexes, Discrete Math. 307 (2007), no. 21, 2591-2597. MR 2359603 (2008j:05373)
  • 18. Dmitry N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88 (1999), no. 1, 112-122. MR 1713484 (2000j:05036)
  • 19. Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321-330. MR 1979537 (2004c:05144)
  • 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. MR 593648 (82c:52010)
  • 21. 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 (2002d:05001)
  • 22. Richard P. Stanley, Combinatorics and commutative algebra, second ed., Progress in Mathematics, vol. 41, Birkhäuser Boston Inc., Boston, MA, 1996. MR 1453579 (98h:05001)
  • 23. William T. Trotter, Combinatorics and partially ordered sets, Dimension theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. MR 1169299 (94a:06001)
  • 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. MR 2417022 (2009b:13056)
  • 25. Rafael H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990), no. 3, 277-293. MR 1031197 (91b:13031)
  • 26. -, Monomial algebras, Monographs and Textbooks in Pure and Applied Mathematics, vol. 238, Marcel Dekker Inc., New York, 2001. MR 1800904 (2002c:13001)
  • 27. M. L. Wachs, Obstructions to shellability, Discrete Comput. Geom. 22 (1999), no. 1, 95-103. MR 1692690 (2000k:52011)
  • 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. MR 2383132

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 13F55, 05C38, 05E99

Retrieve articles in all journals with MSC (2000): 13F55, 05C38, 05E99


Additional Information

Russ Woodroofe
Affiliation: Department of Mathematics, Washington University in St. Louis, St. Louis, Missouri 63130
Email: russw@math.wustl.edu

DOI: https://doi.org/10.1090/S0002-9939-09-09981-X
Keywords: Sequentially Cohen-Macaulay, independence complex, edge ideal, chordal graphs
Received by editor(s): January 8, 2009
Published electronically: June 4, 2009
Communicated by: Jim Haglund
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society