3
$\begingroup$

Let $G,H$ be infinite simple undirected graphs with the property that for any graph $X$ we have $|\text{Hom}(X,G)| = |\text{Hom}(X,H)|$. Does this imply that $G$ is isomorphic to a subgraph of $H$, and vice versa?

(Note that in the finite case the condition above implies $G\cong H$, see here.)

Improve this question
$\endgroup$
2
  • $\begingroup$ I assume that you mean "edge preserving" by homomorphism (not necessarily non-edge preserving). I also assume that you really mean subgraph, not "induced subgraph". Correct? $\endgroup$
    – Goldstern
    May 29, 2015 at 12:12
  • $\begingroup$ Thanks for asking for clarification. You're right: I mean homomorphisms to be edge-preserving, and I mean subgraphs that are not necessarily induced. $\endgroup$
    – Dominic van der Zypen
    May 29, 2015 at 12:28

1 Answer 1

Reset to default
6
$\begingroup$

Did you want both G to be a subgraph of H and H to be a subgraph of G? Then I think the answer is negative. For example if G is infinite and have no isolated vertices and H is G together with an isolated vertex. If X have no isolated vertices the Hom-sets are the same. The set of maps from the set of isolated vertices of X to G or H should be of the same size as the cardinality of the vertex sets of G and H should be the same.

Edit: And if G for example is the integers with edges $\{i,i+1\}$ then I don't think H can be a subgraph.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.