Andrei Bulatov: Homomorphism counts and graph equivalence

Speaker:

Andrei Bulatov (Simon Fraser University)

Time:

  • First Lecture:
    • 17:00-18:00 Beijing Time
    • April 18, 2025 (Friday)
  • Second Lecture:
    • 10:00-11:00 Beijing Time
    • April 20, 2025 (Sunday)
  • Third Lecture:
    • 16:00-17:00 Beijing Time
    • April 23, 2025 (Wednesday)

Venue:

518, Research Building 4

Abstract:

Let A be a class of graphs. Graphs G,H are said to be left (right) A-equivalent if for every F\in A the number of homomorphisms from F to G and H (from G and H to F) are equal. This line of research has started almost 60 years ago by Lovasz and has received much attention recently. Left equivalence usually corresponds to some structural graph parameters, while right equivalence seem to be expressible in terms of various logics. We introduce the problem, briefly survey recent results and state several future research directions.

Speaker Bio:

Dr Bulatov received his PhD in 1995 from the Ural State University in Ekaterinburg, Russia. His early research area was universal algebra and clone theory. When connections between universal algebra and computer science had been discovered, he pioneered the so-called algebraic approach to the Constraint Satisfaction Problem and related fields. In 2000 Dr Bulatov moved, first, to the University of Oxford, and then to Simon Fraser University in Canada, where he works till now. Dr Bulatov is an expert on applications of algebraic methods in computer science. He is a recipient of the 2021 Godel Prize and 2024 Frontiers of Science Award from the International Congress on Basic sciences.