Théorème de De Bruijn-Erdős (la théorie des graphes)
Théorème de De Bruijn-Erdős (la théorie des graphes) Cet article concerne la coloration de graphes infinis. Pour le nombre de lignes déterminé par un ensemble fini de points, voir le théorème de De Bruijn – Erdős (géométrie d'incidence).
En théorie des graphes, le théorème de De Bruijn – Erdős relie la coloration graphique d'un graphe infini au même problème sur ses sous-graphes finis. Il stipule que, lorsque tous les sous-graphes finis peuvent être colorés avec {displaystyle c} couleurs, il en est de même pour tout le graphique. Le théorème a été prouvé par Nicolaas Govert de Bruijn et Paul Erdős (1951), d'après qui il porte le nom.
Le théorème de De Bruijn – Erdős a plusieurs preuves différentes, tout dépend en quelque sorte de l'axiome du choix. Ses applications incluent l'extension du théorème des quatre couleurs et du théorème de Dilworth à partir de graphes finis et d'ensembles partiellement ordonnés à des ensembles infinis, et réduire le problème de Hadwiger-Nelson sur le nombre chromatique du plan à un problème sur les graphes finis. Il peut être généralisé à partir de nombres finis de couleurs à des ensembles de couleurs dont la cardinalité est un cardinal fortement compact.
Contenu 1 Définitions et déclaration 2 Applications 3 Preuves 4 Dépendance au choix 5 Généralisations 6 Remarques 7 Références Définitions et énoncé Un graphe non orienté est un objet mathématique composé d'un ensemble de sommets et d'un ensemble d'arêtes qui relient des paires de sommets. Les deux sommets associés à chaque arête sont appelés ses extrémités. Le graphe est fini lorsque ses sommets et ses arêtes forment des ensembles finis, et infini sinon. Une coloration de graphe associe chaque sommet à une couleur tirée d'un ensemble de couleurs, de telle sorte que chaque arête ait deux couleurs différentes à ses extrémités. Un objectif fréquent dans la coloration des graphiques est de minimiser le nombre total de couleurs utilisées; le nombre chromatique d'un graphe est ce nombre minimum de couleurs.[1] Le théorème des quatre couleurs stipule que chaque graphe fini qui peut être dessiné sans croisements dans le plan euclidien a besoin d'au plus quatre couleurs; toutefois, certains graphiques avec une connectivité plus compliquée nécessitent plus de quatre couleurs.[2] C'est une conséquence de l'axiome de choix que le nombre chromatique est bien défini pour les graphes infinis, mais pour ces graphes, le nombre chromatique pourrait lui-même être un nombre cardinal infini.[3] Un sous-graphe d'un graphe est un autre graphe obtenu à partir d'un sous-ensemble de ses sommets et d'un sous-ensemble de ses arêtes. Si le plus grand graphique est coloré, la même coloration peut être utilisée pour le sous-graphe. Par conséquent, le nombre chromatique d'un sous-graphe ne peut pas être supérieur au nombre chromatique de l'ensemble du graphe. Le théorème de De Bruijn – Erdős concerne les nombres chromatiques de graphes infinis, et montre que (encore, en supposant l'axiome du choix) ils peuvent être calculés à partir des nombres chromatiques de leurs sous-graphes finis. Il stipule que, si les nombres chromatiques des sous-graphes finis d'un graphe {style d'affichage G} avoir une valeur maximale finie {displaystyle c} , alors le nombre chromatique de {style d'affichage G} lui-même est exactement {displaystyle c} . D'autre part, s'il n'y a pas de borne supérieure finie sur les nombres chromatiques des sous-graphes finis de {style d'affichage G} , alors le nombre chromatique de {style d'affichage G} lui-même doit être infini.[4] Applications La motivation originale d'Erdős dans l'étude de ce problème était d'étendre des graphes finis aux graphes infinis le théorème selon lequel, chaque fois qu'un graphe a une orientation avec un degré extérieur maximal fini {style d'affichage k} , il a aussi un {style d'affichage (2k+1)} -coloration. Pour les graphes finis, cela s'ensuit parce que ces graphes ont toujours un sommet de degré au plus {style d'affichage 2k} , qui peut être coloré avec l'un des {style d'affichage 2k+1} couleurs après que tous les sommets restants sont colorés de manière récursive. Les graphes infinis avec une telle orientation n'ont pas toujours un sommet de faible degré (par exemple, Les réseaux de Bethe ont {style d'affichage k=1} mais degré minimum arbitrairement grand), donc cet argument nécessite que le graphe soit fini. Mais le théorème de De Bruijn-Erdős montre qu'un {style d'affichage (2k+1)} -la coloration existe même pour les graphes infinis.[5] Un sept-coloriage de l'avion, et le fuseau Moser quadrichromatique dessiné comme un graphique de distance unitaire dans le plan, fournissant des limites supérieure et inférieure pour le problème de Hadwiger-Nelson.
Une autre application du théorème de De Bruijn – Erdős est au problème de Hadwiger – Nelson, qui demande combien de couleurs sont nécessaires pour colorer les points du plan euclidien de sorte que tous les deux points distants d'une unité aient des couleurs différentes. Il s'agit d'un problème de coloration de graphe pour un graphe infini qui a un sommet pour chaque point du plan et une arête pour chaque deux points dont la distance euclidienne est exactement un. Les sous-graphes induits de ce graphe sont appelés graphes de distance unitaire. Un graphique de distance unitaire à sept sommets, la broche Moser, nécessite quatre couleurs; dans 2018, des graphiques de distance unitaire beaucoup plus grands ont été trouvés qui nécessitent cinq couleurs.[6] L'ensemble du graphe infini a une coloration connue avec sept couleurs basée sur un pavage hexagonal du plan. Par conséquent, le numéro chromatique du plan doit être soit 5, 6, ou 7, mais on ne sait pas lequel de ces trois nombres est la bonne valeur. Le théorème de De Bruijn-Erdős montre que, pour ce problème, il existe un graphe de distance unitaire fini avec le même nombre chromatique que tout le plan, donc si le nombre chromatique est supérieur à cinq, alors ce fait peut être prouvé par un calcul fini.[7] Le théorème de De Bruijn – Erdős peut également être utilisé pour étendre le théorème de Dilworth d'ensembles finis à infinis partiellement ordonnés. Le théorème de Dilworth stipule que la largeur d'un ordre partiel (le nombre maximal d'éléments dans un ensemble d'éléments mutuellement incomparables) est égal au nombre minimum de chaînes (sous-ensembles totalement ordonnés) dans lequel l'ordre partiel peut être divisé. Une partition en chaînes peut être interprétée comme une coloration du graphe d'incomparabilité de l'ordre partiel. C'est un graphe avec un sommet pour chaque élément de l'ordre et une arête pour chaque paire d'éléments incomparables. En utilisant cette interprétation de coloration, avec une preuve séparée du théorème de Dilworth pour les ensembles finis partiellement ordonnés, il est possible de prouver qu'un ensemble infini partiellement ordonné a une largeur finie {style d'affichage w} si et seulement s'il a une partition dans {style d'affichage w} Chaînes.[8] De la même manière, le théorème de De Bruijn – Erdős étend le théorème des quatre couleurs des graphes planaires finis aux graphes planaires infinis. Chaque graphe planaire fini peut être coloré avec quatre couleurs, par le théorème des quatre couleurs. Le théorème de De Bruijn – Erdős montre alors que tout graphe qui peut être tracé sans croisements dans le plan, fini ou infini, peut être coloré avec quatre couleurs. Plus généralement, tout graphe infini pour lequel tous les sous-graphes finis sont plans peut à nouveau être quadricolore.[9] Preuves La preuve originale du théorème de De Bruijn-Erdős, par De Bruyn, utilisé l'induction transfinie.[10] Gottschalk (1951) fourni la très courte preuve suivante, basé sur le théorème de compacité de Tychonoff en topologie. Supposer que, pour le graphe infini donné {style d'affichage G} , tout sous-graphe fini est {style d'affichage k} -colorable, et laissez {style d'affichage X} être l'espace de toutes les affectations du {style d'affichage k} couleurs aux sommets de {style d'affichage G} (indépendamment du fait qu'ils forment une coloration valide). Alors {style d'affichage X} peut se voir attribuer une topologie en tant qu'espace produit {style d'affichage k^{V(g)}} , où {style d'affichage V(g)} désigne l'ensemble des sommets du graphe. Par le théorème de Tychonoff cet espace topologique est compact. Pour chaque sous-graphe fini {style d'affichage F} de {style d'affichage G} , laisser {style d'affichage X_{F}} être le sous-ensemble de {style d'affichage X} consistant en des attributions de couleurs qui colorent valablement {style d'affichage F} . Alors le système d'ensembles {style d'affichage X_{F}} est une famille d'ensembles fermés avec la propriété d'intersection finie, donc par compacité il a une intersection non vide. Chaque membre de cette intersection est une coloration valide de {style d'affichage G} .[11] Une preuve différente utilisant le lemme de Zorn a été donnée par Lajos Pósa, et aussi dans le 1951 Doctorat. thèse de Gabriel Andrew Dirac. Si {style d'affichage G} est un graphe infini dans lequel chaque sous-graphe fini est {style d'affichage k} -colorable, alors d'après le lemme de Zorn c'est un sous-graphe d'un graphe maximal {style d'affichage M} avec la même propriété (un auquel plus aucune arête ne peut être ajoutée sans que certains sous-graphes finis nécessitent plus de {style d'affichage k} couleurs). La relation binaire de non-adjacence dans {style d'affichage M} est une relation d'équivalence, et ses classes d'équivalence fournissent une {style d'affichage k} -coloration de {style d'affichage G} . Cependant, cette preuve est plus difficile à généraliser que la preuve de compacité.[12] Le théorème peut également être prouvé en utilisant des ultrafiltres[13] ou analyse non standard.[14] Nash-Williams (1967) donne une preuve pour les graphes avec un nombre dénombrable de sommets basée sur le lemme de l'infini de Kőnig.
Dépendance au choix Toutes les preuves du théorème de De Bruijn – Erdős utilisent une forme de l'axiome du choix. Une certaine forme de cette hypothèse est nécessaire, car il existe des modèles de mathématiques dans lesquels l'axiome du choix et le théorème de De Bruijn-Erdős sont faux. Plus précisément, Mycielski (1961) a montré que le théorème est une conséquence du théorème booléen de l'idéal premier, une propriété impliquée par l'axiome de choix mais plus faible que l'axiome de choix complet, et Läuchli (1971) a montré que le théorème de De Bruijn-Erdős et le théorème booléen de l'idéal premier sont équivalents en puissance axiomatique.[15] On peut également montrer que le théorème de De Bruijn – Erdős pour les graphes dénombrables est équivalent en puissance axiomatique, dans une théorie de l'arithmétique du second ordre, au lemme de l'infini de Kőnig.[16] Pour un contre-exemple au théorème dans les modèles de théorie des ensembles sans choix, laisser {style d'affichage G} être un graphe infini dans lequel les sommets représentent tous les nombres réels possibles. Dans {style d'affichage G} , connecter chacun deux nombres réels {style d'affichage x} et {style d'affichage y} par une arête chaque fois qu'une des valeurs {style d'affichage |x-y|pm {sqrt {2}}} est un nombre rationnel. De manière équivalente, dans ce graphique, des arêtes existent entre tous les nombres réels {style d'affichage x} et tous les nombres réels de la forme {style d'affichage x+qpm {sqrt {2}}} , pour les nombres rationnels {style d'affichage q} . Chaque chemin dans ce graphique, à partir de n'importe quel nombre réel {style d'affichage x} , alterne entre des nombres qui diffèrent de {style d'affichage x} par un nombre rationnel plus un multiple pair de {style d'affichage {sqrt {2}}} et des chiffres qui diffèrent de {style d'affichage x} par un nombre rationnel plus un multiple impair de {style d'affichage {sqrt {2}}} . Cette alternance empêche {style d'affichage G} de contenir des cycles de longueur impaire, donc chacun de ses sous-graphes finis ne nécessite que deux couleurs. Cependant, dans le modèle de Solovay dans lequel chaque ensemble de nombres réels est Lebesgue mesurable, {style d'affichage G} nécessite une infinité de couleurs, puisque dans ce cas chaque classe de couleur doit être un ensemble mesurable et on peut montrer que chaque ensemble mesurable de nombres réels sans arêtes dans {style d'affichage G} doit avoir la mesure zéro. Par conséquent, dans le modèle Solovay, la (infini) nombre chromatique de tous {style d'affichage G} est beaucoup plus grand que le nombre chromatique de ses sous-graphes finis (au plus deux).[17] Généralisations Rado (1949) démontre le théorème suivant, qui peut être vu comme une généralisation du théorème de De Bruijn-Erdős. Laisser {style d'affichage V} être un ensemble infini, par exemple l'ensemble des sommets d'un graphe infini. Pour chaque élément {style d'affichage v} de {style d'affichage V} , laisser {displaystyle c_{v}} être un ensemble fini de couleurs. En outre, pour tout sous-ensemble fini {style d'affichage S} de {style d'affichage V} , choisir une coloration particulière {displaystyle C_{S}} de {style d'affichage S} , dans lequel la couleur de chaque élément {style d'affichage v} de {style d'affichage S} appartient à {displaystyle c_{v}} . Alors il existe une coloration globale {style d'affichage chi } de tous de {style d'affichage V} avec la propriété que tout ensemble fini {style d'affichage S} a un sur-ensemble fini {style d'affichage T} sur lequel {style d'affichage chi } et {displaystyle C_{J}} accepter. En particulier, si nous choisissons un {style d'affichage k} -coloration pour chaque sous-graphe fini d'un graphe infini {style d'affichage G} , alors il y a un {style d'affichage k} -coloration de {style d'affichage G} dans lequel chaque graphe fini a un supergraphe plus grand dont la coloration s'accorde avec la coloration de l'ensemble du graphe.[18] Si un graphe n'a pas de nombre chromatique fini, alors le théorème de De Bruijn – Erdős implique qu'il doit contenir des sous-graphes finis de chaque nombre chromatique fini possible. Les chercheurs ont également étudié d'autres conditions sur les sous-graphes qui sont forcés de se produire dans ce cas. Par exemple, les graphes chromatiques illimités doivent également contenir tous les graphes bipartis finis possibles en tant que sous-graphe. Cependant, ils peuvent avoir une circonférence impaire arbitrairement grande, et par conséquent, ils peuvent éviter tout ensemble fini de sous-graphes non bipartis.[19] Le théorème de De Bruijn – Erdős s'applique également directement aux problèmes de coloration d'hypergraphe, où l'on exige que chaque hyperarête ait des sommets de plus d'une couleur. Quant aux graphiques, un hypergraphe a un {style d'affichage k} -coloration si et seulement si chacun de ses sous-hypergraphes finis a une {style d'affichage k} -coloration.[20] C'est un cas particulier du théorème de compacité de Kurt Gödel, indiquant qu'un ensemble de phrases du premier ordre a un modèle si et seulement si chaque sous-ensemble fini de celui-ci a un modèle.[21] Plus précisement, le théorème de De Bruijn – Erdős peut être interprété comme la compacité des structures du premier ordre dont les valeurs non logiques sont n'importe quel ensemble fini de couleurs et dont le seul prédicat sur ces valeurs est l'inégalité.[22] Le théorème peut également être généralisé à des situations dans lesquelles le nombre de couleurs est un nombre cardinal infini. Si {style d'affichage kappa } est un cardinal fortement compact, alors pour chaque graphique {style d'affichage G} et nombre cardinal {style d'affichage lui
Si vous voulez connaître d'autres articles similaires à Théorème de De Bruijn-Erdős (la théorie des graphes) vous pouvez visiter la catégorie Coloration graphique.
Laisser un commentaire