Criteria for the less-equal-relation between partial Lovász-vectors of digraphs

Abstract

Finite digraphs $R$ and $S$ are studied with $\#\mathcal{H}(G,R)\le \#\mathcal{H}(G,S)$ for every finite digraph $G\in {\mathfrak{D}}^{\prime }$, where $\mathcal{H}(G,H)$ is the set of order homomorphisms from $G$ to $H$ and ${\mathfrak{D}}^{\prime }$ is a class of finite digraphs. It is shown that for several classes ${\mathfrak{D}}^{\prime }$ of digraphs and $R\in {\mathfrak{D}}^{\prime }$, the relation $\#\mathcal{H}(G,R)\le \#\mathcal{H}(G,S)$ for every $G\in {\mathfrak{D}}^{\prime }$ is implied by the relation $\#\mathcal{S}(G,R)\le \#\mathcal{S}(G,S)$ for every $G\in {\mathfrak{D}}^{\prime }$, where $\mathcal{S}(G,H)$ is the set of homomorphisms from $G$ to $H$ mapping all proper arcs of $G$ to proper arcs of $H$. Under an application-oriented regularity condition, the two relations are even equivalent. A method is developed for the rearrangement of a digraph $R$, resulting in a digraph $S$ with $\#\mathcal{H}(G,R)\le \#\mathcal{H}(G,S)$ for every digraph $G$. The method is applied in constructing pairs of partially ordered sets $R$ and $S$ with $\#\mathcal{H}(P,R)\le \#\mathcal{H}(P,S)$ for every partially ordered set $P$. The main part of the results holds also for undirected graphs.

23 pages, 5 figures. arXiv admin note: text overlap with arXiv:1906.11758