Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
The first part of Whitehead algorithm made polynomial, als mathkol
Termin
04.12.2006, 17:15 Uhr -
Veranstaltungsort
E 28
Abstract
(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.
Hinweis
Tee ab 16.45 Uhr im Raum M614 (Mathetower)
Vortragende(r)
Enric Ventura
Herkunft der/des Vortragenden
Universitat Politecnica de Catalunya, Manresa-Barselona (Spain)