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

Question

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.

Answer 1

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}$.

Answer 2

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.