Résumé: On s'intéressera à la convergence du spectre d'un
grand graphe vers le spectre d'un graphe infini limite. Les résultats
seront appliqués sur des ensembles usuels de graphes : graphe uniforme
régulier, graphe d'Erdos-Renyi, graphe avec une distribution des
degrés donnée. On esquissera aussi le cas des graphes avec des poids,
des graphes bipartis et des arbres couvrant uniformes sur n
sommets.
Si le temps le permet, on discutera aussi deux conjectures, l'une
reliée à un résultat de Karp et Sipser sur l'appariement maximal et
l'autre sur le nombre de graphes de Ramanujan.
C'est un travail joint avec Marc Lelarge (INRIA & Ecole Normale
Supérieure).
Secrétariat du groupe de travail:
Philippe Duchon, duchon@labri.fr
Au LaBRI: | bureau 361 | téléphone (33) 5 40 00 69 12 | ||
À l'ENSEIRB: | bureau 226 | téléphone (33) 5 56 84 23 58 |