





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。