|
Titre :
|
Les graphes expanseurs (2019)
|
|
Auteurs :
|
Emmanuel Kowalski, Auteur
|
|
Type de document :
|
Article : texte imprimé
|
|
Dans :
|
Tangente (Paris) (190, 09/2019)
|
|
Article en page(s) :
|
p.44-47
|
|
Note générale
|
Bibliographie, schémas.
|
|
Langues de la publication :
|
Français
|
|
Descripteurs
|
[UNESCO] Théorie des graphes
|
|
Mots-clés :
|
schéma et diagramme
|
|
Résumé :
|
Présentation mathématique des graphes expanseurs : leurs propriétés, leurs applications, leur découverte (Mark Semenovitch Pinsker, les travaux de Barzdin et Kolmogorov - graphes orientés), la construction d'exemples explicites de graphes expanseurs (Gregori Aleksandrovitch Margulis), le théorème de Gromov-Guth et les noeuds de distorsion. Encadrés : la constante de Cheeger et le nombre de Cheeger ; la démonstration de Barzdin et Kolmogorov pour représenter un graphe dans un cube de côté environ N1/2, à partir de la constante de Cheeger.
|
|
Nature du document :
|
Article de périodique
|
