Une mathématicienne israélienne résout un problème vieux de 41 ans

Shares

Maria Chudnovsky, une mathématicienne israélienne, a dans le cadre de son travail de thèse à l’université de Princeton sous la direction de Neil Robertson et en collaboration avec Paul Seymour et Robin Thomas, démontré un problème de la théorie des graphes qui était resté ouvert pendant 41 ans. Les plus courageux d’entre nous pourront toujours lire la démonstration qui fait près de 180 pages, mais nous proposons ici pour les autres un bref résumé du problème en question.

Nous avons décrit dans l’article sur A. Trahtman le problème des « sept ponts de Königsberg » qui marqua les débuts de la théorie des graphes. Un peu plus d’un siècle plus tard, Francis Guthrie, en cherchant à résoudre un simple problème de coloriage, proposa un autre problème qui deviendra également un des plus célèbres de la théorie des graphes. En cherchant à colorier la carte des comtés d’Angleterre en 1852, il se posa la question de savoir de combien de couleurs il aurait besoin pour que les comtés qui se touchent ne soient pas coloriés de la même couleur. Il affirma alors qu’il n’aurait besoin que de quatre couleurs, et cette affirmation est connue depuis sous le nom de « conjecture des quatre couleurs » (Figure 1). Ce nombre minimal de couleurs pour colorier un graphe particulier est habituellement noté avec la lettre grecque χ par les théoriciens des graphes et nous l’utiliserons dans la suite.

Soyez informés en temps réel ! Suivez-nous sur...


Figure 1

En 1879, Alfred Kempe, pensant avoir résolu le problème proposa une démonstration qui fut ensuite invalidée en 1890 par Percy John Heawood. La preuve de ce résultat ne fut obtenu que bien plus tard, en 1976, grâce à l’utilisation d’un ordinateur.

Mais ces problèmes de coloriage de graphes, qui peuvent sembler être simples et inutiles, trouvent en fait des applications concrètes de nos jours dans de nombreuses applications et notamment dans la gestion des réseaux (quels qu’ils soient). On peut par exemple représenter un réseau de télécommunication à l’aide d’un graphe. Les sommets du graphe représentent les émetteurs, et deux sommets sont reliés par une arrête s’il y a recouvrement de leur zone d’émission. Le problème pour l’opérateur est alors de déterminer le nombre de canaux nécessaires pour être sûr que deux émetteurs reliés par une arrête n’émettent pas sur le même canal. Si l’on attribue une couleur à chaque canal, cela revient à chercher le nombre minimal de couleurs pour colorier le graphe correspondant. Et l’on peut voir ainsi que le simple problème du coloriage d’une carte au XIXième siècle peut trouver des applications dans le high-tech au XXIième grâce à sa formulation mathématique.

Figure 2

C’est en travaillant sur un problème de coloriage de graphes que Maria Chudnovsky démontra avec Neil Robertson, Paul Seymour, et Robin Thomas une conjecture qui était restée non démontrée pendant 41 ans. Cette conjecture fut proposée par le mathématicien français Claude Bergé dans les années 60 et est connue sous le nom de «SPGC» pour Strong Perfect Graph Conjecture ou théorème fort des graphes parfaits.

Commençons par définir ce qu’est un « graphe parfait » sur lequel repose cette conjecture. Cette caractéristique pour un graphe est reliée à χ, le nombre de couleurs minimal pour le colorier, et à ω la taille de la plus grande « clique » qu’il contient. Mais qu’est-ce qu’une clique me direz-vous ? Une clique est une partie d’un graphe où chaque sommet est relié aux autres sommets de la clique. Sur la figure 2, les trois sommets en rouge forment une clique car ils forment un ensemble où chaque sommet est relié aux autres sommets de cet ensemble. Dans le problème de coloriage des graphes, il est aisé de remarquer que χ, le nombre minimal de couleurs, doit être au moins égal à ω, la taille de la plus grande clique, car chaque sommet d’une clique doit avoir une couleur différente. Dans un graphe parfait, χ et ω sont exactement égaux. Autrement dit, il est possible de colorier tout le graphe avec un nombre de couleurs égal à la taille de la plus grande clique.

Les graphes parfaits sont particulièrement utiles dans la gestion des réseaux de télécommunication car ils permettent une gestion optimale des canaux. En effet, un réseau construit sur un graphe parfait utilise un nombre de canal minimal, et continuera de fonctionner même si un ou plusieurs émetteurs tombent en panne (on peut retirer un sommet d’un graphe parfait sans dénaturer le graphe). Les graphes parfaits sont relativement faciles à décrire, mais il est très difficile de fournir un algorithme pour les construire.

Dans ses travaux de 1961, Claude Bergé remarqua qu’un graphe parfait ne peut pas contenir de polygone avec un nombre de sommets impair supérieur ou égal à 5. En effet, de tels polygones ont un nombre ω égal à 2 et un nombre χ égal à 3. De la même façon, il remarqua qu’un graphe parfait ne peut pas contenir non plus de complémentaire d’un tel polygone (le complémentaire d’un polygone est un graphe ayant les mêmes sommets mais dont les arrêtes sont toutes les arrêtes possibles sauf celles du polygone initial). Car un complémentaire de polygone avec 2k+1 arrêtes possède un nombre ω égal à k et un nombre χ égal à k+1. Les graphes vérifiant ces propriétés furent appelés « graphes de Bergé », et personne à l’époque n’était capable de prouver que les graphes parfaits et les graphes de Bergé étaient exactement les mêmes. Cette conjecture resta ainsi non démontrée jusqu’en 2002, date à laquelle Maria Chudnovsky, alors étudiante en thèse sous la direction de Neil Robertson, proposa une preuve rédigée en collaboration avec Paul Seymour et Robin Thomas.

La démonstration proposée fait plus de 150 pages et dépasse largement le cadre de cet article, mais nous pouvons quand même brièvement relater les circonstances dans lesquelles elle a été obtenue.

Les quatre mathématiciens commencèrent à travailler sur le sujet en 2000, grâce à un financement privé du American Institute of Mathematics à Palo Alto en Californie (cet institut aide, par ses financements, les chercheurs à résoudre des problèmes réputés très difficiles). Les quatre chercheurs commencèrent par suivre une stratégie proposée par Gerard Cornuejols du Carnegie Mellon University à Pittsburgh, Pennsylvanie. En effet, celui-ci proposait à l’époque une récompense de 5000$ à quiconque apporterait la preuve d’une première étape de la démonstration qu’il avait proposée, et 5000$ de plus si celui-ci pouvait fournir la démonstration complète de la conjecture. C’est ainsi qu’à l’été 2002, Neil Robertson présenta un résumé de la démonstration lors d’une conférence à Oberwolfach en Allemagne. Comme toujours dans ce genre de situations où une démonstration longue et complexe doit être rédigée, il fallu attendre encore 4 ans avant que l’article définitif ne soit publié dans le journal Annals of Mathematics en 2006. Claude Bergé, très malade sur son lit d’hôpital, apprit la nouvelle de la démonstration de sa conjecture quelques mois avant sa mort.

Maria Chudnovsky en quelques mots :

Maria Chudnovsky est une jeune mathématicienne née en 1977. Née en Russie, elle immigre avec sa famille en Israël à l’âge de 13 ans. Elle débute ses études au Technion Israel Institute of Technology à Haïfa où elle obtient sa licence en mathématiques avec une mention très bien en 1996 et son master en 1999. Elle part ensuite aux Etats-Unis où elle obtient son doctorat de la prestigieuse université de Princeton. Elle occupera différents postes aux Etats-Unis, notamment à Princeton et au Clay Mathematics Institute. Elle est actuellement Maitre de Conférences à l’université Columbia de New York.

Comme nous vous l’avions déjà annoncé sur siliconwadi, elle est en 2012 l’une des 23 récipiendaires de la bourse de la très prestigieuse fondation MacArthur qui attribue des financements à des scientifiques brillants et prometteurs.

Shares

RetweeTech

Rejoignez nos 2 896 abonnés et recevez nos derniers articles directement sur votre e-mail.