The conjugacy problem for automorphism groups of homogeneous digraphs

Samuel Coskey, Paul Ellis

Abstract


We decide the Borel complexity of the conjugacy problem for automorphism groups of countable homogeneous digraphs. Many of the homogeneous digraphs, as well as several other homogeneous structures, have already been addressed in previous articles. In this article we complete the program, and establish a dichotomy theorem that this complexity is either the minimum or the maximum among relations which are classifiable by countable structures. We also discuss the possibility of extending our results beyond graphs to more general classes of countable homogeneous structures.

Keywords


conjugacy, homogeneous structure, Borel complexity

Full Text:

PDF


DOI: https://doi.org/10.11575/cdm.v12i1.62551

DOI (PDF): https://doi.org/10.11575/cdm.v12i1.62551.g46816

Refbacks

  • There are currently no refbacks.


Contributions to Discrete Mathematics. ISSN: 1715-0868