Košický kombinatorický seminár

Abstrakt: 

In 2017 Andrei Bulatov and Dimitriy Zhuk independently proved the Dichotomy Conjecture for Constraint Satisfaction Problems, 30 years after it was proposed by Tomas Feder and Moshe Vardi. The methods involved deep results in algebra and logic, but also many combinatorial insights. Moreover, a result in algorithmic graph theory was one of the two main motivations for the Feder-Vardi conjecture. I will describe this connection and offer personal reminiscences on how it came about. If time permits, I will also discuss some recent work and open problems on other versions of graph dichotomy.