×

Star clusters in independence complexes of graphs. (English) Zbl 1288.57004

The clique complex of a graph \(G\) is the abstract simplicial complex whose vertex set is the vertex set \(V(G)\) of \(G\) and simplices are the subsets of \(V(G)\) which induce a complete subgraph. The independence complex \(I_G\) of \(G\) is the clique complex of the complement of \(G\) (so, its vertex set is \(V(G)\) and its simplices are given by independent subsets of \(V(G)\), i.e. set of vertices which contains no pair of adjacent vertices). In any abstract simplicial complex \(K\), the star of a vertex \(v\), denoted \(\text{st}_K(v)\), is the subcomplex of \(K\) formed by simplices \(\sigma\) of \(K\) such that \(\sigma \cup \{x\}\) is a simplex of \(K\). In this paper, the author introduces the notion of star cluster of a simplex \(\sigma\), denoted \(SC_K(\sigma)\), which is, by definition, the union \(\bigcup_{v \in \sigma}\text{st}_K(v)\).
Independence complexes constitute a key construction in many works in topological combinatorics and the star cluster construction appears to be a very useful tool for investigating their homotopical properties (as homotopical type or connectivity). As first application, the author proves that the independence complex of a triangle-free graph has the homotopy type of the suspension of some simplicial complex; actually, the statement is much stronger: the author obtains the same conclusion with only the hypothesis that there is an edge which is contained in no triangle. This result extends the one of U. Nagel and V. Reiner [Electron. J. Comb. 16, No. 2, Research Paper R3, 59 p. (2009; Zbl 1186.13022)] where they obtained the same conclusion for bipartite graphs (this last result has also been obtained independently by J. Jonsson in a more recent and unpublished paper) and this proves that the first homology groups of independence complexes of triangle-free graphs don’t have torsion. Next, the author shows how to simplify various known results involving independence complexes by using the star cluster contruction. These results concern homotopical properties of independence complexes of a very large variety of graphs : cycles, forests, Kneser graphs, square grids, claw-free graphs...; we refer to the paper for the many references.
Finally, the author obtains relations between the strong Lusternik-Schnirelmann category of \(I_G\) (the smallest integer \(n\) such that one can find a CW-complex homotopy equivalent to \(I_G\) with \((n+1)\) contractible subcomplexes which cover it), the clique number \(\omega(G)\) and the chromatic number \(\chi(G)\) of \(G\) ; he proves that \(\text{cat}(I_G)\) is bounded by \(\widetilde{\omega}(G)-1\), where \(\widetilde{\omega}(G)\) is the smallest cardinality of a maximal clique (or maximal complete subgraph) in \(G\); so, there are the inequalities: \[ \text{cat}(I_G) +1 \leq \widetilde{\omega}(G)\leq \omega(G)\leq \chi(G) \] The paper ends with results concerning the homotopy type of independence complexes of planar graphs and relations between maximum degree of \(G\) and connectivity of \(I_G\).

MSC:

57M15 Relations of low-dimensional topology with graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
55P15 Classification of homotopy type
05C10 Planar graphs; geometric and topological aspects of graph theory
55P40 Suspensions

Citations:

Zbl 1186.13022
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, R.; Berger, E.; Ziv, R., Independent systems of representatives in weighted graphs, Combinatorica, 27, 3, 253-267 (2007) · Zbl 1164.05020
[2] Babson, E.; Kozlov, D. N., Proof of the Lovász Conjecture, Ann. of Math., 165, 3, 965-1007 (2007) · Zbl 1132.05019
[3] Barmak, J. A., Algebraic topology of finite topological spaces and applications, (Lecture Notes in Mathematics, vol. 2032 (2011), Springer) · Zbl 1235.55001
[4] Barmak, J. A., On Quillen’s Theorem A for posets, J. Combin. Theory Ser. A, 118, 2445-2453 (2011) · Zbl 1234.05237
[5] Barmak, J. A.; Minian, E. G., Strong homotopy types, nerves and collapses, Discrete Comput. Geom., 47, 301-328 (2012) · Zbl 1242.57019
[6] Björner, A., Topological methods, (Handbook of Combinatorics, vol. 2 (1995), Elsevier: Elsevier Amsterdam), 1819-1872 · Zbl 0851.52016
[7] Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T., Chessboard complexes and matching complexes, J. Lond. Math. Soc. (2), 49, 1, 25-39 (1994) · Zbl 0790.57014
[8] Bouc, S., Homologie de certains ensembles de 2-sous-groupes des groupes symtriques, J. Algebra, 150, 158-186 (1992) · Zbl 0786.55005
[9] Boulet, R.; Fieux, E.; Jouve, B., Simplicial simple-homotopy of flag complexes in terms of graphs, European J. Combin., 31, 161-176 (2010) · Zbl 1191.57002
[10] Bousquet-Mélou, M.; Linusson, S.; Nevo, E., On the independence complex of square grids, J. Algebraic Combin., 27, 4, 423-450 (2008) · Zbl 1202.05095
[11] Braun, B., Independence complexes of stable Kneser graphs, Electron. J. Combin., 18 (2011) · Zbl 1217.05174
[12] Brown, R., Elements of Modern Topology (1968), McGraw-Hill: McGraw-Hill London · Zbl 0159.52201
[13] Chen, B.; Yau, S.-T.; Yeh, Y.-N., Graph homotopy and Graham homotopy, Discrete Math., 241, 153-170 (2001), Selected papers in honor of Helge Tverberg · Zbl 0990.05120
[14] Cornea, O.; Lupton, G.; Oprea, J.; Tanré, D., (Lusternik-Schnirelmann category. Lusternik-Schnirelmann category, Mathematical Surveys and Monographs, vol. 103 (2003))
[15] Csorba, P., Subdivision yields Alexander duality on independence complexes, Electron. J. Combin., 16, 2, 7 pp (2009), Special volume in honor of Anders Björner, Research Paper 11 · Zbl 1171.05384
[16] Dowker, C. H., Homology groups of relations, Ann. of Math., 56, 84-95 (1952) · Zbl 0046.40402
[17] Ehrenborg, R.; Hetyei, G., The topology of the independence complex, European J. Combin., 27, 906-923 (2006) · Zbl 1090.05075
[18] Engström, A., Independence complexes of claw-free graphs, European J. Combin., 29, 234-241 (2008) · Zbl 1126.05047
[19] Engström, A., Complexes of directed trees and independence complexes, Discrete Math., 309, 3299-3309 (2009) · Zbl 1226.05084
[21] Engström, A., A local criterion for Tverberg graphs, Combinatorica, 31, 321-332 (2011) · Zbl 1249.05076
[22] Ganea, T., Lusternik-Schnirelmann category and strong category, Illinois J. Math., 11, 417-427 (1967) · Zbl 0149.40703
[25] Kozlov, D. N., Complexes of directed trees, J. Combin. Theory Ser. A, 88, 112-122 (1999) · Zbl 0934.05041
[26] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028
[27] Milnor, J. W., On spaces having the homotopy type of a CW-complex, Trans. Amer. Math. Soc., 90, 272-280 (1959) · Zbl 0084.39002
[28] Nagel, U.; Reiner, V., Betti numbers of monomial ideals and shifted skew shapes, Electron. J. Combin., 16, 2, 59 pp (2009), Special volume in honor of Anders Björner, Research Paper 3 · Zbl 1186.13022
[29] Shareshian, J.; Wachs, M., Torsion in the matching complex and the chessboard complex, Adv. Math., 212, 525-570 (2007) · Zbl 1117.05110
[31] Stanley, R., Enumerative Combinatorics, vol. I (1986), Wadsworth and Brooks/Cole: Wadsworth and Brooks/Cole Pacific Grove · Zbl 0608.05001
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.