Théorème des 4 couleurs & Orientations



Un map monde en 4 couleurs.

Le Théorème des 4 couleurs affirme que toute carte peut être coloriée avec 4 couleurs, de façon à ce que des régions voisines aient des couleurs différentes. Il a fallu plus d'un siècle pour montrer ce résultat et les seuls preuves connues font appel à un programme de vérification. Dis autrement, aucun être humain n'a vérifié 'à la main' chaque étape de ces preuves.


Le but de ce stage sera de tester une hypothèse mathématique en lien avec le Théorème des 4 couleurs. Ces tests se feront sur de petits graphes planaires générés via plantri. L'hypothèse mathématique à tester est la suivante :


  • Est-il vrai que tout graphe planaire 4-connexe vérifie le critère de Alon-Tarsi pour la 4-colorabilité ? Si oui, cela impliquerait le Théorème des 4 couleurs !


Un graphe vérifie le critère de Alon-Tarsi pour la 4-colorabilité s'il admet une orientation telle que ses sommets ont au plus 3 arcs sortants, et telle que les nombres de sous-graphes Eulériens ayant un nombre pair et impair d'arêtes diffèrent.


Le stage comprend une partie programmation (implémentation d'une fonction pour générer les sous-graphes Eulériens d'un graphe orienté) et une partie recherche où l'étudiant cherchera à identifier les caractéristiques des orientations vérifiant le critère de Alon-Tarsi.