On Wednesday (23 October) at 15:00 B404<https://maps.herts.ac.uk/poi/1221>, we have the Mathematical and Theoretical Physics Seminar by our very own Catarina Carvalho<https://researchprofiles.herts.ac.uk/en/persons/catarina-carvalho>. (There is no pre-seminar by Catarina this week due to schedule constraints. Instead, Dimitri Kanakaris Decavel will give a talk Wednesday 14:00 D450<https://maps.herts.ac.uk/poi/1265> on supersymmetric localisation.) After the main seminar, there will be tea and refreshments on Spectra<https://maps.herts.ac.uk/poi/4694> 3rd floor Connect Area.
The constraint satisfaction problem<https://en.wikipedia.org/wiki/Constraint_satisfaction_problem> is a general and fundamental problem in computer science (sudoku, type inference, AI …); in many cases, it can be reduced to the problem of finding which directed graphs (digraphs) admit a homomorphism<https://en.wikipedia.org/wiki/Graph_homomorphism> to a given digraph. Now, sometimes it turns out that there is no homomorphism between a given pair of digraphs. If you are an optimist (like Leibniz<https://en.wikipedia.org/wiki/Principle_of_sufficient_reason>), you might hope that there’s a good reason — an obstruction — for the digraph homomorphism to fail to exist. Catarina will discuss the conjecture that, for a certain class of digraphs, these obstructions are given by the caterpillars<https://en.wikipedia.org/wiki/Caterpillar_tree>, which are ‘trees that metamorphose into paths when the cocoon of endpoints is removed’.
Title: Digraphs with caterpillar duality
Abstract:We search for the class of digraphs whose obstruction sets, in the digraph homomorphism problem, consist of caterpillars. The conjecture being that this class of digraphs should be the same as the class of digraphs that are preserved by majority and set function polymorphisms. This is work in progress.