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

Pour les articles homonymes, voir Théorème d'Erdős.

Fonctions extrémales des graphes de Turán

La fonction extrémale 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 , 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 :

Résultats

Plusieurs versions du théorème ont été prouvées. Soit[3] (pour ) le plus grand t tel que chaque graphe d'ordre n et de taille

contient un .

Erdős et Stone ont prouvé que

pour n suffisamment grand. L'ordre de a été trouvé par Bollobás et Erdős:[4] pour tout r et ε, il existe des constantes et telles que . Chvátal et Szemerédi[5] ont précisé la nature de la dépendance en r et ε:

pour n suffisamment grand.

Références

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