Long paths need not minimize $H$-colorings among trees

Abstract

Given a graph $G$ and a target graph $H$, an $H$-coloring of $G$ is an adjacency-preserving vertex map from $G$ to $H$. By appropriate choice of $H$, these colorings can express, for instance, the independent sets or proper vertex colorings of $G$. Sidorenko proved that for any $H$, the $n$-vertex star admits at least as many $H$-colorings as any other $n$-vertex tree, but the minimization question remains open in general. For many graphs $H$, path graphs are among the trees with the fewest $H$-colorings, but work of Leontovich and subsequently Csikvári and Lin shows that there is a graph $E_7$ on seven vertices and a target graph $H$ for which there are strictly fewer $H$-colorings of $E_7$ than of the path on seven vertices. We introduce a new strategy for enumerating homomorphisms from path-like trees to highly symmetric target graphs that allows us to make the previous observations completely explicit and extend them to infinitely many $n$ beyond $n=7$. In particular, we exhibit a target graph $H$ with the property that for each sufficiently large $n$, there is a tree $E_n$ on $n$ vertices that admits strictly fewer $H$-colorings than the path on $n$ vertices.

17 pages, 3 figures