"La Théorie Extrémale des Graphes : Une Approche Spectrale"

Nous considérons des généralisations spectrales de quelques théorèmes classiques de la théorie extrémale des graphes. Les résultats classiques concernent la quantité ex(n,H), le nombre maximum d'arêtes dans un graphe G de n sommets qui ne contient pas une clique de taille t+1. Nous définissons de même la quantité spex(n,H), le rayon spectral maximum d'un graphe du même ensemble. Le rayon spectral est la plus grande valeur propre lambda_{max}(G), de la matrice d'incidence de G. Il est facile de voir que d_{ave}(G) <= lambda_{max}(G) et alors 2 ex(n,H)/n <= spex(n,h).

En 1941, Paul Turán a prouvé le premier théorème de la théorie extrémale des graphes : ex(n,K_t) <= |E(T(n,t))|, où T(n,t) est le "graphe de Turán". Il a aussi prouvé que T(n,t) est le seul graphe extrémal. Dans l'analogue spectral du théorème de Turán, nous prouvons que spex(n,K_t) <= lambda_{max}(T(n,t)), et que T(n,t) est le seul graphe extrémal.

Pour n'importe quel graphe H non-biparti, nous montrons un renforcement du théorème de Erdös, Stone et Simonovits. Pour le cas de H biparti, on sait beaucoup moins; déjà pour les graphes bipartis complets K_{s,t}, on ne connaît même pas l'ordre de magnitude pour la plupart des valeurs de s et t. Quand même, nous montrons que l'ordre de magnitude de spex(n,K_{s,t}) n'est pas plus grand que l'ordre de magnitude conjecturé pour 2 ex(n,K_{s,t}) / n.

E-mail: barry.guiduli@imag.fr
WWW: http://droopy.imag.fr/~guiduli