Graph Operations and Upper Bounds on Graph Homomorphism Counts

Abstract

We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any $n$-vertex, $d$-regular graph $G$ and any graph $H$ (possibly with loops), \[\hom(G,H) \leq \max\left\lbrace\hom(K_{d,d}, H)^{\frac{n}{2d}}, \hom(K_{d+1},H)^{\frac{n}{d+1}}\right\rbrace,\] where $\mathrm{hom}(G,H)$ is the number of homomorphisms from $G$ to $H$. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of $H$ for which the bound stated above on $\mathrm{hom}(G,H)$ holds for all $n$-vertex, $d$-regular $G$. In particular we show that if $H_{\mathrm{WR}}$ is the complete looped path on three vertices, also known as the Widom-Rowlinson graph, then $$\mathrm{hom}(G,H_{\mathrm{WR}})\le \mathrm{hom}(K_{d+1},H_{\mathrm{WR}}{)}^{\frac{n}{d+1}}$$ for all $n$-vertex, $d$-regular $G$. This verifies a conjecture of Galvin.