Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
@Tom: Sorry, I meant to ask a simpler question and Chris Godsil below guessed correctly. –  Gjergji Zaimi Apr 25 '12 at 2:43
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Ok, yes, that is the question I meant to ask. What is Lovasz' paper where he proves this? –  Gjergji Zaimi Apr 25 '12 at 2:42
    
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.) –  Chris Godsil Apr 25 '12 at 3:19
    
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. –  Jason Reed Sep 21 '12 at 19:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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