Ipoteza lui Harbourt

Probleme nerezolvate la matematică : orice graf plan are o încorporare Fari întreg?

Conjectura lui Harbort afirmă că orice graf plan are o reprezentare plană , în care fiecare muchie este un segment de lungime întreagă [1] [2] [3] . Această presupunere este numită după Heiko Harbort și (dacă este adevărată) ar întări teorema lui Fari privind existența unui desen cu muchii rectilinii pentru orice graf plan. Din acest motiv, desenarea unui grafic cu lungimi de muchii întregi este cunoscută și sub denumirea de încorporare Fari a întregului [4] . În ciuda numeroaselor studii în această direcție, ipoteza rămâne deschisă [5] .

Clase speciale de grafice

Deși nu se știe dacă conjectura lui Harbort este adevărată pentru toate grafurile plane, a fost dovedită pentru unele tipuri speciale de grafuri plane.

Una dintre clasele de grafice care au o încorporare Fari întreg este graficele care pot fi reduse la graficul nul printr-o succesiune de operații de două feluri:

Pentru un astfel de grafic, o încorporare Fari rațională poate fi construită în mod incremental prin inversarea procesului de îndepărtare, folosind faptul că mulțimea de puncte care se află la o distanță rațională de două puncte date este densă în plan și că dacă trei puncte sunt la o distanță rațională de la o pereche și la o distanță, egală cu rădăcinile pătrate ale numerelor raționale din celelalte două perechi, atunci punctele aflate la distanță rațională de toate cele trei puncte sunt dense pe plan [6] [7] . Distanțele dintr-un astfel de atașament pot fi făcute întregi prin scalare cu un factor adecvat. Pe baza acestei construcții, se știe că următoarele grafice au înglobări Fari întregi: grafice plane bipartite , grafice plane (2,1)-sparse , grafice plane cu lățimea arborelui de cel mult 3 și grafice de gradul 4 sau mai puțin care conțin fie un romb în subgraf sau nu sunt grafice conectate cu 4 muchii [4] [8] [9] .

În special, graficele care pot fi reduse la graficul gol prin eliminarea numai vârfurilor de gradul doi sau mai puțin ( grafice plane cu 2 degenerate ) includ atât grafice planare exterioare, cât și grafice paralele - seriale . Totuși, pentru graficele planare exterioare este posibil să se construiască direct o încorporare Fari întreg pe baza existenței unor submulțimi infinite ale cercului unitar în care toate distanțele sunt raționale [10] .

În plus, înglobările întregi Fari sunt cunoscute pentru fiecare dintre cele cinci poliedre regulate [3] .

Ipoteze înrudite

O versiune mai puternică a conjecturii lui Harbort, prezentată de Kleber [11] , presupune că orice graf plan are un model plan în care coordonatele vârfurilor și lungimile muchiilor sunt numere întregi [12] . Se știe că acest lucru este valabil pentru graficele 3-regulate [13] , pentru grafurile care au un grad maxim de 4, dar nu sunt 4-regulari [14] , și pentru 3-arborele planari [14] .

O altă problemă deschisă în geometrie este problema Erdős-Ulam , referitoare la existența unor submulțimi dense în planul în care toate distanțele sunt numere raționale . Dacă ar exista o astfel de submulțime, ar forma un set universal de puncte care ar putea fi folosit pentru a desena toate graficele plane cu lungimi raționale de muchii (și, prin urmare, după o scalare corespunzătoare, lungimi de muchii întregi). Cu toate acestea, Ulam a presupus că mulțimile dense cu distanțe raționale nu există [15] . Conform teoremei Erdős-Anning, nu există seturi infinite de puncte necoliniare unde toate distanțele sunt numere întregi. Acest lucru nu exclude existența mulțimilor în care toate distanțele sunt raționale, dar rezultă că în orice astfel de mulțime numitorii distanțelor raționale pot fi arbitrar mari.

Vezi și

Note

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

Literatură