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] [ 2]
La fonction extrémale
e
x
(
n
;
H
)
{\displaystyle ex(n;H)}
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)}
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)}
0
<
ε
<
1
2
(
r
−
1
)
{\displaystyle 0<\varepsilon <{\frac {1}{2(r-1)}}}
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)}
Bollobás et Erdős[ 4] r et ε, il existe des constantes
c
1
(
r
,
ε
)
{\displaystyle c_{1}(r,\varepsilon )}
c
2
(
r
,
ε
)
{\displaystyle c_{2}(r,\varepsilon )}
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)}
[ 5] 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}
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 
