Two graph structures on $\text{Hom}(G,H)$

Question

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.

Given graphs $G,H$, we denote by $\text{Hom}(G, H)$ the set of all graph homomorphisms $f: G\to H$. Note that for many $G, H$ the set $\text{Hom}(G,H)$ is empty (for instance when $\chi(G) > \chi(H)$).

Define $E_1(G,H) \subseteq [\text{Hom}(G,H)]^2$ to be the largest set such that the evaluation map $e: \text{Hom}(G,H)\times G \to H$, defined by $(f,v) \mapsto f(v)$, is a graph homomorphism. (Here we consider the Cartesian product of graphs, and not the categorical product, see this post.)

Moreover, let $E_2(G,H) = \big\{\{f,g\}\in [\text{Hom}(G,H)]^2: \{f(v), g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}$.

Are there graphs $G,H$ such that neither $E_1(G,H) \subseteq E_2(G,H)$ nor $E_2(G,H) \subseteq E_1(G,H)$?

Answer 1

Here are two answers, depending on what you mean by $\times$, which was not clear to me from your wording.

---

Answer 1, assuming that $\times$ is the Cartesian product, or in other words, that the edges of $F\times G$ are of one of the two following forms:

• $\{(x,v),(y,v)\}$ for $\{x,y\}\in E(F)$ and $v\in V(G)$
• $\{(x,u),(x,v)\}$ for $x\in V(F)$ and $\{u,v\}\in E(G)$.

In this case, your two structures coincide.

One can test whether $\{f,g\}$ is in $E_1(G,H)$ by looking at the image under $e$ of all the putative edges it generates in $\mathrm{Hom}(G,H)\times G$; the pair $\{f,g\}$ is in $E_1(G,H)$ if and only if all of these are in $E(H)$.

The set of putative edges is of the form $\{\{f,g\}\times v\}$ for $v\in V(G)$. Therefore, the pair $\{f,g\}$ is in $E_1(G,H)$ if and only if $\{f(v),g(v)\}$ is in $E(H)$ for all $v\in V(G)$. But this is the definition of $E_2(G,H)$.

---

Answer 2, assuming that $\times$ is the categorical product, or in other words, that the edges of $F\times G$ are of the form $\{(x,u),(y,v)\}$ for $\{x,y\}\in E(F)$ and $\{u,v\}\in E(G)$.

There are graphs where $E_1(G,H)$ and $E_2(G,H)$ are incomparable. Take $V(G)=\{1,2,3\}$ and $E(G)=\{\{1,2\}\}$. Take $V(H)=\{a,b\}$ and $E(H)=\{\{a,b\}\}$.

Then $\mathrm{Hom}(G,H)$ has four elements:

• $f_1(1)=a;\quad f_1(2)=b;\quad f_1(3)=a$
• $f_2(1)=a;\quad f_2(2)=b;\quad f_2(3)=b$
• $f_3(1)=b;\quad f_3(2)=a;\quad f_3(3)=a$
• $f_4(1)=b;\quad f_4(2)=a;\quad f_4(3)=b$

With this interpretation of $\times$ (which I believe corresponds with Eric Wofsey's in the linked question), $E_1(G,H)$ is the set $\{\{f_1,f_2\},\{f_3,f_4\}\}$.

On the other hand, $E_2(G,H)$ is $\{\{f_1,f_4\},\{f_2,f_3\}\}$.