Boise Set Theory Seminar, Boise, September 2014

Abstract: Before studying the conjugacy problem in a given Polish group G, it is natural to ask what is the complexity of the conjugacy equivalence relation. We study this relation in the case when G is the automorphism group of a homogeneous graph (directed or undirected). The homogeneous graphs have been classified by Cherlin and we will briefly run through the complete list. Then we will give examples where the complexity of the conjugacy relation on G is smooth, complete, and in between.