98-13: On the Complexity of the Isomorphism Relation for Finitely Generated Groups

DIMACS TR: 98-13

On the Complexity of the Isomorphism Relation for Finitely Generated Groups

Authors: Simon Thomas, and Boban Velickovic

ABSTRACT
Working within the framework of descriptive set theory, we show that the isomorphism relation for finitely generated groups is a universal essentially countable Borel equivalence relation. We also prove the corresponding result for the conjugacy relation for subgroups of the free group on two generators. The proofs are group-theoretic, and we refer to descriptive set theory only for the relevant definitions and for motivation for the results.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-13.ps.gz

DIMACS Home Page