The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3

DOI10.1016/J.EJC.2022.103534MaRDI QIDQ2143403zbMATH OpenOpenAlexFDO

Authors Jinha Kim

Publication date 31 May 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.07131

zbMATH Keywords

homotopy typeindependence complexternary graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Combinatorial aspects of simplicial complexes (05E45)

Abstract: We prove Engstr"{o}m's conjecture that the independence complex of graphs with no induced cycle of length divisible by $3$ is either contractible or homotopy equivalent to a sphere. Our result strengthens a result by Zhang and Wu, verifying a conjecture of Kalai and Meshulam which states that the total Betti number of the independence complex of such a graph is at most $1$. A weaker conjecture was proved earlier by Chudnovsky, Scott, Seymour, and Spirkl, who showed that in such a graph, the number of independent sets of even size minus the number of independent sets of odd size has values $0$, $1$, or $-1$.

Review text

The independence complex of a graph \(G\) is a simplicial complex whose simplices are the independent sets of \(G\) and we call a graph ternary if it contains no induced cycle of length divisible by 3. In [\textit{H. Wu} and \textit{W. Zhang}, ``The Betti number of the independence complex of ternary graphs, Preprint, \url{arXiv:2011.10939}], the authors prove that the total Betti number of the independence complex of ternary graphs is at most 1. In this article, the author strengthens the result of Wu and Zhang [loc. cit.] by showing that the independence complex of ternary graphs is either contractible or homotopy equivalent to a sphere. This also proves \textit{A. Engström}'s conjecture 1.5 [``On the topological Kalai-Meshulam conjecture, Preprint, \url{arXiv:2009.11077}].

Recommendations

• Proof of the Kalai-Meshulam conjecture
• On the homology of independence complexes
• Independence complexes of chordal graphs
• scientific article; zbMATH DE number 7499158
• Higher independence complexes of graphs and their homotopy types

Cites work

• Complexes of directed trees
• Proof of the Kalai-Meshulam conjecture

Cited in

(7)

• Proof of the Kalai-Meshulam conjecture
• scientific article; zbMATH DE number 7499158 (Why is no real title available?)
• Homotopy type of the independence complex of some categorical products of graphs
• The total Betti number of the independence complex of ternary graphs
• A note on the alternating number of independent sets in a graph
• Asymptotic depth of invariant chains of edge ideals
• Planar ternary graphs, flag spheres, and Delannoy polynomials

This page was built for publication: The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143403)