Zarankevics probléma

A Zarankevics-  probléma egy gráfelméleti probléma , amely egy teljes kétrészes gráf síkon történő ábrázolásakor a metszéspontok minimális számának megtalálásához kapcsolódik . [egy]

A turáni téglagyári problémaként is ismert Turán Pál magyar matematikus után , aki a  második világháború alatt egy téglagyári munka közben fogalmazta meg ezt a problémát .

Kazimierz Zarankiewicz lengyel matematikus ( lengyel Kazimierz Zarankiewicz ) úgy sejtette, hogy néhány egyszerű gráfképnek van minimális számú metszéspontja, azonban a speciális esetek kivételével optimálissága bizonyítatlan marad [2] .

Eredet és megfogalmazás

A második világháború idején Turán Pál magyar matematikus egy téglagyárban kényszerült dolgozni, ahol szekérnyi téglát cipelt a kemencékből a raktárakba. A gyárban vasúti síneket fektettek bármelyik kemence és bármely raktár közé , és nehezebb volt tolni a kocsit ott, ahol ezek a vágányok keresztezik egymást. Ez arra ösztönözte Turant, hogy megkérdezze, hogyan lehetne átrendezni az utakat a kereszteződések számának minimalizálása érdekében. [egy]

A matematika szempontjából ez a gráf síkon való ábrázolásának feladata : a kemencék és a raktárak határozzák meg a gráf csúcsait, a vasúti sínek pedig az éleit . Mivel pontosan egy út van minden sütő és raktár között, egy ilyen grafikon egy teljes kétoldalú . Ha van p sütő és s raktár, akkor egy ilyen grafikont jelölünk . Turan problémája, hogy a gráf csúcsait és éleit úgy rendezze el a síkon, hogy egyetlen csúcs se legyen olyan élen, amelynek nem a vége, és ugyanakkor a gráf éleinek minimális számú metszéspontja van. a csúcsokon kívül. Ebben az esetben az éleknek nem kell egyenesnek lenniük , bár a minimálisnak feltételezett megoldásban ez a helyzet. [2]

A Turan-probléma az egyik első probléma a gráfok minimális metszéspontjaival kapcsolatban . [3] Különleges eset a " Házak és kutak " klasszikus matematikai probléma, amelyben a kemencék és raktárak szerepét házak és kutak játsszák, mindegyik - három darab.

Megoldási kísérletek

Zarankiewicz és Kazimierz Urbanik ( lengyelül: Kazimierz Urbanik ) 1952-ben részt vett Turan lengyelországi előadásain [4] , és egymástól függetlenül tett közzé kísérleteket a probléma megoldására. [5]

Mindkét esetben egy komplett kétoldali gráf megrajzolását javasolták a következőképpen (lásd a képet a cikk elején): a függőleges tengely mentén rajzoljunk egy színű csúcsokat („kemencék”), egy másik színű csúcsokat („raktárak”). a vízszintes tengely mentén, és a tengelyek metszéspontját úgy válasszuk meg, hogy mindkét oldalon egyformán (ha vannak egy adott színű páros csúcsok ) vagy majdnem egyenlően (ha páratlanok) legyenek. Ennek eredményeként mindkettő a következő számú metszéspontot kapta a gráf éleihez:

Ez a példa megadja a metszéspontok számának felső korlátját, de a minimálisságának mindkét, alsó korlátot adó bizonyítéka tévesnek bizonyult: Gerhard Ringel és Paul Kainen szinte egyszerre, 1965- ben cáfolta őket  [6].

Bár általános esetben a minimalitás kérdése még csak sejtés, a speciális esetek sikeresen bebizonyítottak: maga Zarankevics esete, majd később a . [7] Mivel bármely két p, s esetén a minimálisság bizonyítása véges számú ellenőrzést igényel, elég kicsi p, s esetén végeztük el. [8] Az is bebizonyosodott, hogy a kereszteződések minimális száma legalább a Zarankiewicz-becslés 83%-a. [9]

Jegyzetek

  1. ↑ 1 2 Turan, P. (1977), A note of welcome , Journal of Graph Theory 1. kötet : 7–9 , doi 10.1002/jgt.3190010105  .
  2. ↑ 1 2 Pach, Janos & Sharir, Micha (2009), 5.1 Crossings – the Brick Factory Problem, Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures , vol. 152, Mathematical Surveys and Monographs, American Mathematical Society , p. 126–127  .
  3. ↑ Foulds, LR (1992), Graph Theory Applications , Universitex, Springer, p. 71, ISBN 9781461209331 , < https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71 > Archiválva 2022. július 12-én a Wayback Machine -nél . 
  4. ↑ Beineke, Lowell & Wilson, Robin (2010), A téglagyári probléma korai története , The Mathematical Intelligencer vol. 32 (2): 41–48 , DOI 10.1007/s00283-009-9120-4  .
  5. ↑ Urbanik, K. (1955), Solution du probleme pose par P. Turan, Colloq. Math. T. 3: 200–201  . Amint azt Szekely, Laszlo A. (2001), Zarankiewicz keresztezési számsejtés idézi , Hazewinkel, Michiel, Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4 
  6. ↑ Guy, Richard K. (1969), Zarankiewicz tételének hanyatlása és bukása, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , Academic Press, New York, p. . 63–69  .
  7. ↑ Kleitman, Daniel J. (1970), The crossing number of K 5, n , Journal of Combinatorial Theory vol. 9: 315–323 , DOI 10.1016/s0021-9800(70)80087-4  .
  8. ↑ Christian, Robin; Richter, R. Bruce & Salazar, Gelasio (2013), Zarankiewicz sejtése véges minden rögzített m -re , Journal of Combinatorial Theory , Series B vol. 103 (2): 237–247 , DOI 10.1016/j.jctb.2012.11.  .
  9. ↑ de Klerk, E.; Maharry, J.; Pasechnik, DV & Richter, RB (2006), Javított határértékek a K m,n és K n keresztezési számokhoz , SIAM Journal on Discrete Mathematics 20. kötet (1): 189–202, DOI 10.1137/S0895480101442  .

Linkek