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

Abstract

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.

2 pages

Cited by in corpus (1)

• Projective Dimension, Graph Domination Parameters, and Independence Complex Homology