E 28

(Joint work with P. Weil and A. Roig) The classical Whitehead algorithm to check whether two words in a free group belong to the same orbit has two separated steps, the first of which being typically polinomial on the length of the words, and exponential on the ambient rank. However, some recent heuristics, partial results and computational experiments indicate that, in practice, the algorithm is faster than this. We present a modification of this classical algorithm which is polynomial on both the length and the rank ambient. The new algorithm is surprisingly simple, making use of a classical argument about Whitehead automorphisms and Whitehead graphs, and the classical Max-Flow Min-Cut algorithm for graphs. The mentioned result is, in fact, extended from pairs of words to pairs of finitely generated subgroups, following an idea of S. Gersten. As an application, we obtain the first polynomial algorithm checking wether two given subgroups of a free group are one a free factor of the other.

Tee ab 16.45 Uhr im Raum M614 (Mathetower)

Enric Ventura

Universitat Politecnica de Catalunya, Manresa-Barselona (Spain)