Homomorphism complexes and $k$-cores

Abstract

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex $\text{Hom}(G,K_m)$ is at least $m-D\left(G\right)-2$, where $D\left(G\right)={max}_{H\subseteq G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of Cukic and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne \varnothing \}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes $\text{Hom}\left(G\right(n,p),K_m)$ when $p=c/n$ for a fixed constant $c>0$.