The conjugacy problem for the automorphism group of the random graph

Abstract

We prove that the conjugacy problem for the automorphism group of the random graph is Borel complete, and discuss the analogous problem for some other countably categorical structures.

7 pages

Cited by in corpus (4)

• The complexity of classification problems for models of arithmetic
• The conjugacy problem for automorphism groups of countable homogeneous structures
• A López-Escobar theorem for metric structures, and the topological Vaught conjecture
• Conjugacy for homogeneous ordered graphs