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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle T(rt,r)}$:

${\displaystyle {\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] ${\displaystyle s_{r,\varepsilon }(n)}$ (pour ${\displaystyle 0<\varepsilon <{\frac {1}{2(r-1)}}}$) le plus grand t tel que chaque graphe d'ordre n et de taille

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

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

Erdős et Stone ont prouvé que

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

pour n suffisamment grand. L'ordre de ${\displaystyle s_{r,\varepsilon }(n)}$ a été trouvé par Bollobás et Erdős^[4] : pour tout r et ε, il existe des constantes ${\displaystyle c_{1}(r,\varepsilon )}$ et ${\displaystyle c_{2}(r,\varepsilon )}$ telles que ${\displaystyle 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 ε:

${\displaystyle {\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