RELIER CHAQUE POINT À TOUS LES AUTRES : LE MINIMUM DE CROISEMENTS, DÉMONTRÉ

Placez cinq points sur une feuille de papier et reliez chaque paire par une courbe : dix courbes en tout. Elles peuvent se courber à volonté, mais aucune ne doit passer par un troisième point. Essayez d’éviter tout croisement : vous échouerez. Avec cinq points, au moins 1 croisement est inévitable ; avec six, au moins 3 ; avec dix, au moins 60.

Les mathématiciens appellent un tel dessin un tracé du graphe complet Kₙ — n points, chaque paire reliée — et le plus petit nombre de croisements qu’un tracé puisse atteindre, son nombre de croisements. Martin Balko, de l’université Charles en République tchèque, qualifie la question de « l’un des problèmes les plus célèbres de la théorie topologique des graphes ».

Le compte d’un artiste

À la fin des années 1950, l’artiste britannique Anthony Hill a construit des tracés de Kₙ avec exactement

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

croisements, où ⌊ ⌋ signifie arrondir à l’entier inférieur. L’idée qu’aucun tracé ne fait mieux a d’abord été publiée par Guy, puis discutée par Harary et Hill, et popularisée par Erdős et Guy. On l’appelle la conjecture de Harary–Hill, ou conjecture de Guy.

La formule grimpe vite :

• 4 points ou moins : 0 croisement
• 5 points : 1
• 7 points : 9
• 10 points : 60
• 14 points : 315

Six décennies de réponses partielles

Des tracés à exactement Z(n) croisements existaient pour tout nombre de points ; le plus dur était de montrer qu’aucun tracé ne fait mieux.

Pendant plus de soixante ans, on ne l’a démontré que pour des types particuliers de tracés — par exemple avec tous les points sur une droite et chaque courbe gardée d’un seul côté de celle-ci, ou avec les points sur une sphère et chaque courbe prenant le plus court chemin. Balko avait d’ailleurs réglé l’une de ces classes, avec Fulek et Kynčl. En 2021, des ordinateurs avaient confirmé la formule jusqu’à 14 points. Pour de très grands nombres de points, les meilleurs résultats généraux garantissaient au moins 98,5 %, puis 98,99 %, de Z(n).

Une preuve, puis une plus claire

En 2026, OpenAI a annoncé une preuve valable pour tout nombre de points, que l’article de Balko référence comme une « prépublication OpenAI Math Release » et à laquelle il attribue le théorème. L’article ne dit pas comment cette preuve a été trouvée. Selon Balko, l’original « est relativement court », mais « assez difficile à suivre ». Sa prépublication présente une variante allégée qui, selon son auteur, « ne demande que des connaissances élémentaires en algèbre linéaire et en théorie des graphes ». Un autre mathématicien, Gelasio Salazar, prépare de son côté un exposé détaillé.

Compter des coefficients au lieu des croisements

Comme des tracés connus atteignent déjà Z(n), seule la borne inférieure reste à prouver. Il faut quatre étapes.

1. Les nombres impairs suffisent. Un meilleur tracé peut être redessiné de façon que deux courbes qui partagent un point ne se croisent jamais ; chaque croisement met alors en jeu 4 points différents. Supprimez tour à tour chacun de 6 points : chaque dessin restant à 5 points a au moins 1 croisement, et chaque croisement survit à exactement 2 des 6 suppressions (il disparaît dès qu’on supprime l’un de ses 4 points, et survit aux 2 autres). Le double du nombre de croisements vaut donc au moins 6 : au moins 3, soit Z(6). Le même décompte marche pour tout nombre pair.
2. Une famille de polynômes. Donnez à chaque point son propre nombre. Un croisement met en jeu deux courbes, donc quatre points, donc quatre nombres. Balko utilise des polynômes à quatre variables, choisis pour que la famille ait exactement Z(n) coefficients indépendants quand n est impair — pour 7 points, 3 × 3 = 9.
3. Trop peu de croisements laissent de la place. Demander à un polynôme de s’annuler en un croisement, c’est une équation. Avec moins d’équations que de coefficients libres, l’algèbre linéaire laisse toujours une solution non nulle. Un tracé à moins de Z(n) croisements viendrait donc avec un polynôme non nul qui s’annule en tous ses croisements ; prenons celui de plus bas degré.
4. Le plan résiste. La géométrie entre par un seul fait classique : dans le plan, une boucle fermée en croise une autre de droite à gauche exactement aussi souvent que de gauche à droite. Avec des poids bien choisis, on en tire une somme de carrés des valeurs du polynôme, certains comptés positivement, d’autres négativement, dont le total est nul. Les termes positifs tombent tous sur des croisements, où le polynôme est nul, donc les négatifs doivent s’annuler aussi. Un second usage du fait sur les boucles le rend divisible par un facteur fixe ; la division donne un polynôme non nul de degré plus bas qui a la même propriété, ce qui est impossible puisqu’on avait pris le plus bas.

Cet argument de signes est le principal changement apporté par Balko : il remplace l’argument original, « faisant intervenir une forme bilinéaire non dégénérée et des supplémentaires orthogonaux ». L’article démontre aussi autrement le fait sur les boucles et isole chaque point plus directement.

D’autres réseaux réglés d’un coup

La réponse reste Z(n) si l’on compte, au lieu des croisements, les paires de courbes qui se croisent au moins une fois, ou un nombre impair de fois — tant que deux courbes qui partagent un point ne se rencontrent nulle part ailleurs. Combiné à des réductions antérieures, le théorème donne aussi le nombre de croisements exact de graphes complets auxquels on a retiré quelques liens, de copies d’un graphe complet enchaînées le long d’un chemin ou autour d’un cycle pair, et d’une famille de réseaux d’allure fractale appelés graphes de Sierpiński étendus.

Retirez une seule courbe du graphe complet à 6 points : son minimum passe de 3 croisements à 2 ; à 8 points, de 18 à 15.