Vertex decomposable graphs and obstructions to shellability

Woodroofe, Russ

doi:10.1090/S0002-9939-09-09981-X

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