Théorie des graphes extrémaux
La théorie des graphes extrémaux étudie la taille ou la densité maximale qu'un graphe peut atteindre tout en évitant une sous-structure prescrite, et identifie les configurations extrémales.
Definition
L'étude de la valeur maximale ou minimale d'un paramètre de graphe, tel que le nombre d'arêtes, sous une contrainte structurelle comme l'absence d'un sous-graphe fixe.
Scope
Ce sujet se concentre sur les problèmes de type Turan – le nombre maximal d'arêtes dans un graphe sans sous-graphe donné – en commençant par les théorèmes de Mantel et de Turan et en s'étendant au théorème d'Erdos-Stone, qui détermine la densité extrémale asymptotique pour tout sous-graphe interdit. Il introduit l'interaction entre la densité, la structure et la méthode de régularité de Szemeredi.
Core questions
- Quel est le nombre maximal d'arêtes dans un graphe à n sommets qui ne contient aucune copie d'un sous-graphe donné ?
- Quels graphes atteignent ces bornes extrémales ?
- Comment le nombre chromatique d'un sous-graphe interdit régit-il la réponse asymptotique ?
- Comment les méthodes de régularité réduisent-elles les graphes denses à une structure bornée ?
Key concepts
- Sous-graphes interdits
- Graphe de Turan
- Théorème de Mantel
- Nombre extrémal (nombre de Turan)
- Théorème d'Erdos-Stone
- Lemme de régularité de Szemeredi
Key theories
- Théorème de Turan
- Parmi tous les graphes à n sommets sans sous-graphe complet à r+1 sommets, le graphe r-partite complet équilibré possède le plus grand nombre d'arêtes, généralisant la borne de Mantel pour les graphes sans triangle et servant de fondement à la théorie des graphes extrémaux.
- Théorème d'Erdos-Stone
- Pour tout sous-graphe interdit H fixé, la densité maximale d'arêtes d'un graphe sans H est asymptotiquement déterminée par le nombre chromatique de H, unifiant les résultats extrémaux de type Turan.
Clinical relevance
Les résultats sur la densité extrémale bornent la structure des grands réseaux et des systèmes de contraintes, et la méthode de régularité développée dans ce domaine a des applications dans les tests de propriétés, l'informatique théorique et la combinatoire additive.
History
La borne de Mantel de 1907 pour les graphes sans triangle et la généralisation de Turan en 1941 ont lancé le domaine ; la théorie d'Erdos-Stone-Simonovits et le lemme de régularité de Szemeredi en ont fait un pilier central de la combinatoire moderne.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- Qu'est-ce qu'un problème de type Turan ?
- Il s'agit de déterminer le plus grand nombre d'arêtes qu'un graphe peut avoir tout en évitant un sous-graphe fixe ; l'exemple canonique est le nombre maximal d'arêtes dans un graphe sans triangle.
- Comment la théorie des graphes extrémaux est-elle liée à la théorie de Ramsey ?
- Les deux étudient la structure inévitable, mais la théorie extrémale fixe un sous-graphe interdit et maximise les arêtes, tandis que la théorie de Ramsey garantit une structure monochromatique une fois que le graphe est suffisamment grand.