Talk15@CATGT: October 28, 2020, Marcin Wrochna (University of Oxford)

Speaker: Marcin Wrochna (University of Oxford)

Title: Understanding homomorphism approximation problems using topology
Abstract: We consider an approximation version of the graph colouring computational problem: can we efficiently distinguish a 3-colourable graph from a graph that is not even 100-colourable? More generally, given a structure that is promised to have a homomorphism to G, can we at least find a (much weaker) homomorphism to H? This is an ages-old question in which we recently made some surprising progress using topology and algebra, e.g. studying maps from a torus to a sphere, or looking at some adjoint functors in the category of graphs. I will introduce all necessary basics to explain these unexpected connections. Joint work with Andrei Krokhin, Jakub Opršal, and Standa Živný.