On A Correspondence Between Graphs and Groups

A group satisfies PP3 (the permutation property of degree \(3\)) if any product of \(3\) elements remains invariant under some nontrivial permutation of its factors, or equivalently, if \(G\) has at most one nontrivial commutator of order \(2\). A PP3 group is \(\underline{\text{elementary}}\) if it is a finite group of exponent at most \(4\). There is an algorithm that associates an elementary PP3 group to an arbitrary graph. It follows, for instance, that almost every nontrivial graph automorphism has order a power of \(2\) and that the first-order theory of (elementary) PP3 groups is hereditarily undecidable.