Words, cycles and paths
Speaker:
Benoit Larose, Université du Québec à Montréal (UQÀM)
Date and Time:
Sunday, June 6, 2021 - 10:00am to 11:00am
Location:
Online
Abstract:
Polymorphisms of relational structures have come to play a critical role in the study of the algorithmic complexity of constraint satisfaction problems. We apply topological and combinatorial tools to investigate the nature of polymorphisms of graphs. In particular, we show that reflexive cycles of girth at least 4 are Słupecki, i.e. their surjective polymorphisms are essentially unary. (Work in progress, in collaboration with I. Larivićre (Waterloo) and D. E. Pazmiño Pullas (UQAM).)