Séminaires : Séminaire de Géométrie

Equipe(s) : gd,
Responsables :L. Hauswirth, P. Laurain, R. Souam, E. Toubiana
Email des responsables :
Salle : https://bbb-front.math.univ-paris-diderot.fr/recherche/pau-6ha-of4-mea
Adresse :Sophie Germain
Description

Archive avant 2014

Hébergé par le projet Géométrie et Dynamique de l’IMJ-PRG

 

 


Orateur(s) Éric COLIN DE VERDIERE - CNRS, LIGM, Marne-la-Vallée,
Titre Contractibilité de courbes sur le bord des 3-variétés
Date12/12/2016
Horaire13:30 à 15:00
Diffusion
RésumeÉtant donnée une courbe c dans une 3-variété triangulée M, comment
déterminer si c est contractile ?
Dans la suite, nous supposons toujours que c est sur le bord de M. Le cas
où c est sans auto-intersections a été étudié par Hass, Lagarias et
Pippenger (1999) en utilisant la notion de surfaces normales, en lien avec
le problème du noeud ; ils montrent que le problème est dans NP, ce qui
donne un algorithme exponentiel. Je décrirai un algorithme avec la même
complexité qui résout le problème dans le cas plus général où c peut avoir
des auto-intersections. La méthode repose de façon clé sur la
démonstration du Loop Theorem.

Cet exposé, résultat d'un travail en commun avec Salman Parsa, ne
nécessite aucune connaissance préalable en algorithmique et complexité.
Sallehttps://bbb-front.math.univ-paris-diderot.fr/recherche/pau-6ha-of4-mea
AdresseSophie Germain
© IMJ-PRG