Boise Set Theory and Logic Seminar, Boise, October 2019

Abstract: Given a graph or tree G, the conjugacy problem for G is the conjugacy equivalence relation on the group Aut(G) of automorphisms of G. In this talk we will introduce the basic framework for studying the complexity of the conjugacy problem for G, and then use it to examine a series of examples of graphs and trees G. In particular we will demonstrate that a variety of complexities can occur, from trivial (smooth), up to maximally complex (Borel complete), and in between.