Mixing is hard for triangle-free reflexive graphs

Abstract

In the problem $\mathrm{Mix}(H)$ one is given a graph $G$ and must decide if the Hom-graph $\mathbf{Hom}(G,H)$ is connected. We show that if $H$ is a triangle-free reflexive graph with at least one cycle, $\mathrm{Mix}(H)$ is $\mathrm{coNP}$-complete. The main part of this is a reduction to the problem $\mathrm{NonFlat}(\mathbf{H})$ for a simplicial complex $\mathbf{H}$, in which one is given a simplicial complex $\mathbf{G}$ and must decide if there are any simplicial maps $\varphi$ from $\mathbf{G}$ to $\mathbf{H}$ under which some $1$-cycles of $\mathbf{G}$ maps to homologically non-trivial cycle of $\mathbf{H}$. We show that for any reflexive graph $H$, if the clique complex $\mathbf{H}$ of $H$ has a free, non-trivial homology group $H_1(\mathbf{H})$, then $\mathrm{NonFlat}(\mathbf{H})$ is $\mathrm{NP}$-complete.