Star clusters in independence complexes of graphs
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)\).NEWLINENEWLINEIndependence 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.NEWLINENEWLINEFinally, 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: NEWLINE\[NEWLINE\text{cat}(I_G) +1 \leq \widetilde{\omega}(G)\leq \omega(G)\leq \chi(G)NEWLINE\]NEWLINE 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\).
- A local criterion for Tverberg graphs
- Algebraic topology of finite topological spaces and applications
- Betti numbers of monomial ideals and shifted skew shapes
- Chessboard Complexes and Matching Complexes
- Complexes of directed trees
- Complexes of directed trees and independence complexes
- Graph homotopy and Graham homotopy
- Homology groups of relations
- Homology of certain sets of 2-subgroups of symmetric groups
- scientific article; zbMATH DE number 3983158 (Why is no real title available?)
- scientific article; zbMATH DE number 1973373 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- scientific article; zbMATH DE number 3257107 (Why is no real title available?)
- Independence complexes of claw-free graphs
- Independence complexes of stable Kneser graphs
- Independent systems of representatives in weighted graphs
- Kneser's conjecture, chromatic number, and homotopy
- Lusternik-Schnirelmann category and strong category
- On Quillen's theorem A for posets
- On Spaces Having the Homotopy Type of a CW-Complex
- On the independence complex of square grids
- Proof of the Lovász conjecture
- Simplicial simple-homotopy of flag complexes in terms of graphs
- Strong homotopy types, nerves and collapses
- Subdivision yields Alexander duality on independence complexes
- The topology of the independence complex
- Torsion in the matching complex and chessboard complex
- On endo-homology of complexes of graphs
- Homotopy type of circle graph complexes motivated by extreme Khovanov homology
- Matching complexes of trees and applications of the matching tree algorithm
- Distance \(r\)-domination number and \(r\)-independence complexes of graphs
- Aspects of topological approaches for data science
- On Vietoris-Rips complexes of hypercube graphs
- A hierarchy of dismantlings in graphs
- Domination numbers and noncover complexes of hypergraphs
- Further applications of clutter domination parameters to projective dimension
- Matching and independence complexes related to small grids
- Independence complexes of claw-free graphs
- A dual independence complex
- scientific article; zbMATH DE number 7499158 (Why is no real title available?)
- Random cyclic dynamical systems
- Clique complexes and graph powers
- Extremal problems related to Betti numbers of flag complexes
- Splittings of independence complexes and the powers of cycles
- scientific article; zbMATH DE number 1559018 (Why is no real title available?)
- Higher independence complexes of graphs and their homotopy types
- Topology of clique complexes of line graphs
- On the homology of independence complexes
- The cubical matching complex revisited
- Vertex decomposability of complexes associated to forests
- Topological connectedness and independent sets in graphs
- Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
- Star clusters in the matching, Morse, and generalized complex of discrete Morse functions
- On Vietoris-Rips complexes of finite metric spaces with scale 2
- Dominance complexes and vertex cover numbers of graphs
- On Quillen's theorem A for posets
- Dominance complexes, neighborhood complexes and combinatorial Alexander duals
- Complexity of simplicial homology and independence complexes of chordal graphs
- Homotopy types of Vietoris-Rips complexes of hypercube graphs
- On the homotopy type of the polyhedral join over the independence complex of a forest
- Facets in the Vietoris–Rips Complexes of Hypercubes
- Topology of total cut complexes and cut complexes of grid graphs
- Exploring homological properties of independence complexes of Kneser graphs
This page was built for publication: Star clusters in independence complexes of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390992)
