On A Correspondence Between Graphs and Groups

Abstract

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 $\underset{\_}{\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.