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 e x ( n ; H ) {\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 e x ( n ; K r ) = t r − 1 ( n ) {\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 T ( r t , r ) {\displaystyle T(rt,r)} :
ex ( n ; K r ( t ) ) = ( r − 2 r − 1 + o ( 1 ) ) ( n 2 ) . {\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] s r , ε ( n ) {\displaystyle s_{r,\varepsilon }(n)} (pour 0 < ε < 1 2 ( r − 1 ) {\displaystyle 0<\varepsilon <{\frac {1}{2(r-1)}}} ) le plus grand t tel que chaque graphe d'ordre n et de taille
( r − 2 2 ( r − 1 ) + ε ) n 2 {\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}} contient un K r ( t ) {\displaystyle K_{r}(t)} .
Erdős et Stone ont prouvé que
s r , ε ( n ) ≥ ( log ⋯ log ⏟ r − 1 n ) 1 / 2 {\displaystyle 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 , ε ( n ) {\displaystyle 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 , ε ) {\displaystyle c_{1}(r,\varepsilon )} et c 2 ( r , ε ) {\displaystyle c_{2}(r,\varepsilon )} telles que c 1 ( r , ε ) log ( n ) < s r , ε ( n ) < c 2 ( r , ε ) log ( n ) {\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 ε:
1 500 log ( 1 / ε ) log n < s r , ε ( n ) < 5 log ( 1 / ε ) log n {\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n} pour n suffisamment grand. ↑ Erdős et Stone, A. H., « On the structure of linear graphs », Bulletin of the American Mathematical Society , vol. 52, no 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, no 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, no 2, 1981 , p. 207–214 (DOI 10.1112/jlms/s2-23.2.207 )