0
$\begingroup$

Let $G, H$ be simple, undirected graphs without loops. We say that $G, H$ have the same homomorphism fingerprint if $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all graphs $X$. (By graph homomorphisms I mean edge preserving maps; so for instance $\text{Hom}(X,K_2)=\emptyset$ if $\chi(X) > 2$).

From Lovasz [1] we have the following theorem: If $G, H$ are finite and they have the same homomorphism fingerprint, then $G\cong H$.

Are there non-isomorphic infinite graphs that have the same homomorphism fingerprint?

[1] L. Lovasz, Operations with structures,Acta Math. Hungar. 18(1967), 321–328

$\endgroup$
1
  • 1
    $\begingroup$ If you can construct a graph $G$ such that $|\text{Hom}(X, G)|$ is always either empty or infinite, then I think you can take $H = G \times G$, and for most $G$ this should be a counterexample. (I'm not sure which graph product you need for the universal property in this setting.) $\endgroup$ Dec 3, 2014 at 6:11

2 Answers 2

8
$\begingroup$

In any category, if $G$ and $H$ are objects such that there exist monic maps $G\to H$ and $H\to G$, then $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all $X$. There are plenty of pairs of non-isomorphic infinite graphs with this property.

$\endgroup$
3
$\begingroup$

For graphs $G, H$, let $G \times H$ denote the graph with vertex set $V(G) \times V(H)$ and such that $(g_0, h_0)$ and $(g_1, h_1)$ are connected by an edge iff $g_0$ and $g_1$ are connected by an edge and $h_0$ and $h_1$ are also connected by an edge. By construction this is the categorical product in the category of graphs we're considering, hence we have a natural isomorphism

$$\text{Hom}(X, G \times H) \cong \text{Hom}(X, G) \times \text{Hom}(X, H).$$

Now let $G$ be the disjoint union of countably many copies $Y_n, n \in \mathbb{N}$ of some auxiliary graph $Y$. I claim that $|\text{Hom}(X, G)|$ is always either empty or infinite, as follows: if $f : X \to G$ is a homomorphism, consider the embedding $[k] : G \to G$ which sends $Y_n$ to $Y_{n+k}$. Then the homomorphisms $[k] \circ f : X \to G$ are distinct for all $k$: they can be distinguished by the smallest index $j$ for which the image of the homomorphism intersects $Y_j$ (which is necessarily $k$ plus the corresponding index for $f$ itself).

Letting $H = G \times G$, and using the fact that infinite cardinalities are equal to their squares (unfortunately this is equivalent to the axiom of choice; probably this can be avoided by picking $H$ more carefully), we conclude that if we can find a graph $Y$ for which $G$ and $G \times G$ are not isomorphic, then we have constructed a counterexample.

We can take $Y$ to be the path graph $P_3$ on $3$ vertices. Then $H$ is the disjoint union of countably many copies of $Y \times Y$, which is a connected graph with $9$ vertices. Hence $G$ and $H$ have connected components of different cardinalities and are not isomorphic.

(The moral of the story is that two infinite cardinalities being equal is a much weaker condition than two finite cardinalities being equal.)

$\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.