Isomorphisms, homomorphisms, and some algebra

Abstract: We give a survey on connections between Graph Isomorphism, the CSP, and counting homomorphisms. In the first part we give a brief review of the main approaches to solving the Graph Isomorphism problem and make some observations on how the CSP techniques can be helpful. In the second part we focus on relaxations of graph isomorphisms and how they can be characterized using the numbers of homomorphisms from various graph classes.

computational complexitycategory theorylogic

Audience: researchers in the topic

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.