Théorème d'Erdős-Stone

Modèle:Voir homonymes En théorie des graphes extrémaux, le théorème d'Erdős-Stone est un résultat asymptotique généralisant le théorème de Turán donnant une borne supérieure au nombre d'arêtes dans un graphe privé de H, H étant un graphe non complet. Il est nommé d'après Paul Erdős et Arthur Stone, qui l'ont prouvé en 1946, et a été décrit comme le « théorème fondamental de la théorie des graphes extrémaux ».

Fonctions extrémales des graphes de Turán

La fonction extrémale $ex(n;H)$ est définie comme le nombre maximum d'arêtes dans un graphe d'ordre n ne contenant pas de sous-graphe isomorphe à H. Le théorème de Turán énonce que $ex(n;K_r)=t_{r-1}(n)$, l'ordre du graphe de Turán, et que le graphe Turan est le graphe extrêmal unique. Le théorème d'Erdős-Stone étend cela aux graphes de Turán $T(rt,r)$:

$\text{ex}(n;K_r(t))=(\frac{r-2}{r-1}+o(1))(\genfrac{}{}{0ex}{}{n}{2}).$

Résultats

Plusieurs versions du théorème ont été prouvées. Soit $s_{r,\epsilon }(n)$ (pour $0<\epsilon <\frac{1}{2(r-1)}$) le plus grand t tel que chaque graphe d'ordre n et de taille

$(\frac{r-2}{2(r-1)}+\epsilon )n^2$

contient un $K_r(t)$.

Erdős et Stone ont prouvé que

$s_{r,\epsilon }(n)\ge {\left(\underset{r-1}{\underbrace{\log \cdots \log }}n\right)}^{1/2}$

pour n suffisamment grand. L'ordre de $s_{r,\epsilon }(n)$ a été trouvé par Bollobás et Erdős : pour tout r et ε, il existe des constantes $c_1(r,\epsilon )$ et $c_2(r,\epsilon )$ telles que $c_1(r,\epsilon )\log (n)<s_{r,\epsilon }(n)<c_2(r,\epsilon )\log (n)$. Chvátal et Szemerédi ont précisé la nature de la dépendance en r et ε:

$\frac{1}{500\log (1/\epsilon )}\log n<s_{r,\epsilon }(n)<\frac{5}{\log (1/\epsilon )}\log n$ pour n suffisamment grand.