1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

It is trivial that such a maximal $E$ exists, and consists of pairs $\{f,g\}$ such that whenever $x$ and $y$ are adjacent, $f(x)$ and $g(y)$ are adjacent. However, it does not make $\operatorname{Hom}(G,H)$ an exponential object, essentially because morally (according to the definition above) it should have a loop at every vertex. For instance, when $G=H$, then for any graph $K$, there is a projection map $K\times G\to G$. But the associated map $K\to \operatorname{Hom}(G,G)$ sends every point to the identity, and so is not a graph homomorphism unless $K$ has no edges.

Your $E'$ is adjoint not to the categorical product, but to the Cartesian product (which is rather unfortunately named from the perspective of category theory).

$\endgroup$
  • $\begingroup$ Is there a construction that's adjoint to the categorical product? $\endgroup$ – Dominic van der Zypen Jul 10 '15 at 12:07
  • 2
    $\begingroup$ No, the counterexample coming from the adjoint of a projection still rules that out. By the way, if there were an exponential object (as there is in the category of graphs with loops), its vertex set would not be $\operatorname{Hom}(G,H)$, but the set of all maps from $V(G)$ to $V(H)$ (since $\bullet\times G$ is $G$ with all its edges removed). The graph-homomorphisms would just be those vertices of the exponential object that have loops. This reflects the fact that (in the category of graphs with loops) the terminal object is a vertex with a loop, not just a vertex. $\endgroup$ – Eric Wofsey Jul 10 '15 at 13:33

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.