Plonger des graphes dans des espaces vectoriels euclidiens… ou pas euclidiens !
Conférence par Alain Valette, Professeur à l’université de Neuchâtel.
JEUDI 22 OCTOBRE 2015 à 19 heures
Institut des Hautes Etudes de Belgique
Université Libre de Bruxelles, Bâtiment S, Rez-de-chaussée Avenue Jeanne, 44, 1050 Bruxelles
_______________________________________________
Pour comprendre de gros graphes, il peut être intéressant de les plonger dans un espace euclidien de grande dimension: cela se fait par exemple en bioinformatique.
Mais on peut aussi considérer d’autres distances que la distance euclidienne, par exemple la distance L1 (ou de Manhattan).
La distorsion d’un graphe, introduite en 1985 par le mathématicien belge Jean Bourgain, mesure la difficulté à le plonger dans un espace L1.
Ces travaux de Bourgain ont trouvé des applications en informatique théorique, par exemple dans le problème SPARSEST CUT, qui demande de trouver le nombre minimal d’arêtes à retirer à un graphe pour le déconnecter.
