NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 14/10/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

TOPOLOGIE

 

Débutants

Géométrie

QUATRE COULEURS

Divers

 

Glossaire

Géométrie

 

INDEX

 

Quatre couleurs

 

 

Géométrie

 

Topologie

 

 

Général

Historique

Prince de Möbius

Diamant de Birkhoff

 

Sommaire de cette page

 

>>> Origine (Gunthrie)

>>> Premières démonstrations (Kempe)

>>> Méthode de réduction (Heesch)

>>> La démonstration (Appel)

 

 

 

 

 

 

Théorèmes des quatre couleurs

Ou problème de Gunthrie

Historique

Premier questionnement en 1852 à propos de la coloration des cantons anglais. Résolution en 1976 avec l'aide d'un ordinateur pour explorer systématiquement les 1500 cas récalcitrants.

Pour résoudre ce problème qui semblait simple, il a fallu attendre que la puissance de calcul des ordinateurs soit disponible.

Américain: The four color problem  ot the 4-color theorem (4CT) or the Gunthrie's problem

 

 

 

 

Historique

 

 

Comme souvent pour les problèmes les plus ardus, la démonstration correspond à une succession de procédés permettant de reporter la démonstration générale dans un autre monde et, comme cela, de rebond en rebond, aboutir à la solution finale.

 

Historique

 

/

/

*    Aucune trace de ce problème attestée avant 1840.

1750

Leonhard Euler

(1717-1783)

*    Lettre à Goldbach mentionnant la relation relative aux polyèdres.

1794

Adrien-Marie Legendre

(1752-1833)

*    Prouve la relation d'Euler.

1811

Simon-Antoine Lhuilier

*    La relation d'Euler s'applique aux polyèdres troués.

1813

Augustin Cauchy

(1798-1857)

*    Montre que la relation d'Euler relative aux polyèdres est valable aussi pour les cartes de plus de deux régions et sans région incluse.

1840

August Möbius

(1790-1868)

Astronome Leipzig

*    Problème des cinq princes qui préfigure l'énoncé du problème des quatre couleurs. Ce problème montre l'impossibilité de partager le royaume en cinq régions mitoyennes entre elles.

1852

Francis Guthrie

(1831-1899)

Mathématicien et botaniste Anglais alors professeur à la South African University, Cape Town (Afrique du Sud)

*    Énonce le problème. Il remarque qu'il lui suffit de quatre couleurs pour colorer la carte chargée des cantons (counties) d'Angleterre. Les cantons ayant une frontière commune sont tous de couleurs différentes.

*    Ancien élève de De Morgan, il lui communique la conjecture via son frère Frederick, alors encore lui aussi élève de De Morgan.

*    Cette illustration était dans la marge de la correspondance entre lui et son frère.

 

1852

Auguste De Morgan

(1806-1871)

University College, Londres

 

William Hamilton

(1830-1803)

Irlandais

*    De Morgan s'y intéresse, avoue qu'il n'a pas beaucoup progressé, et passe le bébé à Hamilton.

 

Le 23 octobre 1852 ; lettre d'Augustus de Morgan, professeur de mathématiques à University College (Londres) à Sir William Rowan Hamilton, professeur au Trinity College (Dublin):

"… Si quatre régions ont deux à deux une ligne frontalière, trois d'entre elles enclavent la quatrième et empêchent n'importe quelle cinquième de la toucher. Si ceci était vrai, quatre couleurs seraient toujours suffisantes…"

Hamilton répond qu'il n'a guère le temps (l'envie) de s'intéresser à ce problème de quaternion de couleurs (I'm not likely to attempt your "quaternion" of colours very soon).

Extrait de la lettre 23 octobre 1852

 

*    De Morgan laisse tout de même un théorème:

Il est impossible de disposer cinq régions de telle façon qu'il existe des frontières communes entre tous les couples possibles.

Propriété qui laisse penser que quatre couleurs devraient suffire.

1860

De Morgan

http://upload.wikimedia.org/wikipedia/commons/2/2c/De_Morgan_Augustus.jpg

 

William Whewell

Philosophe

*    De Morgan écrit à ce philosophe sur le problème des quatre couleurs ainsi qu'à Robert Ellis.

*    Whewell publie: The philosophy of discovery dans le magazine Athenaeum.

*    De Morgan, en retour, publie la revue de cet article et se faisant, il est  le premier à mentionner le problème des quatre couleurs dans un écrit public. Ainsi, le problème devint connu aux États-Unis.

(…) Now, it must have been always known to map-colourers that four different colours are enough. (En fait, les cartogrpahes ont toujours su que quatre couleurs sont suffisantes).

1869

Charles Sanders Pierce

Américian

*    Lui aussi alerté par De Morgan, passe une bonne part de sa vie sur ce problème et ne conçoit pas que les mathématiciens aient à passer autant de temps sur un problème aussi simple.
Il aurait présenté une solution à HArvard qui n'a jamais été retrouvée dans ses manuscrits.

*    Il s'intéresse également aux volumes et pense, par exemple, qu'il faut sept couleurs pour un tore.

1973

Carl Hierholzer

(1840-1871)

*    La preuve du théorème d'Euler (nombre pair d'arêtes) fut en fait publiée par Hierholzer.

1878

Arthur Cayley

(1821-1895)

*    Publie le problème des quatre couleurs dans les Proceedings of the London Mathematical Society.

C'est la première référence écrite  énonçant le problème et sollicitant une réponse.

 

1879

Alfred Kempe

(1849-1922)

*    Publie une solution dans L'American Journal of Mathematics. Elle s'avère non valable pour quatre couleurs. Notamment dans le traitement de réduction des pentagones. Par contre:

*    elle fera progresser la démonstration pour cinq couleurs, et

*    elle contient la trame de la solution finale: les chaines de Kempe. >>>

*    Théorème: dans toute carte, il existe au moins une région avec cinq voisines ou moins. La région est en forme de cercle, de triangle, de carré ou de pentagone.

1880

Peter Tait

(1831-1901)

 et

Julius Peterson

*    Le premier publie aussi une solution, réfutée par le second.
(Tait est connu pour ses études sur la classification des nœuds).

*    Il conjecture  que les graphes hamiltoniens peuvent être colorés avec quatre couleurs. Contre-exemple trouvé en 1946 par William Tutte (1917-2002). 

1885

Thomas Penyngton Kirkman

*    Spécialiste des polyèdres, il redémontre la relation d'Euler et il étudie les cycles (hamiltoniens) dans ces volumes.

1885

Richard Baltzer

Géomètre allemand

*    Exhume l'énigme des cinq princes de Möbius. Il en déduit à tord, comme beaucoup d'autres à l'époque, que cela prouve que quatre couleurs sont suffisantes.

*    Frederick Temple, évêque de Londres, fera la même confusion en 1889. 

1886

/

*    Le problème est posé comme défi aux élèves du Clifton College.

1890

1891

Percy Heawood

(1861-1955)

*    Découvre une erreur dans la démonstration de Kempe.
Aménage la démonstration  et établit le théorème des cinq couleurs.

*    Détermine le nombre maximum de couleurs pour toutes les surfaces, sauf le plan (Conjecture).

*    Il s'intéresse aussi aux surfaces non planes. Il conjecture une limite supérieure du nombre de couleurs en fonction du nombre de trous dans la surface.

1891

Lothar Heffter

*    Constate une erreur dans le raisonnement de Heawood sur les tores avec un ou deux trous.

1900?

Heinrich Tietze (1880-1964)

*    Établit un premier résultat sur les domaines adjacents d'une surface orientée.

*    Démonstration du fait que le théorème des quatre couleurs n'a pas d'équivalent dans les dimensions supérieures à 2.

1904

Paul Wernicke

Allemand

*    Démontre que toute carte doit contenir au moins l'une de ces cinq configurations inévitables:

*    Un des premiers à établir des configurations inévitables de grande ampleur. Par exemple: le pentagone inévitable serait remplacé par un couple de pentagones adjacents et un pentagone adjacent à un hexagone, ce qui produit une configuration inévitable plus grande.

1913

George D. Birkhoff

(1884-1944)

Harvard

*    Il introduit la notion de configurations réductibles.

*    Introduit les polynômes chromatiques qui s'avérèrent utiles mais pas pour le problème des quatre couleurs.

*    Le diamant de Birkhoff est réductible

1922

Philip Franklin

(1898-1965)

MIT

*    Sur la base des travaux de Birhoff, développe le concept de configurations réductibles et démontre que la conjecture est vraie (quatre couleurs) pour toutes les cartes de moins de 26 couleurs: tout graphe planaire ayant au plus 25 sommets est 4-coloriable.

1926, Reynolds donne 27;

1940, Winn arrive à       35;

1970, Ore et Stemple à 39; et

1976, Mater atteint         95.

*    Il donne un contre-exemple de la conjecture de Heawood avec un graphe cubique à 12 sommets.

1940

Henri Lebesque

(1875-1941)

*    S'intéresse au problème: analyse le voisinage des pentagones et en donne la liste exhaustive

*    À partir de la relation d'Euler, construit un nombre considérable de configurations inévitables.

 

Hermann Minkowski (1864-1909) prend ce problème de haut en prétendant que seuls des mathématiciens de troisième catégorie auraient étudié ce problème. Ce qui expliquerait qu'il ne soit pas encore résolu. Il entreprend son étude et reconnait quelque temps plus tard: "J'ai indisposé le ciel par mon arrogance: ma démonstration est, elle aussi, inexacte". (Heaven is angered by my arrogance; my proof is also defective).

 

 

1950

à

1970

Henrish Heesch

(1906-1995)

Hanovre

Dürre (le programmeur)

Jean Mayer

Montpellier

*    Développe les ingrédients qui s'avéreront utiles à la preuve finale, notamment la notion de réduction. 

*    C'est lui qui passe à la représentation des cartes en graphes.

*    Analogie des charges électriques pour réduire le nombre de cas inévitables (1969).

*    Pense que 8 900 cas irréductibles sont à explorer. Il utilise pour cela les ordinateurs.

*    Cependant des configurations (circuit) ayant 18 régions comme frontière apparaissent. Trop gigantesque pour être testées.

*    Son ouvrage s'intitule: Untersuchungen zum Vierfarbenproblem.

1959

HSM Coxeter

Géomètre

*    C'est lui qui donne la paternité du problème à Guthrie et non à  Möbius Ce que personne ne conteste depuis.

1968

G. Ringel et

E. Youngs

*    Démonstration de la conjecture d'Heawood: le nombre minimal de couleurs  est égal à la limite de Heawood. Deux exceptions: la sphère et la bouteille de Klein.

 

1970

Wolfgang Haken

(né en 1928)

*    Perfectionne la méthode des charges de Heesch.

*    Pense que le problème est désormais à portée.

1976

Kenneth Appel

(1932-2013)

 et Wolfgang Haken

John Coke

Programmeur

*    Démonstration finale par exploration systématique des cas particuliers (Université de l'Illinois).

*    En effet, la démonstration résout les cas généraux en laissant de côté 1478 cas particuliers.

*    Ils ont réussi à limiter les configurations maximales à 14 régions en frontières. Ce qui devenait accessible au calcul par ordinateurs.

*    C'est la première démonstration mathématique assistée par ordinateur.

*    Elle pose souci aux autres mathématiciens. La confirmation n'est pas aisée. Comment vérifier l'informatique sous-jacente? Est-ce que le programme réalisé est fiable ?

1995

Neil Robertson

(né en 1938),

Daniel Sanders,

Paul Seymour

(né en 1950)

et Robin Thomas

(né en 1962)

*    Simplification de la solution.
Réduction des cas à tester à 633 au lieu de 1478.

*    Ci-contre analyse de graphes utilisant la formule d'Euler et le calcul de charges.

2004

Georges Gonthier (Cambridge) et Benjamin Werner (INRIA-France)

*    Preuve formelle à l'aide d'un assistant de preuve (programme Coq).

*    La preuve du théorème des quatre couleurs est définitivement admise par tous les mathématiciens.

Voir Preuve concernant l'empilement des sphères

2005

J. Ferro

*    Disqualifie certaines prétendues preuves rapides du théorème.

Reference 1: The four color theoremMathWorld

J. Ferro (pers. comm., Nov. 8, 2005) has debunked a number of purported "short" proofs of the four-color theorem.

Traduction: J. Ferro (communication personnelle du 8 novembre 2005) a démystifié un certain nombre de prétendues courtes preuves du théorème des quatre couleurs.

Reference 2: Vertex Coloring of Planar Graphs with Restrictions over Shortest Paths.

2014

/

*    Toujours pas de preuve classique (sans ordinateur)

 

 

 

 

 

Retour

*    Problème des quatre couleurs

*    Démonstration de Kempe

Suite

*    Princes de Moebius

*    Quatre couleursIndex

Voir

*    Cinq pays

*    Couleurs

*    Démonstration

*    Graphe à 2 couleurs

*    Indicateur d'Euler-Poincaré

*    Introduction à la topologie

*    Quadrichromie

*    TopologieGlossaire

*    TopologieIndex  

DicoNombre

*    Nombre 4

Sites

*    Voir références

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Geometri/TopoQHis.htm