4
$\begingroup$

I was thinking about this question a couple of days ago, and got reminded again by a recent question on graph homomorphisms.

Given a graph $G$, we call two vertices $u,v$ indistinguishable if the map which interchanges $u$ and $v$ and is the identity on the rest of the vertices is an isomorphism. Let $\mathbb{Graph}$ be the underlying quiver of the category of graphs with graph homomorphisms. I.e. the vertices are isomorphism classes of finite graphs, and there are $|Hom(G,H)|$ arrows from $G$ to $H$.

Is it true that $\mathbb{Graph}$ has no pairs of indistinguishable vetices?

$\endgroup$
1
  • $\begingroup$ @Tom: Sorry, I meant to ask a simpler question and Chris Godsil below guessed correctly. $\endgroup$ Apr 25, 2012 at 2:43

1 Answer 1

7
$\begingroup$

It's an old result of Lovasz that if $|\mathrm{Hom}(G,X)|=|\mathrm{Hom}(H,X)|$ for all graphs $X$, then $G$ and $H$ are isomorphic. If I understand your quiver correctly, the answer to your question is yes, for the trivial reason that the quiver does not contain a pair of equivalent vertices.

$\endgroup$
3
  • $\begingroup$ Ok, yes, that is the question I meant to ask. What is Lovasz' paper where he proves this? $\endgroup$ Apr 25, 2012 at 2:42
  • $\begingroup$ It might be in L. Lov ́asz: Direct product in locally finite categories, Acta Sci. Math. Szeged 23 (1972), 319-322. (But it's not that hard to prove.) $\endgroup$ Apr 25, 2012 at 3:19
  • $\begingroup$ The discussion in cs.elte.hu/~lovasz/hom-survey.pdf seems to imply than an extra technical condition ("twin-freeness") is required. Is this satisfied by the questioner's setup? I can't tell. $\endgroup$
    – Jason Reed
    Sep 21, 2012 at 19:05

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.