Zarankievics problémája

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 10-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Zarankiewicz-probléma , a matematika nyitott problémája, azt a kérdést teszi fel, hogy egy adott számú csúcsú, de adott méretű teljes kétrészes részgráfot nem tartalmazó bipartit gráfnak hány éle van [1] . A probléma az extremális gráfelmélet területéhez tartozik, a kombinatorika egyik ágához , és Kazimir Zarankiewicz lengyel matematikusról kapta a nevét , aki 1951-ben leírta a probléma néhány speciális esetét [2] .

A Kovari Tamásról, T. Sos Veráról és Turan Pálról elnevezett Kovari–Sos–Turan tétel felső korlátot ad a Zarankievics-probléma számára. Bebizonyosodott, hogy ha egy tiltott kétrészes gráf egyik részének legfeljebb három csúcsa van, akkor ez a korlát legfeljebb egy állandó tényezővel tér el a valódi értéktől. A nagyobb tiltott részgráfoknál jobb határértékek ismertek, és van egy sejtés, hogy ezek szorosak. A Kovari–Sos–Turan tétel alkalmazásai tartalmazzák a különféle típusú geometriai objektumok előfordulási számának becslését a kombinatorikus geometriában .

A probléma leírása

A G  = ( U ,  V ,  E ) kétrészes gráf két diszjunkt U és V csúcshalmazból , valamint élek halmazából áll, amelyek mindegyike összeköt egy U -ból egy csúcsot egy V -ből származó csúcsgal . Két él nem kötheti össze ugyanazt a csúcspárt. A teljes bipartit gráf egy olyan bipartit gráf, amelyben minden csúcspár (az egyik U -ból , a másik V -ből ) egy éllel van összekötve. Egy teljes kétrészes gráfot, amelyben U -nak s , V -nek t csúcsa van, K s , t -vel jelöljük . Ha G  = ( U ,  V ,  E ) kétrészes, és U -nak s csúcsának és V -nek t csúcsának van olyan részhalmaza, hogy e két halmaz összes csúcsa össze van kapcsolva, akkor ezek a csúcsok az alak generált részgráfját alkotják. K s , t . (Itt az s és t sorrendje szignifikáns – az s csúcshalmaznak U -hoz, a t csúcshalmaznak pedig V -hez kell tartoznia .)

A z ( m ,  n ;  s ,  t ) Zarankievics-függvény a G  = ( U ,  V ,  E ) kétrészes gráf éleinek maximális lehetséges számát jelöli , amelyre | U | =  m és | v | =  n , amely nem tartalmaz K s , t alakú részgráfot . A z ( n ,  n ;  t ,  t ) esetet z ( n ;  t )-vel írjuk a rövidség kedvéért . A Zarankievich-probléma felveti a Zarankievics-függvény képletének kérdését, vagy (ha nem állítható fel) a z ( n ;  t ) növekedési ráta szoros aszimptotikus határainak kérdését, feltéve, hogy t fix és n hajlamos végtelenség.

S = t = 2 esetén ez a probléma egybeesik a hatos kerületű cellák megtalálásának problémájával. A Zarankiewicz-probléma, a cellák és a véges geometriák szorosan összefüggenek [3] .

Ugyanez a probléma megfogalmazható a digitális geometriával . A G  = ( U ,  V ,  E ) kétrészes gráf lehetséges élei egy téglalap pontjaiként rajzolhatók meg | U | × | v | egy egész rácson , és egy teljes részgráf a sorok és oszlopok halmaza ebben a téglalapban, amely magában foglalja az összes pontot. Ekkor z ( m ,  n ;  s ,  t ) jelöli az m  ×  n rácsban elhelyezhető pontok maximális számát úgy, hogy a sorok és oszlopok egyetlen részhalmaza sem alkot teljes s  ×  t rácsot [4] . Alternatív és ekvivalens definíció, hogy z ( m ,  n ;  s ,  t ) a legkisebb k egész szám úgy, hogy minden m × n  (  0,1)-mátrixnak k  + 1 egyessel kell rendelkeznie s sorral és t oszloppal, hogy a megfelelő s × t almátrix kizárólag egyesekből áll.

Példák

A z szám ( n , 2) egy olyan kétrészes gráf éleinek maximális számának felel meg, amelyeknek minden része n csúcsa van, és amelynek nincsenek 4 hosszúságú ciklusai (a kerülete legalább hat). Ekkor z (2, 2) = 3 (három ívből álló pályán elérve), és z (3, 2) = 6 ( hatszög ).

A probléma eredeti megfogalmazásában Zarankievics kérdést tett fel z ( n ; 3) értékeiről n  = 4, 5 és 6 esetén. Hamarosan Vaclav Sierpinski válaszolt: z (4; 3) = 13, z ( 5; 3) = 20 és z (6; 3) = 26 [4] . A z (4; 3) eset viszonylag egyszerű - egy kétrészes gráf 13 éllel és minden részében négy csúcstal, amely nem tartalmaz K 3,3 részgráfot, egy hosszú átló hozzáadásával kapható meg a kockagráfhoz . Ezzel szemben, ha egy 14 élű kétrészes gráf minden részében négy csúcs van, akkor mindkét oldalon két csúcsnak négyes fokozatúnak kell lennie . Ezt a négy csúcsot és a rájuk eső 12 élt eltávolítva egy nem üres élhalmaz marad, amelyek közül bármelyik a négy eltávolított csúcsgal együtt egy K 3,3 részgráfot alkot .

Felső határok

Tomasz Kovari, Vera T. Sos és Pal Turan röviddel a probléma felállítása után megállapították a következő felső korlátot [5] , és ez a korlát Kovari–Sos–Turan tételként vált ismertté :

Valójában Kovari, Sos és Turan bebizonyította a megfelelő egyenlőtlenséget z -re ( n ;  t ), de nem sokkal ezután Hilten-Cavallius észrevette, hogy pontosan ugyanazok az érvek használhatók az általános eset bizonyítására [6] . A képlet jobb oldalán lévő állandó tényező javítását a z ( n ;  t ) esetre Stefan Znam [7] adta meg :

Ha az s - t és a t- t "O" jelöléssel javítjuk , akkor aszimptotikusabban átírhatjuk ezeket a képleteket a következőképpen

és

Alsó határok

Ha t = 2 és n  végtelen sok értéke , akkor egy véges projektív Levi-gráfjaként kaphatunk egy kétrészes gráfot, amelynek minden részében n csúcs van és Ω( n 3/2 ) élek K 2,2 nélkül. sík , n pontból és egyenesből álló rendszer, ahol minden két pont egyetlen egyeneshez tartozik, és minden két egyenes egyetlen pontban metszi egymást. Az ebből a geometriából kialakított gráfnak minden ponthoz van egy csúcsa az egyik oldalon, és minden egyenesnek egy csúcsa a másik oldalon. A p -rendű véges mező felett definiált projektív síkok K 2,2 -mentes gráfokhoz vezetnek n  =  p 2  +  p  + 1 és ( p 2  +  p  + 1)( p  + 1) élekkel. Például a Fano-sík Lévy-gráfja megadja a Heawood-gráfot , egy kétrészes gráfot, amelynek minden részében hét csúcs van, 21 éllel és 4 ciklus nélkül, ami azt mutatja, hogy z (7; 2) ≥ 21. az e családpéldák által megadott Zarankiewicz-függvény megfelel az I. Reiman által jelzett felső korlátnak [8] . Így t  = 2 és n azon értékei esetén, amelyekre ez a konstrukció elvégezhető, pontos választ kapunk a Zarankievich-problémára. Az n egyéb értékei esetében az alsó és felső határból az következik, hogy aszimptotikusan [9]

Általánosabb esetben [10] ,

t  = 3 és végtelen számú n érték esetén lehetőség van kétrészes gráfok létrehozására, amelyek mindegyik részében n csúcsú és Ω( n 5/3 ) csúcsokkal nem rendelkeznek K 3,3 részgráfokkal , szintén egy véges geometria , ha figyelembe vesszük a pontokat és a gömböket (gondosan fix sugarat választva) egy háromdimenziós véges affin térben. Ebben az esetben az élek a pontok és gömbök beesését jelentik [11] .

Feltételezték, hogy

t minden állandó értékére , de most csak t  = 2 és t  = 3 esetén van megerősítés a fenti konstrukciók szerint [12] . Szigorú határok ismertek a nagy méretkülönbséggel rendelkező ( s ,  t ) párokra (különösen s  ≥ ( t  − 1) esetén!). Ezeknek a pároknak

ami a fenti hipotézist valószínűsíti [13] . .

Nem kétoldalú gráfok

Egy állandó tényezőig z ( n ;  t ) korlátozza egy olyan n csúcsú gráf éleinek számát is (nem feltétlenül bipartit), amely nem tartalmazza a K t , t részgráfot. Egyik módon egy kétrészes gráf z ( n ;  t ) élekkel és n csúcsokkal minden részében redukálható n csúcsú és z ( n ;  t )/4 élű gráfra, ha véletlenszerűen választunk n /2 csúcsot az összesből. a gráf csúcsainak száma . Ezzel ellentétes irányban egy K t , t részgráfok nélküli n csúcsú gráf átalakítható kétrészes gráfrá, amelynek minden része n csúcsa van és kétszer annyi él, amely továbbra sem tartalmazza a K t , t részgráfot, kétrészes kettős borítójának megépítésével [14] .

Alkalmazások

A Kovari–Cos–Turan tételt a kombinatorikus geometriában használják a különböző típusú geometriai objektumok közötti előfordulások számának korlátozására. Egyszerű példaként az euklideszi síkban lévő n pontból és m egyenesből álló halmaz nem tartalmaz K 2,2 -t, így a Kovari–Cos–Turan tétel szerint ennek a konfigurációnak legfeljebb O ( nm 1/2  +  m ) pontja van. -vonalbeli előfordulások. Ez a korlát közel van, ha m sokkal nagyobb, mint n , de közel azonos m -re és n -re a Szemedi-Trotter-tétel szorosabb korlátos O -t ad ( n 2/3 m 2/3  +  n  +  m ). A Szemedi-Trotter tétel azonban bebizonyítható, ha a pontokat és egyeneseket részhalmazokra osztjuk, amelyekre a Kovari-Sos-Turan határok szorosak [15] .

Lásd még

Jegyzetek

  1. ↑ Bollobás, 2004 , p. 309–326.
  2. ↑ Zarankiewicz, 1951 , p. 301.
  3. ↑ Héger Tamás, Szőnyi Tamás, Damásdi Gábor. A Zarankiewicz-probléma, ketrecek és geometriák . Gács András és Reiman István emlékének dedikált  (angol) (pdf) . Budapesti Egyetem (2013. március 19.) . Letöltve: 2017. május 25. Az eredetiből archiválva : 2016. március 4.
  4. ↑ 1 2 Sierpiński, 1951 , p. 173–174.
  5. ↑ Kővári et al, 1954 , p. 50–57.
  6. ↑ Hyltén-Cavallius, 1958 , p. 59–65.
  7. ↑ Znam, 1963 , p. 81–84.
  8. ↑ Reiman, 1958 , p. 269–273.
  9. ↑ Bollobás, 2004 , p. 313. Következmény 2.7.
  10. ↑ Furedi, 1996 , p. 141–144.
  11. ↑ Brown, 1966 , p. 281–285.
  12. ↑ Bollobás, 2004 , p. 312, 15. sejtés.
  13. ↑ Alon et al, 1999 , p. 280–290.
  14. ↑ Bollobás (2004 ), 2.3. tétel, p. 310.
  15. ↑ Matousek, 2002 , p. 65–68.

Irodalom