SMF

Une introduction aux graphes expanseurs

An introduction to expander graphs

Emmanuel KOWALSKI
Une introduction aux graphes expanseurs
  • Consulter un extrait
  • Année : 2019
  • Tome : 26
  • Format : Papier
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 05CXX, 05C50, 05C81, 11C20, 11G30, 14H25, 22D10, 60J10
  • Nb. de pages : x+276
  • ISBN : 978-2-85629-898-5
  • ISSN : 1284-6090

Les graphes expanseurs sont des familles de graphes finis qui sont simultanément peu denses et extrêmement bien connectés. Depuis leur découverte dans les années 1960, ils sont apparus dans des domaines apparemment éloignés des mathématiques, allant de l'informatique théorique à la géométrie algébrique ou arithmétique, ou de la théorie des représentations à la théorie des nombres.

 

Le but de ce livre est de présenter la théorie des graphes expanseurs et d'explorer certains de ses liens. En plus d'une exposition détaillée et soignée des aspects élémentaires de la théorie, comprenant les caractérisations des graphes expanseurs par la constante de Cheeger, par les marches au hasard et par le laplacien discret, le livre décrit de nombreuses constructions d'expanseurs. Les applications qui sont présentées dans le dernier chapitre essaient de communiquer l'influence remarquable des graphes expanseurs dans les mathématiques actuelles.

 

Expander graphs are families of finite graphs that are simultaneously relatively sparse and highly connected.  Since their discovery in the lates 1960s, they have appeared in many seemingly unrelated areas of mathematics, from theoretical computer science to arithmetic and algebraic geometry, from representation theory to number theory.

The goal of this book is to present the theory of expander graphs and to explore some of these rich connections. Besides a careful exposition of the basic parts of the theory, including the Cheeger constant, random walks and spectral gap characterizations of expander graphs, it contains many different constructions of various families of expander graphs. The applications that are surveyed in the last chapter try to communicate the remarkable reach of expander graphs in modern mathematics.

Graphes expanseurs, constante de Cheeger, marches aléatoires sur les graphes, graphes de Ramanujan, laplacien discret, lacune spectrale, crible dans les groupes discrets, propriété (T), croissance dans les groupes, combinatoire additive, géométrie arithmétique, graphes de Cayley
Expander graphs, Cheeger constant, random walks on graphs, Ramanujan graphs, discrete Laplace operator, spectral gap, sieve in discrete groups, Property (T), growth in groups, additive combinatorics, arithmetic geometry, Cayley graphs
Prix
Adhérent 35 €
Non-Adhérent 50 €
Quantité
- +