Groupe de Travail


Théorie du MinMax et Algorithmie géométrique

Organisé par

Matthieu Fradelizi-Xavier Goaoc-Laurent Hauswirth

Ce groupe de travail collaboratif se propose de réunir des chercheurs intéressés par la géométrie, l'analyse, l'algorithmique et la géométrie computationnelle autour des techniques de MinMax et des estimées de hauteur de passage du col ("Waist inequality").

Les séances auront lieu les mardi après-midi 15h45 en Salle 4B05R ou 4B09R-Bâtiment Copernic-Marne-la-Vallée.

Programme :


  • mardi 14/11/17 à 15h45 : Stéphane Sabourau- "TBA"

  • mardi 07/11/17 à 15h45 : Vincent Jugé- "La forme normale de relaxation à droite pour les tresses est rationnelle"
Résumé :La représentation des tresses en tant que classes d'isotopie de laminations du disque épointé est à l'origine de toute une famille de formes normales dites "de relaxation". Intuitivement, chaque tresse est identifiée à un dessin sur le disque épointé, et en réduisant peu à peu la complexité de ce dessin on obtient une forme normale de relaxation. Nous étudierons une de ces formes normales, la forme normale de relaxation à droite, et nous montrerons que cette forme normale est rationnelle. Dans un deuxième temps, nous pourrons intéresser au caractère automatique de cette forme normale : celle-ci s'avère être bi-automatique synchrone si et seulement si le groupe de tresses considéré compte trois brins ou moins. Enfin, nous mettrons en évidence des liens entre cette forme normale et la sigma-positivité des tresses.
  • mardi 24/10/17 à 15h45 : Éric Colin de Verdière- "Le problème du nœud est dans NP -III" d'après Hass, Lagarias et Pippenger.

  • mardi 17/10/17 à 15h45 : Éric Colin de Verdière- "Le problème du nœud est dans NP -II" d'après Hass, Lagarias et Pippenger.

  • mardi 10/10/17 à 15h45 : Éric Colin de Verdière- "Le problème du nœud est dans NP-I" d'après Hass, Lagarias et Pippenger.

  • mardi 14/03 à 15h40 : Clément Maria-"Breaking complexity barriers in low-dimensional topology "
Résumé: In this talk, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the 3-manifold as parameter. The computation of TV4,q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the large family of 3-manifolds with first homology group of bounded rank. After giving an overview of complexity theory in low-dimensional topology, we will give details on the construction of the algorithm, relying on a new topological interpretation of the invariant TV4,q.
  • mardi 07/03 de 16h30 à 18h00 : Xavier Goaoc-"A point in many simplices: the convex case"

  • mardi 20/02 de 16h30 à 18h00 : Alfredo Hubard-"Selection Lemma-A point in many triangles"
Résumé: We will survey several results around the selection lemma and the waist inequality. We will give a full proof of the selection lemma for affine maps.
  • mardi 31/01 de 16h30 à 18h00 : Xavier Goaoc-"Kakeya discret et méthode polynomiale en géométrie des incidences"
Résumé: Je présenterai d'abord une borne, due à Zeev Dvir, pour le problème de Kakeya dans les corps finis. La preuve a inspiré Larry Guth et Nets Katz, qui ont développé une méthode polynomiale" pour l'étude de problèmes d'incidence dans R^d ; j'en donnerai un ou deux exemples.
  • mardi 10/01 de 16h20 à 17h30 : Stéphane Sabourau-"Waist Theorem IV"

  • mardi 13/12 de 16h à 17h30 : Stéphane Sabourau-"Waist Theorem III"

  • mardi 29/11 de 16h à 17h30 : Stéphane Sabourau-"Waist Theorem II"

  • mardi 22/11 de 16h à 17h30 : Stéphabe Sabourau-"Waist Theorem I"

Ce groupe de travail est organisé dans le cadre du Labex Bézout-Géométrie discrète