# Why are homomorphisms of graphs/relations defined the way they are?

Dealing with relations and functions in a set theoretic context i.e. as just sets of ordered pairs, note for any relations $$R$$ and $$L$$ that for any given function $$f$$ we have:

$$\forall x,y\in \text{dom}(f)\left(xRy\implies f(x)Lf(y)\right)\iff f^{-1}\circ L\circ f\supseteq R\cap\text{dom}(f)^2$$ $$\forall x,y\in \text{dom}(f)\left(f(x)Lf(y)\implies xRy\right)\iff f^{-1}\circ L\circ f\subseteq R\cap\text{dom}(f)^2$$ $$\forall x,y\in \text{dom}(f)\left(xRy\iff f(x)Lf(y)\right)\iff f^{-1}\circ L\circ f=R\cap\text{dom}(f)^2$$

With that said, why define the first one to be say a homomorphism in the context of graph theory?

Are the latter two notions less important then the first one? If so, why?

Reading the page on nlab: https://ncatlab.org/nlab/show/relation#morphisms it says that:

In general, it's more natural to require only preservation; these are the morphisms you get if you consider a set with a relation as a models of a finite-limit theory or a simply directed graph.

Though I don't really understand why this makes the first notion more natural, if someone could elaborate on why this is more natural for me I would really appreciate it.

To begin with, homomorphisms of graphs are not as important to graph theory as, for example, homomorphisms of groups are important to group theory. They show up occasionally, but I think people coming from an abstract algebra background tend to overemphasize them.

It's much more frequent to encounter subgraphs. We can say that $$G$$ is a subgraph of $$H$$ iff there is an injective homomorphism from $$G$$ to $$H$$, which motivates your first notion. That being said, an injective $$f : V(G) \to V(H)$$ that satisfies your third property gives us an induced copy of $$G$$ in $$H$$, so that one's not too bad either.

There are at least two more important notions in graph theory that are captured by graph homomorphisms:

• A walk of length $$n$$ in $$G$$ is a homomorphism from a path graph with $$n$$ edges to $$G$$.
• A $$k$$-coloring of $$G$$ is a homomorphism from $$G$$ to a clique $$K_k$$.

So we like the first notion best because it has the most applications to things we actually care about.

Your second notion is not interesting for graphs in particular, because it doesn't add anything new: a function $$f: V(G) \to V(H)$$ satisfies the second property iff $$f$$ is a homomorphism from the complement $$\overline{G}$$ to the complement $$\overline{H}$$.

• In regards to your last comment, wouldn't that just mean the second notion is equally strong as the first one? Since you can express either in terms of the other, using graph complements. – Ethan Jan 21 at 23:31
• Right - that comment is not an argument for why the second notion is worse than the first, just an argument for why we shouldn't keep both. – Misha Lavrov Jan 22 at 0:01
• And since the third can be expressed in terms of one and two, which can be expressed in terms of either one or two, all three can then be expressed in terms of the first notion or the second notion, so it suffices to study just one or two if we want to study all three? Is that the underlying argument? – Ethan Jan 22 at 0:05
• Most of my argument is that the first notion is the one that actually appears in things we want to describe in practice. But that's certainly a factor, yes. (If the second notion appeared very often, though, we'd keep it around even though it can be expressed in terms of the first. For example, we have a word for closed sets even though they're just complements of open sets.) – Misha Lavrov Jan 22 at 0:07

I think the nLab passage is making things more mysterious than they need to be: the key point is that this definition of homomorphism is the one which generalizes the usual notion of homomorphism of functional structures appropriately.

Let's consider, say, magma homomorphisms. A magma is just a set with a binary operation; given magmas $$\mathcal{A}=(A,*)$$ and $$\mathcal{B}=(B, +)$$, a homomorphism $$h$$ from $$\mathcal{A}$$ to $$\mathcal{B}$$ "obviously" needs to satisfy $$h(x*y)=h(x)+h(y).$$

Now, the point is that functions can be thought of as special kinds of relations. Specifically, a function $$f$$ is "equivalent to" in some sense its graph, $$\{(a_1,...,a_n,b): f(a_1,...,a_n)=b\}$$. When we "relationize" a magma, we're looking at a set with a ternary relation $$R$$ on it, and the homomorphism condition above turns into $$R_*(x,y,z)\implies R_+(h(x),h(y),h(z)).$$ That is, equality preservation corresponds to relation preservation. Meanwhile, the above implication clearly doesn't reverse in general.

This motivates the definition of homomorphism, not just for graphs, but for arbitrary first-order structures: preserve equality of terms, and preserve instances (but not necessarily non-instances) of relations.

• If we write $R_{*}(x,y,z)\iff x*y=z$ and $R_{+}(a,b,c)\iff a+b=c$ then its clearly to me that if $h$ is a homomorphism from $\mathcal{A}$ to $\mathcal{B}$ then we have $R_{*}(x,y,z)\implies R_{+}(h(x),h(y),h(z))$. However I don't see how having $R_{*}(x,y,z)\implies R_{+}(h(x),h(y),h(z))$ alone, would imply $h$ is a homomorphism from $\mathcal{A}$ to $\mathcal{B}$. Am I misunderstanding what you wrote? – Ethan Jan 21 at 23:17