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

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, which contains only one representative from each isomorphism class. The right $\mathbf{D}$-profile of a graph $G$ is the infinite vector $(G \to \mathbf{D}) := (h(G,G_1),h(G,G_2),\dots)$.

Is it true that $(G\to \mathbf{D}) = (H\to \mathbf{D})$ iff $G \simeq H$?

The analogous left-profile is important in the theory of graph limits. Lovász showed that $(\mathbf{D}\to G) = (\mathbf{D}\to H)$ iff $G \simeq H$.

  • L. Lovász, Operations with structures, Acta Mathematica Hungarica 18(3), 1967, 321–328. doi:10.1007/BF02280291 (reprint)

It is also possible to restrict $\mathbf{D}$ to be a smaller set, for instance just the complete graphs. In this case, right-profile equivalence implies that $G$ and $H$ have the same chromatic polynomials. A conjecture of Bollobás, Pebody and Riordan about the chromatic polynomial implies that this is enough to show isomorphism for almost all graphs, although they also showed that it is likely to be nontrivial to construct examples of non-isomorphic graphs $G$ and $H$ which have the same right-profiles with respect to the set of complete graphs.

One can also ask whether there is a set of target graphs (strictly smaller than the set $\mathbf{D}$ of all graphs) that can be used to determine graph isomorphism; clearly this would imply my question. If such a set is well-known, then I would appreciate a hint or pointer.

  • B. Bollobás, L. Pebody, O. Riordan, Contraction-deletion invariants for graphs, JCTB 80, 2000, 320–345. doi:10.1006/jctb.2000.1988

There are at least two related MO questions: Complete graph invariants? and Invariants that might determine a graph up to isomorphism although these address a somewhat different question.

share|improve this question
    
Just so I get clear: we are talking graphs as digraphs with loops? and homomorphisms are certain maps of vertex sets? So that h(G,H)=1 and h(H,G)=0, with G being a graph having only one edge between its two vertices and H has only one loop on one of its two vertices? I can imagine the answer being different if homomorphisms were (based on) edge maps. Gerhard "Mucking With The Details Again" Paseman, 2013.06.04 –  Gerhard Paseman Jun 4 '13 at 21:07
    
There is also the issue of (v,u) in G COND (h(u),h(v)) in H, where COND could be either implies or iff, depending on how you like your graph map h from G to H. Gerhard "Rusty In Dealing With Relationships" Paseman, 2013.06.04 –  Gerhard Paseman Jun 4 '13 at 21:14
    
Usual notion of homomorphism, as in the Lovász paper: $u~v$ implies $f(u)~f(v)$. People don't seem to worry about loops and multi-edges in this context because it often seems easy to translate between the graph/multigraph cases with small tweaks. –  András Salamon Jun 5 '13 at 0:16
add comment

1 Answer

up vote 4 down vote accepted

It is true. It's Exercise 12 on page 128 of "Algebraic Graph Theory", by Royle and somebody. If I recall correctly (and I might not) the trick is to show that the number of homomorphisms determines the number of injective homomorphisms. [EDIT: as Andras notes, I should have said surjections.]

The result is quite old, and I am somewhat surprised that it's not in the paper of Lovász you cite.

share|improve this answer
    
Thanks for the explicit pointer, "somebody"! –  András Salamon Jun 4 '13 at 21:34
    
The "trick" is (for the left profile) in a retelling of Lovasz's result ("Algebras, Lattices, Varieties", Chapter 5). It is not clear to me that a corresponding trick exists for the right profile. Are you sure the exercise applies to the right profile? (It seems likely the same trick should work, but the light has yet to dawn on me.) Gerhard "Thinks Electric Bill Got Paid" Paseman, 2013.06.04 –  Gerhard Paseman Jun 4 '13 at 22:49
    
One switches sides, so one has to use surjections for the right-profile. When the number of surjective homomorphisms is always equal, then the graphs are isomorphic. So one just has to show that this holds when the right-profiles are identical. Partition the homomorphisms into those that are surjective on every subgraph of the target. The number of homomorphisms is the same, and the proper subgraphs lead to equal numbers by an inductive argument; the number of surjective homomorphisms is the difference, which is then equal for the two graphs. –  András Salamon Jun 5 '13 at 0:12
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.