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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok, yes, that is the question I meant to ask. What is Lovasz' paper where he proves this? $\endgroup$
    – Gjergji Zaimi
    Commented 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$
    – Chris Godsil
    Commented 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
    Commented Sep 21, 2012 at 19:05

You must log in to answer this question.

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