On the hardness of 3-colouring H-colourable graphs

In 2019, me and Andrei Krokhin proved that colouring graphs that are promised to map homomorphically to a fixed (but arbitrary long) odd cycle with 3 colours is NP-hard [¹]. The original proof was a combinatorial argument based on some ideas of homotopy and a degree of a continuous endomap of a cycle. For that reason, we have included an overview of a topological intuition behind our combinatorial proof. Time has shown that this was a good decision since that intuition was immediately formalised by Marcin Wrochna and Standa Živný [²]. Since that paper appeared, I knew that Marcin’s and Standa’s proof of the statement is the right proof.

We have subsequently published a joined journal version of the two articles [³]. A lot of compromises were made when we wrote that paper; for example, it is not clear to me to this day who the target audience actually is. We tried to present relatively short but self-contained argument including all the definitions that a combinatorist might be unfamiliar with. We tried to avoid category theory at all cost, as well as any unnecessary definitions—including a definition of a relational structure. The result is a paper that is not easy to appreciate. In this note, I want to revisit this paper and highlight the key ideas, and explain some of the choices you may make when formalising the argument.

The proof

I am assuming that you know basics of promise CSPs, and are familiar with the content of the first four sections of [⁴], or the content of [⁵]. You may also check Andrei’s and mine survey on the topic [⁶].

The key to showing the NP-hardness of colouring graphs that map to an odd cycle with 3 colours is an analysis of polymorphisms of the template. The rest is a simple application of a known hardness condition. Where is the trouble? Well, there are simply too many polymorphisms, and there is no apparent structure to them. The main obstacle is to find any signal in this amount of noise. This is where homotopy gives the critical advantage. Two continuous maps are homotopic if one can be continuously transformed to the other. Homotopy of graph colourings is a discrete version of that.

Let us explain the proof on an example of 3-colouring graphs that map homomorphically to a 7-cycle. A polymorphism say from a 7-cycle to the 3-clique is just a 3-colouring of a power of the cycle like this one:

This is just one of them, there are more than 518,000 in total! For example, we can obtain a new polymorphism by changing a colour of a single vertex in the above picture — in quite a few cases there is just one colour in a neighbourhood of a vertex. Intuitively, such two polymorphisms don’t really differ much, so it is conceivable to think that they would carry the same information.

We may then intuit to say that two graph colourings are homotopic if one can be obtained from the other by changing a colour of a single vertex at a time. In combinatorics, this is sometimes called reconfiguration, but here I will stick with the name homotopy because what I want to do with it — use group invariants. Now, we are ready to explain the essence of the proof: take all polymorphisms $\operatorname{pol}(C_7, K_3)$ and factor them by homotopy to obtain a smaller minion $\operatorname{hpol}(C_7, K_3)$. It is quite easy to observe that the factor map \[ \operatorname{pol}(C_7, K_3) \to \operatorname{hpol}(C_7, K_3) \] is a minion homomorphism, i.e., it preserves minors. What is a bit harder is to see is that $\operatorname{hpol}(C_7, K_3)$ has bounded essential arity.

A recurring theme in mathematics is that continuous systems are easier to analyse and compute with, and that a lot can be learned by transforming from discrete systems to continuous ones. Take for example the Langlands program whose connection between number theory and elliptic curves brought us a proof of Fermat’s Last Theorem. In order to complete the last step of the proof, we do the same: We transfer from the discrete graphs $C_7$ and $K_3$ to topological spaces. This trick has a long history that goes back to Lovász’s proof of Kneser conjecture, but let us not get distracted with this at the moment. Lovász discovered a construction that assigns a topological space to a graph: odd cycles get assigned a circle $S^1$, curiously even cycles get assigned the space $S^1 + S^1$ consisisting of two disjoint copies of $S^1$, and a clique $K_n$ is assigned the $(n-2)$-dimensional sphere $S^{n-2}$. The critical observation is that Lovász’s construction is functorial, i.e., a graph homomorphism induces a continuous map between the two spaces, and moreover, it preserves homotopies, i.e., the two maps assigned to homotopic graph homomorphisms are homotopic as continuous maps (this relation was studied in detail by Wrochna [⁷]). In our case, we get a map \[ \operatorname{hpol}(C_7, K_3) \to \operatorname{hpol}(S^1, S^1). \] Naturally, we need to check that this map preserves minors, which is a technical exercise.

The final step is to analyse the homotopy classes of continuous polymorphisms of $S^1$. This is another place where homopty theory shine: $S^1$ is a space that is homotopically extremely simple! It is the classifying space $B\mathbb Z$, also known as the Eilenberg-MacLane space $K(1, \mathbb Z)$. This means that for each topological space $X$ we have a bijection \[ [X, S^1] \simeq H^1(X, \mathbb Z). \] Where $[X, S^1]$ denotes the set of homotopy classes of maps from $X$ to $S^1$ and $H^1(X, \mathbb Z)$ is a cohomology group of $X$, i.e., one of the basic group invariants of the space that you learn to compute during a basic course of algebraic topology. This means that in order to characterise maps into $S^1$ from a given space, we just need to compute the cohomology of $X$ which is an exercise for a student of algebraic topology. In our case, we are interested in maps from powers of $S^1$ which are $n$-dimensional tori $T^n$ (that is what topologists call powers of a circle). It is well-known that $H^1(T^n, \mathbb Z) \simeq \mathbb Z^n$.

One thing to note before we progress with the proof is that, for any space $X$, the assignment $[n] \mapsto H^1(X^n, \mathbb Z)$ is an abstract minion, i.e., there’s a natural map ${\cdot}^\sigma\colon H^1(X^n, \mathbb Z) \to H^1(X^m, \mathbb Z)$ for each $\sigma\colon [n] \to [m]$. In case of tori, this is given by summing the coefficients, as expected: the $i$-th coordinate of $t^\sigma$ is the sum of all coordinates of $t$ that are mapped to $i$ by $\sigma$. This is the same as taking coefficients of affine functions over $\mathbb Z$, hence the minion $\operatorname{hpol}(S^1, S^1)$ is isomorphic to the minion $\operatorname{pol}(\mathbb Z)$ of $\mathbb Z$-affine maps.

Altogether, we get a minion homomorphism \[ \operatorname{pol}(C_7, K_3) \to \operatorname{pol}(\mathbb Z). \] This is where the homotopy approach concludes, and the proof is finished by a simple combinatorial argument showing that the image has bounded arity since $\operatorname{pol}(C_7, K_3)$ contains only finitely many functions of any given arity (unlike $\operatorname{pol}(\mathbb Z)$).

Conclusion

There is a lot of freedom in the proof above, and it generalises well from graphs to other relational structures. We have used these ideas successfully to obtain NP-hardness of a version of hypergraph colouring [⁸]. In this latter proof, the homotopy calculations are a bit deeper, and it really shows that it is a well-developed theory that we can take advantage of at places where other (combinatorial) approaches fail.

In the proof, we made a lot of choices in the presentation. We have avoided category theory even though it can unite a lot of definitions throughout the proof. The only reason for that is that some people are alergic to category theory. We have presented homotopy through topological spaces. The reason is simply that that’s where homotopy theory is most developed and it’s easier for us to find references. Even through that, it was often hard to find a suitable reference for some basic typological statements that ‘everybody knows’.

It is also important to note that topological spaces can be completely avoided in the above proof if we find a different way into the homotopy category: We could define discrete homotopy on graphs staying quite in line with the original proof in [¹]. We could trace our way through simplicial sets (the homomorphism complex is naturally constructed through a poset of multihomomorphisms; it’s nerve is a simplicial set), and do all the homotopy computations there. All of these are implementation details that are technical, but rather dull. I believe that in the long term, the community will settle on some version of homotopy theory that will be both easy to use and strong-enough to prove anything we would like to use it for.