Interdependencies of less-equal-relations between partial Lovász-vectors of digraphs

Abstract

For digraphs $G$ and $H$, let $\mathcal{H}(G,H)$ be the set of all homomorphisms from $G$ to $H$, and let $\mathcal{S}(G,H)$ be the subset of those homomorphisms mapping all proper arcs in $G$ to proper arcs in $H$. From an earlier investigation we know that for certain digraphs $R$ and $S$, the relation "$\#\mathcal{S}(G,R)\le \#\mathcal{S}(G,S)$ for all $G\in {\mathfrak{D}}^{\prime }$" implies "$\#\mathcal{H}(G,R)\le \#\mathcal{H}(G,S)$ for all $G\in {\mathfrak{D}}^{\prime }$", where ${\mathfrak{D}}^{\prime }$ is a subclass of digraphs. Now we ask for the inverse: For which digraphs $R,S$ and which subclasses ${\mathfrak{D}}^{\prime }$ of digraphs does "$\#\mathcal{H}(G,R)\le \#\mathcal{H}(G,S)$ for all $G\in {\mathfrak{D}}^{\prime }$" imply "$\#\mathcal{S}(G,R)\le \#\mathcal{S}(G,S)$ for all $G\in {\mathfrak{D}}^{\prime }$"? We prove this implication for three combinations of digraph classes. In particular, the relations are equivalent for all flat posets $R,S$ with respect to all flat posets $G$.

27 pages, 3 figures