Cut-homotopies and the complexity
of edge-coloring problems
January 01, 1970
Abstract
We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We show that every such problem is poly-time equivalent to a Constraint Satisfaction Problem, yielding a P vs.NP-complete dichotomy. Our main contribution lies in the reduction from the CSP to the coloring problem where we apply methods from Ramsey theory and a novel notion of cut-homotopy.
1 Introduction↩︎
Fix a finite family \(\mathcal{F}\) of edge-colored graphs and let \(A\) be the set of occurring colors. Let \(\mathop{\mathrm{Col}}(\mathcal{F})\) be the following computational problem:
Is there an edge-coloring of a given input graph using colors from \(A\) so that no member of \(\mathcal{F}\) appears as an induced edge-colored subgraph?
If there is such an edge-coloring we refer to it as an \(\mathcal{F}\)-free coloring. Clearly, every such problem \(\mathop{\mathrm{Col}}( \mathcal{F})\) is contained in NP; moreover, a recent result due to Kun and Nešetřil [1] asserts that the class of computational problems arising in this fashion is NP-rich. In search of subclasses avoiding NP-richness a natural next step is therefore to restrict the shape of forbidden graphs. In the present paper, we consider the case where every member of \(\mathcal{F}\) is a colored clique. One of the earliest works in this direction dates back to Garey and Johnson’s list of NP-complete problems [2] which contains the problem \(\mathop{\mathrm{Col}}(\mathcal{F})\), where \(\mathcal{F}\) consists of monochromatic triangles in two colors. Later, this was extended to monochromatic cliques of arbitrary size \(\geq 3\) [3] and to arbitrarily many colors [4], [5]. We extend these hardness results to a P vs.NP-complete dichotomy for \(\mathop{\mathrm{Col}}(\mathcal{F})\), when \(\mathcal{F}\) consists of arbitrary edge-colored cliques.
Theorem 1. For every finite family \(\mathcal{F}\) of edge-colored cliques, the problem \(\mathop{\mathrm{Col}}(\mathcal{F})\) is either solvable in polynomial time or NP-complete.
Such coloring problems with forbidden cliques can be expressed in GMSNP, a logic capturing more general coloring problems. It was introduced independently in [6], [7] and has been studied extensively in subsequent work [8]–[16]. Our result makes progress on the question whether GMSNP admits a complexity dichotomy, raised in [6]. It also makes progress on the Bodirsky–Pinsker conjecture [17] predicting a P vs.NP-complete dichotomy for an even more general class of forbidden-pattern coloring problems. Despite intense development of the theoretical tools to tackle such problems [18]–[27], see also [28], a proof of the general conjecture—while being verified for various subclasses [14]–[16], [19], [29]–[37]—still seems to be out of reach. One fundamental challenge lies in overcoming the problem of coloring with more than two “relevant” colors. This is exemplified by the fact that it proves to be a core challenge in a unified approach to the above dichotomies initiated in [19]. For further discussion of this challenge, we refer the reader to the concluding discussion in [15].
1.1 An upper bound for the complexity↩︎
The constraint satisfaction problem associated to a relational structure \(\mathbb{A}\),1 denoted by \(\operatorname{CSP}(\mathbb{A})\) for short, is the computational problem of deciding whether a given structure \(\mathbb{X}\) admits a homomorphism to \(\mathbb{A}\). Each problem \(\mathop{\mathrm{Col}}(\mathcal{F})\) admits a simple reduction to the CSP of a suitably chosen structure \(\mathbb{A}\), whose domain is the set \(A\) of colors and whose relations encode the \(\mathcal{F}\)-free colorings of cliques. Given a graph \(G\), we construct a structure \(\hat{G}\) in the same signature as \(\mathbb{A}\), whose domain is the set of edges of \(G\) and whose relations encode the cliques contained in \(G\). The relations of both \(\mathbb{A}\) and \(\hat{G}\) are chosen precisely, so that \(\mathcal{F}\)-free colorings of \(G\) are exactly the homomorphisms \(\hat{G}\to \mathbb{A}\). As such, the assignment \(G \mapsto \hat{G}\) is a poly-time reduction from \(\mathop{\mathrm{Col}}(\mathcal{F})\) to \(\operatorname{CSP}(\mathbb{A})\). Further, CSPs admit a P vs.NP-complete dichotomy [38]–[40], so in order to prove Theorem 1 it suffices to show that \(\mathop{\mathrm{Col}}(\mathcal{F})\) is NP-complete, whenever the corresponding \(\operatorname{CSP}(\mathbb{A})\) is.
Let \(\mathcal{F}\) contain monochromatic triangles in two colors. The corresponding structure \(\mathbb{A}\) is boolean, with a ternary relation consisting of all non-monochromatic colorings of the triangle: \[\{(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)\}.\] In this case, \(\operatorname{CSP}(\mathbb{A})\) is the classical NotAllEqual-SAT problem.
1.2 Polymorphisms and cut-homotopies↩︎
To every \(\operatorname{CSP}(\mathbb{A})\), one can associate a structure \(\operatorname{Pol}(\mathbb{A})\), the polymorphism minion of \(\mathbb{A}\), which determines its complexity up to log-space reductions [41]. Polymorphisms are homomorphisms \(\mathbb{A}^n \to \mathbb{A}\) and they allow combining solutions of \(\operatorname{CSP}(\mathbb{A})\). Namely, given an \(n\)-tuple \(\mathbb{X}\to \mathbb{A}^n\) of solutions to a given input \(\mathbb{X}\), composing with a polymorphism \(\mathbb{A}^n \to \mathbb{A}\) creates a new solution \(\mathbb{X}\to \mathbb{A}\). While the aforementioned results of Bulatov [38] and Zhuk [39], [40] provide efficient algorithms in the presence of “non-trivial” polymorphisms of \(\mathbb{A}\), their absence readily implies hardness of \(\operatorname{CSP}(\mathbb{A})\) [42]. The latter statement can be formalized by requiring the existence of a minion homomorphism \(\operatorname{Pol}(\mathbb{A}) \to \mathop{\mathrm{id}}\), see [41], [43].
In the context of edge-coloring problems, we introduce the notion of cut-homotopies between polymorphisms, enriching the structure of the polymorphism minion \(\operatorname{Pol}(\mathbb{A})\). Cut-homotopies allow for even further combinations of solutions to \(\mathop{\mathrm{Col}}(\mathcal{F})\): Let \(G\) be a graph and \(\chi\colon\hat{G}\to \mathbb{A}^n\) be a homomorphism, which corresponds to an \(n\)-tuple of \(\mathcal{F}\)-free colorings of \(G\). Given a cut-homotopy between two polymorphisms \(f,g\colon\mathbb{A}^n\to\mathbb{A}\), every cut of \(G\) into two pieces produces a new \(\mathcal{F}\)-free coloring of \(G\) that agrees with \(f \circ \chi\) on edges contained in one side of the cut, and with \(g \circ \chi\) on the other side of the cut. The cut-homotopy provides a coherent way of coloring the cut edges, as visualized in Figure 1. Using cut-homotopies, we prove a hardness criterion for \(\mathop{\mathrm{Col}}(\mathcal{F})\), analogous to the hardness criterion for CSPs.
theoremthmReduction Assume that there is a minion homomorphism \(\alpha\colon \operatorname{Pol}(\mathbb{A})\to \mathop{\mathrm{id}}\) that collapses cut-homotopies, meaning \(\alpha(f)=\alpha(g)\) whenever \(f\) and \(g\) are cut-homotopic polymorphisms of \(\mathbb{A}\). Then the problem \(\mathop{\mathrm{Col}}(\mathcal{F})\) is NP-complete.
1.3 Gadget reductions↩︎
To prove Theorem [thm:reduction] we will reduce \(\operatorname{CSP}(\mathbb{A})\) to \(\mathop{\mathrm{Col}}(\mathcal{F})\) by producing, for every input \(\mathbb{X}\) to \(\operatorname{CSP}(\mathbb{A})\), a graph \(G_{\mathbb{X}}\) that admits an \(\mathcal{F}\)-free coloring if and only if there is a homomorphism \(\mathbb{X} \to \mathbb{A}\). To do so, fix a graph \(G_D\) and for every \(r\)-ary relation \(S\) of \(\mathbb{A}\), a graph \(G_S\) containing \(r\) marked copies of \(G_D\). Given \(\mathbb{X}\), we construct \(G_{\mathbb{X}}\) by taking a copy of \(G_D\) for every \(x \in X\) and for every tuple \(s\) of every relation \(S\) of \(\mathbb{X}\) a copy of \(G_S\). For every \(x \in X\) we then identify the corresponding copy of \(G_D\) with the \(i\)th marked copy of \(G_D\) in \(G_S\) corresponding to \(s\in S\) whenever \(x\) appears in the \(i\)th entry of \(s\).
By choosing suitable graphs \(G_D\) and \(G_S\) —therein lies the difficulty— we ensure that colorings of \(G_{\mathbb{X}}\) translate to a homomorphism \(\mathbb{X} \to \mathbb{A}\), with the value of \(x\) being determined by the coloring of the corresponding copy of \(G_D\), and vice versa.
Consider the problem of finding a vertex-coloring of a graph with two colors that avoids monochromatic triangles. Trying to reduce NotAllEqual-SAT to this problem, choose \(G_D\) and \(G_S\) to be \(K_1\) and \(K_3\) respectively. The resulting replacement procedure is displayed in Figure 2. However, solutions of a given input \(\mathbb{X}\) of NotAllEqual-SAT do not always translate to valid colorings of the resulting graph, as new triangles might be created during the identification process.
This issue was resolved for vertex-coloring problems, by showing that, without changing the computational complexity, one may assume that the inputs of a CSP have large girth, meaning that they do not contain short cycles [44], [45]. In this way, no new triangles are introduced and solutions of such inputs to NotAllEqual-SAT correspond to valid colorings of the graph obtained by the above replacement procedure. However, this approach fails for edge colorings, as the replacement procedure might create new cliques, even if inputs have large girth.
Consider the problem Edge-Mono-Tri from above. Figure 4 displays the naïve gadget replacement, taking \(G_D\) to be an edge and \(G_S\) to be a triangle, with the colors indicating the directions in which the edges are identified. Note that the identification step collapses some edges that are associated with different elements of the input \(\mathbb{X}\) (red-green and black-blue edges in Figure 4). In particular, solutions of \(\mathbb{X}\) cannot correspond to valid colorings of the resulting graph.
To avoid this problem, we look for equality-free gadgets, i.e., gadgets in which copies of \(G_D\) within \(G_S\) are pairwise disjoint. Moreover, if the distance between distinct copies of \(G_D\) is large enough, no new cliques will be created by the replacement, even if the girth of the input is small. In this case however, \(G_D\) cannot be a single edge in general, as the following example shows.
Let \(A\) consist of two colors and let \(\mathcal{F}\) be the family of forbidden edge-colorings of \(K_4\), which are obtained from the two monochromatic colorings by switching the colors of all the edges incident to a specific vertex. Up to symmetries, there are six of them:
Figure 3: 
.
Observe that, given any graph \(G_S\) with an \(\mathcal{F}\)-free coloring, a new \(\mathcal{F}\)-free coloring can be obtained by switching the colors around any vertex of \(G_S\). In particular, if \(G_S\) has an \(\mathcal{F}\)-free coloring, then any pairwise disjoint edges \(e_1,\dots,e_r\) can take any possible combination of the two colors.
We extend the notion of cut-homotopy to colorings of graphs and, using Ramsey-theoretic tools, we construct graphs \(G_D\) and \(G_S\) with the following properties. Every coloring of \(G_D\) that extends to a coloring of \(G_S\) is cut-homotopic to a coloring obtained by applying a polymorphism \(f\) to a fixed tuple of colorings (Proposition [prop:homotopy95witness2]). Moreover, \(G_D\) can be chosen such that \(f\) is unique up to cut-homotopy (Proposition [prop:homotopy95witness]). In this sense, colorings of \(G_D\) that extend to \(G_S\) correspond, up to cut-homotopy, to polymorphisms of \(\mathbb{A}\). Using the minion homomorphisms in the assumption of Theorem [thm:reduction], we show that this gadget yields a reduction from \(\operatorname{CSP}(\mathbb{A})\) to \(\mathop{\mathrm{Col}}(\mathcal{F})\).
Cut-homotopies were inspired by the notion of multi-polymorphisms, which characterize equality-free primitive-positive definability in relational structures [46], [47], which corresponds to equality-free gadget reductions between CSPs, where the domain gadget \(G_D\) is a single vertex.
1.4 Outlook↩︎
We define cut-homotopies only for those problems discussed in the present paper, however they seem to naturally be applicable to more general forbidden-pattern-coloring problems, including edge-coloring problems with more general shapes of forbidden graphs, and also those that require coloring of ordered edges of potentially higher arity. We wonder how far our techniques can scale, in particular: how much closer can cut-homotopies bring us to a complexity dichotomy for GMSNP?
Problems in the scope of the Bodirsky–Pinsker conjecture admit a standard reduction to a finite CSP [26], similar to what we describe in Section 1.1 and the notion of cut-homotopies can also be translated to this setting. However, there are tractable problems where the corresponding CSP is NP-complete; such problems include temporal [30] and phylogeny [31] constraint satisfaction. We wonder where and how exactly our proof techniques fail for these problems, but also if it is still possible to extract meaningful information using our methods, perhaps similar to the treatment of temporal constraint satisfaction problems in [19].
1.5 Overview↩︎
In Section 2, we recall CSPs and minions, and formally describe the structure \(\mathbb{A}\) and the reduction \(G\mapsto\hat{G}\) corresponding to a family \(\mathcal{F}\). In Section 3, we define cut-homotopies of polymorphisms and an analogous notion for colorings of graphs. The reduction of Theorem [thm:reduction] is presented in Section 4. In Section 5, we show that the assumptions of Theorem [thm:reduction] are satisfied for a problem \(\mathop{\mathrm{Col}}(\mathcal{F})\), whenever the corresponding CSP is NP-complete, completing the proof of Theorem 1. Finally, in Section 6, we prove the Ramsey-theoretic claims used in Sections 4 and 5.
2 Preliminaries↩︎
2.1 Graphs, colorings and the hat↩︎
In this paper, all graphs are assumed to be undirected and finite. For a graph \(G\), we will abuse the notation and refer to its vertex set as \(G\) and denote its edges as \(vw\), where \(v,w \in G\). Since edges are symmetric, we have \(vw =wv\). For a natural number \(n\), the clique \(K_n\) is the graph with \(n\) vertices and an edge \(vw\) for each pair of distinct vertices \(v,w\in K_n\). We identify its set of edges with \(\binom{n}{2}\).
A relational structure is a tuple \(\mathbb{A} = (A, R_1,\dots, R_q)\)—where the domain \(A\) is a set and every relation \(R_i\subseteq A^{r_i}\) is a set of functions \(r_i \to A\), for some finite set \(r_i\) called the arity of \(R_i\). The tuple of arities \((r_1,\ldots, r_q)\) is the signature of \(\mathbb{A}\). Given another structure \(\mathbb{X}=(X,S_1, \dots, S_q)\) of the same signature, a map \(f\colon X \to A\) is called a homomorphism if \(f\circ s\in R_i\) for every \(s\in S_i\) and \(i\leq q\).
The hat associated to a fixed family \(\mathcal{F}\) of edge-colored graphs assigns to every graph \(G\) a structure \(\hat{G}\) that is defined as follows. The domain of \(\hat{G}\) consists of the edges of \(G\). For every \(n\) such that \(\mathcal{F}\) contains at least one clique of size \(n\), the structure \(\hat{G}\) has a \(\binom{n}{2}\)-ary relation consisting of all maps of the form \[\hat{\phi} \colon \binom{n}{2} \to \hat{G}, \quad ij \mapsto \phi(i)\phi(j),\] where \(\phi\) is a homomorphism from \(K_n\) to \(G\). Generally, for a homomorphism of graphs \(\phi\colon G \to H\), the map \(\hat{\phi}\colon \hat{G} \to \hat{H}\) defined as \(vw \mapsto \phi(v) \phi(w)\), is a homomorphism of structures. The hat preserves identity maps and composition, so it is a functor from the category of graphs to the category of structures in the signature dictated by \(\mathcal{F}\).
We denote by \(\mathbb{A}\) the structure of the same signature whose domain is the set \(A\) of colors that appear among the colorings of cliques in \(\mathcal{F}\), where every \(\binom{n}{2}\)-ary relation \(R_n\) consists of all \(\mathcal{F}\)-free edge-colorings of \(K_n\). Observe that a map from the set of edges of \(G\) to \(A\) is a homomorphism \(\chi\colon \hat{G}\to \mathbb{A}\), if and only if it is an \(\mathcal{F}\)-free coloring. Further, a map \(f\colon \mathbb{A}^r \to \mathbb{A}\) is a homomorphism if and only if for every clique \(K_n\) and every coloring \(\chi \colon \hat{K}_n \to \mathbb{A}^r\), the composition \(f\circ \chi\) is an \(\mathcal{F}\)-free coloring of \(K_n\).
2.2 CSPs, polymorphisms and minions↩︎
The constraint satisfaction problem \(\operatorname{CSP}(\mathbb{A})\) of a relational structure \(\mathbb{A}\) takes structures \(\mathbb{X}\) of the same signature as \(\mathbb{A}\) as inputs and asks whether there is a homomorphism \(\mathbb{X}\to\mathbb{A}\). For a finite set \(r\), \(\mathbb{\mathbb{A}}^r\) denotes the \(r\)-th cartesian power of \(\mathbb{A}\) whose domain consists of functions \(r\to A\). If \(r = \{1,\dots,n\}\) we treat \({\mathbb{A}}^r\) and \(\mathbb{A}^n\) as being equal. Homomorphisms \(\mathbb{A}^r\to\mathbb{A}\) are called \(r\)-ary polymorphisms. We denote the set of homomorphisms from \(\mathbb{B}\) to \(\mathbb{A}\) by \(\hom(\mathbb{B}, \mathbb{A})\). The identity homomorphism of a structure \(\mathbb{A}\) is denoted by \(\mathop{\mathrm{id}}_{\mathbb{A}}\).
A minion \(\mathcal{M}\) is a functor from the category of finite sets to itself. Explicitly, for every finite set \(r\) there is a finite set \(\mathcal{M}^{(r)}\) and for every map \(\sigma\colon r\to s\) there is a map \(\mathcal{M}^{(\sigma)}\colon \mathcal{M}^{(r)}\to \mathcal{M}^{(s)}\) respecting identity maps and composition. By \(\mathop{\mathrm{id}}\), we denote the identity minion with \(\mathop{\mathrm{id}}^{(r)} = r\). A minion homomorphism \(\alpha \colon \mathcal{M} \to \mathcal{N}\) is a natural transformation, that is, \(\alpha\) is a family of maps \(\alpha_r\colon \mathcal{M}^{(r)} \to \mathcal{N}^{(r)}\) such that the following square commutes for every map \(\sigma\colon r \to s\). \[\label{eq:naturality} \begin{tikzcd} \mathcal{M}^{(r)} \arrow[r, "\mathcal{M}^{(\sigma)}"] \arrow[d, "\alpha_r"'] & \mathcal{M}^{(s)} \arrow[d, "\alpha_s"]\\ \mathcal{N}^{(r)} \arrow[r, "\mathcal{N}^{(\sigma)}"] & \mathcal{N}^{(s)} \end{tikzcd}\tag{1}\] We will frequently abuse notation and write \(\alpha(x)\) instead of \(\alpha_r(x)\). The fundamental example of a minion is a polymorphism minion: For a relational structure \(\mathbb{A}\), let \(\operatorname{Pol}(\mathbb{A})\) be the minion with \(\operatorname{Pol}(\mathbb{A})^{(r)} = \hom(\mathbb{A}^r,\mathbb{A}).\) Moreover, for a map \(\sigma\colon r\to s\), the map \(\operatorname{Pol}(\mathbb{A})^{(\sigma)}\) assigns to each \(f\colon \mathbb{A}^r\to \mathbb{A}\), the polymorphism \(f\circ\sigma^*\colon\mathbb{A}^s\to \mathbb{A}\), \(a \mapsto f(a \circ \sigma)\), where \(\sigma^*\) denotes the precomposition map \(a\mapsto a\circ\sigma\). Of particular importance are minion homomorphisms \(\alpha\colon\operatorname{Pol}(\mathbb{A})\to\mathop{\mathrm{id}}\), as their existence implies hardness of \(\operatorname{CSP}(\mathbb{A})\), see Corollary 9.5 in [41]. The naturality condition (1 ) of such \(\alpha\) precisely states that \(\alpha( f\circ \sigma^* ) = \sigma(\alpha(f))\) for all polymorphisms \(f\) and maps \(\sigma\).
3 Cut-homotopies↩︎
Consider the looped path \(P_k\) of length \(k\), i.e., the graph with vertices \(0,\dots,k\) that has a loop \(ii\) for every \(i\in P_k\) and an edge \(i(i+1)\) for each \(0\leq i < k\).
Definition 1. We call a homomorphism \(h\colon \mathbb{A}^r \times \hat{P}_k\to \mathbb{A}\) a \(k\)-step cut-homotopy of polymorphisms.
Observe that every \(h_{i}:= h(-,ii)\colon \mathbb{A}^r\to\mathbb{A}\) is a polymorphism of \(\mathbb{A}\); we say that \(h_0\) and \(h_k\) are \(k\)-step cut-homotopic and write \(h_{0}\sim_k h_{k}\). Given a \(k\)-step cut-homotopy \(h\colon \mathbb{A}^r \times \hat{P}_k\to \mathbb{A}\), for \(0\leq i\leq k\) we shorten \(h(-,ii)\) to \(h_i\) and for \(0\leq i < k\) we shorten \(h(-,i(i+1))\) to \(h_{i(i+1)}\). For \(k=1\), we simply say cut-homotopy and cut-homotopic.
We refer to any graph homomorphism \(G \to P_1\) as a cut of \(G\). One can think of a cut partitioning the vertices of \(G\) into two sets. Given a partition of \(G\) into \(G_0,G_1\) we denote by \(G_0\mid G_1\) the cut \(c: G \to P_1\) such that \(c^{-1}(0) = G_0\) and \(c^{-1}(1) = G_1\). To illustrate their application, consider a cut-homotopy \(h \colon \mathbb{A}^r \times \hat{P}_1 \to \mathbb{A}\), a graph \(G\) and a coloring \(\chi \colon \hat{G} \to \mathbb{A}^r\). The polymorphisms \(h_{0}, h_{1}\) induce two colorings of \(G\), \(h_{0}\circ \chi\) and \(h_{1}\circ \chi\), and \(h\) provides a way to “translate” between the two. More precisely, given any cut \(c \colon G \to P_1\), the coloring \[\hat{G}\xrightarrow{(\chi,\hat{c})} \mathbb{A}^r\times\hat{P}_1\xrightarrow{h} \mathbb{A}\] agrees with \(h_0\circ \chi\) on all edges \(vw\) with \(\hat{c}(vw) = 00\), with \(h_1 \circ \chi\) on all edges \(vw\) with \(\hat{c}(vw) = 11\) and with \(h_{01}\circ \chi\) on the remaining edges. For two graphs \(G,H\), denote by \(G\times H\) the graph whose vertices are all the pairs \((v,i)\) for \(v\in G, i\in H\) and \((v,i)(w,j)\) is an edge if and only if \(vw\) is an edge of \(G\) and \(ij\) is an edge of \(H\). If \(vw \in \hat{G}\), \(ij \in \hat{H}\) we get two different edges of \(G \times H\) which, following our naming convention for edges of graphs, technically are \((v,i)(w,j)\) and \((v,j)(w,i)\). To have a slimmer notation however we will refer to them as \((vw,ij)\) and \((vw,ji)\) respectively.
Definition 2. We call a coloring \(\eta\colon\widehat{G\times P_k}\to \mathbb{A}\) a \(k\)-step cut-homotopy of colorings, say that \(\eta_0\coloneq\eta(- ,00)\) and \(\eta_k\coloneq\eta(-,kk)\) are \(k\)-step cut-homotopic* and write \(\eta_0\sim_k \eta_k\). Again, for \(k=1\), we simply say cut-homotopy and cut-homotopic.*
Suppose \(\mathcal{F}\) consists of both monochromatic triangles in two colors. Figure 5 depicts a cut-homotopy between two \(\mathcal{F}\)-free colorings of the triangle \(K_3\).
Observe that cut-homotopies of polymorphisms induce cut-homotopies of colorings: given a graph \(G\), a coloring \(\chi\colon\hat{G}\to\mathbb{A}^r\) and a cut-homotopy \(h\colon \mathbb{A}^r\times \hat{P}_k\to\mathbb{A}\), we can define the cut-homotopy of colorings \[\eta\colon\widehat{G\times P_k}\to\mathbb{A},\quad (vw,ij)\mapsto h(\chi(vw),ij).\] Moreover, both notions of cut-homotopies are transitive: if \(f,g,h\) are polymorphisms and \(f\sim_k g\) and \(g\sim_\ell h\), then \(f\sim_{k+\ell} g\), and similarly for colorings.
4 Reductions↩︎
The goal of the current section is to show the following statement.
Figure 6: 
.
We will prove this by showing that for an arbitrary relational structure \(\mathbb{B}\) we can find an equality-free gadget reduction from \(\operatorname{CSP}(\mathbb{B})\) to \(\mathop{\mathrm{Col}}(\mathcal{F})\). We point out that gadget reductions are a well-studied technique for \(\operatorname{CSP}\)s [48], [49], our contribution lies in using cut-homotopies to find the correct gadget. A gadget consists of
a graph \(G_D\) for the domain;
a graph \(G_S\) for every relation \(S\) of \(\mathbb{B}\);
an embedding \(\phi^S_i\colon G_D\to G_S\) for every \(r\)-ary relation \(S\) of \(\mathbb{B}\) and \(i\in r\).
The gadget has girth \(k\) if \(k\) is the minimal distance (number of edges in the shortest path) between the images of any two distinct embeddings \(\phi_i^S\). We say that the gadget is equality-free if it has girth at least one.
Given a gadget, the corresponding gadget replacement takes a \(\sigma\)-structure \(\mathbb{X}\) and constructs a graph \(G_\mathbb{X}\) in the following way. For every element \(x\in \mathbb{X}\) introduce a copy \(G_x\) of \(G_D\) and for every \(\bar x\in S(\mathbb{X})\) introduce a copy \(G_{\bar x}\) of \(G_S\). Imagine each \(x\) and \(\bar x\) being “replaced” by the respective graphs. Afterwards, whenever we have \(\bar x(i) = x\) for some coordinate \(i\), identify \(v\in G_x\) with \(\phi_i^S(v)\in G_{\bar x}\), see Figure 7. We denote the resulting graph by \(G_\mathbb{X}\).
Observe that if the girth of the gadget is at least four, the image of every homomorphism from a clique to \(G_\mathbb{X}\) is fully contained in a copy \(G_x\) of \(G_D\) or in a copy \(G_{\bar{x}}\) of \(G_S\). To find gadgets, we will employ the following two propositions that relate cut-homotopies of polymorphisms to cut-homotopies of colorings. They will be proved in Section 6.
propositionpropGadgetOne For any two numbers \(k\) and \(n\) there is a graph \(G\) and a coloring \(\chi\colon\hat{G}\to\mathbb{A}^n\) with the following property: any two polymorphisms \(f,g\colon \mathbb{A}^n\to \mathbb{A}\) are \(k\)-step cut-homotopic whenever the colorings \(f\circ \chi\) and \(g\circ \chi\) are \(k\)-step cut-homotopic: \[f\circ \chi \sim_k g\circ\chi \Longrightarrow f\sim_k g\]
The converse implication holds for all \(G\) and \(\chi\).
propositionlemRamsey Fix a number \(n\), a finite number of graphs \(G_i\) and colorings \(\chi_i\colon \hat{G}_i\to \mathbb{A}^n\), for \(i \in r\). There exists a graph \(H\), a coloring \(\chi\colon \hat{H}\to \mathbb{A}^n\) and embeddings \(\phi_i\colon G_i\to H\) with \(\chi\circ\hat{\phi}_i = \chi_i\) for all \(i \in r\), such that for every coloring \(\eta\colon\hat{H}\to \mathbb{A}\), there is a polymorphism \(f\colon \mathbb{A}^n\to \mathbb{A}\) and \(2\)-step cut-homotopies \[f\circ \chi_i \sim_2 \eta\circ\hat{\phi}_i\] for all \(i \in r\). Moreover, the distance between the images of any two distinct \(\phi_i\) is at least four.
Proof of Theorem [thm:reduction]. Take a minion homomorphism \(\alpha\colon \operatorname{Pol}(\mathbb{A})\to \mathop{\mathrm{id}}\) that collapses cut-homotopies. For any finite relational structure \(\mathbb{B}\), we will find a gadget replacement that reduces \(\operatorname{CSP}(\mathbb{B})\) to \(\mathop{\mathrm{Col}}(\mathcal{F})\). Let \(G_D\) be the graph obtained from Proposition [prop:homotopy95witness], for \(k=4\) and \(n=B\). Denote the obtained coloring by \(\chi_D\colon \hat{G}_D\to\mathbb{A}^B\).
Given a relation \(S \subseteq B^r\) of \(\mathbb{B}\) with arity \(r\) we define a graph \(G_S\) in the following way. For every coordinate \(i \in r\), let \(\chi_i\colon \hat{G}_D\to\mathbb{A}^S\) be the coloring defined by \[\chi_i = \pi_i^*\circ \chi_D\] where \(\pi_i\colon S\to B\) is the \(i\)-th projection and \(\pi_i^*\) denotes the precomposition map \(\mathbb{A}^B\to\mathbb{A}^S\), \(a\mapsto a\circ\pi_i\). Applying Proposition [prop:homotopy95witness2] with \(n=S\) to these colorings, we obtain the graph \(G_S\), embeddings \(\phi_i^S\colon G_D\to G_S\) for all \(i \in r\) and a coloring \(\chi_S\colon \hat{G}_S\to \mathbb{A}^S\). By the proposition, the girth of this gadget is at least four, we show that it yields a reduction.
First we show completeness, that is, whenever \(\mathbb{X}\) is a YES-instance of \(\operatorname{CSP}(\mathbb{B})\) then \(G_\mathbb{X}\) is a YES-instance of \(\mathop{\mathrm{Col}}(\mathcal{F})\). Indeed, given a homomorphism \(f\colon \mathbb{X}\to \mathbb{B}\), we construct a coloring \(\eta\colon\hat{G}_\mathbb{X}\to \mathbb{A}\) as follows. Whenever an edge \(vw\in\hat{G}_\mathbb{X}\) is contained in a copy \(G_x\) of \(G_D\), we take the function \(\chi_D(vw)\in \mathbb{A}^B\) and evaluate at \(f(x)\) to obtain the color \(vw\). Similarly, if \(vw\) is contained in a copy \(G_{\bar x}\) of some \(G_S\), we take \(\chi_S(vw)\) and evaluate at \((f\circ\bar x)\). \[\eta(vw) = \begin{cases} \chi_D(vw)(f(x)) &\text{if } v,w \in G_x \\ \chi_S(vw)(f\circ \bar x) &\text{if } v,w\in G_{\bar x} \end{cases}\] Note that every edge \(vw\) is contained in some \(G_x\) or \(G_{\bar x}\) and the condition \(\pi_i^*\circ\chi_D=\chi_i = \chi_S\circ\hat{\phi}^S_i\) ensures that \(\eta\) is well-defined. Moreover, since the girth of the gadget is at least four, every clique in \(G_\mathbb{X}\) is fully contained in one of the \(G_x\) or \(G_{\bar x}\), hence the coloring \(\eta\) is \(\mathcal{F}\)-free if and only if \(\chi_D, \chi_S\) are, and they are \(\mathcal{F}\)-free at each coordinate, by definition. Next we show soundness, that is, whenever \(G_\mathbb{X}\) is a YES-instance of \(\mathop{\mathrm{Col}}(\mathcal{F})\) then \(\mathbb{X}\) is a YES-instance of \(\operatorname{CSP}(\mathbb{B})\). Indeed, given a coloring \(\eta\colon\hat{G}_\mathbb{X}\to \mathbb{A}\), we show the existence of a homomorphism \(g\colon \mathbb{X}\to \mathbb{B}\) as follows. Let \(g\colon X\to B\) be any map that satisfies \(g(x)=\alpha(f)\), whenever there is a polymorphism \(f: \mathbb{A}^B \rightarrow \mathbb{A}\) such that \(\eta_x\sim_2 f\circ\chi_D\), where \(\eta_x\) indicates the restriction of \(\eta\) to \(G_x\). Such a map exists, since whenever two polymorphisms \(f\) and \(f'\) satisfy the above condition, we get \(f'\circ \chi_D \sim_4 f\circ\chi_D\), which, by the definition of \(G_D\), implies \(f\sim_4 f'\) and hence \(\alpha(f)=\alpha(f')\), by assumption. We prove that \(g\) describes a homomorphism. For this purpose we take \(\bar x\in S(\mathbb{X})\) and we show that \(g\circ\bar x \in S\). Let \(\eta_{\bar x}\) be the restriction of \(\eta\) to \(G_{\bar x}\). By the definition of \(G_S\), there is a polymorphism \(f\colon\mathbb{A}^S\to\mathbb{A}\) and 2-step cut-homotopies \[f\circ\chi_i\sim_2\eta_{\bar x}\circ\hat{\phi}_i\] for all \(i \in r\). Moreover, by definition, \(f\circ \chi_i =f\circ\pi_i^*\circ \chi_D\) and \(\eta_{\bar x}\circ\hat{\phi}^S_i = \eta_{\bar x(i)}\), so the function \(i\mapsto g(\bar x(i))\) indeed belongs to \(S\) since \(\alpha(f)\in S\) and \[g(\bar x(i)) = \alpha(f\circ\pi_i^*)= \pi_i(\alpha(f)).\] The first equality holds by the definition of \(g\), and the second one follows from the fact that \(\alpha\) is a minion homomorphism. ◻
As usual with gadget reductions, the minion homomorphism \(\alpha\) was used only to guarantee soundness. For completeness, we used the gadget’s girth and the existence of certain colorings. We remark that, using essentially the same proof, one can show a slight refinement of Theorem [thm:reduction]: If there is a minion homomorphism \(\operatorname{Pol}\mathbb{A}\to\operatorname{Pol}\mathbb{B}\) that collapses cut-homotopies, then there is an efficient reduction from \(\operatorname{CSP}(\mathbb{B})\) to \(\mathop{\mathrm{Col}}(\mathcal{F})\).
5 There are no weird homotopies!↩︎
This section is devoted to the proof of the following theorem.
theoremnoHomotopies If there is a minion homomorphism \(\operatorname{Pol}(\mathbb{A}) \to \mathop{\mathrm{id}}\), then there is a minion homomorphism \(\operatorname{Pol}(\mathbb{A})\to \mathop{\mathrm{id}}\) that collapses cut-homotopies.
5.1 Preliminaries↩︎
We review standard notions from the algebraic approach to CSPs that are needed below, and which can be found in e.g., [49]. An endomorphism of \(\mathbb{A}\) is a homomorphism from \(\mathbb{A}\) to itself. A structure \(\mathbb{A}\) is called a core if every endomorphism of \(\mathbb{A}\) is an isomorphism. For every structure \(\mathbb{A}\) there is a core \(\mathbb{A}'\) that is homomorphically equivalent to \(\mathbb{A}\), i.e., there are homomorphisms \(\mathbb{A} \to \mathbb{A}'\) and \(\mathbb{A}' \to \mathbb{A}\). The structure \(\mathbb{A}'\) is unique up to isomorphism, justifying the name the core of \(\mathbb{A}\), and embeds into \(\mathbb{A}\). Let \(\mathbb{A}'\) be the core of \(\mathbb{A}\) and \(\iota \colon \mathbb{A}' \to \mathbb{A}\), \(\psi\colon \mathbb{A} \to \mathbb{A}'\) be homomorphisms. These maps induce a minion homomorphism \(\operatorname{Pol}(\mathbb{A}) \to \operatorname{Pol}(\mathbb{A}'), f \mapsto \psi \circ f\circ \iota_*\), where \(\iota_*\) denotes the map \((\mathbb{A}')^r \to \mathbb{A}^r, a \mapsto \iota\circ a\) for all \(r\). We refer to it as the minion homomorphism associated with \(\iota\) and \(\psi\).
The unary minor of a function \(f\colon \mathbb{A}^n \to \mathbb{A}\) is the unary map \(e_f(x) \coloneq f(x,\ldots,x)\). We say that \(f\) is idempotent if \(e_f= \mathop{\mathrm{id}}_\mathbb{A}\). We denote the minion consisting of all idempotent polymorphisms of \(\mathbb{A}\) by \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\). If \(\mathbb{A}\) is a core, there is a minion homomorphism \(\alpha_\mathrm{idem}\colon\operatorname{Pol}(\mathbb{A}) \to \operatorname{Pol}(\mathbb{A})_\mathrm{idem}, f\mapsto e_f^{-1}\circ f\). We say that a cut-homotopy \(h\colon \mathbb{A}^n \times \hat{P}_k \to \mathbb{A}\) is idempotent if \(h(a,\dots,a,ij) = a\), for all \(a \in \mathbb{A}, ij\in \hat{P}_k\).
Let \(S\subseteq A\) be a subset preserved by \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) and \(\theta \subseteq S^2\) be an equivalence relation preserved by \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\). For every number \(n\), \(\theta\) induces an equivalence relation on \(S^n\) by requiring elements to be \(\theta\)-related componentwise; we also refer to this equivalence relation by \(\theta\). Saying that \(S\) and \(\theta\) are preserved by \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) precisely means that for every number \(n\), every \(n\)-ary \(f \in \operatorname{Pol}(\mathbb{A})\) induces a function \[S^n/_\theta \to S/_\theta, \quad a/_\theta \mapsto f(a)/_\theta,\] the action of \(f\) on \(S/_\theta\). The pair \((S, \theta)\) is called a naked set of \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) if \(\theta\) has two equivalence classes and every function contained in \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) acts as a projection on \(S/_\theta\). The assignment \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\to \mathop{\mathrm{id}}\) sending \(f\colon \mathbb{A}^n \to \mathbb{A}\) to \(i \in \{1,\dots, n \}\), where \(f\) acts as the \(i\)-th coordinate projection on \(S/_\theta\) is easily seen to be a minion homomorphism. We refer to it as the minion homomorphism induced by \((S,\theta)\). Finally, we say that a minion homomorphism \(\alpha: \operatorname{Pol}(\mathbb{A}) \rightarrow \operatorname{Pol}(\mathbb{B})\) preserves cut-homotopies if whenever \(f, g \in \operatorname{Pol}(\mathbb{A})\) are cut-homotopic, then so are \(\alpha(f), \alpha(g)\).
5.2 The master proof of Theorem [thm:noHomotopies]↩︎
Let \(\mathbb{A}'\) be the core of \(\mathbb{A}\). The existence of a minion homomorphism \(\operatorname{Pol}(\mathbb{A}) \to \mathop{\mathrm{id}}\) implies the existence of a minion homomorphism \(\operatorname{Pol}(\mathbb{A}')_\mathrm{idem}\to \mathop{\mathrm{id}}\), see e.g., [20]. By [50] the latter statement implies the existence of a naked set \((S,\theta)\) of \(\operatorname{Pol}(\mathbb{A}')_\mathrm{idem}\). The induced minion homomorphism \(\alpha \colon \operatorname{Pol}(\mathbb{A}')_\mathrm{idem}\to \mathop{\mathrm{id}}\) collapses idempotent cut-homotopies by Proposition [prop:noHomotopies]. Further, the combination of Lemma 1 and Lemma 2 yields a minion homomorphism \(\beta \colon \operatorname{Pol}(\mathbb{A}) \to \operatorname{Pol}(\mathbb{A}')_\mathrm{idem}\) that preserves cut-homotopies. Moreover, Lemma 2 shows that \(\beta(f)\sim_1 \beta(g)\) is witnessed by an idempotent cut-homotopy, for all \(f\sim_1 g\) in \(\operatorname{Pol}(\mathbb{A})\). Thus, the composition \(\alpha \circ \beta \colon \operatorname{Pol}(\mathbb{A}) \to \mathop{\mathrm{id}}\) yields the desired minion homomorphism that collapses cut-homotopies.
\[\operatorname{Pol}(\mathbb{A}) \xrightarrow[\text{Lemma~\ref{lem:str95to95core}}]{\substack{\text{preserves}\\\text{cut-homotopies}}} \operatorname{Pol}(\mathbb{A}') \xrightarrow[\text{Lemma~\ref{lem:core95to95idemp}}]{\substack{\text{makes cut-homotopies}\\\text{idempotent}}} \operatorname{Pol}(\mathbb{A}')_{\mathrm{idem}} \xrightarrow[\text{Proposition~\ref{prop:noHomotopies}}]{\substack{\text{collapses idempotent}\\\text{cut-homotopies}}} \mathop{\mathrm{id}}\]
5.3 Auxiliary results for the proof of Theorem [thm:noHomotopies]↩︎
Since \(\mathbb{A}\) corresponds to some finite family \(\mathcal{F}\) of forbidden edge-colored cliques, also the core \(\mathbb{A}'\) of \(\mathbb{A}\) corresponds to some finite family \(\mathcal{F}'\) of edge-colored cliques. Namely, since \(\mathbb{A}'\) is an induced substructure of \(\mathbb{A}\) we may choose \(\mathcal{F}'\) so that the \(\mathcal{F}'\)-free colorings of cliques are precisely the \(\mathcal{F}\)-free colorings with colors contained in the domain of \(\mathbb{A}'\). For this reason we may (and will) verify that a map \((\mathbb{A}')^n \to \mathbb{A}'\) or \((\mathbb{A}')^n \times \hat{P}_1 \to \mathbb{A}'\) is a homomorphism in the same way we do for \(\mathbb{A}\).
Lemma 1. Let \(\mathbb{A}'\) be the core of \(\mathbb{A}\) and let \(\iota\colon \mathbb{A}'\to \mathbb{A}\), \(\psi\colon \mathbb{A}\to \mathbb{A}'\) be homomorphisms. Then the minion homomorphism \(\alpha\colon\operatorname{Pol}(\mathbb{A})\to\operatorname{Pol}(\mathbb{A}')\) associated with \(\iota\) and \(\psi\) preserves cut-homotopies.
Proof. Let \(h\colon \mathbb{A}^n \times \hat{P}_1 \to \mathbb{A}\) be a cut-homotopy between polymorphisms \(h_0\) and \(h_1\) of \(\mathbb{A}\). The map \[\psi\circ h\circ (\iota_* \times \mathop{\mathrm{id}}_{\hat{P}_1}) \colon (\mathbb{A}')^n \times \hat{P}_1 \to \mathbb{A}^n \times \hat{P}_1 \to \mathbb{A} \to \mathbb{A}'\] is a cut-homotopy between \(\psi \circ h_0 \circ \iota_* = \alpha(h_0)\) and \(\psi \circ h_1 \circ \iota_* = \alpha(h_1)\). ◻
Lemma 2. Let \(\mathbb{A}\) be a core. Then the minion homomorphism \(\alpha_\mathrm{idem}\colon \operatorname{Pol}(\mathbb{A})\to \operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) preserves cut-homotopies and whenever \(f,g\in\operatorname{Pol}(\mathbb{A})\) are cut-homotopic, the existence of a cut-homotopy \(\alpha_\mathrm{idem}(f)\sim_1\alpha_\mathrm{idem}(g)\) is witnessed by an idempotent cut-homotopy.
Proof. Let \(h\) be a cut-homotopy between two polymorphisms \(h_{0}\) and \(h_{1}\) of \(\mathbb{A}\). We will construct an idempotent cut-homotopy \(h''\) such that \(h''_{0} = \alpha_{\mathrm{idem}}(h_{0})\) and \(h''_{1} = \alpha_{\mathrm{idem}}(h_{1})\). Let \(e\colon \mathbb{A}\times {\hat{P}_1} \to \mathbb{A}\) be the unary minor of \(h\), i.e., \(e(x,ij)\coloneq h(x,\ldots,x, ij)\). Clearly, \(e\) is a homomorphism.
Note that \(e_{0},e_{1}\) are endomorphisms of \(\mathbb{A}\) and, since \(\mathbb{A}\) is a core, they have inverses. Define \(h'\coloneq e_0^{-1}\circ h\) and let \(e'\) be its unary minor, so \(e' = e_0^{-1}\circ e\). We now verify that \(e'_{01}\) is invertible. Since \(\mathbb{A}\) is a core it suffices to show that \((e_{01}')^2\) is an endomorphism of \(\mathbb{A}\). We do that by checking that for every \(K_m\) and every coloring \(\chi \colon \hat{K}_m \to \mathbb{A}\), also \((e'_{01})^2\circ \chi\) is a coloring of \(K_m\). For every vertex \(v\in K_m\), define the cut \(c_{v}\coloneq K_m\setminus \{v\} \mid v\). Since \(e'\) is a homomorphism with \(e'_{0} = \mathop{\mathrm{id}}_{\mathbb{A}}\), the coloring \(e'\circ (\chi, \hat{c}_v)\colon \hat{K}_m \to \mathbb{A}\) is valid and it differs from \(\chi\) only on edges incident to \(v\), where it agrees with \(e'_{01}\circ \chi\). Repeating this for every \(v\in K_m\) gives a valid coloring, which coincides with \((e_{01}')^2\circ \chi\) at every edge. Since \(\mathbb{A}\) is finite and \(e'_{01}\) bijective, there exists some number \(N\) such that \((e'_{01})^N = (e'_{01})^{-1}\). We define a map \(\tilde{e} \colon \mathbb{A} \times \hat{P}_1 \to \mathbb{A}\) as follows \[\begin{align} \tilde{e}_0 &= \mathop{\mathrm{id}}_{\mathbb{A}},\\ \tilde{e}_{01} &= (e'_{01})^N,\\ \tilde{e}_1 &= (e'_{01})^{2N}; \end{align}\] and verify that it is a homotopy. To this end we show that for every \(K_m\), every coloring \(\chi\colon \hat{K}_m \to \mathbb{A}\) and every cut \(c\colon K_m \to P_1\), the map \(\chi' \coloneq \tilde{e} \circ (\chi, \hat{c})\) is a valid coloring. Let \(v \in K_m\) be a vertex with \(c(v) = 1\), let \(c_v \coloneq K_m \setminus \{v\} \mid v\) and set \(\chi_1 \coloneq e' \circ (\chi,\hat{c}_v)\). Recursively we define \(\chi_{i+1} \coloneq e' \circ (\chi_i,\hat{c}_v)\) for \(i < N\) to obtain a valid coloring \(\chi_N \colon \hat{K}_m \to \mathbb{A}\) that agrees with \(\chi'\) on all edges of the form \(vw\) and \(w w'\) where \(w, w' \in K_m\) with \(c(w)= c(w')=0\). Here we crucially use that \(e'_0 = \mathop{\mathrm{id}}_{\mathbb{A}}\). Replacing \(\chi\) by \(\chi_N\) we repeat this procedure for every further vertex \(v' \in K_m\) with \(c(v') = 1\) to obtain a coloring that agrees with \(\chi'\) proving it to be valid.
We may now define the homotopy \(h''\colon \mathbb{A}^n \times \hat{P}_1 \to \mathbb{A}\) as the composition \[\mathbb{A}^n \times \hat{P}_1 \xrightarrow{(h'\times\mathop{\mathrm{id}}_{\hat{P}_1})} \mathbb{A} \times \hat{P}_1 \xrightarrow{\tilde{e}} \mathbb{A}.\] Let \(e''\) be its unary minor and observe that \(e''_{0} = \mathop{\mathrm{id}}_{\mathbb{A}} = e''_{01}\). Furthermore, \(h''_1 = \tilde{e}_1 \circ e_0^{-1} \circ h_1\), so it will follow that \(\alpha_{\mathrm{idem}}(h_1) = h''_1\) once we have established that \(e_1'' = \mathop{\mathrm{id}}_{\mathbb{A}}\). Assuming the contrary we obtain distinct \(a,b\in \mathbb{A}\) with \(e_{1}''(a) = b\) and argue that the map \(\phi\colon \mathbb{A} \to \mathbb{A}\) with \(\phi(a)=b\) and \(\phi(a')=a'\) for every \(a'\in \mathbb{A}\setminus \{a\}\) is a homomorphism. This contradicts \(\mathbb{A}\) being a core. To do so we show that for every clique \(K_m\) and every coloring \(\chi\colon \hat{K}_m\to \mathbb{A}\), \(\phi \circ \chi\) is a valid coloring of \(K_m\) itself. For every edge \(vw \in \hat{K}_m\) with \(\chi(vw)=a\), we consider the cut \(c_{vw}\colon K_m\setminus \{v,w\}\mid \{v,w\}\), and note that \(e''\circ (\chi, \hat{c}_{vw})\) is a valid coloring which only differs from \(\chi\) on the edge \(vw\) where it takes the value \(b\). Repeating this for every further \(a\)-colored edge results in a valid coloring that coincides with \(\phi\circ \chi\), so \(\phi\) is a homomorphism. ◻
For the next proposition, we need the following Ramsey-theoretic lemma, which we prove in Section 6.
lemmamapFactory Let \(n\) be a number, and for each \(a\in \mathbb{A}^n\) pick a subset \(U_{a}\subseteq A\). Assume that for every graph \(G\) and every coloring \(\chi\colon \hat{G}\to \mathbb{A}^n\), there is a coloring \(\eta\colon \hat{G}\to \mathbb{A}\) such that \[\forall vw\in\hat{G}: \eta(vw)\in U_{\chi(vw)}.\] Then there exists a polymorphism \(f \colon \mathbb{A}^n \to \mathbb{A}\) with \(f(a)\in U_{a}\) for all \(a \in \mathbb{A}^n\).
We are now prepared to establish that there are no “weird homotopies”, i.e., an idempotent cut-homotopy between two polymorphisms that act as different projections on a given naked set \((S,\theta)\).
Let \(\mathbb{A}\) be a core and \((S,\theta)\) be a naked set of \(\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\). Then the minion homomorphism \(\alpha\colon \operatorname{Pol}(\mathbb{A})_\mathrm{idem}\to\mathop{\mathrm{id}}\) induced by \((S, \theta)\) collapses idempotent cut-homotopies, i.e., if \(f,g\in\operatorname{Pol}(\mathbb{A})_\mathrm{idem}\) and \(f\sim_1 g\) with \(h\) idempotent, then \(\alpha(f)=\alpha(g)\).
Proof. Striving for a contradiction we assume that \(h\) is an idempotent cut-homotopy between \(n\)-ary polymorphisms \(h_0,h_1\) that act as different projections on \(S/_\theta\), without loss of generality, the first and second projection. Then, \(h' \colon \mathbb{A}^2 \times \hat{P}_1 \to \mathbb{A}, (x,y,ij) \mapsto h_{ij}(x,y,\dots, y)\) is a cut-homotopy between binary polymorphisms of \(\mathbb{A}\) that act as different projections on \(S/_\theta\). Hence, we may assume \(h\) to be binary, and that \(h_0, h_1\) act on \(S/_\theta\) as the first and second projection, respectively.
Let \(d\) be the homomorphism \((h_0, h_1) \colon \mathbb{A}^2\to \mathbb{A}^2, (a,b) \mapsto (h_0(a,b),h_1(a,b))\), and choose \(N\) so that \(d^N\) is a retraction, i.e., \(d^N = d^{2N}\). Let \(D\) be the image of \(d^N\), and note that \(d^N\) restricts to the identity on \(D\).
The composition \(f\coloneq h_{01}\circ d^N\) is an idempotent polymorphism of \(\mathbb{A}\) satisfying \(f|_D = h_{01}|_D\).
Proof of the claim. We show that for every \(K_m\) and every coloring \(\chi\colon \hat{K}_m\to \mathbb{A}^2\), the map \(f \circ \chi\) is a homomorphism \(\hat{K}_m \to \mathbb{A}\). Define \(\chi_0\coloneq d^N\circ \chi\).
Fix a vertex \(v\in K_m\) and consider the two cuts \(c_{0} \coloneq K_m\setminus\{v\}\mid v\) and \(c_1\coloneq v\mid K_m\setminus\{v\}\). Applying \(h\) to \(\chi_0\) along each cut yields a coloring \(\hat{K}_m \to \mathbb{A}\) and we let \(\chi_1\colon \hat{K}_m \to \mathbb{A}^2\) denote their product. More formally, \(\chi_1\) is defined to be the homomorphism \(\big( h \circ (\chi_0,\hat{c}_0), h \circ (\chi_0,\hat{c}_1) \big)\colon \hat{K}_m \to \mathbb{A}^2\). For every \(w w' \in \hat{K}_m\) it holds \[\chi_1(w w') = \begin{cases} \big(h_0\circ\chi_0(w w'), h_1\circ \chi_0(w w') \big) = d\circ \chi_0(w w') &\text{if } v\notin \{w, w'\} \\ \big(h_{01}\circ\chi_0(w w'), h_{01}\circ\chi_0(w w')\big) &\text{if } v\in \{w, w'\}. \end{cases}\] Observe that in the latter case both entries of \(\chi_1(w w')\) agree. We iterate this construction, obtaining \(\chi_{i+1}\) from \(\chi_i\) in the same way \(\chi_1\) is obtained from \(\chi_0\) until we arrive at the coloring \(\chi_N\). The aforementioned observation in combination with the fact that \(h\) is idempotent guarantees that for every \(w w' \in \hat{K}_m\) it holds \[\chi_N(w w') = \begin{cases} d^N \circ \chi_0(w w') = \chi_0(w w')&\text{if } v\notin \{w, w'\}\\ \big(h_{01}\circ\chi_0(w w'),h_{01}\circ\chi_0(w w')\big) &\text{if } v\in \{w, w'\}. \end{cases}\] Replacing \(\chi_0\) with \(\chi_N\) we repeat this procedure for every vertex of \(K_m\). Once we have exhausted all vertices, we call the resulting coloring \(\chi'\colon \hat{K}_m \to \mathbb{A}^2\). For every edge \(w w'\) of \(K_m\), as it is incident to precisely two vertices of \(K_m\), we have \[\begin{align} \chi'(w w') &= \Big( h_{01}\big(h_{01}\circ \chi_0(w w'), h_{01}\circ \chi_0(w w')\big), h_{01}\big(h_{01}\circ \chi_0(w w'), h_{01}\circ \chi_0(w w')\big) \Big)\\ &= \big( h_{01}\circ \chi_0(w w'), h_{01}\circ \chi_0(w w') \big)\\ &= \big( f \circ \chi(w w'), f \circ \chi(w w') \big), \end{align}\] in particular, \(f \circ \chi\) is a homomorphism \(\hat{K}_m \to \mathbb{A}\). Thus, \(f\) is a homomorphism; its idempotence is clear. ◻
Without loss of generality we may assume that \(f\) acts as the first projection on \(S/_\theta\). Thus, by definition of \(f\) each pair \((a,b) \in S^2 \cap D\) satisfies \(h_{01}(a,b)/_\theta = a/_\theta\). Further, recall that \(h_0\) and \(h_1\) act as the first and second projection on \(S/_\theta\), respectively.
We now fix \(a,b\in S\) in different classes of \(\theta\). We use Lemma [lem:mapFactory] to show that there is a polymorphism \(g: \mathbb{A}^2 \rightarrow \mathbb{A}\) with \(g(a,b)/_\theta = b/_\theta\) and \(g(a',b')/_\theta = a'/_\theta\) whenever \(a',b'\in S\) with \((a,b)/_\theta\not= (a',b')/_\theta\), contradicting the fact that \((S,\theta)\) is a naked set. To this end, we verify that for every graph \(G\) and every coloring \(\chi\colon \hat{G}\to \mathbb{A}^2\), there is a coloring \(\eta\colon \hat{G}\to \mathbb{A}\) such that for all \(vw \in \hat{G}\) it holds: \[\eta(vw) \in \begin{cases} b/_\theta, &\text{ if } \chi(v w) \in S^2 \text{ and } \chi(v w)/_\theta = (a,b)/_\theta \\ a'/_\theta, &\text{ if } \chi(vw) = (a',b') \in S^2\text{ and } (a',b')/_\theta \not= (a,b)/_\theta. \end{cases}\]
So let \(G\) be a graph and \(\chi = (\chi_1,\chi_2) \colon \hat{G}\to \mathbb{A}^2\) a coloring. Note that the coloring \(d^N\circ \chi\) agrees with \(\chi\) modulo \((S,\theta)\) on all \(vw \in \hat{G}\) with \(\chi(vw)\in S^2\) and additionally its image is contained in \(D\). Take any edge \(v_0 w_0 \in \hat{G}\) with \(\chi(v_0 w_0)/_\theta = (a,b)/_\theta\) and consider the cut \(c \coloneq G\setminus \{v_0,w_0\} \mid \{v_0,w_0\}\). Define \(\eta'\colon \hat{G}\to \mathbb{A}\) to be the coloring \(h \circ (d^N\circ \chi,\hat{c})\). Using the properties of \(h\), in particular that \(h_{01}|_D\) acts as the first projection on \(S/_\theta\) we obtain that for \(v w \in \hat{G}\) it holds \[\eta'(v w) \in \begin{cases} h_{1}(d^N \circ \chi(v w))/_\theta = b/_\theta &\text{ if } v w = v_0 w_0 \\ h_{01}(d^N \circ \chi(v w))/_\theta = a'/_\theta &\text{ if } \chi(v w) = (a',b') \in S^2\text{ and } |\{v, w\}\cap \{v_0,w_0\}| = 1 \\ h_{0}(d^N \circ \chi(v w))/_\theta = a'/_\theta &\text{ if } \chi(v w) = (a',b') \in S^2 \text{ and } |\{v, w\} \cap \{v_0,w_0\}| = 0. \end{cases}\] Define the coloring \(\chi' \coloneq (\eta',\chi_2)\colon \hat{G} \to \mathbb{A}\) and observe that on all \(vw \in \hat{G}\setminus \{v_0 w_0\}\) with \(\chi(vw)\in S^2\), \(\chi(vw)\) and \(\chi'(vw)\) agree modulo \(\theta\) and furthermore \(\chi'(v_0 w_0)/_\theta = (b,b)/_\theta\). We repeat the same procedure with \(\chi'\) in place of \(\chi\) with every further edge \(v_0' w_0' \in \hat{G}\) with \(\chi(v_0' w_0')/_\theta = (a,b)/_\theta\) until we have exhausted all such edges. We obtain a coloring \(\tilde{\eta} \colon \hat{G} \to \mathbb{A}\) such that for all \(vw \in \hat{G}\) it holds \[\tilde{\eta}(v w) \in \begin{cases} b/_\theta &\text{ if } \chi(v w)/_\theta = (a,b)/_\theta\\ a'/_\theta &\text{ if } \chi(v w) = (a',b') \in S^2 \text{ and } (a',b')/_\theta \not= (a, b)/_\theta. \end{cases}\] Thus, \(\tilde{\eta}\) is the desired coloring \(\eta\). ◻
6 Ramsey’s toolbox↩︎
In this section we prove the Ramsey-theoretical claims used in Section 4 and Section 5, namely Propositions [prop:homotopy95witness] and [prop:homotopy95witness2] and Lemma [lem:mapFactory].
Definition 3. A category \(\mathcal{C}\) is said to be Ramsey* if for any two objects \(\mathbf{A}\) and \(\mathbf{B}\) and any finite set \(N\) there exists an object \(\mathbf{C}\) such that for all maps \(\hom(\mathbf{A},\mathbf{C})\xrightarrow{\chi} N\) there exists a morphism \(\mathbf{B}\xrightarrow{g} \mathbf{C}\) such that the composition \[\chi\circ g_*:\hom(A,B)\xrightarrow{g_*} \hom(A,C)\xrightarrow{\chi} N\] is a constant map, where \(g_*\) is the postcomposition map \(f\mapsto g\circ f\). Any such object \(\mathbf{C}\) is called a Ramsey witness of \(\mathbf{A},\mathbf{B}\) and \(N\).*
Given a number \(n\) we define a category \(\mathcal{C}\), where the objects are \(\mathbb{A}^n\)-colored, linearly ordered graphs, that is, triples \(\mathbf{G}=(G,\chi,<)\) where \(G\) is a graph, \(\chi\colon \hat{G}\to \mathbb{A}^n\) is a homomorphism and \(<\) is a linear order on the vertices of \(G\). A morphism in this category \(\iota\colon\mathbf{G}=(G,\chi,<)\to\mathbf{G'}=(G',\chi',<')\) is an embedding between the graphs \(G\) and \(G'\), that is monotone with respect to the linear orders and that respects the colorings, meaning \(\chi' \circ \hat{\iota} = \chi\). Since the patterns we are forbidding are cliques, a theorem by Nešetřil and Rödl [51] implies that for any given \(n\), \(\mathcal{C}\) enjoys the Ramsey property. For a more recent treatment see Theorem 2.9 in [52].
Theorem 2 (Special case of [51]). For every \(n\) the category \(\mathcal{C}\) is Ramsey.
Let \(\mathcal{D} \colon \mathcal{C}^{\mathrm{op}}\to \mathrm{set}\) be a contravariant functor from \(\mathcal{C}\) to the category of sets. We call a family \(\{s_\mathbf{G}\}_{\mathbf{G}\in \mathcal{C}}\) a solution of \(\mathcal{D}\) if \(s_\mathbf{G}\in \mathcal{D}(\mathbf{G})\) for each \(\mathbf{G}\in \mathcal{C}\), and for every embedding \(\iota\colon \mathbf{G} \to \mathbf{H}\) in \(\mathcal{C}\), we have \(\mathcal{D}_\iota(s_\mathbf{H}) = s_\mathbf{G}\). We say that a category is confluent if for any three objects and two morphisms \[\mathbf{B} \leftarrow\mathbf{A} \rightarrow\mathbf{C}\] there is an object \(\mathbf{D}\) and two morphisms \[\mathbf{B} \rightarrow \mathbf{D} \leftarrow \mathbf{C}.\] The category \(\mathcal{C}\) described above is confluent: indeed given two colored ordered graphs \(\mathbf{B}\) and \(\mathbf{C}\) the corresponding \(\mathbf{D}\) can be obtained by taking the disjoint union and completing the resulting partial order in an arbitrary way to a linear order.
Theorem 3 (Theorem 1.2 in [53]). Let \(\mathcal{C}\) be a category that is confluent and Ramsey and let \(\mathcal{D}\colon \mathcal{C}^{\mathrm{op}}\to\mathrm{set}\) be a functor, such that the set \(\mathcal{D}(\mathbf{C})\) is finite and nonempty for each \(\mathbf{C}\in \mathcal{C}\). Then there is a solution of \(\mathcal{D}\).
We have gathered all necessary ingredients to prove the following lemma, from which Proposition [prop:homotopy95witness2] and Lemma [lem:mapFactory] will follow.
Lemma 3. Fix a number \(n\), a graph \(G\) and a coloring \(\chi\colon \hat{G}\to \mathbb{A}^n\). Then there exists a graph \(H\) and a coloring \(\chi'\colon \hat{H}\to \mathbb{A}^n\) such that for every coloring \(\eta\colon\hat{H}\to \mathbb{A}\), there is a polymorphism \(f\colon \mathbb{A}^n\to \mathbb{A}\) and an embedding \(\phi\colon G\to H\) such that \[\chi'\circ\hat{\phi} = \chi \text{ and } f\circ \chi = \eta\circ\hat{\phi}.\]
Proof. We define \(\mathbf{G}:=(G,\chi,<)\) where \(<\) is some linear order. Given a colored, ordered graph \(\mathbf{J} = (J,\xi,<)\), we call a coloring \(\eta\colon \hat{J}\to \mathbb{A}\) good if there is a polymorphism \(f\) and a morphism \(\phi\colon \mathbf{G}\to\mathbf{J}\) satisfying the condition above. Otherwise we call \(\eta\) bad.
Let \(\mathcal{D}\colon\mathcal{C}^{\mathrm{op}}\to\mathrm{set}\) be the functor that sends \(\mathbf{J}\) to the set of all bad colorings \(\eta \colon\hat{J}\to \mathbb{A}\). For each embedding \(\iota\colon \mathbf{J'}\to\mathbf{J}\), let \(\mathcal{D}_\iota\) be the map that restricts colorings \(\eta\) along \(\iota\): \[\mathcal{D}_\iota\colon \mathcal{D}(\mathbf{J})\to\mathcal{D}(\mathbf{J'}),\quad \eta\mapsto \eta\circ\hat{\iota}\] One may verify that, given a bad coloring \(\eta\), the composition \(\eta\circ\hat{\iota}\) is also bad. The claim will follow from Theorem 3 once we show that this diagram has no solution, as this implies that \(\mathcal{D}(\mathbf{H})\) is empty for some \(\mathbf{H}\), meaning that all its colorings are good. Indeed, assume that \(\{\eta_\mathbf{J}\}_{\mathbf{J}\in\mathcal{C}}\) is a solution. For each tuple \(a\in\mathbb{A}^n\), let \(\mathbf{G}_a\) be \(K_2\) with the standard order and with its single edge \(01\) colored by \(a\). Then define a polymorphism \(f\) as \[f(a)\coloneq \eta_{\mathbf{G}_a}(01).\] To show that this constitutes a polymorphism, consider any coloring \(\chi\colon\hat{K}_m\to\mathbb{A}^n\), and let \(\mathbf{G}_\chi:= (K_m, \chi, <)\), where \(<\) is the standard order on the \(m\)-element set. We show that \(f\circ \chi = \eta_{\mathbf{G}_\chi}\), which yields that \(f\circ \chi\) is indeed a homomorphism \(\hat{K}_m\to \mathbb{A}\). Given an edge \(vw\) of \(K_m\) with \(v < w\) there is a morphism in \(\mathcal{C}\) \[\iota\colon \mathbf{G}_{\chi(vw)}\to\mathbf{G}_\chi,\quad 01\mapsto vw\] Now compute the following: \[\begin{align} f(\chi(vw)) = \eta_{\mathbf{G}_{\chi(vw)}} (01) &= \mathcal{D}_\iota ( \eta_{\mathbf{G}_\chi})(01) \\&= \eta_{\mathbf{G}_\chi}(\hat{\iota}(01)) = \eta_{\mathbf{G}_\chi}(vw) \end{align}\] The first, third and fourth equalities hold by definition, the second because \(\{\eta_\mathbf{J}\}_{\mathbf{J}\in\mathcal{C}}\) is a solution. But the same computation shows that \(\eta_{\mathbf{G}}=f\circ\chi\), contradicting the assumption that \(\eta_{\mathbf{G}}\) is bad. ◻
Proof. Let \(G_\bullet\) be a graph consisting of \(|A^n|\) many disjoint edges and let \(\chi_\bullet\colon\hat{G}_\bullet\to\mathbb{A}^n\) be a surjective homomorphism. By Lemma 3 there is a graph \(H\) and a coloring \(\chi\colon\hat{H}\to\mathbb{A}^n\), such that for all colorings \(\eta\colon\hat{H}\to \mathbb{A}\), there is a polymorphism \(f\) and an embedding \(\phi\), such that \[\chi\circ\hat{\phi} = \chi_\bullet \text{ and } f\circ \chi_\bullet = \eta\circ\hat{\phi}.\] Pick a coloring \(\eta\colon \hat{H}\to \mathbb{A}\) such that \(\eta(vw)\in U_{\chi(vw)}\) for all edges \(vw\in\hat{H}\). Then for every \(a\in\mathbb{A}^n\) there is an edge \(xy\in \hat{G}_\bullet\) with \(a=\chi_\bullet(xy)=\chi(\hat{\phi}(xy))\), so \[f(a) = f(\chi_\bullet(xy)) = \eta(\hat{\phi}(xy)) \in U_{\chi(\hat{\phi}(xy))} = U_a\] ◻
Proof. Let \(G_\bullet\) be the disjoint union of all graphs \(G_i\) and let \(\chi_\bullet\colon \hat{G}_\bullet\to\mathbb{A}^n\) be the disjoint union of the colorings \(\chi_i\). Let \(J\) and \(\xi\colon \hat{J}\to\mathbb{A}^n\) be the graph and coloring obtained from Lemma 3. We construct the desired graph \(H\) as follows. Take the disjoint union of \(G_\bullet\) and \(J\). For every embedding \(\iota\colon G_\bullet\to J\)with \(\xi\circ\hat{\iota}=\chi_\bullet\), introduce a copy of \(G_\bullet \times P_2\) and identify:
every \(v\in G_\bullet\) with \((v,0)\in G_\bullet\times P_2\) and
every \((v,2)\in G_\bullet\times P_2\) with \(\iota(v)\in J\)
Let \(\chi\colon\hat{H}\to\mathbb{A}^n\) be the following coloring: \[\chi(e) = \begin{cases} \chi_\bullet(vw) &\text{if } e = (vw,ij)\in\widehat{G_\bullet\times P_2}\\ \xi(e) &\text{if } e\in \hat{J} \end{cases}\] Observe that \(\chi\) is indeed a homomorphism, as every clique in \(H\) is fully contained in either \(J\) or one of the \(G_\bullet\times P_2\).
Let the embeddings \(\phi_i\colon G_i\to H\) be the respective inclusions \(G_i\subseteq G_\bullet\subseteq H\). The distance between different \(G_i\) is at least four, as any path has to go through \(J\). For every coloring \(\eta\colon \hat{H}\to\mathbb{A}\) consider its restrictions \(\eta_J\) and \(\eta_\bullet\) to \(J\subseteq H\) and \(G_\bullet\subseteq H\) respectively. The copy of \(G_{\bullet}\) is the one from which this construction started; in Figure 8 it is the copy on the left. By Lemma 3 there is a polymorphism \(f\colon\mathbb{A}^n\to \mathbb{A}\) and an embedding \(\iota\colon G_\bullet\to J\) such that \(f\circ\chi_\bullet = \eta_J\circ \hat{\iota}\). Restricting \(\eta\) to the copy of \(G_\bullet\times P_2\) in \(H\) corresponding to \(\iota\), yields a 2-step cut-homotopy \(\eta_\bullet\sim_2 f\circ\chi_\bullet\). Restricting this cut-homotopy to \(G_i\times P_2\subseteq G_\bullet\times P_2\) yields cut-homotopies \(\eta\circ \hat{\phi}_i\sim_2 f\circ\chi_i\). ◻
Recall that we use the notation \((vw, ij)\) for the edge \((v, i)(w, j)\) of a graph \(G\times H\).
Lemma 4. Let \(k\) and \(n\) be numbers and \(U_{a,ij} \subseteq A\) for all \({a}\in A^n\) and \(ij \in \hat{P_k}\). Assume that for every graph \(G\) and every coloring \(\chi\colon \hat{G} \to \mathbb{A}^n\), there is a coloring \(\eta\colon \widehat{G\times P_k}\to \mathbb{A}\) such that \[\eta(vw,ij)\in U_{\chi(vw), ij}\] for all edges \((vw,ij)\in\widehat{G\times P_k}\). Then there exists a homomorphism \(h \colon \mathbb{A}^n \times \hat{P_k} \to \mathbb{A}\) with \(h({a}, ij)\in U_{{a}, ij}\) for all \(a \in A^n\) and \(ij \in \hat{P_k}\).
In particular, for each pair of edges \(vw\) in \(G\) and \(ij\) in \(P_k\) with \(i\not=j\), the assumptions require that both \(\eta(vw,ij)\) and \(\eta(vw, ji)\) belong to \(U_{\chi(vw),ij}\).
Proof. Let \(\mathcal{D}\colon \mathcal{C}^{\mathrm{op}}\to\mathrm{set}\) be the functor that sends each linearly ordered \(\mathbb{A}^n\)-colored graph \(\mathbf{G}\coloneq (G,<,\chi)\) to the set of all homomorphisms \(\eta\colon \widehat{G\times P_k} \to \mathbb{A}\) that satisfy \(\eta(vw,ij)\in U_{\chi(vw),ij}\) for all \(vw \in \hat{G}\) and \(ij\in\hat{P}_k\). This set is finite and, by assumption, nonempty. For a morphism \(\iota \colon \mathbf{G} \to \mathbf{H}\) define the map \[\mathcal{D}_\iota\colon \mathcal{D}(\mathbf{H})\to \mathcal{D}(\mathbf{G})\] to be the precomposition with the embedding \(\widehat{(\iota\times \mathrm{id})}\colon \widehat{G\times P_k} \to \widehat{H \times P_k}\).
The category \(\mathcal{C}\) is confluent and Ramsey, hence, by Theorem 3, there exists a solution to \(\mathcal{D}\). Let \(\{\eta_{\mathbf{G}}\}_{\mathbf{G} \in \mathcal{C}}\) be such a solution. From this we construct the homomorphism \(h\colon \mathbb{A}^n \times \hat{P}_k \to \mathbb{A}\) as follows. Given \(a\in \mathbb{A}^n, ij\in \hat{P}_k\) with \(i\leq j\), we consider \(\mathbf{G}_{a} \coloneq (K_2, 0<1, 01 \mapsto a)\) and define \[h(a,ij) \coloneq \eta_{\mathbf{G}_{a}}(01, ij).\] Note that the left-hand side of the definition does not depend on the order of \(i\) and \(j\), but the right-hand side does, as \((01,ij)\neq (01,ji)\), by our naming convention for edges of \(G \times P_k\). Note that \(\eta_{\mathbf{G}_{a}}(01, ij)\) belongs to \(U_{a,ij}\) by definition, so it remains to check that \(h\) is a homomorphism. To this end it suffices to check that for every \(K_m\), every coloring \(\chi\colon \hat{K}_m\to \mathbb{A}^n\), and every \(k\)-cut \(c\colon K_m\to P_k\), the mapping \(h \circ (\chi,\hat{c})\) is a homomorphism \(\hat{K}_m \to \mathbb{A}\). We define \(\mathbf{G}_\chi \coloneq (K_m,\chi, <_c)\) where \(<_c\) is any order that satisfies \(v<_c w\) for all \(v,w \in K_m\) with \(c(v)<c(w)\). In other words, \(<_c\) is the order that makes \(c\) monotone with respect to the standard order \(\leq\) on the vertices of \(P_k\). For all \(v, w \in K_m\) with \(v<_c w\), we have a morphism \[\iota\colon\mathbf{G}_{\chi(vw)} \to\mathbf{G}_\chi,\quad 01\mapsto vw,\] which we use to compute \[\begin{align} h(\chi(vw), \hat{c}(vw) ) &= \eta_{\mathbf{G}_{\chi(vw)}}( 01, \hat{c}(vw))\\&= \mathcal{D}_\iota (\eta_{\mathbf{G}_{\chi}})( 01, \hat{c}(vw)) \\&= \eta_{\mathbf{G}_\chi} \circ \widehat{(\iota\times\mathrm{id})}( 01, \hat{c}(vw)) \\&= \eta_{\mathbf{G}_{\chi}}( vw, \hat{c}(vw))\\&= \eta_{\mathbf{G}_\chi} \circ \widehat{(\mathrm{id},c)} (vw). \end{align}\] Note that the first equality holds because \(c(v) \leq c(w),\) the second one holds because \(\{\eta_{\mathbf{G}}\}_{\mathbf{G} \in \mathcal{C}}\) constitutes a solution of \(\mathcal{D}\) while the remaining equalities are simply expansions of definitions. This shows that \(h\circ (\chi,\hat{c})\colon\hat{K}_m \to \mathbb{A}\) equals the map \(\eta_{\mathbf{G}_\chi} \circ \widehat{(\mathrm{id},c)}\), which is a homomorphism, since it is the composition of two homomorphisms. ◻
Proof. Fix two polymorphisms \(f,g\colon \mathbb{A}^n\to\mathbb{A}\) that are not \(k\)-step cut-homotopic and set \[U_{b,ij}\coloneq \begin{cases} \{f(b)\} &\text{if } ij = 00\\ \{g(b)\} &\text{if } ij = kk\\ A &\text{otherwise,} \end{cases}\] whenever \(ij\) is an edge in \(P_k\) and \(b\in\mathbb{A}^n\). By the contraposition of Lemma 4, there is a graph \(G_{fg}\) and a coloring \(\chi_{fg}\colon \hat{G}_{fg}\to\mathbb{A}^n\) such that there is no coloring \(\eta\colon \widehat{G_{fg}\times P_k}\to \mathbb{A}\) with \(\eta(vw,00) = f(\chi_{fg}(vw))\) and \(\eta(vw,kk) = g(\chi_{fg}(vw))\). In other words, there is no \(k\)-step cut-homotopy between \(f\circ\chi_{fg}\) and \(g\circ \chi_{fg}\).
We then find the desired \(G\) by taking the disjoint union of all \(G_{fg}\) where \(f,g\) are not \(k\)-step cut-homotopic and taking \(\chi\colon \hat{G}\to \mathbb{A}^n\) to be the disjoint union of all \(\chi_{fg}\). ◻
Although Theorem 3 is a compactness lemma, its choice-free cousin, Proposition 3.1 in [53], suffices for all applications above. From its proof, one can construct the graphs we obtain in Propositions [prop:homotopy95witness] and [prop:homotopy95witness2] explicitly as iterated Ramsey witnesses.