Cours spécialisé (Com, GT, HFE, Pro)

Expander graphs, groups, and applications

Karim ADIPRASITO et Harald HELFGOTT

Contact : karim.adiprasito à imj-prg.fr et harald.helfgott à imj-prg.fr

Notes d'un cours antérieur de Helfgott (prises par Zhicheng HAN).

Langue du cours : anglais

Présentation

This course provides an introduction to expander graphs — special graphs with desirable properties — and their applications across various areas of mathematics and computer science.

Contenu

• Expander graphs
• Spectral properties and Cheeger/Alon-Milman/Dodziuk inequalities
• Random walks. Relations to group theory
• Error-correcting codes
• Distortion of embeddings
• Constructions, such as the Margulis construction and the Zig-Zag product

Prérequis

You should at the very least remember the spectral theorem. Knowing about Lie groups and a bit of probability theory will not hurt.
The following courses are related to this one :
Analyse et géométrie sur les groupes and La croissance, les inégalités isopérimétriques et les fonctions harmoniques.

Coordonnées

t = Mercredis de 14h à 16h, jeudis de 13h30 à 15h30. Campus Jussieu.

Wednesday from 2:00pm to 4:00pm, Thursday from 1:30pm to 3:30pm.

(x(t),y(t),z(t)) :
mercredi : salle 15/16 4.13 (de mars 5 à mars 19), salle 15/16 1.01 (mars 26 à avril 9)
jeudi : salle 15/16 1.01 (de mars 6 à avril 3), salle 15/25 1.01 (avril 10)

Wed: room 15/16 4.13 (from March 5 to March 19) and room 15/16 1.01 (from March 26 to April 9)
Th: room 15/16 1.01 (from March 6 to April 3) and room 15/25 1.01 (April 10)

Bibliographie

• Hoory, Linial, Wigderson. Expander Graphs and Their Applications. [PDF]