(2025) Colorier une carte... un défi mathématique

Exposé pour le marathon des sciences du 35e Festival d'Astronomie de Fleurance le 2 août 2025. Il s'agit d'une présentation succincte des théorèmes des 4/7/9... couleurs

Transcript

1. Colorier une carte... ... un défi mathématique Roger Mansuy Festival Astronomie de Fleurance 2025
3. Angola dont Province de Cabinda Lesotho
6. On a utilisé 7 couleurs.
8. On a utilisé 4 couleurs.
9. Bleu: Malawi, Jaune: Mozambique Vert: Tanzanie, Rouge: Zambie
10. Il faut au moins 4 couleurs. Bleu: Malawi, Jaune: Mozambique Vert: Tanzanie, Rouge: Zambie
11. Des mathématiques! Conjecture des quatre couleurs Toute carte dessinée sur une sphère peut être coloriée avec quatre couleurs.
12. Exclave: morceau de territoire sous souveraineté d’un pays, séparé du territoire principal par un ou plusieurs pays ou mers
13. Si on autorise toutes sortes d’exclaves, on peut construire des cartes telles que la conjecture des quatre couleurs soit fausse. Ici, les cinq pays comportent tous des exclaves des quatres autres donc sont tous voisins.
14. Conjecture corrigée des quatre couleurs Toute carte dessinée sans exclave sur une sphère peut être coloriée avec quatre couleurs.
15. • 1879: Preuve par Alfred Kempe • 1880: Preuve par Peter Guthrie Tait
16. • 1879: Preuve par Alfred Kempe • 1880: Preuve par Peter Guthrie Tait • 1890: Réfutation de la preuve de Kempe par Percy Heawood
17. • 1879: Preuve par Alfred Kempe • 1880: Preuve par Peter Guthrie Tait • 1890: Réfutation de la preuve de Kempe par Percy Heawood • 1891: Réfutation de la preuve de Peter Guthrie Tait par Julius Petersen
18. Théorème des cinq couleurs [Heawood, 1890] Toute carte dessinée sans exclave sur une sphère peut être coloriée avec cinq couleurs.
19. Théorème des cinq couleurs [Heawood, 1890] Toute carte dessinée sans exclave sur une sphère peut être coloriée avec cinq couleurs. • preuve par récurrence d’une vingtaine de lignes • cela repose sur le fait qu’il existe un pays avec au plus cinq voisins
20. La preuve de Heawood fournit un algorithme de coloriage avec 5 couleurs, significativement amélioré dans les années 1980.
21. ”H.S.M. Coxeter, géomètre à l’université de Toronto, était presque le seul à croire que cette conjecture était fausse. L’intuition de Coxeter a maintenant été confirmée. En novembre 1974, William McGregor, un théoricien des graphes de Wappingers Falls, dans l’État de New York, a construit une carte de 110 régions qui ne peuvent être colorées avec moins de cinq couleurs. Le rapport technique de McGregor paraîtra en 1978 dans le Journal of Combinatorial Theory, Series B.” Six sensational discoveries that somehow or another have escaped public attention, Martin Gardner, Scientific American, avril 1975
23. Théorème des quatre couleurs [Appel et Haken, 1976] Toute carte dessinée sans exclave sur une sphère peut être coloriée avec quatre couleurs.
24. • Les articles font respectivement 62 et 77 pages. • Schématiquement, il y a une phase de réduction à certains cas puis une phase d’analyse de ces cas.
25. • Les articles font respectivement 62 et 77 pages. • Schématiquement, il y a une phase de réduction à certains cas puis une phase d’analyse de ces cas. • Il y a recours à l’outil informatique pour ”tester” ces cas.
28. • on ramène le problème du coloriage de carte à l’étude des graphes planaires triangulés quasi 6-connexes • on exhibe 1476 configurations qui sont inévitables dans ces graphes • par récurrence, on enlève une configuration inévitable et on étend les coloriages du graphe privé de cette configuration au graphe de départ
29. En complément de la preuve, l’article d’Appel et Haken fournit un algorithme de coloriage avec 4 couleurs donc la complexité est quartique.
30. En complément de la preuve, l’article d’Appel et Haken fournit un algorithme de coloriage avec 4 couleurs donc la complexité est quartique. La simplification de la preuve par Neil Robertson, Daniel P. Sanders, Paul Seymour, et Robin Thomas (1996) donne un algo- rithme quadratique!
31. ”Même le triomphe d’Appel et Haken en 1976 avait un goût d’échec : ils avaient utilisé un ordinateur pour faire la démonstration à leur place ! La controverse mathématique autour de la démonstration s’est peut-être apaisée avec la publication de leur livre et l’élégante révision de 1995 par Robertson, Saunders, Seymour et Thomas. Cependant, quelque chose clochait encore : les deux démonstrations combinaient un argument textuel, qui pouvait être raisonnablement vérifié par inspection, avec un code informatique qui ne pouvait pas l’être.” Formal Proof — The Four-Color Theorem, Georges Gonthier, Notices of the AMS, décembre 2008
32. ”Même le triomphe d’Appel et Haken en 1976 avait un goût d’échec : ils avaient utilisé un ordinateur pour faire la démonstration à leur place ! La controverse mathématique autour de la démonstration s’est peut-être apaisée avec la publication de leur livre et l’élégante révision de 1995 par Robertson, Saunders, Seymour et Thomas. Cependant, quelque chose clochait encore : les deux démonstrations combinaient un argument textuel, qui pouvait être raisonnablement vérifié par inspection, avec un code informatique qui ne pouvait pas l’être.” Formal Proof — The Four-Color Theorem, Georges Gonthier, Notices of the AMS, décembre 2008 • Preuve formelle en Rocq par Georges Gonthier et Benjamin Werner, 2005
33. Et la forme des pays?
38. Théorème de Kuratowski Un graphe correspond à une carte sur la sphère si, et seulement si, il ne contient pas un sous-graphe dont une subdivision est K5 ou K3,3. K5 K3,3
39. Théorème de Kuratowski Un graphe correspond à une carte sur la sphère si, et seulement si, il ne contient pas un sous-graphe dont une subdivision est K5 ou K3,3. K5 K3,3 La géométrie des pays est peu importante... mais celle de la planète?
40. Et si la Terre était ... Dans les années 1970, Joseph N. Portney (1927-2012), un ingénieur en aéronautique et ancien de US Air Force, a conçu un livret et une série d’affiches éducatives ”What if the earth were...”
41. Cela ne change rien pour le coloriage des cartes!
42. Cela ne change rien pour le coloriage des cartes!
43. Cela ne change rien pour le coloriage des cartes!
44. Cela ne change rien pour le coloriage des cartes!
45. Cela ne change rien pour le coloriage des cartes!
46. La projection stéréographique permet de passer du plan à la sphère.
48. Cela change tout pour le coloriage des cartes!
49. Théorème des sept couleurs Toute carte dessinée sans exclave sur un tore peut être coloriée avec sept couleurs.
50. Théorème des sept couleurs Toute carte dessinée sans exclave sur un tore peut être coloriée avec sept couleurs. Sept couleurs sont nécessaires dans le cas général!
51. La situation se complique encore quand on change le genre g de la surface (grosso modo, le nombre de trous): ⌊ 7+ √ 48g+1 2 ⌋ Illustration par Blaide Fedorowytsch
52. Coloriages contraints
53. 2 1 9 4 8 2 3 6 3 6 7 9 3 8 2 6 4 3 7 1 3 9 7 6
54. Quelques recommandations (1) • Le Rulpidon sous toutes ses coutures, Sylvie Benzoni-Gavage, Dunod, 2024 • Les couleurs du Rulpidon, Sylvie Benzoni-Gavage, vidéo Le Myriogon, 2024
55. Quelques recommandations (2) Construire un polyèdre de Szilassi (1977): sept faces telles que deux d’entre elles ont toujours au moins un côté en commun.