Graphe diophantien d'Erdős

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.

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].

• Portail des mathématiques
• Portail de l'informatique théorique