Graphe diophantien d'Erdős

Un graphe diophantien d'Erdős, tirant son nom de Paul Erdős, est un graphe complet dont les sommets sont situés aux nœuds du réseau carré ${\displaystyle \mathbb {Z} ^{2}}$, appelé ici plan diophantien^[1], tel que les distances entre deux sommets quelconques sont entières, et tel que les autres points du réseau sont situés à une distance non entière d'au moins un sommet du graphe.

Graphe diophantien d'Erdős à 5 sommets formé de quatre triangles pythagoriciens.

Ce sont des cas particuliers de graphes diophantiens, graphes complets du plan diophantien dont les longueurs des arêtes sont entières^[1] ; leur appellation vient de ce que leur détermination fait appel à des résolutions d'équations diophantiennes. Les graphes diophantiens d'Erdős sont les graphes diophantiens maximaux. L'existence d'un graphe diophantien d'Erdős contenant tout graphe diophantien découle du théorème d'Erdős-Anning, énonçant que tout ensemble infini de points du plan à distances mutuelles entières est formé de points alignés. Par conséquent, tout processus d’extension d’un graphe diophantien formé de points non alignés atteint une figure qui ne peut plus être étendue.

Graphe diophantien à 6 sommets conjecturé être maximal^[2], faisant apparaître les triplets pythagoriciens (7,24,25), (9,12,15) = 3(3,4,5) et (12,16,20) = 4(3,4,5).

Exemples

Tout graphe ayant zéro ou un point peut être étendu de manière triviale, et tout graphe diophantien à deux points peut être étendu par des points sur la droite qu'ils déterminent. Un graphe diophantien d'Erdős possède donc au moins trois points non alignés.

Triangle diophantien, triangle à côtés entiers à sommets dans le réseau ${\displaystyle \mathbb {Z} ^{2}}$

Un triangle pythagoricien (triangle rectangle à côtés entiers) à sommets dans le plan diophantien est un graphe diophantien à trois sommets non maximal ; il peut être étendu de deux façons en un graphe diophantien d'Erdős, un à quatre sommets en ajoutant un triangle identique le long de l’hypoténuse, et un à cinq sommets en ajoutant trois triangles identiques formant un losange (voir figure).

Un graphe diophantien à trois sommets, ou triangle diophantien est obtenu en retirant 3 triangles pythagoriciens à un rectangle entier, certains étant éventuellement réduits à un point. Un exemple est illustré ci-contre, la formule générale se trouvant dans^[1].

Cet exemple, n'est pas maximal, mais par recherche numérique, Kohnert & Kurz ont montré qu'il existe des graphes diophantiens d'Erdős à trois sommets^[2]. Le plus petit a pour longueurs d'arête les entiers 2066, 1803 et 505. Les longueurs d'arête du suivant sont 2549, 2307 et 1492.

Brancheva a prouvé que la somme des longueurs des côtés d'un triangle diophantien est paire^[1]. Plus généralement, la longueur totale de tout chemin fermé dans un graphe diophantien d'Erdős est paire^[2].