Univerzális pontkészlet

Megoldatlan problémák a matematikában : A síkgráfok univerzális ponthalmazainak mérete szubquadratikus?

Az n rendű univerzális ponthalmaz az euklideszi síkban lévő S pontok halmaza , azzal a tulajdonsággal, hogy bármely n csúcsú síkgráfnak van egy egyenes élmintája, amelyben minden csúcs S pontokban helyezkedik el .

Az univerzális pontkészlet méreteinek korlátai

Ha n legfeljebb tíz, akkor van egy univerzális ponthalmaz, amelynek pontosan n pontja van, de minden n -hez  ≥ 15 további pont szükséges [1] .

Egyes szerzők kimutatták, hogy egy O ( n ) ×  O ( n ) méretű egész rács részhalmaza univerzális. Konkrétan Freysix, Pach és Pollak [2] kimutatta, hogy a (2 n  − 3) × ( n  − 1) rács univerzális, míg Schneider [3] redukálta a rácsot ( n  − 1) × ( n  − 1). háromszög részhalmazhoz ) n 2 /2 −  O ( n ) ponttal. Freysix, Pach és Schneider módszerének módosításával Brandenburg [4] bármely síkgráf beágyazódását találta a rács 4 n 2 /9 pontot tartalmazó háromszög részhalmazába. Egy téglalap alakú rács alakú univerzális ponthalmaznak legalább n /3 ×  n /3 méretűnek kell lennie [5] , de ez nem zárja ki egy kisebb, más típusú univerzális ponthalmaz létezését. . A legkisebb ismert univerzális ponthalmazok nem rácsokon alapulnak, hanem szupersémákból épülnek fel ( az adott méretű permutációk összes képét tartalmazó permutációk ). Az így felépített univerzális ponthalmazok mérete n 2 /4 −  O ( n ) [6] .

Freysix, Pach és Pollack [2] bizonyította az első nem triviális alsó korlátot egy n  + Ω(√ n ) univerzális ponthalmaz méretére vonatkozóan, míg Chrobak és Karloff [7] kimutatta, hogy az univerzális ponthalmaznak legalább 1,098 n  −  o ( n ) pontot tartalmaznak. Kurowski [8] még erősebb 1,235 n  −  o ( n ) korlátot javasolt, amely továbbra is a legjobb alsó korlát [9] .

Az ismert lineáris határok és a másodfokú felső határok közötti rés bezárása továbbra is nyitott probléma marad [10] .

A gráfok speciális osztályai

A síkgráfok alosztályai általában kisebb univerzális halmazokkal rendelkezhetnek (ponthalmazok, amelyek lehetővé teszik az összes n csúcsú, közvetlen élű gráf megrajzolását az alosztályban), mint az összes síkgráf teljes osztálya, és sok esetben vannak univerzális pontok. n pontosságú halmazok . Például könnyen belátható, hogy az konvex pozícióban lévő bármely n pont halmaza (amelyek egy konvex sokszög csúcsaiként szolgálnak) univerzális n csúcsú külső sík gráfokhoz , és különösen fákhoz . Kevésbé nyilvánvaló, hogy bármely általános helyzetben lévő n pont halmaza (nincs három ugyanazon az egyenesen) univerzális marad a síkbeli gráfok számára [11] .

A beágyazott hurokra bontható síkgráfok és a korlátozott útvonalszélességű síkgráfok szinte lineáris méretű univerzális pontkészlettel rendelkeznek [12] [6] . A sík 3-fák univerzális O méretű pontkészlettel rendelkeznek ( n 5/3 ). Ugyanez a határ érvényes a párhuzamos-szekvenciális gráfokra [13] .

Egyéb rajzstílusok

Az egyenes élű gráfrajzhoz hasonlóan más stílusokhoz is tanulmányozták az univerzális ponthalmazokat. A legtöbb esetben vannak olyan univerzális ponthalmazok, amelyek pontosan n ponttal rendelkeznek, és egy topológiai könyvbeágyazáson alapulnak , amelyben a csúcsok a síkban egy egyenesen helyezkednek el, és az élek görbékként vannak megrajzolva, amelyek ezt metszik. sort legfeljebb egyszer. Például bármely n kollineáris pontból álló halmaz univerzális egy olyan ívdiagramhoz , amelyben minden él egyetlen félkörként vagy két félkörből alkotott sima görbeként van ábrázolva [14] .

Megmutatható, hogy egy ilyen elrendezést használva a síkban lévő bármely konvex görbe n pontból álló részhalmazt tartalmaz, ami univerzális olyan vonallánc minták esetén, amelyek élenként legfeljebb egy törést tartalmaznak [15] . Ez a halmaz csak a minta csúcsait tartalmazza, a töréspontokat nem. Ismertek nagyobb halmazok, amelyek szaggatott vonalakat használó rajzokhoz használhatók, amelyekben a csúcsok és az összes töréspont a halmaz pontjai [16] .

Jegyzetek

  1. ↑ Cardinal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach és Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandenburg, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak és Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . Valiant (1981 ) korábban adott egy gyengébb másodfokú korlátot a síkgráf-rajzokhoz szükséges rács méretére .
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) azzal érvelt, hogy Kurowski bizonyítása téves, de később (a Gene Cardinallal folytatott megbeszélés után) visszavonta állítását. Magyarázatért lásd Kurowski bizonyítékát. Archiválva : 2017. március 15. a Wayback Machine -nél .
  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, Tóth, 2013 .
  14. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  15. ↑ Everett, Lazard, Liotta, Wismath, 2010 .
  16. ↑ Dujmovic, Evans, Lazard, Lenhart, 2013 .

Irodalom