Graph Homomorphisms and Cores

Today I’d like to talk about an open problem I’ve been interested in for the past couple of years. It’s a very hard problem, in that there are easier special cases that are famously unapproachable, but it makes for some rather pretty algebra, living at the intersection of graph theory and category theory. If you ask me, it’s too good to be false.

A graph homomorphism $f : G \to H$ between two (simple) graphs $G$ and $H$ is a function $f : V(G) \to V(H)$ of the vertices that preserves edges, i.e. such that if $uv \in E(G)$, then $f(u) f(v) \in E(H)$. If you want to see a couple of professionals handle these bad boys, I would heartily recommend flipping open Chapter 6 of Algebraic Graph Theory by Godsil and Royle.

This is an appropriate notion of morphism for a category $\mathsf{Graph}$ of graphs, for a number of reasons, not least of which is that the iso arrows are the usual graph isomorphisms. We will see this category rear its head again and again, in more or less obvious ways, but that won’t be important until much later.

A homomorphism $f : G \to H$ partitions $V(G)$ into fibres $f^{-1}(v) = \{ u \in V(G) : f(u) = v \}$, one for each $v \in V(H)$. If two vertices of $G$ fall into the same fibre, they cannot be adjacent, because otherwise $H$ would have a loop edge. So each fibre is a coclique¹. Consequently, a homomorphism $G \to K_n$ is an $n$-colouring of the graph $G$, and it doesn’t take too much imagination to view homomorphisms as a generalization of graph colouring.

You can restate a number of other interesting graph theoretical conditions in terms of homomorphisms as well. For example, $K_n \to G$ iff $G$ has an $n$-clique, so we can talk about the clique number $\omega(G)$. Odd girth—the length of the shortest odd cycle in $G$–is another example. Even cycles are bipartite, so $C_{2k} \to K_2 \to G$ so long as $G$ is nonempty, but with an odd cycle $C_{2k+1}$, you have to wrap it around a smaller odd cycle, so e.g. if $G$ is triangle-free then $C_3 \not\to G$.

Now define a relation $\to$ on the set of graphs $\def\G{\mathcal G}\G$ by saying $G \to H$ if there exists a homomorphism from $G$ to $H$. This relation is a preorder on $\G$, that is, it’s reflexive and transitive. It’s not a partial order, though, even up to isomorphism: as we saw just a moment ago, $C_{2k} \to K_2$ and $K_2 \to C_{2k}$. More generally, $\to$ will confuse any nonempty bipartite graph for $K_2$, and likewise if $\chi(G) = \omega(G) = n$ then $G \to K_n$ and $K_n \to G$.

---

When faced with a preorder, a standard trick is to quotient out by equivalence relation generated by the preorder, and look at the resulting partial order. In our case, the equivalence relation is called hom-equivalence $\def\fromto{\leftrightarrow}\fromto$. Technically, all of my statements from now on should be about $(\G/{\fromto}, {\to})$, but because hom-equivalence respects most of our intuition, I will often talk about the graphs themselves and not their hom-equivalence classes.

So now we’re living in a poset, $(\G/{\fromto}, {\to})$. Let’s try to understand its structure. As of late, my favourite objects on this ‘blog have been lattices, so it should come as no surprise that $(\G/{\fromto}, {\to})$ is a lattice. What may be more surprising is what the meet and join are.

Recall that a lattice is a poset such that every pair of elements has a greatest lower bound, called a meet, and a least upper bound, called a join. In our case, we have a slightly nonstandard order $\to$, so in the intuitive picture of something being ‘above’ or ‘greater than’ another, I am considering the codomain to be above the domain, i.e. $({\to}) \approx ({\le})$.

First off, let’s try to figure out the join. That is, for two graphs $G$ and $H$, we want a graph $J$ such that $J \to X$ iff $G \to X$ and $H \to X$. In particular, $J \to J$, so we should have $G \to J$ and $H \to J$.

The most brain-dead thing to try that obviously has this property is the disjoint union $G + H$. If $G + H \to X$ then we can clearly read off a pair of homs $G \to X$ and $H \to X$. Similarly, if $g : G \to X$ and $h : H \to X$, then the way to construct a hom $G + H \to X$ is to simply send the $G$-half via $g$ and the $H$-half via $h$. So this poset has a join, namely disjoint union.

Now, let’s consider the meet. It’s a bit of a counterintuitive answer, but I have to tell you what it is because I will make use of it later.

Define the graph $G \times H$ by taking the vertex set $V(G \times H) = V(G) \times V(H)$, and the edge set

$$E(G \times H) = \{ (g,h)(g',h') : gg' \in E(G)\ \text{and}\ hh' \in E(H) \}.$$

This graph is variously called the direct product, tensor product, or categorical product of the two graphs $G$ and $H$. The two projection maps $\pi_G$ and $\pi_H$ to the coordinates of the vertex set are in fact surjective graph homomorphisms onto the factors.

Proposition. If $g : X \to G$ and $h : X \to H$, then there is a homomorphism $f : X \to G \times H$ such that $g = \pi_G \circ f$ and $h = \pi_H \circ f$.

Proof. Define $f$ by $f(x) = (g(x),h(x))$ for each $x \in V(X)$. This is a homomorphism if both $g$ and $h$ are, and it is very explicit that postcomposing projection maps recovers $g$ and $h$. ∎

It follows that the direct product $\times$ is the meet in our poset, and hence it is a lattice.

Theorem. The hom-equivalence classes of graphs form a lattice. ∎

---

The next step in grokking this lattice $(\G/{\fromto},{\to},{\times},{+})$ will be to get a better handle on its elements. Specifically, I would like to find a collection of interesting representatives for the hom-equivalence classes, much like the representatives $\{0,...,n-1\}$ for $\def\Z{\mathbb Z}\Z/n\Z$. By the serendipity of analogy, it will turn out that the vertex-minimal elements of each hom-equivalence class will have exceptional structure.

Theorem. Graphs in a hom-equivalence class having the minimum number of vertices are determined up to isomorphism by the hom-equivalence class.

Proof. Let $G \fromto H$ be two graphs with the minimum number of vertices for their hom-equivalence class. Let $f : G \to H$ and $g : H \to G$ be homomorphisms. By the minimality condition, both $f$ and $g$ must be surjective, so $g \circ f : G \to G$ is a surjective endomorphism, that is, an automorphism. Then $f$ has two-sided inverse $(g \circ f)^{-1} \circ g$, and it follows that $G \cong H$. ∎

The unique-up-to-isomorphism graph of a hom-equivalence class $[G]$ is called the core $G^\bullet$. It turns out cores are particularly susceptible to this sort of minimality argument, which give them a number of algebraically pleasing properties.

Exercise. $G^\bullet$ is isomorphic to an induced subgraph of $G$.

With this result in hand, I will immediately abuse notation to say that $G^\bullet$ is an induced subgraph of $G$.

Theorem. A graph $G$ is a core iff $\def\End{\mathrm{End}}\def\Aut{\mathrm{Aut}}\End(G) = \Aut(G)$.

Proof. Suppose $G$ is a core, and let $f \in \End(G)$ be an endomorphism, that is, a homomorphism $f : G \to G$. If $f$ is not an automorphism of $G$, then it fails to be surjective, which contradicts minimality. Conversely, suppose $G$ is a graph such that $\End(G) = \Aut(G)$. By the previous exercise, $G^\bullet$ embeds into $G$. There exists an endomorphism $G \to G^\bullet$, and by hypothesis it is an automorphism, so $G \cong G^\bullet$ and hence $G$ is a core. ∎

This is just the tip of the iceberg, though it is enough for now. There is a lot of great stuff on cores that I will eventually get to, but I have a particular goal this time.

The question I have is a simple one. The poset $(\G^\bullet,{\to})$ of cores is isomorphic to the lattice $(\G/{\fromto},{\to})$ of hom-equivalence classes. So what is the lattice structure on $(\G^\bullet,{\to})$?

In one sense, it’s easy to describe. For $X, Y \in \G^\bullet$, $X$ meet $Y$ is just $(X \times Y)^\bullet$, and same with the join. But I claim we can do a bit better than that.

First off, given two cores $X$ and $Y$, either they are comparable or not. If $X \to Y$, then it’s not very hard to see that $X \times Y \fromto X$ and $X + Y \fromto Y$. So we may assume that $X$ and $Y$ are hom-incomparable cores.

Let me show you a result about disjoint unions of cores which we can use to attack this problem.

Lemma. If $X$ and $Y$ are connected hom-incomparable cores, then $X + Y$ is a core.

Proof. Consider an endomorphism $f : X + Y \to X + Y$. By the universal property of disjoint unions, this is determined by the two homomorphisms $g = f \circ \iota_X : X \to X + Y$ and $h = f \circ \iota_Y : Y \to X + Y$. Since $X$ is connected, $g$ sends $X$ to one of the two components of $X + Y$. But then by hom-incomparability, $X \not\to Y$, so $g$ is essentially an endomorphism of $X$. $X$ is a core, so $\End(X) = \Aut(X)$ and $g$ is an isomorphism of $X$ and the $X$ component of the disjoint union. By symmetry, $h$ is also an isomorphism of $Y$ onto the $Y$-component of $X + Y$, and hence $f$ must be an automorphism. $\End(X + Y) = \Aut(X + Y)$, so $X + Y$ is a core. ∎

If you think about it for a bit, this tells us that really the only thing that can go wrong is that if $A \to A'$, then $(A + B) + (A' + C) \fromto A' + B + C$. So if $X$ and $Y$ are cores, then $(X + Y)^\bullet$ consists of the $\to$-maximal connected components of $X + Y$. That is what I consider a satisfactory answer: aside from the NP-complete problem of hom-existence between different components, we algebraically know exactly what the core is in terms of the factors.

---

So you might look at that and be optimistic about the dual case. We just need a similar lemma for the direct product—something to do with $\times$-irreducible hom-incomparable cores. Then we can just decompose all cores into their $\times$-factorizations and use our lemma a bunch!

Well, let’s not get hasty. $\times$-factorization doesn’t actually make sense in general!

Exercise. Show that $P_4 \times K_3 \cong K_2 \times G$ for some $\times$-irreducible graph $G$, where $P_4$ is the path on four vertices.

So you have a moment of panic, and then gather your thoughts and say, “Surely this is in the literature!” Well, yes, it is. Chapter 8 of the Handbook of Product Graphs, by Hammack, Imrich, and Klavžar, is all you need to know about direct product factorization, and in fact section 8.5 proves that the connected nonbipartite graphs have unique factorization in the graphs-with-loops.

“Okay, that’s a bit weird. Is that workable? Can we look at the proof and modify it?” Well, maybe. I don’t know yet. It’s kinda gross because the dependencies go back to the start of Chapter 7, and the Handbook is not light bedtime reading. Digesting it is on my to-do list, but nowhere near the top.

I have asked MathOverflow about this and they don’t seem to know either. In fact, in a way that is easy to see but hard to formally state, this question is stronger than the following open problem:

Conjecture (Hedetniemi, 1966). For all graphs $G$ and $H$, $\chi(G \times H) = \min\{\chi(G),\chi(H)\}$.

It’s worth noting that the chromatic number of a product is easily upper bounded by that of both factors, because of the projection maps, so most of the work is trying to see that bound hold tightly. Currently, we know this conjecture is true when either of $G$ or $H$ is 4-colourable. If you want some reading material on this topic, the Wikipedia page has a pretty good list of references. The following paper in particular looks at Hedetniemi’s conjecture from the hom perspective.

Häggkvist et al. On multiplicative graphs and the product conjecture. Combinatorica (1988) 8: 63. doi:10.1007/BF02122553

Another thing MO pointed out to me was some more categorical ideas involving map graphs (don’t look this one up on Wikipedia, it’s something different). The point is that, not only is the direct product the product of the category of graphs and graph homs, but it has an exponential object with respect to this product. That route seems even less workable if you look closely, but I haven’t fully convinced myself the approach is useless.

---

It appears that I’ve run out the clock on actually explaining any more of this in more detail. I definitely have a lot more I’d like to say, but this is a pretty good introduction to the core problem. Each of the directions to proceed from here could fill a post or two of their own, so I think I’ll do that and refer back to this post as material to set the scene.

To end off on a high note, let me present some good news. The smallest pair of hom-incomparable graphs is $K_3$ and the Grötzsch graph $G$ on 11 vertices. $G$ is $\times$-irreducible, because 11 is a prime number, so we should expect that $K_3 \times G$ is a core. This graph has 33 vertices, which is a lot when you’re asking about cores, but running the world’s laziest SageMath code for a week has confirmed that, yes, $K_3 \times G$ is a core.

The next pair of hom-incomparable $\times$-irreducible cores I can think of are the Möbius ladder $M_8$ and the Petersen graphs, whose product comes to 80 vertices, but I don’t own any supercomputers yet, so trying to figure out a more efficient way to test for that is yet another interesting direction to explore.