Séminaire

Dans cet exposé, on considère une variante du jeu du gendarme et et du voleur où les joueurs ont des vitesses différentes. La différence avec la version classique de ce jeu est qu’à chaque étape, le gendarme peut se déplacer le long d’un chemin de longueur au plus s’ et le voleur le long d’un chemin de longueur au plus s (tout en évitant la position du gendarme). Un graphe est (s,s’)-gagnant si un gendarme avec une vitesse s’ a une stratégie pour capturer n’importe quel voleur se déplaçant à vitesse s. Les graphes delta-hyperboliques sont des graphes qui ressemblent à des arbres d’un point de vue métrique. On présentera quelques unes des nombreuses définitions de l’hyperbolicité. On présentera ensuite nos résultats reliant le jeu du gendarme et du voleur et l’hyperbolicité du graphe. On montre que si un graphe est delta-hyperbolique, alors il est (2r,r+2delta)-gagnant pour tout r. Réciproquement, on montre que si un graphe est (s,s’)-gagnant (avec s > s’), alors il est O(s^2)-hyperbolique. On présentera ensuite un algorithme quadratique basé sur notre approche pour approximer l’hyperbolicité d’un graphe à partir de sa matrice de distance. (Travail réalisé avec V. Chepoi, P. Papasoglu et T. Pecatte)