Séminaires : Séminaire d'Analyse Fonctionnelle

Equipe(s) : af,
Responsables :E. Abakoumov - A.Eskenazis - D. Cordero-Erausquin - M. Fathi - O. Guédon - B. Maurey
Email des responsables :
Salle : salle 13 - couloir 15-16 - 4ème étage
Adresse :Campus Pierre et Marie Curie
Description
Le Jeudi à 10h30 -  IMJ-PRG - 4 place Jussieu - 75005 PARIS
Orateur(s) Pierre Youssef - LPMA, Paris 7,
Titre Trou spectral pour les graphes aléatoires uniformes dans le régime dense
Date05/01/2017
Horaire10:30 à 11:30
Diffusion
Résume 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\sqrtd-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(\sqrtd)$ pour tout $d\leq \sqrtn$. 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(\sqrtd)$ 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.
Sallesalle 13 - couloir 15-16 - 4ème étage
AdresseCampus Pierre et Marie Curie
© IMJ-PRG