Vertex decomposability of complexes associated to forests

Document Type : Research Paper


Department of Mathematics, Chennai Mathematical Institute, Kelambakkam, Chennai, India


In this article‎, ‎we discuss the vertex decomposability of three well-studied simplicial complexes associated to forests‎. ‎In particular‎, ‎we show that the bounded degree complex of a forest and the complex of directed trees of a multidiforest is vertex decomposable‎. ‎We then prove that the non-cover complex of a forest is either contractible or homotopy equivalent to a sphere‎. ‎Finally we provide a complete characterization of forests whose non-cover complexes are vertex decomposable‎.


Main Subjects

[1] J. A. Barmak, Star clusters in independence complexes of graphs, Adv. Math., 241 (2013) 33–57.
[2] A. Björner, M. Wachs and V. Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math., 169
(2009) 295–316.
[3] A. Björner and M. L. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc., 348 (1996)
[4] A. Björner and M. L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc., 349 (1997)
[5] I. D. Castrillón and E. Reyes, Pure vertex decomposable simplicial complex associated to graphs whose 5-cycles are
chorded, Bol. Soc. Mat. Mex. (3), 23 (2017) 399–412.
[6] M. Coleman, A. Dochtermann, N. Geist and S. Oh, Completing and extending shellings of vertex decomposable
complexes, arXiv preprint arXiv:2011.12225, 2020.
[7] A. Dochtermann and A. Engström, Algebraic properties of edge ideals via combinatorial topology, Electron. J.
Combin., 16 (2009), Special volume in honor of Anders Björner), pp. 24.
[8] R. Ehrenborg and G. Hetyei, The topology of the independence complex, European J. Combin., 27 (2006) 906–923.
[9] A. Engström, Independence complexes of claw-free graphs, European J. Combin., 29 (2008) 234–241.
[10] S. Goyal, S. Shukla and A. Singh, Topology of clique complexes of line graphs, arXiv preprint arXiv:2009.12130,
[11] D. Jojić, Shellability of complexes of directed trees, Filomat, 27 (2013) 1551–1559.
[12] J. Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, 1928, Springer-Verlag, Berlin, 2008.
[13] V. Klee and P. Kleinschmidt, The d-step conjecture and its relatives, Math. Oper. Res., 12 (1987) 718–755.
[14] D. N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A, 88 (1999) 112–122.
[15] M. Marietti and D. Testa, A uniform approach to complexes arising from forests, Electron. J. Combin., 15 (2008)
pp. 18.
[16] T. Matsushita, Independence complexes of hypergraphs and bounded degree complexes, arXiv preprint
arXiv:2004.13281, 2020.
[17] E. G. Minian and J. T. Rodríguez, A note on the homotopy type of the Alexander dual, Discrete Comput. Geom.,
52 (2014) 34–43.
[18] S. Moradi, Vertex decomposable simplicial complexes associated to path graphs, Mathematical Researches, 5 (2019)
[19] J. S. Provan and L. J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra,
Math. Oper. Res., 5 (1980) 576–594.
[20] V. Reiner and J. Roberts, Minimal resolutions and the homology of matching and chessboard complexes, J. Algebraic
Combin., 11 (2000) 135–154.
[21] R. S. Simon, Combinatorial properties of “cleanness”, J. Algebra, 167 (1994) 361–388.
[22] A. Singh, Bounded degree complexes of forests, Discrete Math., 343 (2020) 7 pp.
[23] A. Singh, Higher matching complexes of complete graphs and complete bipartite graphs, arXiv preprint
arXiv:2006.13632, 2020.
[24] R. P. Stanley, Linear Diophantine equations and local cohomology, Invent. Math., 68 (1982) 175–193.
[25] R. P. Stanley, Combinatorics and commutative algebra, edition. Progress in Mathematics, 41, Birkhäuser Boston,
Inc., Boston, MA, 1996.
[26] J. Vega, Two-matching complexes, arXiv preprint arXiv:1909.10406, 2019.
[27] M. L. Wachs, Obstructions to shellability, Discrete Comput. Geom., 22 (1999) 95–103.
[28] M. L. Wachs, Topology of matching, Topology of matching, chessboard, and general bounded degree graph com-
plexes, Algebra Universalis, 49 (2003) 345–385.
[29] R. Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc., 137 (2009)
[30] G. M. Ziegler, Lectures on polytopes, volume 152 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995