IMJ-PRG
IMJ-PRG

Pierre Youssef - LPMA - Paris 7

Séminaire d’Analyse Fonctionnelle

Trou spectral pour les graphes aléatoires uniformes dans le régime dense

jeudi 5 janvier 2017 à 10:30

On note \lambda la deuxième plus grande valeur propre en valeur absolue d’un graphe aléatoire {d}-régulier sur n-sommets suivant le modèle uniforme. Friedman a montré la conjecture d’Alon qui affirmait que lorsque le degré {d} est une constante indépendante de n, alors \lambda\leq 2\sqrt{d-1} +o(1) avec probabilité qui tend vers 1 avec n. Ceci signifie qu’il y a un écart avec la plus grande valeur propre qui est égale à {d} et montre que les graphes {d}-réguliers uniformes sont presque Ramanujan.
Vu a conjecturé que cette borne reste valable pour tout d\leq n/2. Des avancées sur ce problème ont été réalisées par Broder, Frieze, Suen et Upfal qui ont montré que \lambda \leq O(\sqrt{d}) pour tout {d}\leq \sqrt{n}. Le régime de {d} a été étendu récemment à {d}\leq n^{2/3} par Cook, Goldstein et Johnson. Nous complétons ces résultats en montrant que pour tout \delta\in (0,1), on a \lambda\leq O(\sqrt{d}) pour tout n^{\delta}\leq {d}\leq n/2. Ceci montre à constante près la conjecture faite par Vu.
Ce travail est en collaboration avec Konstantin Tikhomirov.

Autres séances


INTRANET

WEBMAIL imj-prg.fr

MENTION LEGALES