Sujet : Graphes Hyperboliques

Responsable : Cyril Gavoille & Olivier Ly
Téléphone : 05.40.00.88.12 / 38.73
e-mail : mailto:gavoille@labri.fr,ly@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille et http://www.labri.fr/~ly
Equipe : CombAlgo & L3A

Présentation du sujet :

L'hyperbolicité est un concept fondamental issu de la géométrie, et plus précisement de la classification des espaces géométriques. Il a été introduit au XIXe siècle dans le cadre de l'axiomatisation de la géométrie. Ses applications sont aujourd'hui multiples, tant théoriques que pratiques, et notamment dans le domaine de la physique [KMP].

Récemment, dans le cadre de l'étude de certains groupes fondamentaux et de leurs graphes de Cayley, M. Gromov a donné et étudié une version combinatoire de l'hyperbolicité [GdLH]. Cette déclinaison du concept s'est avérée très profonde, comme en témoigne par exemple le théorème de Z. Sela qui établit la décidabilité du problème de l'isomorphisme des groupes hyperboliques.

L'hyperbolicité telle que l'a définit Gromov dépasse en fait le domaine des groupes, et s'applique d'une façon générale aux graphes [BC,KM]. Elle permet de definir un critère simple d'ordre géométrique. Dans ce cadre, on montre que l'hyperbolicité définit de façon naturelle de nouvelles familles de graphes pour lesquelles les problèmes de routage et d'approximation de distance trouvent des solutions surprenantes en terme de stockage d'information.

Le travail de thèse proposé ici consiste en l'étude systématique de l'hyperbolicité et de ces implications dans le domaine du routage et d'approximation de distance. Il s'agira notamment d'établir des comparaison avec d'autres critères comme par exemple la doubling dimension [CGMZ,T] ou encore la tree-length [GD].

Mot-clés : théorie des graphes, algorithmes, graphes hyperboliques

Références :
[BC] H.-J. Bandelt, V. Chepoi. 1-Hyperbolic Graphs. SIAM Journal on Discrete Mathematics, vol. 16(2), pp. 323-334, 2003.

[CGMZ] H. Chan, A. Gupta, B. Maggs, S. Zhou. On Hierarchical Routing in Bounded Growth Metrics. In 16th Symposium on Discrete Algorithms (SODA). ACM-SIAM, jan. 2005.

[GD] C. Gavoille, Y. Dourisboure. Tree-decompositions with bags of small diameter. Discrete Mathematics, 2005. To appear.

[GdLH] E. Ghyps, P. de La Harpe. Sur les Groupes Hyperboliques d'après Mikhael Gromov. Progress in Mathematics, Birkhäuser, 1990.

[KM] J. Koolen, V. Moulton. Hyperbolic bridged graphs. European Journal of Combinatorics, Academic Press Ltd., vol. 23(6), pp. 683-699, 2002.

[KMP] C. Kenyon, E. Mossel, Y. Peres. Glauber Dynamics on Trees and Hyperbolic Graphs. 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, pp. 568-578, oct. 2001.

[T] K. Talwar. Bypassing the Embedding: Algorithms for Low Dimensional Metrics. 36th Annual ACM Symposium on Theory of Computing (STOC). pp. 281-290, jun. 2004.