Criteria for the less-equal-relation between partial Lovász-vectors of digraphs
Author:
Preprint
Abstract
Finite digraphs $R$ and $S$ are studied with $\# {\cal H}(G,R) \leq \# {\cal H}(G,S)$ for every finite digraph $G \in \mathfrak{ D }'$, where ${\cal H}(G,H)$ is the set of order homomorphisms from $G$ to $H$ and $\mathfrak{ D }'$ is a class of finite digraphs. It is shown that for several classes $\mathfrak{ D }'$ of digraphs and $R \in \mathfrak{ D }'$, the relation $\# {\cal H}(G,R) \leq \# {\cal H}(G,S)$ for every $G \in \mathfrak{ D }'$ is implied by the relation $\# {\cal S}(G,R) \leq \# {\cal S}(G,S)$ for every $G \in \mathfrak{ D }'$, where ${\cal 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 $\# {\cal H}(G,R) \leq \# {\cal H}(G,S)$ for every digraph $G$. The method is applied in constructing pairs of partially ordered sets $R$ and $S$ with $\# {\cal H}(P,R) \leq \# {\cal H}(P,S)$ for every partially ordered set $P$. The main part of the results holds also for undirected graphs.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- On recognizing graphs by numbers of homomorphismsJournal of Graph Theory, 2010
- Graph invariants in the spin modelJournal of Combinatorial Theory, Series B, 2009
- Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testingAdvances in Mathematics, 2008
- Contractors and connectors of graph algebrasJournal of Graph Theory, 2008
- The rank of connection matrices and the dimension of graph algebrasEuropean Journal of Combinatorics, 2006
- The Zig-Zag Property and Exponential Cancellation of Ordered SetsOrder, 2003
- Arithmetic of Finite Ordered Sets: Cancellation of Exponents, IIOrder, 2000
- Arithmetic of Finite Ordered Sets: Cancellation of Exponents, IOrder, 1999
- Graph Homomorphisms and Phase TransitionsJournal of Combinatorial Theory, Series B, 1999
- Relations (graphs) with given finitely generated semigroupsMonatshefte für Mathematik, 1964