On a lower bound for the connectivity of the independence complex of a graph

Abstract. Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false. Given a finite simple graph G, its independence complex IG is defined as the simplicial complex whose vertices are the vertices of G and whose simplices are the independent sets of G. The topology of independence complexes has been studied by a number of authors. In particular, the connectivity of independence complexes has shown to be of interest in the study of Tverberg graphs [5, Theorem 2.2], independent systems of representatives [3, Theorem 2.1] and other important problems. In [3], Aharoni, Berger and Ziv proposed a function ψ defined on graphs which is a lower bound for the connectivity of IG and conjectured that this bound is optimal. No explicit proof of this bound is given in that article, although the corresponding bound for the homological connectivity follows immediately from a result of Meshulam [9, Claim 3.1]. Moreover, a homological version of the conjecture has been considered, as well as reformulations takin