Graph colourings and Hedetniemi’s conjecture II: universal colouring

In my previous post, I stated the recently disproved Hedetniemi’s conjecture on colourings of product graphs (see this post for my conventions on graphs). In the next few posts, I will explain some of the ideas of the proof from an algebraic geometer’s perspective.

Today we will start with the universal colouring on G \times \mathbf{Hom}(G, K_n).

Lemma. Let G be a graph. Then there exists an n-colouring \phi_{\operatorname{univ}} on G \times \mathbf{Hom}(G, K_n) such that for every graph H and every n-colouring \phi on G \times H, there is a unique morphism f \colon H \to \mathbf{Hom}(G, K_n) such that f^*\phi_{\operatorname{univ}} = \phi.

Proof. By this post, we have the adjunction

(1)   \[\operatorname{Hom}(G \times H, K_n) \cong \operatorname{Hom}(H, \mathbf{Hom}(G, K_n)).\]

In particular, the identity \mathbf{Hom}(G,K_n) \to \mathbf{Hom}(G,K_n) gives an n-colouring \phi_{\operatorname{univ}} \colon G \times \mathbf{Hom}(G, K_n) \to K_n under this adjunction. If H is any other graph, (1) gives a bijection between morphisms H \to \mathbf{Hom}(G, K_n) and n-colourings of G \times H, which by naturality of (1) is given by f \mapsto f^* \phi_{\operatorname{univ}} := \phi_{\operatorname{univ}} \circ (\operatorname{id}_G \times f). \qedsymbol

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case H = \mathbf{Hom}(G,K_n), for every n and every loopless graph G.

Proof. Suppose by contradiction that there is a counterexample (G,H), i.e. there are loopless graphs G and H such that

(2)   \[n = \chi(G \times H) < \min(\chi(G), \chi(H)).\]

Then there exists an n-colouring \phi \colon G \times H \to K_n, so the lemma gives a map f \colon H \to \mathbf{Hom}(G,K_n) such that \phi = f^*\phi_{\operatorname{univ}}. This forces \chi(H) \leq \chi(\mathbf{Hom}(G,K_n)) since an m-colouring on \mathbf{Hom}(G,K_n) induces an m-colouring on H by pullback. Thus, (2) implies

    \[\chi(G \times \mathbf{Hom}(G,K_n)) \leq n < \min(\chi(G),\chi(H)) \leq \min(\chi(G), \chi(\mathbf{Hom}(G,K_n))),\]

showing that (G,\mathbf{Hom}(G,K_n)) is a counterexample as well. \qedsymbol

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph G and any n \in \mathbf Z_{>0}, either G or \mathbf{Hom}(G,K_n) admits an n-colouring. \qedsymbol

Example. By the final example of my previous post and the proof of the first corollary above, the cases n \leq 2 are trivially true. We can also check this by hand:

  • If G does not have a 1-colouring, then it has an edge. Then \mathbf{Hom}(G,K_1) has no edges by construction, since K_1 has no edges. See also Example 2 of this post.
  • If G does not have a 2-colouring, then it has an odd cycle C_m \subseteq G. We need to produce a 2-colouring on \mathbf{Hom}(G,K_2). Choose identifications V(K_2) \cong \mathbf Z/2 and V(C_m) \cong \mathbf Z/m with adjacencies \{i,i+1\}. Consider the map

        \begin{align*}\Sigma \colon \mathbf{Hom}(G,K_2) &\to K_2\\f &\mapsto \sum_{c \in C_m} f(c) \in \mathbf Z/2.\end{align*}

    To show this is a graph homomorphism, we must show that for adjacent f, g we have \Sigma(f) \neq \Sigma(g). If two maps f, g \colon G \to K_2 are adjacent, then for adjacent x, y \in G we have f(x) \neq g(y). Taking (x,y) = (c_i, c_{i+1}) shows that f(c_i) = g(c_{i+1}) + 1, so

        \[\Sigma(f) = \sum_{i = 1}^m f(c_i) = \sum_{i=1}^m \Big(g(c_{i+1}) + 1 \Big) = \Sigma(g)  + 1 \in \mathbf Z/2,\]

    since m is odd. \qedsymbol

The case n = 3 is treated in [EZS85], which seems to be one of the first places where the internal Hom of graphs appears (in the specific setting of \mathbf{Hom}(-,K_n)).


References.

[EZS85] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5.2, p. 121–126 (1985).

Graph colourings and Hedetniemi’s conjecture I: statement of conjecture

The past three posts have been building up to the statement of the recently disproved Hedetniemi’s conjecture. I wanted to make an attempt to write about this, because from a first reading the main ideas of the counterexample seemed very familiar to an algebraic geometer. (More about this in a future post, hopefully.)

Definition. A colouring of a loopless graph G with n colours is a graph homomorphism G \to K_n. The chromatic number \chi(G) of G is the smallest positive integer n such that G admits a colouring with n colours.

Note that if G has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is \chi(G) \leq \# V(G), since G is a subgraph of the complete graph on V(G).

Example. We have \chi(G) = 1 if and only if G has no edges (we say that G is discrete), and \chi(G) \leq 2 if and only if G contains no odd cycles (we say that G is bipartite). Indeed, if you try to produce a 2-colouring by colouring adjacent vertices opposite colours, either this produces a 2-colouring or you find an odd cycle.

Conjecture (Hedetniemi). Let G and H be graphs. Then

    \[\chi(G \times H) = \min(\chi(G), \chi(H)).\]

Remark. Note that \chi(G \times H) \leq \min(\chi(G), \chi(H)): if G \to K_n is a colouring, then the composition G \times H \to G \to K_n is a colouring of G \times H, and similarly for H. Thus, it remains to rule out \chi(G \times H) = n with \chi(G) > n and \chi(H) > n.

Example. The case where \chi(G \times H) \leq 2 is easy to check:

  • If \chi(G) > 1 and \chi(H) > 1, then both G and H have an edge, hence so does G \times H. Then \chi(G \times H) > 1.
  • If \chi(G) > 2 and \chi(H) > 2, then both G and H contain an odd cycle. If G has an n-cycle and H an m-cycle with n and m odd, then these give morphisms C_n \to G and C_m \to H. Wrapping around m (resp. n) times gives morphisms C_{mn} \to G, C_{mn} \to H, hence to the product: C_{mn} \to G \times H. Thus, G \times H does not admit a 2-colouring since C_{mn} doesn’t.

Thus, if \chi(G \times H) \leq 2, then \chi(G \times H) = \min(\chi(G), \chi(H)).

Internal Hom in the category of graphs

In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

Definition. Let G and H be graphs. Then the graph \mathbf{Hom}(G, H) has vertices \operatorname{Map}(V(G), V(H)), and an edge from f \colon V(G) \to V(H) to g \colon V(G) \to V(H) if and only if \{x,y\} \in E(G) implies \{f(x), g(y)\} \in E(H) (where we allow x = y as usual).

Lemma. If G, H, and K are graphs, then there is a natural isomorphism

    \[\operatorname{Hom}(G \times H, K) \stackrel\sim\to \operatorname{Hom}(G, \mathbf{Hom}(H, K)).\]

In other words, \mathbf{Hom}(H,K) is the internal Hom in the symmetric monoidal category (\mathbf{Grph}, \times).

Proof. There is a bijection

    \begin{align*}\alpha \colon \operatorname{Map}(V(G), V(\mathbf{Hom}(H, K))) &\stackrel\sim\to \operatorname{Map}(V(G \times H), V(K))\\\phi &\mapsto \bigg((g,h) \mapsto \phi(g)(h)\bigg).\end{align*}

So it suffices to show that \phi is a graph homomorphism if and only if \psi = \alpha(\phi) is. The condition that \phi is a graph homomorphism means that for any \{x,y\} \in E(G), the functions \phi(x), \phi(y) \colon V(H) \to V(K) have the property that \{a,b\} \in E(H) implies \{\phi(x)(a), \phi(y)(b)\} \in E(K). This is equivalent to \{\psi(x,a),\psi(y,b)\} \in E(K) for all \{x,y\} \in E(G) and all \{a,b\} \in E(H). By the construction of the product graph G \times H, this is exactly the condition that \psi is a graph homomorphism. \qedsymbol

Because the symmetric monoidal structure on \mathbf{Grph} is given by the categorical product, it is customary to refer to the internal \mathbf{Hom}(G,H) as the exponential graph H^G.

Example 1. Let S^{\operatorname{disc}} be the discrete graph on a set S. Then \mathbf{Hom}(S^{\operatorname{disc}}, K) is the complete graph with loops on the set V(K)^S. Indeed, the condition for two functions f, g \colon S \to V(K) to be adjacent is vacuous since S^{\operatorname{disc}} has no edges.

In particular, any function V(G) \to V(\mathbf{Hom}(S^{\operatorname{disc}}, K)) is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function V(G \times S^{\operatorname{disc}}) \to V(H) is a graph homomorphism, since G \times S^{\operatorname{disc}} is a discrete graph.

Example 2. Conversely, \mathbf{Hom}(H, S^{\operatorname{disc}}) is discrete as soon as H has an edge, and complete with loops otherwise. Indeed, the condition

    \[\{x,y\} \in E(H) \Rightarrow \{f(x),g(y)\} \in E(S^{\operatorname{disc}}) = \varnothing\]

can only be satisfied if E(H) = \varnothing, and in that case is true for all f and g.

In particular, a function V(G) \to V(\mathbf{Hom}(H, S^{\operatorname{disc}})) is a graph homomorphism if and only if either G or H has no edges. Under the adjunction above, this corresponds to the fact that a function V(G \times H) \to S is a graph homomorphism to S^{\operatorname{disc}} if and only if G \times H has no edges, which means either G or H has no edges.

Example 3. Let S^{\operatorname{loop}} be the discrete graph on a set S with loops at every point. Then \mathbf{Hom}(S^{\operatorname{loop}}, K) = K^S is the S-fold power of K. Indeed, the condition that two functions f, g \colon S \to V(K) are adjacent is that \{f(s), g(s)\} \in E(K) for all s \in S, which means exactly that \{\pi_s(f), \pi_s(g)\} \in E(K) for each of the projections \pi_s \colon K^S \to K.

In particular, graph homomorphisms f \colon G \to \mathbf{Hom}(S^{\operatorname{loop}}, K) correspond to giving S graph homomorphisms f_s \colon G \to K. Under the adjunction above, this corresponds to the fact that a graph homomorphism g \colon G \times S^{\operatorname{loop}} \to K is the same thing as S graph homomorphisms g_s \colon G \to K, since G \times S^{\operatorname{loop}} is the S-fold disjoint union of G.

Example 4. Let * = \{\operatorname{pt}\}^{\operatorname{loop}} be the terminal graph consisting of a single point with a loop (note that we used * instead for \{\operatorname{pt}\}^{\operatorname{disc}} in this earlier post). The observation above that G \times * \cong G also works the other way around: * \times G \cong G. Then the adjunction gives

    \[\operatorname{Hom}(G, K) \cong \operatorname{Hom}(*, \mathbf{Hom}(G,K)).\]

This is actually true in any symmetric monoidal category with internal hom and identity object *. We conclude that a function f \colon V(G) \to V(K) is a graph homomorphism if and only if \mathbf{Hom}(G, K) has a loop at f. This is also immediately seen from the definition: \mathbf{Hom}(G, K) has a loop at f if and only if \{x,y\} \in E(G) implies \{f(x), f(y)\} \in E(H).

Example 5. Let K_n and K_m be the complete graphs on n and m vertices respectively. Then \mathbf{Hom}(K_n, K_m) has as vertices all n-tuples (a_1,\ldots,a_n) \in \{1,\ldots,m\}^n, and an edge from (a_1,\ldots,a_n) to (b_1,\ldots,b_n) if and only if a_i \neq b_j when i \neq j. For example, for n = 2 we get an edge between (a_1, a_2) and (b_1, b_2) if and only if a_1 \neq b_2 and a_2 \neq b_1.