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ý.

commutative algebraalgebraic topologycombinatorics

Audience: researchers in the topic

Applications of Combinatorics in Algebra, Topology and Graph Theory

Series comments: To get email notification of the upcoming talk in this series, please subscribe to the mailing list or contact one of the organizers. Please visit webinar webpage for information about forthcoming and previous webinars. Thank you!