Homomorphism complexes on three levels of abstraction

3 Jan 2025

Throughout this note, I assume that $G$ and $H$ are simple undirected graphs, and loops (i.e., edges of the form $uu$) are allowed. I will also not pay attention to the distinction between simplicial complexes and their geometric realisations, using topological notions freely for simplicial complexes.

My goal with this note is to give a brief overview of several constructions of topological spaces from graphs. I will pick a few of these constructions on various levels of abstraction — from purely combinatorial to deeply categorical. Each one of these will suit different audience, and you may pick your favourite one.

Before we get deeper, let me note that all of the constructions below assign to a graph $G$ a topological space $X$ with an additional involution $\nu$ (although in the case of the first complex $\nu^2$ is a retraction rather than the identity). Moreover, all constructions below are homotopy equivalent — even when we take this extra involution into account.

Level 1: Lovász’s neighbourhood complex

In his original proof of Kneser’s conjecture, Lovász used a construction which he called the neighbourhood complex. It is a rather straightforward way to construct a simplicial complex with the same vertex set as the original graph which nevertheless has interesting higher dimensional structure.

Definition (neighbourhood complex)
We define a simplicial complex $N(G)$ with vertices $V(G)$ whose faces are subsets of $V(G)$ which share a neighbour.

For example $N(K_3)$ is a border of a triangle, and hence homeomorphic to a sphere. Similarly, $N(K_4)$ is the surface of a tetrahedron, and more generally, $N(K_n)$ is the surface of the $(n-1)$-dimensional simplex, hence homoemorphic to the $(n-2)$-dimensional sphere $S^{n-2}$.

The key step in Lovász’s proof of Kneser’s conjecture is the following theorem.

Theorem 1 (Lovász, 1978)
If $N(G)$ is $(n-2)$-connected then $G$ is not $n$-colourable.

During the proof, Lovász constructs a continuous map $\nu\colon N(G) \to N(G)$ satisfying $\nu^3 = \nu$. This map is defined as a simiplicial map on the first barycentric subdivision $\operatorname{sd} N(G)$. The vertices of this subdivision are faces of $N(G)$, hence non-empty subsets of $V(G)$ which share a neighbour. Finally, we let \[ \nu(X) = \{ v \in V(G) \mid uv \in E(G) \text{ for all }u\in X \}. \] It may be observed that $\nu$ satisfies $\nu(X) \supseteq \nu(Y)$ if $X \subseteq Y$, and hence it is a simplicial map.

Having established the structure the rest of the proof goes as follows. First, Lovász using the $(n-2)$-connectedness shows that there is a continuous map $S^{n-1} \to N(G)$ which moreover satisfies $f(-x) = \nu(f(x))$. Next, he uses the Borsuk-Ulam theorem in the following formulation:

Theorem 2 (Borsuk, 1933)
If the $k$-dimensional sphere $S^k$ is covered with $k+1$ closed sets $F_1, \dots, F_k$, then one of the sets contains a pair of antipodal points.

Such a covering can be thought of as a “closed colouring” of $S^k$ with $k+1$ colours where each point can have several colours and the preimage of a each set of colours is closed. The neighbourhood complex of an $n$-colourable graph admits such a closed $n$-colouring by colouring a face $F$ with the colours of its neighbours. The map $S^{n-1} \to N(G)$ then lifts this colouring to $S^{n-1}$, and hence the Borsuk theorem yields a pair $x, -x$ of antipodal points with the same colour. In turn, we get that $f(x)$ and $\nu(f(x))$ have the same colour, which yields a monochromatic edge in $G$.

We often thing about groundbreaking results like this one as being a stroke of genius of the author, lifted above everything else that has been done at the same time. But that is not the case — no result exists on its own without the context it was created in! Earlier, Erdős and Hajnal constructed Borsuk graphs which have similar properties to Kneser graphs — Lovász learned the analogy between these graphs from Miklós Simonovits. The Borsuk graphs are constructed from a sphere by connecting nodes that are nearly antipodal.1 Hence a connection between spheres and high chromatic number was already established before Lovász started working on his proof.

In subsequent work, another refined construction took over the neighbourhood complex, namely the box complex. One of the advantages of this box complex is that the map $\nu$ is a proper involution unlike in the case of the neighbourhood complex. A brilliant overview of various definitions of box complexes, and its wider context was written by Matoušek and Ziegler [arXiv:math/​0208072], and there’s not much I could add to their work.

Level 2: Homomorphism complexes

I work on homomorphism problems, also known as the constraint satisfaction problems (CSPs). Hence, it is quite natural to consider homomorphism complexes instead of instead of the neighbourhood complex $N(G)$ or any variation on the box complex.

In our applications in the study of complexity of the promise graph homomorphism problem, we settled on using the homomorphism complex $\operatorname{Hom}(K_2, G)$. This complex has a few advantages over the box complex. Firstly, it generalises immediately to arbitrary relational structures, which is crucially important for applications in more general CSPs. Secondly, the involution $\nu$ is more apparent as it comes from the non-trivial automorphism of $K_2$ acting naturally on the complex.

There are a few ways how to define the homomorphism complex. For example, Babson and Kozlov [Isr. J. Math. 152 (2006), 285–312] define the complex as a certain polyhedral complex whose vertices are homomorphisms. On the other hand, Matoušek [Using the Borsuk-Ulam Theorem, doi:10.1007/​978-3-540-76649-0] defines a simplicial complex that is in effect the barycentric subdivision of the Babson–Kozlov polyhedral complex. I will stick with Matoušek’s definition here.

Definition (homomorphism complex)
The order complex of a poset $(P, \leq)$ is a simplicial complex whose vertices are elements of $P$ and faces are chains of $P$, i.e., subsets ${p_0, \dots, p_d}\subseteq P$ where $p_0 \leq \dots \leq p_n$.
The homomorphism complex $\operatorname{Hom}(G, H)$ is the order complex of the poset of multihomomorphisms $G \to H$. A multihomomorphism from $G$ to $H$ is a mapping $m \colon V(G) \to 2^{V(H)} \setminus \emptyset$ that maps edges to complete bipartite subgraphs, i.e., such that $m(u) \times m(v) \subseteq E(H)$ for all $uv \in E(G)$.

Let me reiterate that the simplicial complex $\operatorname{Hom}(K_2, G)$ is homotopy equivalent with the neighbourhood complex $N(G)$, and moreover there is a homotopy equivalence that commutes with the involution $\nu$.

The homomorphism complexes allow us to talk about “topology” of the solutions of a CSP. More precisely, given a graph (a structure) $A$, and an input $X$ of $\operatorname{CSP}(A)$, i.e., another graph (or a structure of the same signature. We may consider the homomorphism complex $\operatorname{Hom}(X, A)$ as the “space of solutions” of this CSP instance. There is ongoing research on how the possible topology of this space influences complexity of the problem. Two papers should be mentioned here:

In topological combinatorics, homomorphism complexes came into prominence through a conjecture of Lovász which was later confirmed by Babson and Kozlov [Annals of Mathematics, 165 (2007), 965–1007, doi:10.4007/​annals.2007.165.965] toghether with several follow-up improvements on the proof by Živaljević [arXiv:math/​0506075], Schultz [doi:10.1016/​j.aim.2009.03.006], and Kozlov [doi:10.1090/​S1079-6762-06-00161-2].

Theorem 3 (Babson & Kozlov, 2007)
If $\operatorname{Hom}(C_{2k+1}, G)$ is $(n-3)$-connected then $G$ is not $n$-colourable.

Note that the dimension differs from Lovász’ bound by one. Intuitively, the difference is caused by the use of the homomorphism complex of an odd-cycle which itself is 1-dimensional (the neighbourhood complex $N(C_{2k+1})$ is homeomorphic to the circle $S^1$). Curiously, even though the automorphism group of an odd cycle is bigger, the only additional structure on these odd-cycle complexes that is usually considered uses only the involution induced by flipping over an axis passing through a vertex and the opposite edge.

Finally, let me list the applications in computational complexity of (mostly promise) CSPs which are the papers that brought me to write this note in the first place.

Level 3: Kan’s simplicial nerve

Although the homomorphism complexes are clearly useful, they caused me some headaches during writing since the construction does not preserve products! It preserves products only up to homotopy equivalence, which is an idiosyncrasy that makes working with homomorphism complexes in the context of CSPs more troublesome. How to avoid this annoyance?

An algebraic answer would be to try to express the homomorphism complex as a pp-construction — for relational structures such a pp-construction is a logical interpretation in the primitive positive fragment of first-order logic, i.e., using only existential quantification, and conjunction. Nevertheless, a simplicial complex is not a first-order structure in the usual sense. Instead, in this setting is much more natural to use the categorical formalism of pp-constructions, and consider simplicial sets in place of simplicial complexes.

The right formalism can be found in Kan’s 1958 paper [Trans. Amer. Math. Soc. 87 (1958), 330-346]. Kan was investigating certain pairs of adjoints to the category of simplicial sets (at that time called complete semi-simplicial complexes). Considering the same functors between categories of relational structures yield the gadget reductions and pp-construction we so well known in the CSP context; gadget reductions are the left adjoints and pp-constructions are the right adjoints.

A simplicial set is a contravariant functor from the category $\Delta$ of finite non-empty ordinals with monotone maps to the category of sets. I will follow Kan’s notation for objects of $\Delta$ and let $[n] = (\{0, \dots, n\}, \leq)$. I will also denote by $X[n]$, the image of $[n]$ under $X$. The set $X[n]$ can be thought off as the set of $n$-dimensional faces of $X$.

Definition (Kan’s nerve)
Given an arbitrary category $\mathscr C$ and a covariant functor $\Gamma \colon \Delta \to \mathscr C$, Kan defines a functor $N_\Gamma$ from $\mathscr C$ to simplicial sets by \[ N_\Gamma(G)\colon [n] \mapsto \hom(\Gamma[n], G).\]
Extending this definition on morphisms is straightforward. The functor $N_\Gamma$ is called the nerve functor assigned to $\Gamma$.

For completeness, let me also say that a covariant functor from $\Delta$ to a category $\mathscr C$ is called a cosimplicial object of $\mathscr C$; a prime example is the cosimplicial topological space which assigns to $[n]$ the $n$-dimensional simplex. The corresponding nerve of this cosimplicial topological space is the usual topological nerve of a topological space. In case the category $\mathscr C$ is co-complete, the nerve has a left adjoint; in the case of the topological nerve, the left adjoint is the geometric realisation of the simplicial set. There is a lot to say, but we are getting distracted — let me return to the construction of simplicial sets from graphs.

According to Kan, we just need to provide a cosimplicial graph $\Gamma$. A natural choice would be to take digraphs $\Delta_{gr}[n]$ with vertices $\{0, \dots, n\}$ and edges $ij$ where $i\leq j$, i.e., transitive tournaments on $n+1$ vertices with loops. We may then define a simplicial set from a graph $G$ as $N_{\Delta_{gr}}(G)$. The trouble with this construction is that it results in the empty simplicial sets unless $G$ itself has a loop — it only talks about looped cliques inside $G$! This is not what we want. Instead, we make a slight change to the definition of the cosimplicial graph, and define a cosimplicial graph $\Gamma$ by \[ \Gamma[n] = \Delta_{gr}[n] \times K_2. \] The resulting space $N_\Gamma(G)$ is then only empty if $G$ has no edges. In fact, you may observe that it is homotopy equivalent to both the neighbourhood complex $N(G)$ and the homomorphism complex $\operatorname{Hom}(K_2, G)$. The main advantage of this construction is that $N_\Gamma$ preserves products, and hence provides a proper minion homomorphism!2

Lemma 4
There is a minion homomorphism $\operatorname{pol}(G, H) \to \operatorname{pol}(N_\Gamma(G), N_\Gamma(H))$.

Let me conclude with a note that the choice of the cosimplicial graph $\Gamma$ is essential here. We may obtain other homomorphism complexes by letting $\Gamma[n] = \Delta_{gr}[n] \times G$. This construction still relies on the right choice of the grounding cosimplicial graph $\Delta_{gr}[n]$ which appears natural in this setting, but it is not so clear which cosimplicial object should be taken for arbitrary relational structures. Are there any other interesting choices of cosimplicial graphs?

Note

Thanks to Tomáš Jakl for making me read Kan’s paper. Some omitted proofs will hopefully appear soon in our joint paper.

  1. Much later, Csorba [10.1007/​s00493-007-2204-x] investigated which complexes can appear as neighbourhood complexes of graphs, and these Borsuk graphs are closely related to Csorba’s construction applied to fine triangulations of a sphere. [return]
  2. Observe that, since the category of graphs is co-complete, the functor $N_\Gamma$ has a left adjoint; see also the previous footnote. [return]