Turáns tegelfabriksproblem - Turán's brick factory problem
 |
Olöst problem i matematik : Kan någon fullständig bipartitgraf ritas med färre korsningar än antalet som ges av Zarankiewicz?
(mer olösta problem i matematik)
|
I matematiken i grafritning , Turans tegelbruk problem frågar efter minsta antalet korsningar i en ritning av ett komplett bipartit graf . Problemet är uppkallat efter Pál Turán , som formulerade det medan han tvingades arbeta i en tegelfabrik under andra världskriget.
En ritningsmetod som hittats av Kazimierz Zarankiewicz har antagits för att ge det rätta svaret för varje fullständig bipartitgraf, och uttalandet att detta är sant har blivit känt som Zarankiewicz korsningsnummer . Antagandet förblir öppen, med endast några speciella fall löst.
Ursprung och formulering
Under andra världskriget tvingades den ungerska matematikern Pál Turán att arbeta i en tegelfabrik och pressade vagnmassor av tegel från ugnar till lagringsplatser. Fabriken hade spår från varje ugn till varje lagringsplats, och vagnarna var svårare att skjuta vid de punkter där spåren korsade varandra. Turán inspirerades av denna situation för att fråga hur fabriken skulle kunna redesignas för att minimera antalet korsningar mellan dessa spår.
Matematiskt kan detta problem formaliseras som att begära en grafritning av en fullständig bipartitgraf , vars hörn representerar ugnar och lagringsplatser, och vars kanter representerar spåren från varje ugn till varje lagringsplats. Diagrammet ska ritas i planet med varje toppunkt som en punkt, varje kant som en kurva som förbinder sina två slutpunkter, och inget toppunkt placeras på en kant som det inte inträffar. En korsning räknas närhelst två kanter som inte är sammanhängande i diagrammet har en oskälig korsning i planet. Frågan är då, vad är det minsta antalet korsningar i en sådan ritning?
Turáns formulering av detta problem erkänns ofta som en av de första studierna av korsande antal grafer . (En annan oberoende formulering av samma koncept inträffade i sociologin, i metoder för att rita sociogram , och ett mycket äldre pussel, de tre verktygsproblemen , kan ses som ett speciellt fall av tegelfabriksproblemet med tre ugnar och tre lagringsanläggningar.) Korsnummer har sedan dess fått större betydelse, som ett centralt studieobjekt inom grafritning och som ett viktigt verktyg i VLSI- design och diskret geometri .
Övre gräns
Både Zarankiewicz och Kazimierz Urbanik såg Turán tala om tegelfabriksproblemet i olika samtal i Polen 1952 och publicerade oberoende försök till lösningar på problemet med motsvarande formler för antalet korsningar. Som båda visade är det alltid möjligt att rita den fullständiga bipartitgrafen K m, n (en graf med m- hörn på ena sidan, n hörn på andra sidan och mn kanter som förbinder de två sidorna) med ett antal korsningar lika med
Konstruktionen är enkel: placera m- hörn på x- axeln på planet, undvik ursprunget , med lika eller nästan lika många punkter till vänster och höger om y- axeln. På samma sätt placerar du n- hörn på y- axeln på planet, och undviker ursprunget, med lika eller nästan lika många punkter över och under x- axeln. Anslut sedan varje punkt på x -axeln med ett linjärt segment till varje punkt på y -axeln.
Deras bevis på att denna formel är optimal, det vill säga att det inte kan finnas några ritningar med färre korsningar, var felaktiga. Gapet upptäcktes inte förrän elva år efter publiceringen, nästan samtidigt av Gerhard Ringel och Paul Kainen . Ändå antas att Zarankiewicz och Urbaniks formel är optimal. Detta har kommit att bli känt som Zarankiewicz korsningsnummer gissningar. Även om vissa speciella fall är kända för att vara sanna, förblir det allmänna fallet öppet.
Lägre gränser
Eftersom K m, n och K n, m är isomorfa är det tillräckligt att överväga fallet där m ≤ n . Dessutom, för m ≤ 2 ger Zarankiewicz konstruktion inga korsningar, vilket naturligtvis inte kan bäst. Så de enda icke-privata fallen är de för vilka m och n båda är ≥ 3 .
Zarankiewicz försök att bevisa antagandet, även om det är ogiltigt för det allmänna fallet med K m , n , fungerar för fallet m = 3 . Det har sedan utvidgats till andra små värden på m , och Zarankiewicz gissningar är känt för att vara sant för den fullständiga tvådelade grafer K m, n med m ≤ 6 . Antagandet är också känt för att vara sant för K 7,7 , K 7,8 och K 7,9 . Om ett motexempel existerar, det vill säga en graf K m, n som kräver färre korsningar än Zarankiewicz-bunden, måste i det minsta motexemplet både m och n vara udda.
För varje fast val av m kan sanningen om antagandet för alla Km , n verifieras genom att endast testa ett begränsat antal val av n . Mer allmänt har det bevisats att varje fullständig bipartitgraf kräver ett antal korsningar som är (för tillräckligt stora grafer) minst 83% av antalet som ges av Zarankiewicz-bundna. Att stänga klyftan mellan denna nedre gräns och den övre gränsen är fortfarande ett öppet problem.
Rätlinjiga korsningsnummer
Om kanter måste ritas som raka linjesegment, snarare än godtyckliga kurvor, behöver vissa grafer fler korsningar än vad de skulle göra när de ritades med böjda kanter. Den övre gränsen som Zarankiewicz har fastställt för korsningen av hela tvåpartsdiagram kan dock uppnås med endast raka kanter. Därför, om Zarankiewicz-antagandet är korrekt, har de fullständiga tvåpartsdiagrammen rätlinjiga korsningstal lika med deras korsningstal.