Galois

L'équipe-action Galois (Méthodes géométriques en combinatoire, algorithmes combinatoires en géométrie) est un projet financé par le labex Persyval. Les membres du projets sont

Le but principal du projet est de rassembler les chercheurs des différents laboratoires du site grenoblois pour s'attaquer à des problèmes difficiles alliant Géométrie et Combinatoire.

Réunions

  1. 26 Septembre 2013 (G-SCOP - 16h) - 1ère réunion, présentation des participants, et mise au point d'un plan de travail.
  2. 24 Octobre 2013 (Institut Fourier - 15h30) - Yves Colin de Verdière : Introduction à mu (1ère partie) et Louis Esperet : Boxicité des graphes. Compte-rendu des exposés
  3. 7 Novembre 2013 (G-SCOP - 16h) - Yves Colin de Verdière : Introduction à mu (2ème partie).  Compte-rendu de séance
  4. 12 Décembre 2013 (G-SCOP - 15h30) - Yves Colin de Verdière : Introduction à mu (3ème partie)
  5. 6 Février 2014 (G-SCOP - 15h30) - Francis Lazarus et Vincent Despré : Problème du cycle de partage dans un graphe plongé ou une triangulation. Présentation de Vincent
  6. 3 Avril 2014 (G-SCOP - 15h30) - Vincent Despré : Vincent explique comment une largeur de face 3 (resp. 4) dans une bouteille de Klein (resp. dans un double tore) assure l'existence d'un cycle de partage (articles de Robertson et Thomas 1991 et d'Ellingham et Zha 2003). Discussion concernant le cas général orientable (largeur de face au moins 6) et non-orientable (largeur de face au moins 5). Voir la présentation de Vincent ci-dessus pour plus de détails.
  7. 15 Mai 2014 (G-SCOP - 15h45) - Francis Lazarus : présentation des résultats de Piotr Przytycki sur le nombre maximal de courbes simples deux à deux non-homotopes et se coupant au plus une fois deux à deux. La version originale de Piotr et une version française remaniée.
  8. 16 Octobre 2014 (G-SCOP - 15h30) - Vincent Jost : Quelques pistes pour résoudre efficacement le problème suivant. Étant donnés un petit et un grand rectangle, comment placer un nombre maximum de copies du petit rectangle à l'intérieur de grand sans que ces copies se chevauchent. Ici, on suppose que les copies sont translatées les unes des autres et ont leurs côtés parallèles à ceux du grand rectangle. Louis Esperet nous donne ensuite une jolie preuve du fait qu'un rectangle pavable par des carrés a des côtés de longueurs commensurables. Compte-rendu de séance.
  9. 26 février 2015 (G-SCOP - 14h00) - András Sebö : Introduction au problème de Carathéodory entier pour les cônes. Rappelons que si V est une famille de vecteurs de Rd, le cône sur V, noté cone(V), est l'ensemble des combinaisons linéaires à coefficients non-négatifs de ces vecteurs. Le théorème de Carathéodory affirme que tout point de cone(V) est combinaison non-négative d'au plus d vecteurs de V (c'est l'analogue vectoriel du fait que l'enveloppe convexe de points de Rd est la réunion des d-simplexes formés avec ces points). Une base de Hilbert de cone(V) est une famille de vecteurs H telle que les points entiers contenus dans cone(V) coïncident avec les combinaisons à coefficients naturels (entiers non-négatifs) de H. Dit autrement, c'est une famille génératrice minimale de l'intersection de cone(V) avec le réseau Zd, vu comme semi-groupe pour l'addition vectorielle. Le problème de Carathéodory entier s'intéresse à exprimer tout point entier de cone(V) comme combinaison naturelle d'un nombre borné de vecteurs de H. On sait que ce nombre est compris entre 7d/6 et 2d-2... Présentation d'András.
  10. 19 mars 2015 (G-SCOP - 16h) - András Sebö : Présentation de quelques résultats concernant le problème du simplexe vide : étant donné un ensembles V de n points entiers de Z^n linéairement indépendants, il s'agit de décider si le simplexe conv(0,V) contient un point entier autre que ses sommets. Le problème est clairement dans NP : un certificat est donné par les coordonnées barycentriques d'un point entier répondant au problème.
    En fin de séance András Introduit également le problème du coureur solitaire. On considère k coureurs se déplaçant à vitesses constantes non nulles sur une piste circulaire de longueur unité et partant tous de la même ligne de départ à l'instant 0. La conjecture du coureur solitaire (lonely runner conjecture) affirme l'existence d'un temps t>0 tel que chaque coureur est à une distance au moins 1/(k+1) de la ligne de départ. (Dans une version équivalente de la conjecture on considère k+1 coureurs ayant des vitesses toutes distinctes et on affirme pour chaque coureur l'existence d'un temps auquel le coureur est "isolé" des autres, i.e. est à distance au moins 1/(k+1) de tous les autres).     Présentation d'András.
  11. 28 avril 2015 (G-SCOP - 14h30) - András Sebö : poursuit sa présentation de la conjecture du coureur solitaire. Celle-ci est formellement prouvée jusqu'à k=6 coureurs mais reste ouverte ensuite ! On peut supposer que les vitesses sont entières ce qui permet de donner des preuves particulièrement simples et élégantes pour k=2,3,4. cf. présentation d'András. On décide de consacrer la prochaine rencontre à une séance de brain-storming sur ce joli sujet (sauf si Endrás a résolu la conjecture d'ici là :-). Parmi les questions ouvertes : l'ordre cyclique des coureurs autour de la piste évolue au fur et à mesure des dépassements. Peut-on obtenir tous les ordres cyliques ? Sinon, quelle est la structure des ces ordres ?
  12. 28 mai 2015 (G-SCOP - 16h) - Séance de remue-méninges autour de la conjecture du coureur solitaire, menée par András (transparents de présentation). On discute également d'un "post" de Terence Tao qui montre que l'on peut  tester la conjecture sur des vitesses bornées en fonction du nombre de coureurs. Francis fournit un petit code Python pour visualiser les graphes des distances de chaque coureur à la ligne de départ en fonction du temps ainsi que l'enveloppe inférieure de ces courbes (t -> min_i d(0,v_i*t)). Pour le lancer il faut
    1) installer python sur sa machine
    2) installer la bibliothèque matplotlib pour tracer des courbes avec python
    3) recopier le fichier lonelyRunner.py dans un répertoire
    5) ouvrir un terminal et se placer dans ce répertoire
    4) lancer python dans ce terminal (taper python, puis faire return)
    5) attendre l'invite >>> de python et taper :
        import lonelyRunner as lr
        puis faire return
    6) enfin, pour visualiser les courbes correspondant aux entiers v_1,..,v_k taper
        lr.plotAll([v_1,..,v_k],50000)
        puis faire return 
    Deux exemples de résultats avec 3 coureurs ou 6 coureurs. La ligne horizontale pointillée rouge sur les figures indique la valeur 1/(k+1) (donc ici 1/4 et 1/7). La conjecture se traduit par l'existence d'un point sur l'enveloppe inférieure (en trait noir épais) au dessus de cette ligne. L'aire sous l'enveloppe inférieure est également indiquée en commentaire sur la figure. Chaque coureur est identifié à sa vitesse entière.
  13. Séminaire de Francis Lazarus à l'institut Fourier autour du nombre géométrique d'intersection. Annonce et résumé.

 

Recrutement de Jean-Noël Glesser sur un contrat de 6 mois (novembre 2015 à avril 2016) renouvelé (mai à octobre 2016)

Bienvenu à Jean-Noël ! Sa mission est d'implémenter une bibliothèque de manipulation de surfaces combinatoires comportant un certain nombre d'algorithmes de nature topologique ou géométrique (comme le calcul de système de lacet canonique ou le test d'homotopie...). La bibliothèque sera implémentée en C++ dans le cadre de la bibliothèque de géométrie algorithmique CGAL.

 

Manifestations soutenues par Galois

  • Meeting in honor of András Sebő, April 24-25, 2014, Grenoble, France, site web
  • 9th International colloquium on graph theory and combinatorics, June 30-July 4, 2014, Grenoble, France, site web et numéro spécial Discrete Applied Mathematics
  • Journées Graphes et Surfaces, 1-3 février 2016, Grenoble, France. programme
  • École de Printemps d'Informatique Théorique (ÉPIT) Graphes et surfaces : algorithmique, combinatoire et topologie, 9-13 Mai 2016, CIRM Marseille, site web

 

Autres événements liés à l'équipe-action Galois

  • Soutenance d'HDR de Francis Lazarus, 16 septembre 2014 à 14h. voir ici pour un plan d'accès, et ici pour le mémoire d'HDR.
  • Soutenance de thèse de Vincent Despré, 18 octobre 2016 à 14h en salle Mont-Blanc du GIPSA-Lab.
  • Soutenance d'HDR de Benjamin Lévêque, 19 octobre 2016 à 14h30 à l'amphi C, 1er étage du batiment C au G-SCOP.
  • Séminaires de l'équipe Optimisation Combinatoire du laboratoire G-SCOP

       À l'occasion des soutenances de Vincent et Benjamin, organisation d'une

semaine de séminaires Géométrie et Topologie Combinatoires du 17 au 20 octobre 2016

Programme :

Lundi 17 octobre : 
  • 15h - Olivier Devillers - Analyse d’algorithmes géométriques sous des hypothèses probabilistes - GIPSA-Lab Campus
  • 16h - Sergio Cabello - Peeling potatoes near-optimally in near-linear time - GIPSA-Lab Campus
Mardi 18 octobre :
  • 10h15 - Imre Barany - Curves in R^d intersecting every hyperplane at most d+1 times - Salle C219 - INP - Gare
  • 14h - Vincent Despré - Soutenance de thèse - Salle Mont-blanc - GIPSA-Lab - Campus 
Mecredi 19 octobre 
  • 10h - Stefan Felsner - Salle C319 - INP - Gare
  • 14h30 - Benjamin Lévêque - Generalization of Schnyder woods to orientable surfaces and applications - Soutenance d'HDR - Amphi C - INP - Gare
Jeudi 20 octobre :
  • 10h - Victor Chepoi - A Counterexample to Thiagarajan's Conjecture on Regular Event Structures- Salle C319 - INP - Gare
  • 14h - Marc Noy - Logic and Combinatorics - Salle C319 - INP - Gare
  • 15h30 - Eric Colin de Verdière - Algorithmique des graphes sur les surfaces - Salle C319 - INP - Gare

 

Journées GALOIS de géométrie combinatoire, 21 et 22 mars 2017, INP-Viallet

Mardi 21:  matin dans la salle C219, l'apres-midi dans la salle F217

  • 11h15  - Arnaud de Mesmay :  Probleme ouvert sur les "string graphs"
  • 12h      - Yann Vaxes : Titre: Couverture et Packing d'ensembles quasiconvexes dans les graphes delta-hyperboliques.

Les graphes delta-hyperboliques sont définis par la condition métrique suivante : pour tout quadruplet de sommets $u,v,w,x$, les deux plus grandes distances parmi $d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w)$ diffèrent par au plus $2\delta$. La delta-hyperbilicité mesure la ressemblance d'un graphe à un arbre du point de vue métrique. En particulier, la métrique d'un arbre est 0-hyperbolique.

  • 13h   Discussion + Pause dejeuner
  • 15h00  Matej Stehlik : Neighbourhood complexes of critical graphs

The neigbourhood complex N(G) of a graph G has the same vertex set as G, and the simplices are the sets of vertices having a common neighbour. In his celebrated proof of Kneser’s conjecture, Lovasz showed that if N(G) is k-connected, then G cannot be (k + 2)-coloured. Csorba showed that neighbourhood complexes can have essentially any form up to homotopy type. However, we show that if N(G) is k-connected and G is (k + 3)-critical, then N(G) has the homotopy type of a wedge sum of an odd number of (k + 2)-dimensional spheres.

  • 16h00  Discussions, session de problemes en petits groupes + pause café
  •  17h00  Guyslain Naves : Couverture et packing de boules dans les surfaces de Busemann

We prove that for any compact subset $S$ of a Busemann surface $({\mathcal S},d)$ (in particular, for any simple polygon with geodesic metric) and any positive number $\delta$, the minimum number of closed balls of radius $\delta$ with centers at $\mathcal S$ and covering the set $S$ is at most \constant{} times the maximum number of disjoint closed balls of radius $\delta$ centered at points of $S$: $\nu(S)\le \rho(S)\le \constant{}\nu(S)$, where $\rho(S)$ and $\nu(S)$ are the covering and the packing numbers of $S$ by ${\delta}$-balls.

Mercredi 22:    Toute la journee dans la salle C319

  •  9h30   Éric Colin de Verdière : Une preuve "directe" du théorème fort de Hanani-Tutte sur le plan projectif

Dans sa version de base, le théorème de Hanani-Tutte stipule que, si un graphe peut être dessiné dans le plan de sorte que chaque paire d'arêtes se croise un nombre pair de fois, alors le graphe est planaire.  En fait, le résultat plus fort suivant est vrai : il suffit que chaque paire d'arêtes _indépendante_ (ne partageant pas un sommet) se croise un nombre pair de fois.

La version de base de ce théorème s'étend en remplaçant le plan par toute surface.  En revanche, la version forte n'est connue que dans le cas du plan et du plan projectif.  Je présenterai un survol de ces résultats, et en particulier une démonstration de la version forte dans le cas du plan projectif qui ne passe pas par les mineurs de graphes, obtenue en collaboration avec Vojtěch Kaluža, Pavel Paták, Zuzana Patáková et Martin Tancer.

  • 10h30        Discussion, pause cafe
  •  11h   Frederic Meunier :  Problem on the number of colorful simplices
  •  Problem Session
  •  11h45   Andrew Ryzhikov : Some conjectures on words

A seventieth-year-old conjecture of Lyngsø and Pedersen states that each binary circular word has a linear anti-palindromic subsequence of length at least 2/3 of the length of the whole word. I will present several more conjectures of this spirit, obtained by exhaustive computer search. One direction of study is to change anti-palindromes to palindromes in the conjecture. Another direction is to study special classes of words, for example, words without three consecutive equal letters. For this class of words, I will present a simple proof of the Lyngsø-Pedersen conjecture and state some stronger conjectures. Finally, I will state several conjectures about palindromes in linear words and give some proofs supporting my believes in this conjectures.

  • 12h30 Discussion + Pause dejeuner
  • 14h30    Victor Chepoi: Hitting set and packing problems for axis-parallel rectangles

After a brief survey on the hitting set-packing relationship for geometric instances and on Wegner conjecture and its Gyarfas&Lehel relaxation, we will present the results on those questions in the particular case of families of axis-parallel rectangles intersecting a monotone curve. Talk based on the paper V. Chepoi and S. Felsner, Approximating hitting sets of axis-parallel rectangles with opposite corners separated by a monotone curve, Computational Geometry, 46 (2013), 1036--1041.

  • 16h00  Gouter et reprise de certains sujets,

               discussions finales sur les problemes ...

 

Publications