Théorème de De Bruijn-Erdős (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le théorème de De Bruijn-Erdős en théorie des graphes, démontré par Nicolaas Govert de Bruijn et Paul Erdős[1], établit que (pour tout entier naturel k) pour qu'un graphe non orienté infini possède une coloration par k couleurs, il suffit qu'il en soit ainsi pour tous ses sous-graphes finis. Autrement dit : tout graphe k-critique (en) (i.e. dont toute coloration a au moins k couleurs mais dont tous les sous-graphes propres sont k – 1-colorables) a un nombre fini de sommets.

Démonstrations[modifier | modifier le code]

La preuve originelle de De Bruijn utilisait l'induction transfinie[2].

Gottschalk[3] a fourni la preuve suivante, très courte, basée sur le théorème de compacité de Tychonoff en topologie. Notons K l'ensemble des k couleurs et soit G = (V, E) un graphe. D'après le théorème de Tychonoff, l'espace produit X = KV de toutes les applications de V dans K est compact. Pour toute application f d'une partie de V dans K, les éléments de X qui coïncident avec f sur cette partie forment un fermé. Par conséquent, pour tout sous-graphe fini F de G, l'ensemble XF des éléments de X dont la restriction à F est une k-coloration est fermé (par réunion finie). Si tous ces F sont k-colorables, tous ces XF forment une famille de fermés ayant la propriété d'intersection finie (en), c'est-à-dire que toute sous-famille finie est d'intersection non vide. Par compacité leur intersection est donc non vide, or cette intersection n'est autre que l'ensemble des k-colorations de G[4].

Une preuve différente, utilisant le lemme de Zorn, a été donnée par Lajos Pósa (en), ainsi que dans la thèse de Ph.D. de 1951 de Gabriel Andrew Dirac. Si tout sous-graphe fini de G est k-colorable alors, d'après le lemme de Zorn, G est un graphe partiel d'un graphe M maximal pour cette propriété. La relation binaire de non-adjacence dans M est une relation d'équivalence dont les classes fournissent une k-coloration de G. Cependant, cette preuve est plus difficile à généraliser que celle par compacité[5].

Le théorème peut aussi se démontrer en utilisant les ultrafiltres[6] ou l'analyse non standard[7].

Dans le cas particulier où V est dénombrable, Crispin Nash-Williams donne une preuve basée sur le lemme de König[8].

Rôle de l'axiome du choix[modifier | modifier le code]

Toutes les démonstrations du théorème de De Bruijn-Erdős utilisent une forme ou une autre de l'axiome du choix. Cela est inévitable, car il existe des modèles des mathématiques ne vérifiant pas ce théorème (ni cet axiome).

Par exemple[9] pour k = 2, soit G le graphe dont les sommets sont les nombres réels et dans lequel deux réels x et y sont joints par une arête lorsque |x – y| ± 2 est un nombre rationnel, c'est-à-dire que les sommets reliés à un réel x sont les réels de la forme x ± (2 + q) avec q rationnel. Définissons sur les sommets de G une relation d'équivalence par : deux sommets sont équivalents si leur différence est somme d'un rationnel et d'un multiple de racine carrée de 2 par un entier pair. Ainsi, dans une 2-coloration de G, deux sommets équivalents doivent être de la même couleur. Le graphe formé en contractant chaque classe d'équivalence en un unique sommet forme alors un couplage infini et peut facilement être 2-coloré en utilisant l'axiome du choix. Par conséquent, tout sous-graphe fini de G est 2-colorable. Cependant, on peut montrer que dans toute coloration de G, tout ensemble Lebesgue-mesurable monochrome est nécessairement de mesure nulle. Il en résulte que dans le modèle de Solovay (en) (dans lequel tout ensemble de réels est mesurable), G n'est colorable que par une infinité de couleurs.

Le théorème de De Bruijn-Erdős pour les graphes dénombrables est équivalent, dans l'arithmétique du second ordre (en), au lemme de König[10].

Applications[modifier | modifier le code]

Une 7-coloration du plan et un graphe distance-unité de nombre chromatique égal à 4 fournissent un majorant et un minorant pour le problème de Hadwiger-Nelson.

Une application du théorème de De Bruijn-Erdős concerne le problème de Hadwiger-Nelson sur le nombre chromatique du graphe distance-unité du plan euclidien (ses sommets sont les points du plan et deux sommets sont reliés par une arête lorsque leur distance euclidienne vaut 1). Certains de ses sous-graphes, comme le fuseau de Moser, ne sont pas colorables par moins de 4 couleurs. Le graphe lui-même possède une 7-coloration, basée sur le pavage hexagonal du plan. Par conséquent, le nombre chromatique de ce graphe est l'un des quatre entiers 4, 5, 6 ou 7, mais on ne sait pas lequel. Le théorème de De Bruijn-Erdős montre cependant qu'il existe un graphe distance-unité fini dont le nombre chromatique est le même que celui du plan tout entier, donc si ce dernier est strictement plus grand que 4 alors ce fait peut être démontré par un calcul fini[11].

Le théorème de De Bruijn-Erdős peut aussi être utilisé pour étendre le théorème de Dilworth, sur les ensembles (partiellement) ordonnés, du cas fini au cas infini. Ce théorème établit que la largeur de tout ordre fini (i.e. la taille maximum d'une antichaîne) est égale à la taille minimum d'une partition en chaînes. Une partition en chaînes peut s'interpréter comme une coloration du graphe d'incomparabilité de l'ordre (le graphe dont les sommets sont les éléments de l'ensemble ordonné et les arêtes relient les paires d'éléments non comparables). À partir de cette interprétation et au théorème de Dilworth, on peut démontrer, grâce au théorème de De Bruijn-Erdős, que tout ordre infini de largeur inférieure ou égale à un entier w est réunion de w chaînes disjointes[12].

De même, le théorème de De Bruijn-Erdős permet d'étendre le théorème des quatre couleurs, sur les graphes planaires, du cas fini au cas infini : tout graphe planaire infini, ou plus généralement tout graphe infini dont les sous-graphes finis sont planaires, peut être coloré par 4 couleurs[13].

Il peut aussi servir à répondre à une question de Fred Galvin (en) sur un « théorème des valeurs intermédiaires pour les nombres chromatiques de graphes » : pour tout graphe G de nombre chromatique k et tout entier j < k, G possède un sous-graphe de nombre chromatique j. Pour en trouver un, il suffit de prendre un sous-graphe fini de G de nombre chromatique k et de supprimer un par un des sommets jusqu'à ce que le nombre chromatique du sous-graphe atteigne la valeur j. Cependant, la situation pour des nombres chromatiques infinis est plus compliquée : la théorie des ensembles est consistante avec l'existence d'un graphe de nombre chromatique (et nombre de sommets) égal à 2, n'ayant aucun sous-graphe de nombre chromatique égal à 1[14].

Généralisations[modifier | modifier le code]

Richard Rado (en 1949) a démontré le théorème suivant, qui généralise et précise celui de De Bruijn-Erdős[15]. Soient V un ensemble infini et, pour chaque élément v de V, un ensemble fini cv de couleurs. On choisit, pour toute partie finie S de V, une application CS de S dans l'ensemble des couleurs, telle que la couleur de chaque élément v de S appartienne à cv. Alors il existe une application χ, définie sur V tout entier, telle que toute partie finie S soit incluse dans une partie finie T sur laquelle χ et CT coïncident.

Si le nombre chromatique d'un graphe G est infini alors, le théorème de De Bruijn-Erdős implique que G contient, pour tout entier j, un sous-graphe dont le nombre chromatique est j (cf. théorème des valeurs intermédiaires ci-dessus). Des chercheurs ont aussi examiné d'autres conséquences sur les sous-graphes de G ; par exemple, G doit aussi contenir tout graphe biparti fini comme sous-graphe. Cependant, G peut avoir une maille impaire arbitrairement grande et, par conséquent, pour tout ensemble fini de graphes non bipartis, il existe un G dont aucun sous-graphe n'appartient à cet ensemble[16].

Le théorème de De Bruijn-Erdős s'applique aussi directement aux problèmes de coloration d'hypergraphes, où l'on demande que pour chaque hyperarête, les sommets ne soient pas tous de la même couleur : comme pour les graphes, un hypergraphe est k-colorable si et seulement si chacun de ses sous-hypergraphes finis l'est[17]. C'est un cas particulier du théorème de compacité de Gödel, selon lequel un ensemble d'énoncés du premier ordre a un modèle dès que chacune de ses parties finies en a.

On peut aussi généraliser le théorème à des situations où le nombre de couleurs est un cardinal infini : si κ est un cardinal fortement compact (en) alors, pour tout graphe G et tout cardinal μ < κ, le nombre chromatique de G est inférieur ou égal à μ si et seulement s'il en est de même pour chacun de ses sous-graphes de cardinal strictement inférieur à κ[18]. Le théorème originel de De Bruijn-Erdős est le cas κ = ℵ0 de cette généralisation. Mais celle-ci nécessite une hypothèse comme celle de compacité forte de κ : sous l'hypothèse généralisée du continu, pour tout cardinal infini γ, il existe un graphe G de cardinal (2γ)+ dont le nombre chromatique est strictement supérieur à γ, mais dont tous les sous-graphes strictement plus petits (en nombre de sommets) que le graphe ont un nombre chromatique inférieur ou égal à γ[19]. Lake[20] caractérise les graphes infinis pour lesquels la généralisation du théorème de De Bruijn-Erdős est vraie, au sens où leur nombre chromatique est égal au maximum des nombres chromatiques de leurs sous-graphes strictement plus petits.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « De Bruijn–Erdős theorem (graph theory) » (voir la liste des auteurs)

  1. (en) N. G. de Bruijn et P. Erdős, « A colour problem for infinite graphs and a problem in the theory of relations », Nederl. Akad. Wetensch. Proc. Ser. A, vol. 54,‎ 1951, p. 371–373 (lire en ligne)
  2. (en) Alexander Soifer (en), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer,‎ 2008 (ISBN 978-0-387-74640-1, lire en ligne), p. 236
  3. (en) W. H. Gottschalk, « Choice functions and Tychonoff's theorem », Proc. Amer. Math. Soc., vol. 2,‎ 1951, p. 172 (lire en ligne)
  4. (en) Tommy R. Jensen et Bjarne Toft, Graph coloring problems, John Wiley & Sons, coll. « Wiley-Interscience Series in Discrete Mathematics and Optimization »,‎ 1995 (ISBN 978-0-471-02865-9, lire en ligne), p. 2-3, Theorem 1. Gottschalk 1951 prouve le théorème de De Bruijn-Erdős en redémontrant un théorème plus général de Richard Rado : (en) R. Rado, « Axiomatic treatment of rank in infinite sets », Canad. J. Math., vol. 1,‎ 1949, p. 337-343 (lire en ligne)
  5. (en) Egbert Harzheim, Ordered sets, Springer, coll. « Advances in Mathematics » (no 7),‎ 2005 (ISBN 978-0-387-24219-4, lire en ligne), p. 59, Theorem 5.5. Jensen et Toft 1995 attribuent à Gert Sabidussi (en) la remarque que la preuve de Gottschalk est plus facile à généraliser. Soifer 2008, p. 238-239 donne la même preuve par le lemme de Zorn, redécouverte en 2005 par l'étudiant de premier cycle Dmytro Karabash.
  6. (en) W. A. J. Luxemburg (en), « A remark on a paper by N. G. de Bruijn and P. Erdős », Indagationes Mathematicae, vol. 24,‎ 1962, p. 343-345
  7. (en) Albert E. Hurd et Peter A. Loeb (en), An introduction to nonstandard real analysis, Academic Press, coll. « Pure and Applied Mathematics » (no 118),‎ 1985 (ISBN 0-12-362440-1, lire en ligne), p. 92, Theorem 5.14
  8. (en) C. St. J. A. Nash-Williams, « Infinite graphs – a survey », JCT, vol. 3,‎ 1967, p. 286-301
  9. (en) Saharon Shelah et Alexander Soifer, « Axiom of choice and chromatic number of the plane », JCTA, vol. 103, no 2,‎ 2003, p. 387-391 (lien DOI?) ; Soifer 2008, p. 541-542
  10. (en) James H. Schmerl, « Graph coloring and reverse mathematics », Mathematical Logic Quarterly, vol. 46, no 4,‎ 2000, p. 543-548 (lien <543::AID-MALQ543>3.0.CO;2-E DOI?)
  11. Soifer 2008, p. 39
  12. Harzheim 2005
  13. (en) David Barnette, Map Coloring, Polyhedra, and the Four-Color Problem, MAA, coll. « Dolciani Mathematical Expositions » (no 8),‎ 1983 (ISBN 978-0-88385-309-2), p. 160. Nash-Williams 1967 établit ce résultat seulement pour 5 couleurs – le théorème des 4 couleurs n'était pas encore démontré lors de cette publication – et pour des graphes planaires dénombrables – la preuve du théorème de De Bruijn-Erdős qu'il donne ne s'applique qu'à ce cas. Pour la généralisation aux graphes dont tout sous-graphe fini est planaire (démontrée directement via le théorème de compacité de Gödel), voir (en) Wolfgang Rautenberg (de), A Concise Introduction to Mathematical Logic, Springer, coll. « Universitext »,‎ 2010, 3e éd. (ISBN 978-1-4419-1220-6, lire en ligne), p. 32.
  14. (en) Péter Komjáth (en), « Consistency results on infinite graphs », Isrrael J. Math. (en), vol. 61, no 3,‎ 1988, p. 285-294 (lien DOI?) ; (en) Péter Komjáth, « The chromatic number of infinite graphs – A survey », Discrete Math., vol. 311, no 15,‎ 2011, p. 1448-1450 (lien DOI?, lire en ligne)
  15. Pour ce lien entre le théorème de Rado et celui de De Bruijn-Erdős, voir par exemple la discussion qui suit Theorem A dans Nash-Williams 1967.
  16. (en) P. Erdős et A. Hajnal (en), « On chromatic number of graphs and set-systems », Acta Math. Acad. Sci. Hungar., vol. 17,‎ 1966, p. 61-99 (lire en ligne) ; Komjáth 2011
  17. Soifer 2008, p. 239
  18. Ceci résulte immédiatement de la définition de la compacité forte du cardinal κ : un ensemble de formules de la logique infinitaire (en) dont chacune est de longueur strictement inférieure à κ est satisfaisable dès que toutes ses parties de cardinal strictement inférieur à κ le sont. Voir par exemple (en) Akihiro Kanamori, The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings, Springer, coll. « Springer Monographs in Mathematics »,‎ 2008, 2e éd. (ISBN 978-3-540-88866-6, lire en ligne), p. 37.
  19. (en) P. Erdős et A. Hajnal, « On chromatic number of infinite graphs », dans Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press,‎ 1968 (lire en ligne), p. 83–98
  20. (en) John Lake, « A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs », JCTB, vol. 18,‎ 1975, p. 170-174