Skip to main content
4 of 5
added 16 characters in body

"Canonical" graph structure on $\text{Hom}(G, H)$

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

For the edge set $E \subseteq [\text{Hom}(G,H)]^2$ I would like to pick 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.

Questions.

  1. Is this construction always possible? Does it have a name?

  2. If this works, how does it compare with $E'\subseteq [\text{Hom}(G,H)]^2$ where $E'$ is defined by $E'=\big\{\{f,g\}\in [\text{Hom}(G,H)]^2: \{f(v), g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}$?

(For a more categorical description of this problem, see Todd Trimble's answer to a similar question in the category of topological spaces.)