Erdős-féle diofantoszi gráf

Az Erdős-féle diofantoszi gráf olyan geometriai gráf, aminek csúcspontjai a koordináta-rendszer egész értékű pontjain (rácspontokon) találhatók, egymástól páronként egész szám távolságra, és nem bővíthető ki egyetlen új csúccsal sem.

Erdős-féle diofantoszi gráf 5 csúcsponttal (a csúcsok távolságát jelöltük)

Ezzel ekvivalens definíció szerint az Erdős-féle diofantoszi gráf olyan teljes gráf, melynek csúcspontjai az euklideszi sík rácspontjaira ($\scriptstyle \mathbb {Z} ^{2}$) esnek oly módon, hogy bármely két csúcspont közötti távolság egész, de a rács bármely más pontjától legalább az egyik csúcspontig mért távolság nem-egész szám.

Az Erdős-féle diofantoszi gráfok Erdős Pálról és Diophantoszról kapták nevüket. A diofantoszi gráfok részhalmazát képezik – ezek a diofantoszi síkon (tehát rácspontokon) fekvő olyan teljes gráfok, melyeknél az élek hossza egész szám (egységtávolsággráfok). Tehát az Erdős-féle diofantoszi gráfok olyan diofantoszi gráfok, melyek nem bővíthetők újabb csúcsponttal. Az Erdős-féle diofantoszi gráfok létezése egyenes következménye az Erdős–Anning-tételnek, ami szerint a végtelen diofantoszi gráfoknak kollineárisnak (egyenesen elhelyezkedőnek) kell lenniük. Tehát egy nem kollineáris diofantoszi gráf új csúcspontokkal való bővítésének szükségszerűen, véges sok lépésben meg kell szakadnia.

Példák

A háromnál kevesebb csúcspontú gráfok mindig kollineárisak, tehát háromnál kevesebb csúcspontú Erdős-féle diofantoszi gráfok nem létezhetnek (hiszen triviálisan bővíthetők).

Numerikus kereséssel Kohnert és Kurz megmutatták, hogy léteznek háromszögű Erdős-féle diofantoszi gráfok, bár meglehetősen ritkák. Számításaik szerint 5000 élhosszúság alatt mindössze 7 ilyen létezik, ezek közül a két legkisebb élhosszúságai: 2066, 1803 és 505, illetve 2549, 2307 és 1492. Mindkét esetben a három élhossz összege páros szám. Brancheva igazolta, hogy ez a tulajdonság minden Erdős-diofantoszi háromszögre fennáll. Általánosabban, egy Erdős-diofantoszi gráfban bármely körön haladva az élhosszúságok összege páros szám lesz.

Az ábrán is látható, négy csúcspontból álló Erdős-diofantoszi gráf a 4 és 3 oldalhosszúságú téglalap megfelelő pontjaiból előáll.

Irodalom

• Kohnert, Axel; Kurz, Sascha (2005). "A note on Erdős–Diophantine graphs and Diophantine carpets". arXiv: Math/0511705
• Dimiev, Stancho; Markov, Krassimir (2002). "Gauss integers and Diophantine figures". arXiv: Math/0203061