Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

Cet article présente deux contre-exemples à la deuxième conjecture de Jain sur les flots d'unités vectorielles, démontrant que certaines configurations de points sur la sphère nécessitent des valeurs supplémentaires au-delà de l'ensemble proposé, ce qui invalide une condition clé pour la conjecture des 5-flots de Tutte.

L'essentiel

🌍 Le Grand Jeu des Flèches sur une Boule

Imaginez que vous avez une grosse boule de bowling (une sphère) et que vous devez y dessiner des flèches sur sa surface. Chaque flèche doit avoir exactement la même longueur (disons 1 mètre). C'est ce qu'on appelle un flux de vecteurs unitaires.

Le but du jeu est de placer ces flèches sur les arêtes d'un dessin (un "graphe") de telle sorte que, à chaque intersection (un sommet), les flèches qui arrivent s'annulent exactement avec celles qui partent. C'est comme un jeu de billard où tout ce qui entre doit ressortir, sans rien perdre ni rien gagner.

🧩 Le Défi de Jain : Le Puzzle des Nombres Magiques

Un mathématicien nommé K. Jain a posé un défi fascinant. Il a dit :

"Si vous prenez n'importe quelle boule remplie de points, pouvez-vous attribuer à chaque point un petit nombre entier (comme -4, -3, -2, -1, 1, 2, 3, 4) de manière intelligente ?"

Il y a deux règles strictes pour ce jeu de nombres :

1. La règle du miroir : Si vous prenez un point et son opposé exact de l'autre côté de la boule (comme le pôle Nord et le pôle Sud), leurs nombres doivent s'additionner à zéro (ex: si l'un est +3, l'autre doit être -3).
2. La règle du triangle équilibré : Si vous prenez trois points qui forment un triangle parfait sur un grand cercle (comme l'équateur), la somme de leurs nombres doit aussi être zéro.

Jain pensait que c'était toujours possible avec seulement les nombres de -4 à +4. S'il avait raison, cela prouverait une théorie très célèbre et difficile sur les graphes (la conjecture de Tutte).

💥 Le Coup de Massue : "Non, ça ne marche pas !"

L'auteur de ce papier, Nikolay Ulyanov, a dit : "Attendez, je pense avoir trouvé une faille."

Il a construit deux situations (deux puzzles) où il est impossible de jouer avec seulement les nombres de -4 à +4. Pour résoudre ces puzzles, il est obligé d'utiliser le nombre 5 (ou -5).

C'est un peu comme si vous essayiez de payer une dette avec des pièces de 1, 2, 3 et 4 euros, mais que la somme exacte demandée vous obligeait à sortir une pièce de 5 euros. Jain pensait que la pièce de 5 euros n'était jamais nécessaire, mais Ulyanov a prouvé le contraire.

🏗️ Comment a-t-il construit ces pièges ?

L'auteur a utilisé deux méthodes créatives pour construire ces "pièges" :

1. L'Explosion de l'Icosidodécaèdre (Le Puzzle de 50 points) :
   Imaginez un objet géométrique complexe (un icosaèdre mélangé à un dodécaèdre) qui a 30 sommets. L'auteur a pris chaque point et a créé un petit cercle autour de lui, puis il a ajouté de nouveaux points là où ces cercles se croisent.

   • Le résultat : Un puzzle de 50 points.
   • La preuve : Il a demandé à un ordinateur très puissant (un solveur SAT) de vérifier toutes les combinaisons possibles de nombres. L'ordinateur a crié : "IMPOSSIBLE !". Aucune combinaison avec les nombres -4 à +4 ne fonctionne. Il faut absolument le 5.

2. La Construction Radicale (Le Puzzle de 36 points) :
   Pour la deuxième preuve, il a utilisé une recette différente basée sur des racines carrées et des nombres irrationnels (des nombres un peu "bizarres" comme $\sqrt{3}$). Il a généré des milliers de points potentiels, puis a élagué l'arbre pour ne garder que le cœur du problème : un groupe de 36 points.

   • Le résultat : Un puzzle plus petit, mais tout aussi têtu.
   • La preuve : Encore une fois, l'ordinateur a confirmé que sans le nombre 5, le puzzle reste bloqué.

🤔 Pourquoi est-ce important ?

C'est un peu comme si un architecte disait : "Je peux construire n'importe quel pont avec des briques de taille 1 à 4." Et un inspecteur arrive avec deux exemples de ponts qui s'effondrent s'il n'utilise pas de briques de taille 5.

Cela ne signifie pas que la théorie de Jain est totalement fausse, mais cela signifie que sa deuxième hypothèse (le puzzle des nombres) est trop optimiste. Cela force les mathématiciens à :

• Repenser comment ils veulent prouver la conjecture de Tutte.
• Chercher des solutions plus subtiles, peut-être en utilisant des ensembles de points infinis ou des nombres spéciaux, plutôt que des petits ensembles finis.

En résumé

Ce papier est une chasse au trésor mathématique inversée. Au lieu de chercher une solution, l'auteur a construit des énigmes insolubles avec les règles actuelles. Il a montré que pour certains arrangements de points sur une sphère, on est obligé de sortir le "grand nombre" (le 5) pour équilibrer l'équation, prouvant ainsi que la conjecture de Jain, telle qu'elle était formulée, ne tient pas la route.

C'est une victoire de la logique et de la puissance de calcul : l'ordinateur a dit "Non", et les mathématiciens ont dû écouter.

Résumé technique

1. Contexte et Problématique

Le papier s'attaque à deux conjectures formulées par K. Jain concernant les flots de vecteurs unitaires sur les graphes. Ces conjectures sont liées à la célèbre conjecture des 5-flots de Tutte (1954), qui postule que tout graphe cubique sans pont admet un flot non nul à valeurs entières inférieures à 5.

Les deux conjectures de Jain sont :

1. Conjecture 1 (Flots de vecteurs unitaires) : Tout graphe sans pont admet un flot $f : E(G) \to S^2$ (où chaque arête est assignée un vecteur unitaire dans $\mathbb{R}^3$).
2. Conjecture 2 (Flot $S^2$ non nul de valeur 5) : Il existe une application $q : S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ telle que :
   • Les points antipodaux ont des valeurs opposées ($q(-x) = -q(x)$).
   • La somme des valeurs de trois points équidistants sur un grand cercle est nulle.

L'enjeu : Si les deux conjectures étaient vraies, leur combinaison impliquerait la conjecture de Tutte. L'objectif de l'article est de tester la validité de la deuxième conjecture en cherchant des contre-exemples : des sous-ensembles finis de la sphère $S^2$ pour lesquels une telle application $q$ n'existe pas avec des valeurs limitées à $\{\pm 1, \dots, \pm 4\}$, nécessitant ainsi la valeur $\pm 5$ (ce qui correspondrait à un flot non nul de valeur 6, mais pas 5).

2. Méthodologie

L'auteur utilise une approche combinatoire et computationnelle rigoureuse pour prouver l'impossibilité de certaines assignations de valeurs :

• Construction géométrique : Création de sous-ensembles finis de points sur la sphère $S^2$ en exploitant des structures géométriques symétriques (polyèdres réguliers, arrangements de grands cercles).
• Modélisation SAT (Satisfaisabilité Booléenne) : Le problème d'assignation de valeurs est encodé comme une instance de problème SAT.
  • Pour chaque point antipodal représentatif, 8 variables booléennes sont introduites (une pour chaque valeur possible dans $\{-4, \dots, 4\}$).
  • Des contraintes sont ajoutées :
    • Exactly-one : Un point ne peut avoir qu'une seule valeur.
    • Antipodal : $q(-p) = -q(p)$.
    • Somme de triplets : Pour tout triplet de points équidistants sur un grand cercle, $q(a) + q(b) + q(c) = 0$.
• Vérification par solveurs : Utilisation des solveurs PicoSAT et pycosat pour déterminer si la formule CNF résultante est satisfiable. L'insatisfiabilité prouve l'absence de flot non nul de valeur 5 pour l'ensemble donné.
• Vérification formelle : Une preuve formelle est également fournie via le langage Lean 4 (tactique bv_decide) pour garantir l'exactitude des résultats computationnels.

3. Contributions Clés et Résultats

L'article présente deux contre-exemples majeurs qui réfutent la Conjecture 1.2 de Jain.

Contre-exemple 1 : Expansion à 50 points de l'icosaédodécaèdre

• Construction : Basée sur l'icosaédodécaèdre (30 points). L'auteur ajoute des points en intersectant de petits cercles associés aux paires de points de l'icosaédodécaèdre séparés par une distance sphérique de $2\pi/5$.
• Structure : L'ensemble résultant contient 50 points et 40 triplets de grands cercles.
• Interprétation graphique : En quotientant par les points antipodaux, on obtient un graphe cubique combinant le graphe de Petersen et un escalier de Möbius à 10 sommets.
• Résultat : La formule SAT (200 variables, 19 765 clauses) est insatisfiable. Cela démontre qu'aucune assignation avec des valeurs dans $\{\pm 1, \dots, \pm 4\}$ n'existe. Une assignation nécessitant $\pm 5$ (un flot 6) est possible.

Contre-exemple 2 : Construction à 36 points basée sur l'arithmétique des racines carrées

• Construction : Une approche algorithmique générant des coordonnées via des combinaisons linéaires de $\sqrt{v_1}$ et $\sqrt{v_2}$. Après filtrage et élagage itératif des triplets redondants, un sous-ensemble minimal est extrait.
• Structure : Un ensemble de 36 points et 13 triplets.
• Coordonnées : Les coordonnées impliquent des valeurs algébriques spécifiques (ex: $0, \frac{2-\sqrt{3}}{2}, \frac{\sqrt{3}-1}{2}, \dots$).
• Résultat : La formule SAT (144 variables, 6 710 clauses) est insatisfiable pour les valeurs $\{\pm 1, \dots, \pm 4\}$. Une solution existe cependant avec des valeurs jusqu'à $\pm 5$ (180 variables).

4. Signification et Implications

• Réfutation de la Conjecture 1.2 : Le papier démontre de manière définitive que la deuxième conjecture de Jain est fausse. Il existe des configurations géométriques sur $S^2$ qui ne peuvent pas être étiquetées avec un flot non nul de valeur 5.
• Impact sur la Conjecture de Tutte : Puisque la Conjecture 1.2 est fausse, la voie directe pour prouver la conjecture des 5-flots de Tutte via la combinaison des conjectures de Jain est bloquée. Cela suggère que si la conjecture de Tutte est vraie, elle doit être prouvée par d'autres moyens, ou que la Conjecture 1.1 (existence du flot vectoriel) ne suffit pas à impliquer la Conjecture 1.2 dans sa forme actuelle.
• Questions Ouvertes :
  • Existe-t-il des sous-ensembles nécessitant des valeurs $\pm 6$ ou plus ?
  • Quel est le plus petit contre-exemple possible ?
  • Peut-on sauver la conjecture en restreignant l'ensemble de points à des sous-ensembles infinis ou à des coordonnées algébriques spécifiques pour les graphes cubiques ?
• Observation sur les flots modulaires : L'auteur note que, dans ses expériences, la distinction entre les flots non nuls classiques et les flots non nuls modulo $k$ semble inexistante pour les sous-ensembles testés (le $k$ minimal est le même pour les deux).

Conclusion

Ce travail fournit une réfutation computationnelle et formelle solide d'une conjecture géométrique clé en théorie des graphes. En construisant des configurations de points sur la sphère qui forcent l'utilisation de valeurs supérieures à 4, l'auteur montre que l'approche de Jain pour prouver la conjecture des 5-flots de Tutte via les flots de vecteurs unitaires échoue dans sa formulation actuelle. Les codes sources et les preuves formelles sont disponibles publiquement pour reproductibilité.