Harborths gissning
Har varje plan graf en integrerad Fáry-inbäddning?
Inom matematiken säger Harborths gissning att varje plan graf har en plan ritning där varje kant är ett rakt segment av heltalslängd . Denna gissning är uppkallad efter Heiko Harborth , och (om sann) skulle stärka Fárys sats om förekomsten av rätlinjeritningar för varje plan graf. Av denna anledning är en ritning med heltalskantlängder också känd som en integrerad Fáry-inbäddning . Trots mycket efterföljande forskning förblir Harborths gissningar olösta.
Särskilda klasser av grafer
Även om Harborths gissningar inte är känd för att vara sanna för alla plana grafer, har det bevisats för flera speciella typer av plana grafer.
En klass av grafer som har integrerade Fáry-inbäddningar är de grafer som kan reduceras till den tomma grafen genom en sekvens av operationer av två typer:
- Ta bort en spets av högst två grader.
- Ersätter en vertex av grad tre med en kant mellan två av dess grannar. (Om en sådan kant redan finns, kan toppen av tre grader tas bort utan att lägga till ytterligare en kant mellan dess grannar.)
För en sådan graf kan en rationell Fáry-inbäddning konstrueras inkrementellt genom att vända denna borttagningsprocess, med hjälp av fakta att den uppsättning punkter som ligger på ett rationellt avstånd från två givna punkter är täta i planet, och att om tre punkter har rationell avstånd mellan ett par och kvadratrot-av-rationellt avstånd mellan de andra två paren, då är punkterna på rationella avstånd från alla tre igen täta i planet. Avstånden i en sådan inbäddning kan göras till heltal genom att skala inbäddningen med en lämplig faktor. Baserat på denna konstruktion inkluderar de grafer som är kända för att ha integrerade Fáry-inbäddningar de tvådelade plana graferna, ( 2,1)-glesa plana grafer, plana grafer med högst 3 trädbredder och grafer med högst fyra grader som antingen innehåller en diamantsubgraf eller inte är 4-kantsanslutna .
Särskilt de grafer som kan reduceras till den tomma grafen genom att endast ta bort hörn av grad två (de 2-degenererade plana graferna) inkluderar både de yttre planära graferna och serieparallella graferna . Men för de yttre planargraferna är en mer direkt konstruktion av integrerade Fáry-inbäddningar möjlig, baserat på förekomsten av oändliga delmängder av enhetscirkeln där alla avstånd är rationella.
Dessutom är integrerade Fáry-inbäddningar kända för var och en av de fem platoniska soliderna .
Relaterade gissningar
En starkare version av Harborths gissning, ställd av Kleber (2008) , frågar sig om varje plan graf har en plan ritning där vertexkoordinaterna såväl som kantlängderna är heltal. Det är känt att det stämmer för 3-regelbundna grafer , för grafer som har maximal grad 4 men inte är 4-regelbundna, och för plana 3-träd .
Ett annat olöst problem inom geometrin, Erdős–Ulam-problemet , gäller förekomsten av täta delmängder av planet där alla avstånd är rationella tal . Om en sådan delmängd fanns skulle den bilda en universell punktuppsättning som skulle kunna användas för att rita alla plana grafer med rationella kantlängder (och därför, efter att ha skalat dem på lämpligt sätt, med heltalskantlängder). Ulam förmodade dock att täta rationella avståndsuppsättningar inte existerar. Enligt Erdős–Anning-satsen kan oändliga icke-kollinjära punktuppsättningar där alla avstånd är heltal inte existera. Detta utesluter inte att det finns mängder med alla avstånd rationella, men det innebär att i varje sådan mängd måste nämnarna för de rationella avstånden växa godtyckligt stora.
Se även
- Heltalstriangel , en integrerad Fáry-inbäddning av triangelgrafen
- Tändsticksgraf , en graf som kan ritas plant med alla kantlängder lika med 1
- Erdős–Diophantine graph , en komplett graf med heltalsavstånd som inte kan utökas till en större komplett graf med samma egenskap
- Euler-tegel , ett problem för realisering av heltal avstånd i tre dimensioner