Семинар по маломерной математике "Москва-Петербург"
СПб, ПОМИ, 24.05.2002, 16:00--17:45, ауд. 311

Е.А.Кудрявцева, Д.Л.Гонсалвес, Х.Цишанг
"Индекс пересечения кривых на поверхностях и
новый алгоритм для нахождения минимума числа точек пересечения"

Пусть $\gamma_1,\gamma_2$ -- две кривые на поверхности $S$ с закрепленными
концами на границе $\partial S$. Определяется {\it гомотопический индекс
пересечения} $\lambda(\gamma_1,\gamma_2)$ этих кривых, принимающий
значения в групповом кольце ${\bold Z}[\pi_1(S)]$ фундаментальной группы
поверхности. Как и для алгебраического индекса пересечения
$\langle \gamma_1,\gamma_2 \rangle \in \bold Z$, его значение зависит   
только от гомотопических классов $g_i=[\gamma_i]$, $i=1,2$, кривых.

Показывается (теорема Тураева), что число ненулевых коэффициентов элемента
$\lambda(\gamma_1,\gamma_2)$ равно минимальному числу точек пересечения
кривых $\tilde\gamma_1,\tilde\gamma_2$ по всем кривым классов $g_1,g_2$.

Дается комбинаторный алгоритм, вычисляющий по данным элементам
$g_1,g_2 \in \pi_1(S)$ минимум числа точек пересечения. В отличие от
известных алгоритмов (Рейнхарт, Цишанг, Чиллингворт, Бирман-Сериес,
Люстиг,...), найдены также гомотопические классы точек пересечения кривых
$(\hat\gamma_1,\hat\gamma_2)$ классов $g_1,g_2$, реализующих минимум.