Set universal de puncte

Probleme nerezolvate în matematică : este dimensiunea seturilor universale de puncte ale graficelor plane subpatratică?

O mulțime universală de puncte de ordin n este o mulțime S de puncte în planul euclidian cu proprietatea că orice graf plan cu n vârfuri are un model de muchii drepte în care toate vârfurile sunt situate în punctele din S .

Limite ale dimensiunilor setului universal de puncte

Dacă n este cel mult zece, există un set universal de puncte care are exact n puncte, dar pentru toate n  ≥ sunt necesare 15 puncte suplimentare [1] .

Unii autori au arătat că o submulțime a unei rețele întregi de dimensiunea O ( n ) ×  O ( n ) este universală. În special, Freysix, Pach și Pollak [2] au arătat că rețeaua (2 n  − 3) × ( n  − 1) este universală, în timp ce Schneider [3] a redus rețeaua ( n  − 1) × ( n  − 1) la o submulţime triunghiulară ) cu n 2 /2 −  O ( n ) puncte. Prin modificarea metodei lui Freysix, Pach și Schneider, Brandenburg [4] a găsit o încorporare a oricărui graf plan într-o submulțime triunghiulară a unei rețele care conține 4 n 2 /9 puncte. Un set universal de puncte sub forma unei rețele dreptunghiulare trebuie să aibă o dimensiune de cel puțin n /3 ×  n /3 [5] , dar acest lucru nu exclude posibilitatea existenței unui set universal mai mic de puncte de alte tipuri. . Cele mai mici seturi de puncte universale cunoscute nu se bazează pe rețele, ci sunt construite din superscheme ( permutări care conțin toate imaginile permutărilor de o dimensiune dată). Mulțimile de puncte universale construite în acest fel au dimensiunea n 2 /4 −  O ( n ) [6] .

Freysix, Pach și Pollack [2] au demonstrat prima limită inferioară netrivială a mărimii unei mulțimi universale de puncte sub forma n  + Ω(√ n ), în timp ce Chrobak și Karloff [7] au arătat că setul universal de puncte trebuie conțin cel puțin 1,098 n  −  o ( n ) puncte. Kurowski [8] a propus o limită și mai puternică 1.235 n  −  o ( n ), care rămâne cea mai bună limită inferioară [9] .

Închiderea decalajului dintre limitele liniare cunoscute și limitele superioare pătratice rămâne o problemă deschisă [10] .

Clase speciale de grafice

Subclasele de grafuri plane pot avea, în general, seturi universale mai mici (mulțimi de puncte care permit desenarea tuturor grafurilor cu n vârfuri cu muchii directe în subclasă) decât clasa completă a tuturor grafurilor plane și, în multe cazuri, există puncte universale. mulţimi care au precizie n puncte. De exemplu, este ușor de observat că orice set de n puncte în poziția convexă (care servesc ca vârfuri ale unui poligon convex) este universal pentru graficele planare exterioare cu n vârfuri și în special pentru arbori . Mai puțin evident, orice set de n puncte în poziție generală (nici trei nu se află pe aceeași linie) rămâne universal pentru graficele planare exterioare [11] .

Graficele plane care pot fi împărțite în bucle imbricate și graficele plane cu lățime de cale limitată au un set universal de puncte de dimensiune aproape liniară [12] [6] . Arborii planari 3 au seturi universale de puncte de dimensiunea O ( n 5/3 ). Aceeași limită este valabilă pentru graficele paralel-secvențiale [13] .

Alte stiluri de desen

Ca și în cazul desenului grafic cu margini drepte, seturile de puncte universale au fost studiate pentru alte stiluri. În cele mai multe dintre aceste cazuri, există seturi universale de puncte care au exact n puncte și se bazează pe o înglobare topologică de carte , în care vârfurile sunt situate pe o linie în plan, iar muchiile sunt desenate ca curbe care intersectează aceasta. linie cel mult o dată. De exemplu, orice set de n puncte coliniare este universală pentru o diagramă cu arc , în care fiecare muchie este reprezentată fie ca un singur semicerc , fie ca o curbă netedă formată din două semicercuri [14] .

Se poate demonstra că folosind un astfel de aranjament, orice curbă convexă din plan conține un subset de n puncte, care este universal pentru modelele de polilinii cu cel mult o întrerupere pe muchie [15] . Acest set conține doar vârfurile modelului, nu punctele de întrerupere. Se cunosc seturi mai mari care pot fi folosite pentru desene folosind linii întrerupte, în care vârfurile și toate punctele de întrerupere sunt puncte ale mulțimii [16] .

Note

  1. ↑ Cardinal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach și Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandenburg, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak și Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . O limită pătratică mai slabă a dimensiunii rețelei necesară pentru desenele grafice plane a fost dată anterior de Valiant (1981 ).
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) a susținut că dovada lui Kurowski a fost greșită, dar mai târziu (după o discuție cu Gene Cardinal) și-a retras afirmația. Vezi dovada lui Kurowski pentru o explicație Arhivată 15 martie 2017 la Wayback Machine .
  10. ↑ Demaine, O'Rourke, 2002–2012 ; Brandenburg, Eppstein, Goodrich, Kobourov, 2003 ; Mohar, 2007 .
  11. ↑ Gritzmann, Mohar, Pach, Pollack, 1991 .
  12. ↑ Angelini, Di Battista, Kaufmann, Mchedlidze, 2012 .
  13. ↑ Fulek, Toth, 2013 .
  14. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  15. ↑ Everett, Lazard, Liotta, Wismath, 2010 .
  16. ↑ Dujmovic, Evans, Lazard, Lenhart, 2013 .

Literatură