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].

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}.}$

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.

• (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).

• Portail des mathématiques