logo site
Institut de Mathématiques de Marseille, UMR 7373
Slogan du site
Descriptif du site

Jouer au gendarme et au voleur pour approximer l’hyperbolicité

vendredi
27
mai
2016
11h00 - 12h00
horaire FRUMAM

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)