Classification of automorphic conjugacy classes in the free group on two generators

Abstract

We associate a finite directed graph with each equivalence class of words in $F_2$ under $\mathrm{Aut}{F}_2$, and we completely classify these graphs, giving a structural classification of the automorphic conjugacy classes of $F_2$. This classification refines work of Khan and proves a conjecture of Myasnikov and Shpilrain on the number of minimal words in an automorphic conjugacy class whose minimal words have length $n$, which in turn implies a sharp upper bound on the running time of Whitehead's algorithm for determining whether two words in $F_2$ are automorphic conjugates.

28 pages; final version (more specific title, sharpened some results in Section 3, and expanded Section 5)