Vous êtes ici : Accueil > Extra-muros > Plonger des graphes dans des espaces vectoriels euclidiens... ou pas (...)
Publié : 6 octobre 2015

Plonger des graphes dans des espaces vectoriels euclidiens... ou pas euclidiens !

Conférence par Alain Valette le jeudi 22 octobre

Institut des Hautes Etudes de Belgique

CONFERENCE

JEUDI 22 OCTOBRE 2015 à 19 heures Université Libre de Bruxelles, Batiment S, Rez-de-chaussée Avenue Jeanne, 44, 1050 Bruxelles

Plonger des graphes dans des espaces vectoriels euclidiens... ou pas euclidiens !

Alain Valette,
Professeur à l’université de Neuchatel.

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.

Entrée libre