A simple proof for folds on both sides in complexes of graph homomorphisms

Abstract:

In this paper we study implications of folds in both parameters of Lovász’ $\mathtt {Hom}(-,-)$ complexes. There is an important connection between the topological properties of these complexes and lower bounds for chromatic numbers. We give a very short and conceptual proof of the fact that if $G-v$ is a fold of $G$, then $\operatorname {bd}\mathtt {Hom}(G,H)$ collapses onto $\operatorname {bd}\mathtt {Hom}(G-v,H)$, whereas $\mathtt {Hom}(H,G)$ collapses onto $\mathtt {Hom}(H,G-v)$. We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if $\varphi$ is a closure operator on $P$, then $\Delta (P)$ collapses onto $\Delta (\varphi (P))$.