Harborts hypotese

Uløste problemer i matematik : Har nogen plan graf en heltals Fari-indlejring?

Harborts formodning siger, at enhver plan graf har en plan repræsentation , hvor hver kant er et segment af heltalslængde [1] [2] [3] . Denne formodning er opkaldt efter Heiko Harbort og (hvis den er sand) ville den styrke Faris sætning om eksistensen af ​​en tegning med retlinede kanter for enhver plan graf. Af denne grund er tegning af en graf med heltal kantlængder også kendt som en heltals Fari indlejring [4] . På trods af talrige undersøgelser i denne retning forbliver hypotesen åben [5] .

Særlige klasser af grafer

Selvom det ikke vides, om Harborts formodning er sand for alle plane grafer, er det blevet bevist for nogle specielle slags plane grafer.

En af de klasser af grafer, der har en heltals Fari-indlejring, er grafer, der kan reduceres til nul-grafen ved en række operationer af to slags:

For en sådan graf kan en rationel Fari-indlejring konstrueres trinvist ved at vende fjernelsesprocessen ved at bruge det faktum, at sættet af punkter, der er i en rationel afstand fra to givne punkter, er tæt i planet, og at hvis tre punkter er ved en rationel afstand fra et par og i en afstand, lig med kvadratrødderne af rationelle tal fra de to andre par, så er punkterne i en rationel afstand fra alle tre punkter tætte på planet [6] [7] . Afstandene i en sådan vedhæftning kan gøres heltal ved at skalere med en passende faktor. Baseret på denne konstruktion er følgende grafer kendt for at have heltals Fari-indlejringer: todelte plane grafer, (2,1)-spare plane grafer, plane grafer med træbredde højst 3 og grafer af grad 4 eller mindre, der enten indeholder en diamant ind som en undergraf eller er ikke 4-kant-forbundne grafer [4] [8] [9] .

Især grafer, der kan reduceres til den tomme graf ved kun at fjerne spidser af grad to eller mindre ( 2-degenererede plane grafer), omfatter både ydreplanære grafer og parallel - serielle grafer . For ydreplanære grafer er det dog muligt direkte at konstruere en heltals Fari-indlejring baseret på eksistensen af ​​uendelige delmængder af enhedscirklen , hvor alle afstande er rationelle [10] .

Derudover er heltals Fari-indlejringer kendt for hver af de fem regulære polyedre [3] .

Relaterede hypoteser

En stærkere version af Harborts formodning, præsenteret af Kleber [11] , antager, at enhver plan graf har et plant mønster, hvor toppunktets koordinater og kantlængder er heltal [12] . Dette er kendt for at være sandt for 3-regulære grafer [13] , for grafer, der har en maksimal grad på 4, men ikke er 4-regulære [14] , og for plane 3-træer [14] .

Et andet åbent problem i geometri er Erdős-Ulam-problemet , vedrørende eksistensen af ​​tætte delmængder i planet, hvor alle afstande er rationelle tal . Hvis en sådan delmængde eksisterede, ville den danne et universelt punktsæt, der kunne bruges til at tegne alle plane grafer med rationelle kantlængder (og derfor, efter passende skalering, heltalskantlængder). Imidlertid formodede Ulam, at tætte mængder med rationelle afstande ikke eksisterer [15] . Ifølge Erdős-Anning-sætningen er der ingen uendelige sæt af ikke-kollineære punkter, hvor alle afstande er heltal. Dette udelukker ikke eksistensen af ​​mængder, hvor alle afstande er rationelle, men det følger, at i ethvert sådant sæt kan nævnerne for rationelle afstande være vilkårligt store.

Se også

Noter

  1. ↑ Hartsfield, Ringel, 2013 , s. 247.
  2. ↑ Kemnitz, Harborth, 2001 , s. 191-195.
  3. ↑ 1 2 Harborth, Kemnitz, Möller, Süssenbach, 1987 , s. 118-122.
  4. ↑ Søn 12 , 2013 .
  5. ↑ Messing, Moser, Pach, 2005 , s. 250.
  6. ↑ Almering, 1963 , s. 192-199.
  7. ↑ Berry, 1992 , s. 391-398.
  8. ↑ Biedl, 2011 .
  9. ↑ Søn, 2011 .
  10. ↑ Klee, Wagon, 1991 , s. 132-135.
  11. ↑ Kleber, 2008 .
  12. ↑ Kleber, 2008 , s. 50-53.
  13. ↑ Geelen, Guo, McKinnon, 2008 , s. 270-274.
  14. ↑ 1 2 Benediktovich, 2013 , s. 2061-2064.
  15. ↑ Solymosi, de Zeeuw, 2010 , s. 393-401.

Litteratur