Inégalités isopérimétriques dans les graphes réguliers

par Thomas Budzinski

lundi 28 sept. 2026, 15:30 → 16:30 Europe/Paris

Amphi A (ENS Lyon (UMPA))

La constante de Cheeger d'un graphe décrit la manière la plus efficace de "couper ce graphe en deux" en coupant aussi peu d'arêtes que possible. Les graphes où cette constante est élevée sont appelés "expanseurs", et leur construction est en général un problème non-trivial. Pour des graphes $d$-réguliers (i.e. où chaque sommet a exactement $d$ voisins), la comparaison avec un arbre infini $d$-régulier montre que cette constante est bornée par $d-2$. On verra qu'un argument probabiliste simple, dû à Bollobas, montre que cette borne supérieure n'est pas optimale. Si le temps le permet (cf. https://en.wikipedia.org/wiki/Vacuous_truth), on évoquera des questions analogues sur les surfaces hyperboliques.