The word problem and the Aharoni-Berger-Ziv conjecture on the connectivity of independence complexes

Jonathan Ariel Barmak

Published 2010-09-20Version 1

For each finite simple graph $G$, Aharoni, Berger and Ziv consider a recursively defined number $\psi (G) \in \mathbb{Z}\cup \{+ \infty \}$ which gives a lower bound for the topological connectivity of the independence complex $I_G$. They conjecture that this bound is optimal for every graph. We use a result of recursion theory to give a short disproof of this claim.