Universaali pistesarja

Ratkaisemattomat matematiikan ongelmat : Onko tasograafien universaalien pistejoukkojen koko subquadratinen?

Universaali pistejoukko luokkaa n on joukko S pisteitä euklidisessa tasossa , jolla on ominaisuus, että millä tahansa tasograafilla , jossa on n pistettä, on suorareunakuvio , jossa kaikki kärjet sijaitsevat S :n pisteissä .

Yleisen pistejoukon mittojen rajoitukset

Jos n on enintään kymmenen, on olemassa universaali pistejoukko, jossa on täsmälleen n pistettä, mutta kaikille n :lle  vaaditaan 15 lisäpistettä [1] .

Jotkut kirjoittajat ovat osoittaneet, että kokonaislukuhilan osajoukko, jonka koko on O ( n ) ×  O ( n ), on universaali. Erityisesti Freysix, Pach ja Pollak [2] osoittivat, että hila (2 n  - 3) × ( n  - 1) on universaali, kun taas Schneider [3] pelkisti hilan ( n  - 1) × ( n  - 1) kolmion osajoukkoon ), jossa on n 2 /2 −  O ( n ) pistettä. Muuttamalla Freysixin, Pachin ja Schneiderin menetelmää Brandenburg [4] löysi minkä tahansa tasograafin upottamisen hilan kolmiomaiseen osajoukkoon, joka sisältää 4 n 2 /9 pistettä. Suorakulmaisen hilan muodossa olevan universaalin pistejoukon koon on oltava vähintään n /3 ×  n /3 [5] , mutta tämä ei sulje pois mahdollisuutta, että on olemassa pienempi universaali muiden tyyppisten pisteiden joukko. . Pienimmät tunnetut universaalit pistejoukot eivät perustu hilakoihin, vaan ne rakennetaan superskeemoista ( permutaatiot , jotka sisältävät kaikki tietyn kokoiset permutaatiot Tällä tavalla konstruoitujen universaalien pistejoukkojen koko on n 2 /4 −  O ( n ) [6] .

Freysix, Pach ja Pollack [2] osoittivat ensimmäisen ei-triviaalin alarajan universaalille pistejoukolle muodossa n  + Ω(√ n ), kun taas Chrobak ja Karloff [7] osoittivat, että universaalin pistejoukon täytyy sisältää vähintään 1,098 n  −  o ( n ) pistettä. Kurowski [8] ehdotti vielä vahvempaa rajaa 1,235 n  −  o ( n ), joka on edelleen paras alaraja [9] .

Tunnettujen lineaaristen rajojen ja neliöllisten ylärajojen välisen aukon sulkeminen on edelleen avoin ongelma [10] .

Graafeiden erikoisluokat

Tasograafien alaluokissa voi yleensä olla pienempiä universaaleja joukkoja (pistejoukkoja, jotka mahdollistavat kaikkien graafien piirtämisen, joissa on n pistettä, joilla on suorat reunat alaluokassa) kuin kaikkien tasograafien täysluokka, ja monissa tapauksissa on olemassa universaaleja pisteitä. joukot, joiden tarkkuus on n pistettä. On esimerkiksi helppo nähdä, että mikä tahansa n pisteen joukko kuperassa paikassa (jotka toimivat kuperan monikulmion kärkeinä ) on universaali n pisteen ulkotasograafille ja erityisesti puille . Vähemmän ilmeistä on, että mikä tahansa n pisteen joukko yleisessä sijainnissa (ei kolmea ole samalla viivalla) pysyy universaalina ulompitasoisille kuvaajille [11] .

Tasograafit, jotka voidaan jakaa sisäkkäisiksi silmukoiksi ja tasograafit, joilla on rajoitettu polunleveys , sisältävät universaalin joukon pisteitä, joiden koko on lähes lineaarinen [12] [6] . Tasomaisilla 3-puilla on yleiset pistejoukot, joiden koko on O ( n 5/3 ). Sama raja pätee rinnakkaisille peräkkäisille kuvaajille [13] .

Muut piirustustyylit

Kuten suorien reunojen graafin piirtämisessä, universaaleja pistejoukkoja on tutkittu muille tyyleille. Useimmissa tapauksissa on olemassa universaaleja pistejoukkoja, joissa on täsmälleen n pistettä, ja ne perustuvat topologiseen kirjan upotukseen , jossa kärjet sijaitsevat tason suoralla ja reunat piirretään käyrinä, jotka leikkaavat tämän. rivi enintään kerran. Esimerkiksi mikä tahansa n kollineaarisen pisteen joukko on universaali kaaridiagrammille , jossa jokainen reuna on esitetty joko yhtenä puoliympyränä tai tasaisena kaarena, joka muodostuu kahdesta puoliympyrästä [14] .

Voidaan osoittaa, että käyttämällä tällaista järjestelyä mikä tahansa kupera käyrä tasossa sisältää n pisteen osajoukon, mikä on universaali polyline -kuvioissa , joissa on enintään yksi katko per reuna [15] . Tämä joukko sisältää vain kuvion kärjet, ei keskeytyspisteitä. Tunnetaan suurempia joukkoja, joita voidaan käyttää katkoviivoilla piirtämiseen, joissa kärjet ja kaikki taitepisteet ovat joukon pisteitä [16] .

Muistiinpanot

  1. ↑ Cardinal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach ja Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandenburg, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak ja Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . Valiant (1981 ) antoi aiemmin tasograafisissa piirustuksissa vaaditun hilan koolle heikomman neliöllisen rajan.
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) väitti, että Kurowskin todiste oli väärä, mutta myöhemmin (keskustelun jälkeen Gene Cardinalin kanssa) perui väitteensä. Katso Kurowskin todistus selityksen saamiseksi. Arkistoitu 15. maaliskuuta 2017 Wayback Machinessa .
  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 .

Kirjallisuus