Homomorphism Complexes and k-Cores

Abstract

We prove that the topological connectivity of a graph homomorphism complex Hom($G,K_m$) is at least $m-D(G)-2$, where $D(G)=\underset{H\subseteq G}{\max }\delta (H)$. This is a strong generalization of a theorem of Cukić and Kozlov, in which $D(G)$ is replaced by the maximum degree $\Delta (G)$. It also generalizes the graph theoretic bound for chromatic number, $\chi (G)\le D(G)+1$, as $\chi (G)=\min \{m:\text{Hom}(G,K_m)\ne \varnothing \}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c/n$ for a fixed constant $c>0$.