%0 Journal Article
%T On Borel complexity of the isomorphism problems for graph-related classes of Lie algebras and finite p-groups
%A Ruvim Lipyanski
%A Natalia Vanetik
%J Mathematics
%D 2008
%I arXiv
%X We reduce the isomorphism problem for undirected graphs without loops to the isomorphism problems for a class of finite dimensional $2$-step nilpotent Lie algebras over a field and for a class of finite $p$-groups. We show that the isomorphism problem for graphs is harder than the two latter isomorphism problems in the sense of Borel reducibility. A computable analogue of Borel reducibility was introduced by S. Coskey, J.D. Hamkins, and R. Miller. A relation of the isomorphism problem for undirected graphs to the well-known problem of classifying pairs of matrices over a field (up to similarity) is also studied.
%U http://arxiv.org/abs/0812.4158v6