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)$?

  • $\begingroup$ What do you mean by $\times$? In the linked question it is clear from his characterization of $E_1(G,H)$ in his answer that Eric Wofsey has interpreted your symbol $\times$ to be the categorical product. $\endgroup$ – Gabriel C. Drummond-Cole Jul 13 '15 at 19:15

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\}\}$.

  • $\begingroup$ Structures on $Hom(G,H)$ are discussed in this paper R. Brown, I. Morris, J. Shrimpton and C.D. Wensley, `Graphs of Morphisms of Graphs', Electronic Journal of Combinatorics, A1 of Volume 15(1), 2008. 1-28. pdf available at pages.bangor.ac.uk/~mas010/pdffiles/graphmorphisms-v15i1a1.pdf . This also discusses directed and undirected graphs. $\endgroup$ – Ronnie Brown Aug 8 '15 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.