Star clusters in independence complexes of graphs (Q390992): Difference between revisions

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 \textsl{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 \textsl{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 \textsl{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 \textit{U. Nagel} and \textit{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 \textsl{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 \textsl{clique number} \(\omega(G)\) and the \textsl{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\).