In promise graph colouring, the task is to find a 100-colouring of a graph that is promised to be 3-colourable, say. We prove the hardness of a related problem, PCSP($C_n$, $K_3$), by studying its polymorphisms: we view graphs as topological spaces and polymorphisms as continuous functions up to continuous deformations. It turns out this forgets irrelevant combinatorial noise in a polymorphism, revealing that it essentially only depends on a few inputs. In other words, with basic algebraic topology we can ‘decode’ a polymorphism by showing it is very ‘concentrated’ on a few inputs. I will then turn to adjunction: a definition that captures powerful and almost trivial reductions between Promise CSPs, some pushing the state-of-the-art for classical promise colouring, some related to topology, but overall quite mysterious and ostensibly isolated.
Joint work with Andrei Krokhin, Jakub Opršal, and Stanislav Živný.