Groupe de Travail


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

Organisé par

E. Colin de Verdière, M. Fradelizi, L. Hauswirth, A. Hubard

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 15h30 Bâtiment Copernic-4ème étage-salle rose--4B107--Marne-la-Vallée.

Programme :


  • mardi 19/02/19 à 15h30 : Marcos Cossarini- "Discrete geometry of surfaces towards the filling area conjecture II"

  • mardi 12/02/19 à 15h30 : Marcos Cossarini- "Discrete geometry of surfaces towards the filling area conjecture I"
Résumé : Is the hemisphere a minimal isometric filling of its boundary circle, or can it be replaced by a Riemannian surface of smaller area without reducing the distance between any boundary points? Gromov posed the question and proved the strict minimality of the Euclidean hemisphere among surfaces homeomorphic to a disk. Ivanov considered more general Finsler metrics and proved that the Euclidean hemisphere is still minimal among disks, but there are many other Finsler disks that isometrically fill the circle and have the same area. In this talk I will present a discrete version of the problem:Can a cycle graph of length 2n be filled isometrically with a square-celled combinatorial surface made of less than n(n-1)/2 cells? (The filling is said isometric if the distance between each pair of boundary vertices, measured along the 1-skeleton graph of the filling surface, is not smaller than the distance along the boundary cycle.) This discrete question is equivalent to the continuous problem for self-reverse Finsler metrics, and is related to some known problems and structures including pseudo-line arrangements, minimizing the number of crossings between curves on surfaces, discrete differential forms, posets (including permutations with the Bruhat order), integral polygons, CAT(0) cubical complexes, integer linear programming, electrical networks and plabic graphs.
  • mardi 05/03/18 à 15h00 (Attention Changement d'horaire) : Olivier Guédon- "Inégalités isopérimétriques pour les voisinages tubulaires d'ensembles analytiques complexes."
Résumé : à l'aide d'une méthode de localisation stochastique, on montrera que parmi les fonctions $f: \C^n \to \C^k$ holomorphes avec $f(0)$ fixé, si $Z := f^{-1}(0)$ alors $\gamma_n(Z+r)$ est minimale lorsque $f$ est linéaire, où $\gamma_,$ désigne la mesure Gaussienne sur $\C^n$ et $Z+r = \{z \in \C^n, d(z, Z) \le r\}$. D'après un article de Bo'az Klartag, voir https://arxiv.org/abs/1702.02315
  • mardi 13/02/18 à 15h45 : Alfredo Hubbard-"Un théorème topologique de superposition"
Résumé :Au début des années 1980, Bárány a montré qu'il existe une constante c_d telle que pour tout ensemble de points P dans R^d, il existe un point b in R^d t.q. une fraction d'au moins c_d des (d+1)-tuples de points de P contient b dans son enveloppe convexe. À la fin des années 80, Pach a prouvé une version chromatique de ce théorème : il existe une constante c_d’, telle que pour tout famille de d+1 ensembles P_0, P_1, ..., P_d, il existe un point p in R^d et des sous-ensembles A_i \subset P_i, de taille |A_i|>c_d'|P_i|, tels que tout (d+1)-tuple “arc-en-ciel”, i.e. a_0 \in A_0, a_1 \in A_1, ..., a_d \in A_d, contient p dans son enveloppe convexe. En 2010 Gromov a prouvé une version topologique du théorème de Bárány. Dans cet exposé j'expliquerai l'analogue topologique du théorème de Pach (la version “arc-en-ciel” du théorème de Gromov).
  • mardi 30/01/18 à 15h45 : Laurent Mazet- "Min-max et surface minimale V-La Loi de Weyl"

  • mardi 19/12/17 à 15h45 : Laurent Mazet- "Min-max et surface minimale IV"

  • mardi 05/12/17 à 15h45 : Laurent Mazet- "Min-max et surface minimale III"

  • mardi 28/11/17 à 15h45 : Laurent Mazet- "Min-max et surface minimale II"

  • mardi 21/11/17 à 15h45 : Laurent Mazet- "Min-max et surface minimale I"
Résumé : Dans ces exposés je prendrais la suite des exposés de Stéphane Sabourau du printemps dernier. Il avait introduit la notion de k-width pour les ouverts de R^n et montré un encadrement de ces nombres. Dans ces exposés, je tacherai d'expliquer que ces nombres ont une asymptotique précise (Loi de Weyl, par Liokumovich, Marques et Neves). Par la suite, je tacherai d'expliquer le lien avec les surfaces minimales et comment cette loi de Weyl permet de montrer l'existence d'une infinité de surfaces minimales dans les variétés riemanniennes (par Irie, Marques et Neves).
  • 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éphane Sabourau-"Waist Theorem I"

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