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[1], et a été décrit comme le « théorème fondamental de la théorie des graphes extrémaux »[2].

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[3] $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:[4] 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[5] 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).
1. 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)
2. Béla Bollobás, Modern Graph Theory, New York, Springer-Verlag, 1998, 120 p. (ISBN 0-387-98491-7)
3. Béla Bollobás, Handbook of combinatorics, Elsevier, 1995, 1244 p. (ISBN 0-444-88002-X), « Extremal graph theory »
4. 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)
5. 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)

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] 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)

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

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

[4] 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)

[5] 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)