6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented May 1, 2015 at 19:33
  • $\begingroup$ @EricWofsey What does the box in "$G$ box $H$" mean? $\endgroup$
    – Vidit Nanda
    Commented May 7, 2015 at 2:48
  • $\begingroup$ @ViditNanda: The Cartesian product of graphs, which is adjoint to the Hom described in the question. $\endgroup$
    – Eric Wofsey
    Commented May 7, 2015 at 2:52
  • $\begingroup$ As defined, doesn't the graph $\mathrm{Hom}(H_1, H_2)$ contain a copy of $H_2$, by considering the homomorphisms $H_1 \to H_2$ that send $H_1$ to a single vertex? This would mean Eric Wofsey's construction only works for $H_1 =$ a single point. Perhaps the construction heuristic is true for graph isomorphisms. $\endgroup$
    – Harry Richman
    Commented May 23 at 16:58

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .