Harbortin hypoteesi

Ratkaisemattomat matematiikan ongelmat : Onko missään tasograafissa Fari-upotettu kokonaisluku?

Harbortin oletuksen mukaan millä tahansa tasograafilla on tasoesitys , jossa jokainen reuna on kokonaislukupituinen segmentti [ 1] [2] [3] . Tämä olettamus on nimetty Heiko Harbortin mukaan ja (jos totta) vahvistaisi Farin lausetta suoraviivaisten reunojen olemassaolosta mille tahansa tasograafille. Tästä syystä graafin piirtäminen kokonaislukujen reunapituuksilla tunnetaan myös kokonaisluku Fari-upotuksena [4] . Lukuisista tämänsuuntaisista tutkimuksista huolimatta hypoteesi on edelleen avoin [5] .

Graafeiden erikoisluokat

Vaikka ei tiedetä pitääkö Harbortin olettamus totta kaikille tasograafille, se on todistettu joidenkin erityisten tasograafien kohdalla.

Yksi kaavioluokista, joissa on kokonaisluku Fari-upotus, on graafit, jotka voidaan pelkistää nollakuvaajaksi kahden tyyppisten toimintojen sarjalla:

Tällaiselle kuvaajalle voidaan rakentaa rationaalinen Fari-upotus asteittain kääntämällä poistoprosessi päinvastaiseksi käyttämällä sitä tosiasiaa, että kahdesta annetusta pisteestä rationaalisen etäisyyden päässä olevien pisteiden joukko on tiheä tasossa, ja jos kolme pistettä ovat rationaalinen etäisyys yhdestä parista ja etäisyydellä, joka on yhtä suuri kuin rationaalilukujen neliöjuuret kahdesta muusta parista, niin pisteet, jotka ovat rationaalisen etäisyyden päässä kaikista kolmesta pisteestä, ovat tiheitä tasossa [6] [7] . Tällaisen liitteen etäisyydet voidaan tehdä kokonaislukuina skaalaamalla sopivalla kertoimella. Tämän rakenteen perusteella seuraavilla kaavioilla tiedetään olevan kokonaisluku Fari-upotuksia: kaksiosaiset tasograafit , (2,1)-harvat tasograafit , tasograafit, joiden puunleveys on enintään 3, ja graafit, joiden aste on 4 tai vähemmän ja jotka sisältävät timantin in aligraafina tai eivät ole 4-särmäisiä graafisia [4] [8] [9] .

Erityisesti graafit, jotka voidaan pelkistää tyhjäksi graafiksi poistamalla vain asteen kaksi tai sitä pienemmät pisteet ( 2-degeneroituneet tasograafit), sisältävät sekä ulkotason graafit että rinnakkaissarjakuvaajat . Ulompitasoisille kuvaajille on kuitenkin mahdollista rakentaa suoraan kokonaisluku Fari-upotus perustuen yksikköympyrän äärettömien osajoukkojen olemassaoloon, jossa kaikki etäisyydet ovat rationaalisia [10] .

Lisäksi kokonaisluku Fari-upotukset tunnetaan jokaiselle viidelle säännölliselle polyhedralle [3] .

Aiheeseen liittyviä hypoteeseja

Kleberin [11] esittämä vahvempi versio Harbortin oletuksesta olettaa, että millä tahansa tasograafilla on tasokuvio, jossa kärkikoordinaatit ja reunan pituudet ovat kokonaislukuja [12] . Tämän tiedetään pätevän 3-säännöllisille kaavioille [13] , graafiille, joiden maksimiaste on 4, mutta jotka eivät ole 4-säännöllisiä [14] , ja tasomaisille 3-puille [14] .

Toinen geometrian avoin ongelma on Erdős-Ulam-ongelma , joka koskee tiheiden osajoukkojen olemassaoloa tasossa, jossa kaikki etäisyydet ovat rationaalilukuja . Jos tällainen osajoukko olisi olemassa, se muodostaisi yleisen pistejoukon , jota voitaisiin käyttää kaikkien tasograafien piirtämiseen rationaalisilla reunapituuksilla (ja siten asianmukaisen skaalauksen jälkeen kokonaislukujen reunanpituuksilla). Ulam kuitenkin arveli, että tiheitä joukkoja, joilla on rationaaliset etäisyydet, ei ole olemassa [15] . Erdős-Anningin lauseen mukaan ei ole olemassa äärettömiä ei-kollineaaristen pisteiden joukkoja, joissa kaikki etäisyydet ovat kokonaislukuja. Tämä ei sulje pois joukkoja, joissa kaikki etäisyydet ovat rationaalisia, mutta tästä seuraa, että missä tahansa sellaisessa joukossa rationaalisten etäisyyksien nimittäjät voivat olla mielivaltaisen suuria.

Katso myös

Muistiinpanot

  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. ↑ 12. su , 2013 .
  5. ↑ Brass, Moser, Pach, 2005 , s. 250.
  6. ↑ Almering, 1963 , s. 192-199.
  7. ↑ Berry, 1992 , s. 391-398.
  8. ↑ Biedl, 2011 .
  9. ↑ Sun, 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.

Kirjallisuus