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

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)$:

${\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.$

Résultats

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

$\left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}$

contient un $K_{r}(t)$.

Erdős et Stone ont prouvé que

$s_{r,\varepsilon }(n)\geq \left(\underbrace {\log \cdots \log } _{r-1}n\right)^{1/2}$

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

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

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Stone theorem » (voir la liste des auteurs).

Erdős et Stone, A. H., « On the structure of linear graphs », Bulletin of the American Mathematical Society, vol. 52, n^o 12,‎ 1946, p. 1087–1091 (DOI 10.1090/S0002-9904-1946-08715-7)

Béla Bollobás, Modern Graph Theory, New York, Springer-Verlag, 1998, 120 p. (ISBN 0-387-98491-7)

Béla Bollobás, Handbook of combinatorics, Elsevier, 1995, 1244 p. (ISBN 0-444-88002-X), « Extremal graph theory »

Bollobás et Erdős, P., « On the structure of edge graphs », Bulletin of the London Mathematical Society, vol. 5, n^o 3,‎ 1973, p. 317–321 (DOI 10.1112/blms/5.3.317)

Chvátal et Szemerédi, E., « On the Erdős-Stone theorem », Journal of the London Mathematical Society, vol. 23, n^o 2,‎ 1981, p. 207–214 (DOI 10.1112/jlms/s2-23.2.207)