Problema Zaranevici

Problema Zarankevici  este o problemă de teorie a grafurilor legată de găsirea numărului minim de intersecții atunci când descrieți un graf bipartit complet pe un plan . [unu]

Cunoscută și sub denumirea de problema fabricii de cărămidă a lui Turan , după matematicianul maghiar Pal Turan , care a formulat această problemă în timp ce lucra într-o fabrică de cărămidă în timpul celui de-al Doilea Război Mondial .  

Matematicianul polonez Kazimierz Zarankiewicz ( polonez Kazimierz Zarankiewicz ) a presupus că o imagine grafică simplă are un număr minim de intersecții, totuși, cu excepția cazurilor speciale, optimitatea acesteia rămâne nedemonstrată [2] .

Originea și formularea

În timpul celui de-al Doilea Război Mondial, matematicianul ungur Pál Turán a fost forțat să lucreze într-o fabrică de cărămidă, unde a transportat căruțe cu cărămizi de la cuptoare la depozite. În fabrică, șinele de cale ferată erau așezate între orice cuptor și orice depozit și era mai dificil să împingi căruciorul acolo unde aceste șine se intersectau. Acest lucru l-a inspirat pe Turan să se întrebe cum ar putea fi rearanjate căile pentru a minimiza numărul de intersecții. [unu]

Din punctul de vedere al matematicii, aceasta este sarcina de a reprezenta un grafic pe un plan : cuptoarele și depozitele definesc vârfurile graficului, iar șinele de cale ferată definesc marginile acestuia. Deoarece există exact o cale între fiecare cuptor și fiecare depozit, un astfel de grafic este un bipartit complet . Dacă există p cuptoare și s depozite, atunci un astfel de grafic este notat cu . Problema lui Turan este de a aranja vârfurile și muchiile unui grafic pe plan în așa fel încât niciun vârf să nu se afle pe o muchie al cărei capăt nu este și, în același timp, muchiile graficului să aibă un număr minim de intersecții altele decât vârfuri. În acest caz, marginile nu trebuie să fie rectilinii , deși în soluție, care se presupune a fi minimă, acesta este cazul. [2]

Problema lui Turan este considerată una dintre primele probleme privind numărul minim de intersecții ale graficelor . [3] Un caz aparte este problema matematică clasică „ Case și puțuri ”, în care rolul cuptoarelor și depozitelor este jucat de case și fântâni, fiecare - trei piese.

Încercări de soluție

Zarankiewicz și Kazimierz Urbanik ( poloneză: Kazimierz Urbanik ) au participat la prelegerile lui Turan în Polonia în 1952 [4] și au publicat în mod independent încercările de a rezolva problema. [5]

În ambele cazuri, ei au propus să deseneze un grafic bipartit complet după cum urmează (vezi imaginea de la începutul articolului): desenați vârfuri de o culoare („cuptoare”) de-a lungul axei verticale, vârfuri de altă culoare („depozite”) de-a lungul axei orizontale, iar punctul de intersecție al axelor alegeți astfel încât pe fiecare parte să fie egal (dacă există vârfuri pare de o anumită culoare ) sau aproape egal (dacă sunt impare). Ca rezultat, ambele au primit următorul număr de intersecții pentru marginile graficului:

Acest exemplu oferă o limită superioară a numărului de intersecții, dar ambele dovezi ale minimalității sale, dând o limită inferioară, s-au dovedit a fi incorecte: au fost infirmate de Gerhard Ringel și Paul Kainen aproape simultan, în 1965 [6] 

Deși în cazul general problema minimalității este încă o presupunere, cazuri speciale au fost dovedite cu succes: cazul cu Zaranevici însuși, iar mai târziu cu . [7] Deoarece pentru oricare doi p, s demonstrarea minimalității necesită un număr finit de verificări, a fost efectuată pentru p, s suficient de mic. [8] De asemenea, sa dovedit că numărul minim de intersecții este de cel puțin 83% din estimarea Zarankiewicz. [9]

Note

  1. ↑ 1 2 Turan, P. (1977), A note of welcome , Journal of Graph Theory vol . 1: 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, Studii matematice și monografii, Societatea Americană de Matematică , p. 126–127  .
  3. ↑ Foulds, LR (1992), Aplicații ale teoriei grafurilor , Universitex, Springer, p. 71, ISBN 9781461209331 , < https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71 > Arhivat la 12 iulie 2022 la Wayback Machine . 
  4. ↑ Beineke, Lowell & Wilson, Robin (2010), The early history of the brick factory problem , 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. Matematică. T. 3: 200–201  . După cum este citat de Szekely, Laszlo A. (2001), Zarankiewicz crossing number conjecture , în Hazewinkel, Michiel, Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4 
  6. ↑ Guy, Richard K. (1969), The decline and fall of Zarankiewicz's theorem, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 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), Conjectura lui Zarankiewicz este finită pentru fiecare m fix , Journal of Combinatorial Theory , Series B vol. 103 (2): 237–247 , DOI 10.1016/j.jctb.2012.11.001  .
  9. ↑ de Klerk, E.; Maharry, J.; Pasechnik, DV & Richter, RB (2006), Improved bounds for the crossing numbers of K m,n and K n , SIAM Journal on Discrete Mathematics vol. 20 (1): 189–202 , DOI 10.1137/S0895480104442741  .

Link -uri