Tetali
Le
19 Décembre 2001 à 14h30
au LRI,
Salle 101
(Georgia Institute of Technology)
Discrete isoperimetric constants and concentration
Résumé/Abstract :
We report on some Cheeger-type inequalities relating the spectral
gap to isoperimetric constants (such as sparsity and expansion)
in the context of graphs. If time permits, we describe the proof
of a deviation inequality on the weighted discrete cube conjectured
by Talagrand.
(joint work with S. Bobkov and C. Houdré)