Seminar Details
2013-01-24 (16.00) : Distorsion et trou spectral pour les graphes finis (MAPA Colloquium)
At Bât. Cyclotron, salle de convivialité math
Organized by Mathematical Engineering
Speaker :
Alain Valette (Université de Neufchâtel)
Abstract :
Considérons un graphe fini X, qu'on voit comme espace métrique discret. La distorsion-$L^p$ de X est un invariant numérique qui mesure la difficulté à plonger $X$ isométriquement dans $L^p$. Un résultat fondamental de Bourgain (1984) dit que la distorsion-$L^p$ est bornée supérieurement par une fonction logarithmique du nombre de sommets du graphe.
Nous expliquerons une application de ce résultat à un problème algorithmique issu de linformatique théorique: MINCUT (trouver la coupure minimale dans un graphe).
Pour terminer, nous présenterons un résultat obtenu récemment avec P.-N. Jolissaint, qui donne une borne inférieure sur la distorsion dun graphe connexe fini, en terme du trou spectral,
c'est-à-dire de la première valeur propre du laplacien combinatoire du graphe. On en déduit une preuve très simple du résultat de Linial-London-Rabinovich (1995) que les graphes expanseurs se plongent dans $L^p$ avec distorsion logarithmique.