[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

By Harald Helfgott

Appears in 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]

Information about the video

Date of recording 17/01/2017
Date of publication 17/01/2017
Institution IHP
Language French
Audience Researchers, Graduate Students
Format MP4
Venue IHP - Hermite Amphitheater

Domain(s)

Group Theory

Bibliography

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

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback