# Graph of graph homomorphisms

For (finite or infinite) undirected, simple graphs $G, H$, let

$V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and $E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: \{f(v),g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}.$

We set $\text{Hom}(G,H) = (V_{\text{Hom}}, E_{\text{Hom}})$.

Given any graph $G$, are there always graphs $H_1, H_2$ with more than $1$ point each such that $G\cong \text{Hom}(H_1, H_2)$?

EDIT. Thanks to Vidit for spotting the $1$-point solution solving the problem trivially, so I have excluded this.

• Thanks for spotting it! I just corrected it. (There were in fact 2 typos.) – Dominic van der Zypen May 1 '15 at 11:14
• I suspect that for finite $G$, this holds for most graphs $H_1$ with $|V(H_1)|\gg|V(G)|$ and $H_2=G\square H_1$ (heuristically, for random $H_1$ there should be no maps $H_1\to G\square H_1$ other than the obvious ones). For infinite $G$, the question may involve some nontrivial set theory--for instance, if $G$ is a complete infinite graph, it is easy to see that $H_1$ and $H_2$ must have greater cardinality than $G$. – Eric Wofsey May 1 '15 at 19:33
• @EricWofsey What does the box in "$G$ box $H$" mean? – Vidit Nanda May 7 '15 at 2:48
• @ViditNanda: The Cartesian product of graphs, which is adjoint to the Hom described in the question. – Eric Wofsey May 7 '15 at 2:52

Let $G$ be the graph you want to realize. Then, $\text{Hom}(\bullet,G) \simeq G$ where $\bullet$ is the graph containing one vertex and no edges.