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.

  • $\begingroup$ Thanks for spotting it! I just corrected it. (There were in fact 2 typos.) $\endgroup$ – Dominic van der Zypen May 1 '15 at 11:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – Eric Wofsey May 1 '15 at 19:33
  • $\begingroup$ @EricWofsey What does the box in "$G$ box $H$" mean? $\endgroup$ – Vidit Nanda May 7 '15 at 2:48
  • $\begingroup$ @ViditNanda: The Cartesian product of graphs, which is adjoint to the Hom described in the question. $\endgroup$ – Eric Wofsey May 7 '15 at 2:52

Warning: the following statement answers an older version of this question.

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.


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.