Nankai Logic Colloquium, Nankai, March 2023

Abstract: We aim to study the complexity of conjugacy problems for automorphisms of countable graphs G. Since conjugacy is an equivalence relation on Aut(G), we will study complexity using the invariant descriptive set theory, that is, the Borel reducibility hierarchy. After introducing this background setup, we will give a series of examples of locally finite graphs G whose conjugacy problems have a variety of different complexities. We will see conjugacy problems which are smooth (completely classifiable), complete for hyperfinite relations (E0), complete for essentially countable Borel equivalence relations (E_infinity), and intermediate between E0 and E_infinity.