[1125] Isomorphismes de graphes en temps quasi-polynomial | Vidéo | Carmin.tv

00:00:00 / 00:00:00

[1125] Isomorphismes de graphes en temps quasi-polynomial

De Harald Helfgott

Apparaît dans la collection : Bourbaki - Janvier 2017

Soient donnés deux graphes $Γ_1$, $Γ_2$ à n sommets. Y a-t-il une permutation des sommets qui envoie $Γ_1$ sur $Γ_2$ ? Si de telles permutations existent, elles forment une classe $H$ · $π$ du groupe symétrique sur $n$ éléments. Comment trouver $π$ et des générateurs de $H$ ? Le défi de donner un algorithme toujours efficace en réponse à ces questions est resté longtemps ouvert. Babai a récemment montré comment résoudre ces questions – et d’autres questions liées – en temps quasi-polynomial, c’est-à-dire en temps $O(exp((log \ n)^C))$, où $C$ est une constante. Sa stratégie est basée en partie sur l’algorithme de Luks (1980/82),qui a résolu le cas de graphes de degré borné.

[D’après Babai et Luks]

Informations sur la vidéo

Date de captation 17/01/2017
Date de publication 17/01/2017
Institut IHP
Langue Français
Audience Chercheurs, Doctorants
Format MP4
Lieu IHP - Hermite Amphitheater

Domaine(s)

Théorie des groupes

Bibliographie

Séminaire Bourbaki, 69ème année (2016-2017), n°1125, janvier 2017 PDF

Codes MSC

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Copyright Carmin.tv 2024

Donner son avis