← All problems

The dichotomy conjecture for conjugacy problems of automorphism groups

17 years old · traced to

Let cmathcalMcmathcal M be a countable model of an caleph0caleph_0-categorical theory, let cmathrmautcmathcalMcmathrm{aut}cmathcal M be its automorphism group, and let cmathcalCcmathcalMcmathcal C_{cmathcal M} be the conjugacy equivalence relation on cmathrmautcmathcalMcmathrm{aut}cmathcal M, defined by

fCMg  ⟺  (∃h∈aut⁡M)(hf=gh).f\mathrel{\mathcal C_{\mathcal M}}g\iff(\exists h\in\operatorname{aut}\mathcal M)(hf=gh).

Conjugacy-complexity dichotomy conjecture. If cmathcalMcmathcal M is the countable model in an caleph0caleph_0-categorical theory, then cmathcalCcmathcalMcmathcal C_{cmathcal M} is either smooth or Borel complete.

This conjecture asks which Borel complexities can occur for conjugacy relations of automorphism groups of countable models of caleph0caleph_0-categorical theories. The paper establishes Borel completeness for the conjugacy problem of the random graph, while noting smooth examples such as the automorphism group of a countable set and that of the complete binary tree; the general dichotomy remains open in the supplied text.

References
  1. Samuel Coskey, Paul Ellis and Scott Schneider, “The conjugacy problem for the automorphism group of the random graph”, arXiv:0902.4038 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.