Zarankevich problem

Zarankevich-  problemet är ett grafteoretiskt problem relaterat till att hitta det minsta antalet korsningar när man visar en komplett tvådelad graf på ett plan . [ett]

Även känt som Turans tegelfabriksproblem ,  efter den ungerske matematikern Pal Turan , som formulerade detta problem när han arbetade i en tegelfabrik under andra världskriget .

Den polske matematikern Kazimierz Zarankiewicz ( polska Kazimierz Zarankiewicz ) förmodade att någon enkel grafbild har ett minsta antal skärningspunkter, men med undantag för speciella fall förblir dess optimalitet obevisad [2] .

Ursprung och formulering

Under andra världskriget tvingades den ungerske matematikern Pál Turán att arbeta i en tegelfabrik, där han fraktade vagnlass med tegel från ugnar till lager. I fabriken lades järnvägsspår mellan vilken ugn och vilket lager som helst , och det var svårare att skjuta vagnen där dessa spår korsades. Detta inspirerade Turan att fråga hur stigarna skulle kunna arrangeras om för att minimera antalet korsningar. [ett]

Ur matematikens synvinkel är detta uppgiften att avbilda en graf på ett plan : ugnar och lager definierar grafens hörn, och järnvägsspår definierar dess kanter. Eftersom det finns exakt en väg mellan varje ugn och varje lager, är en sådan graf en komplett tvådelad . Om det finns p ugnar och s lager, så betecknas en sådan graf med . Turans problem är att arrangera en grafs hörn och kanter på planet på ett sådant sätt att ingen vertex ligger på en kant som det inte är slutet på, och samtidigt har grafens kanter ett minsta antal skärningar annat än hörn. I det här fallet behöver kanterna inte vara rätlinjiga , även om det i lösningen, som antas vara minimal, är fallet. [2]

Turans problem anses vara ett av de första problemen med det minsta antalet skärningar av grafer . [3] Ett specialfall är det klassiska matematiska problemet " Hus och brunnar ", där rollen som ugnar och lager spelas av hus och brunnar, vardera - tre stycken.

Lösningsförsök

Zarankiewicz och Kazimierz Urbanik ( polska: Kazimierz Urbanik ) deltog i Turans föreläsningar i Polen 1952 [4] och publicerade oberoende försök att lösa problemet. [5]

I båda fallen föreslog de att rita en komplett tvådelad graf enligt följande (se bilden i början av artikeln): rita hörn av en färg ("ugnar") längs den vertikala axeln, hörn av en annan färg ("lager") längs den horisontella axeln, och skärningspunkten för axlarna väljer så att det på varje sida är lika (om det finns jämna hörn av en given färg ) eller nästan lika (om de är udda). Som ett resultat fick båda följande antal skärningar för grafens kanter:

Detta exempel ger en övre gräns för antalet korsningar, men båda bevisen på dess minimalitet, som gav en nedre gräns, visade sig vara felaktiga: de motbevisades av Gerhard Ringel och Paul Kainen nästan samtidigt, 1965 [6] 

Även om frågan om minimalitet i det allmänna fallet fortfarande är en gissning, har speciella fall framgångsrikt bevisats: fallet med Zarankevich själv och senare med . [7] Eftersom beviset på minimalitet för två p, s kräver ett ändligt antal kontroller, utfördes det för tillräckligt små p, s. [8] Det bevisades också att det minsta antalet korsningar är minst 83 % av Zarankiewicz-uppskattningen. [9]

Anteckningar

  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, Mathematical Surveys and Monographs, American Mathematical Society , sid. 126–127  .
  3. ↑ Foulds, LR (1992), Graph Theory Applications , Universitex, Springer, sid. 71, ISBN 9781461209331 , < https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71 > Arkiverad 12 juli 2022 på 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. Matematik. T. 3: 200–201  . Som citeras av Szekely, Laszlo A. (2001), Zarankiewicz crossing number conjecture , i 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, Mich., 1968) , Academic Press, New York, s . ... 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), Zarankiewiczs gissning är ändlig för varje fast m , Journal of Combinatorial Theory , Series B vol. 103 (2): 237–247 , DOI 10.1016/j.jctb.1.20011.  .
  9. ↑ de Klerk, E.; Maharry, J.; Pasechnik, DV & Richter, RB (2006), Förbättrade gränser för korsningsnumren för K m,n och K n , SIAM Journal on Discrete Mathematics vol. 20 (1): 189–202 , DOI 10.1137/S0895480141442  .

Länkar