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

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(5 intermediate revisions by 5 users not shown)
Property / author
 
Property / author: Jonathan Ariel Barmak / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2963920974 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1007.0418 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Independent systems of representatives in weighted graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proof of the Lovász conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algebraic topology of finite topological spaces and applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Quillen's theorem A for posets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Strong homotopy types, nerves and collapses / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4871782 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chessboard Complexes and Matching Complexes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Homology of certain sets of 2-subgroups of symmetric groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simplicial simple-homotopy of flag complexes in terms of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the independence complex of square grids / rank
 
Normal rank
Property / cites work
 
Property / cites work: Independence complexes of stable Kneser graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5545247 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph homotopy and Graham homotopy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4421932 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Subdivision yields Alexander duality on independence complexes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Homology groups of relations / rank
 
Normal rank
Property / cites work
 
Property / cites work: The topology of the independence complex / rank
 
Normal rank
Property / cites work
 
Property / cites work: Independence complexes of claw-free graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexes of directed trees and independence complexes / rank
 
Normal rank
Property / cites work
 
Property / cites work: A local criterion for Tverberg graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lusternik-Schnirelmann category and strong category / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexes of directed trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Kneser's conjecture, chromatic number, and homotopy / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Spaces Having the Homotopy Type of a CW-Complex / rank
 
Normal rank
Property / cites work
 
Property / cites work: Betti numbers of monomial ideals and shifted skew shapes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Torsion in the matching complex and chessboard complex / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3748279 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 05:41, 7 July 2024

scientific article
Language Label Description Also known as
English
Star clusters in independence complexes of graphs
scientific article

    Statements

    Star clusters in independence complexes of graphs (English)
    0 references
    9 January 2014
    0 references
    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\).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    independence complexes
    0 references
    graphs
    0 references
    simplicial complexes
    0 references
    homotopy types
    0 references
    homotopy invariants
    0 references
    suspensions
    0 references
    0 references
    0 references