Zarankievitšin ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. lokakuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Zarankiewicz -tehtävä, matematiikan avoin ongelma, kysyy suurimmasta mahdollisesta reunojen määrästä kaksiosaisessa graafissa , jossa on tietty määrä pisteitä, mutta joka ei sisällä tietyn kokoisia täydellisiä kaksiosaisia ​​aligraafia [1] . Ongelma kuuluu äärimmäisen graafisen teorian alaan , kombinatoriikan haaraan , ja se on nimetty puolalaisen matemaatikon Kazimir Zarankiewiczin , joka kuvaili joitakin tämän ongelman erikoistapauksia vuonna 1951 [2] .

Tamas Kovarin, Vera T. Sosin ja Pal Turanin mukaan nimetty Kovari–Sos–Turan-lause antaa Zarankievitšin ongelman ylärajan . On todistettu, että jos jollakin kielletyn kaksiosaisen graafin osista on korkeintaan kolme kärkeä, tämä rajoitus poikkeaa vain vakiokertoimella todellisesta arvosta. Suuremmille kielletyille osagraafille tiedetään paremmat raja-arvot, ja oletetaan, että ne ovat tiukkoja. Kovari–Sos–Turan-lauseen sovellukset sisältävät arvion erityyppisten geometristen objektien esiintymisten määrästä kombinatorisessa geometriassa .

Ongelman selvitys

Kaksiosainen graafi G  = ( U ,  V ,  E ) koostuu kahdesta disjunktisesta joukosta pisteitä U ja V ja joukosta reunoja, joista kukin yhdistää kärjen U :sta V :n kärkeen . Kaksi reunaa ei voi yhdistää samaa kärkiparia. Täydellinen kaksiosainen graafi on kaksiosainen graafi, jossa kukin pistepari (toinen U :sta, toinen V :stä ) on yhdistetty reunalla. Täydellinen kaksiosainen graafi, jossa U :lla on s pistettä ja V :llä t pistettä, merkitään K s , t . Jos G  = ( U ,  V ,  E ) on kaksiosainen ja U : n pisteistä on osajoukkoja ja V :n t pisteitä siten, että kaikki näiden kahden joukon pisteet ovat yhteydessä toisiinsa, niin nämä kärjet muodostavat generoidun muodon aligraafin K s , t . (Tässä s:n ja t :n järjestys on merkitsevä – kärkijoukon s tulee kuulua U :lle ja kärkijoukon t kuulua V :lle .)

Zarankievich-funktio z ( m ,  n ;  s ,  t ) ilmaisee maksimaalisen reunojen määrän kaksiosaisessa graafissa G  = ( U ,  V ,  E ), jolle | U | =  m ja | v | =  n joka ei sisällä muotoa K s , t olevaa aligraafia . Tapaus z ( n ,  n ;  t ,  t ) on kirjoitettu z ( n ;  t ) lyhyyden vuoksi . Zarankievich-ongelma herättää kysymyksen Zarankievich-funktion kaavasta tai (jos sellaista ei voida määrittää) kasvunopeuden z ( n ;  t ) tiukoista asymptoottisista rajoista olettaen, että t on kiinteä ja n pyrkii ääretön.

Kun s = t = 2 , tämä ongelma osuu samaan ongelmaan solujen löytämisessä, joiden ympärysmitta on kuusi. Zarankiewicz-ongelma, solut ja äärelliset geometriat ovat vahvasti yhteydessä toisiinsa [3] .

Sama ongelma voidaan muotoilla digitaalisen geometrian avulla . Kaksiosaisen graafin G  = ( U ,  V ,  E ) mahdolliset reunat voidaan piirtää suorakulmion pisteiksi | U | × | v | kokonaislukuhilassa , ja täydellinen alikuvaaja on rivien ja sarakkeiden joukko tässä suorakulmiossa, joka sisältää kaikki pisteet. Tällöin z ( m ,  n ;  s ,  t ) merkitsee pisteiden maksimimäärää, joka voidaan sijoittaa m  ×  n hilaan siten, että mikään rivien ja sarakkeiden osajoukko ei muodosta täydellistä s  ×  t hilaa [4] . Vaihtoehtoinen ja vastaava määritelmä, että z ( m ,  n ;  s ,  t ) on pienin kokonaisluku k siten, että m × n  (  0,1) -matriisissa , joissa on k  + 1 yksi, täytyy olla s riviä ja t saraketta siten, että vastaava s × t -alimatriisi koostuu yksinomaan ykkösistä.

Esimerkkejä

Luku z ( n , 2) vastaa reunojen maksimimäärää kaksiosaisessa graafissa, jossa on n kärkeä kussakin osassa, jossa ei ole 4 pituisia syklejä (sen ympärysmitta on vähintään kuusi). Sitten z (2, 2) = 3 (saavutetaan kolmen kaaren polulla) ja z (3, 2) = 6 ( kuusikulmio ).

Ongelman alkuperäisessä muotoilussa Zarankievitš esitti kysymyksen z ( n ; 3) arvoista n  = 4, 5 ja 6. Pian Vaclav Sierpinski vastasi: z (4; 3) = 13, z ( 5; 3) = 20 ja z (6; 3) = 26 [4] . Tapaus z (4; 3) on suhteellisen yksinkertainen - kaksiosainen graafi, jossa on 13 reunaa ja neljä kärkeä kussakin osassa, joka ei sisällä K 3,3 -aligraafia, voidaan saada lisäämällä pitkä diagonaali kuutiograafiin . Kääntäen, jos kaksiosaisessa graafissa, jossa on 14 reunaa, on neljä kärkeä kussakin osassa, niin kahdella pisteellä kummallakin puolella on oltava aste neljä. Kun nämä neljä kärkeä ja niihin kohdistuvat 12 reunaa poistetaan, jää ei-tyhjä joukko reunoja, joista mikä tahansa yhdessä neljän poistetun kärjen kanssa muodostaa aligraafin K 3,3 .

Ylärajat

Tomasz Kovari, Vera T. Sos ja Pal Turan määrittelivät seuraavan ylärajan pian ongelman asettamisen jälkeen [5] , ja tämä raja tuli tunnetuksi Kovari–Sos–Turan-lauseena :

Itse asiassa Kovari, Sos ja Turan osoittivat vastaavan epäyhtälön z :lle ( n ;  t ), mutta pian sen jälkeen Hilten-Cavallius huomasi, että täsmälleen samoilla argumenteilla voidaan todistaa yleinen tapaus [6] . Stefan Znam [7] antoi parannuksen vakiotekijään kaavan oikealla puolella tapaukselle z ( n ;  t ) :

Jos korjaamme s :n ja t :n käyttämällä "O"-merkintää, voimme kirjoittaa nämä kaavat asymptoottisemmin uudelleen seuraavasti

ja

Alarajat

Kun t  = 2 ja äärettömälle määrälle n: n arvoja , kaksiosainen graafi, jossa on n kärkeä jokaisessa osassa ja Ω( n 3/2 ) reunat ilman K 2,2 :ta , voidaan saada äärellisen projektiivin Levi-graafina taso , n pisteen ja suoran järjestelmä, jossa jokainen kaksi pistettä kuuluu yhdelle suoralle ja jokainen kaksi suoraa leikkaa yhdessä pisteessä. Tästä geometriasta muodostetun graafin toisella puolella on kärki jokaiselle pisteelle ja toiselle puolelle jokaiselle suoralle. Projektiiviset tasot, jotka on määritelty kertaluvun p äärellisen kentän yli, johtavat K 2,2 -vapaisiin graafisiin n  =  p 2  +  p  + 1 ja ( p 2  +  p  + 1) ( p  + 1) -reunoihin. Esimerkiksi Fano-tason Lévy-graafi antaa Heawood-graafin , kaksiosaisen graafin, jossa on seitsemän kärkeä kussakin osassa ja jossa on 21 reunaa eikä 4-sykliä, mikä osoittaa, että z (7; 2) ≥ 21. tämän perheesimerkin antama Zarankiewicz-funktio vastaa I. Reimanin osoittamaa ylärajaa [8] . Siten t  = 2:lle ja n: n arvoille, joille tämä konstruktio voidaan suorittaa, saamme tarkan vastauksen Zarankievich-ongelmaan. Muille n:n arvoille ala- ja ylärajasta seuraa, että asymptoottisesti [9]

Yleisemmässä tapauksessa [10 ]

Kun t  = 3 ja äärettömälle määrälle arvoja n , on mahdollista rakentaa kaksiosaisia ​​graafia, joissa on n kärkeä jokaisessa osassa ja Ω( n 5/3 ) -pisteitä, joissa ei ole aligraafia K 3,3 , myös äärellinen geometria , jos tarkastelemme pisteitä ja palloja (valitsemalla huolellisesti kiinteä säde) kolmiulotteisessa äärellisessä affiinissa avaruudessa. Tässä tapauksessa reunat edustavat pisteiden ja pallojen tuloa [11] .

Oletuksena oli, että

kaikille t :n vakioarvoille , mutta nyt on olemassa vahvistus vain t  = 2:lle ja t  = 3:lle yllä olevien rakenteiden mukaisesti [12] . Tiukat rajat tunnetaan pareille ( s ,  t ), joiden kokoero on suuri (erityisesti s  ≥ ( t  − 1)!). Näille pariskunnille

mikä tekee yllä olevasta hypoteesista uskottavan [13] . .

Ei-kaksiosaiset graafit

Vakiokertoimeen asti z ( n ;  t ) rajoittaa myös sellaisen n - kärkigraafin (ei välttämättä kaksiosaisen) reunojen määrää, joka ei sisällä K t , t :tä aligraafina. Yksi tapa, kaksiosainen graafi, jossa on z ( n ;  t ) reunaa ja n pistettä kussakin osassa, voidaan pelkistää graafiksi, jossa on n pistettä ja z ( n ;  t )/4 reunaa valitsemalla n / 2 pistettä satunnaisesti kokonaismäärästä graafin kärkien lukumäärä . Päinvastaisessa suunnassa n -pisteinen graafi, jossa ei ole aligraafia K t , t , voidaan muuntaa kaksiosaiseksi graafiksi, jossa on n kärkeä kussakin osassa ja kaksinkertainen määrä reunoja, joka ei silti sisällä K t , t aligraafina, rakentamalla sen kaksiosainen kaksoiskansi [14] .

Sovellukset

Kovari–Cos–Turan-lausetta käytetään kombinatorisessa geometriassa rajoittamaan esiintymien määrää erityyppisten geometristen objektien välillä. Yksinkertaisena esimerkkinä voidaan todeta, että euklidisen tason n pisteen ja m suoran joukko ei sisällä arvoa K 2,2 , joten Kovari–Cos–Turan-lauseen mukaan tällä konfiguraatiolla on enintään O ( nm 1/2  +  m ) piste -linjan ilmaantuvuus. Tämä raja on lähellä, jos m on paljon suurempi kuin n , mutta lähes samalle m :lle ja n :lle Szemedi-Trotter-lause antaa tiukemman rajan O ( n 2/3 m 2/3  +  n  +  m ). Szemeredi-Trotter-lause voidaan kuitenkin todistaa jakamalla pisteet ja suorat osajoukkoihin, joille Kovari-Sos-Turan-rajat ovat tiukat [15] .

Katso myös

Muistiinpanot

  1. ↑ Bollobás, 2004 , s. 309–326.
  2. ↑ Zarankiewicz, 1951 , s. 301.
  3. ↑ Tamás Héger, Tamás Szőnyi, Gábor Damásdi. Zarankiewicz-ongelma, häkit ja geometriat . Omistettu András Gácsin ja István Reimanin  (englanniksi) muistolle (pdf) . Budapestin yliopisto (19. maaliskuuta 2013) . Haettu 25. toukokuuta 2017. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  4. ↑ 1 2 Sierpiński, 1951 , s. 173-174.
  5. ↑ Kővári et al, 1954 , s. 50–57.
  6. ↑ Hyltén-Cavallius, 1958 , s. 59–65.
  7. ↑ Znam, 1963 , s. 81–84.
  8. ↑ Reiman, 1958 , s. 269-273.
  9. ↑ Bollobás, 2004 , s. 313, seuraus 2.7.
  10. ↑ Furedi, 1996 , s. 141-144.
  11. ↑ Brown, 1966 , s. 281-285.
  12. ↑ Bollobás, 2004 , s. 312, olettamus 15.
  13. ↑ Alon et ai, 1999 , s. 280-290.
  14. ↑ Bollobás (2004 ), Lause 2.3, s. 310.
  15. ↑ Matousek, 2002 , s. 65–68.

Kirjallisuus