Albertsons hypotes

Olösta problem i matematik : Har kompletta grafer minsta möjliga antal skärningspunkter mellan grafer med samma kromatiska tal ?

Albertsons gissning  är ett obevisat samband mellan skärningsnumret och det kromatiska talet för en graf . Hypotesen är uppkallad efter Michael O. Albertson, professor vid Smith College , som formulerade påståendet som en hypotes 2007 [1] . Gissningarna är en av många gissningar inom graffärgsteorin [2] . Gissningen säger att bland alla grafer som kräver n färger, är den fullständiga grafen K n bland de grafer med minst antal skärningspunkter. På motsvarande sätt, om grafen kan ritas med färre skärningspunkter än K n , kan den, genom gissningar, färgas med färre än n färger.

Hypotetisk formel för det minsta antalet korsningar

Det kan visas direkt att en graf med ett begränsat antal skärningar har ett begränsat kromatiskt antal - du kan tilldela olika färger till ändarna av alla skärande kanter och färga den plana grafen som finns kvar efter att du tagit bort dessa kanter i 4 färger . Albertsons hypotes ersätter detta kvalitativa samband mellan antalet skärningar och antalet färger med ett mer exakt kvantitativt samband. En annan gissning av Richard K. Guy [3] säger att antalet skärningar av hela grafen K n är

Det är känt hur man ritar kompletta grafer med detta antal skärningar, placerar hörn på två koncentriska cirklar. Vad som inte är känt är om det finns ritningar med färre snitt. Således säger en förstärkt formulering av Albertsons gissning att varje n -kromatisk graf har ett skärningsnummer som inte är mindre än den högra sidan av denna formel [4] . Denna förstärkta gissning är sann om och bara om både Guys gissningar och Albertsons gissningar är sanna.

Asymptotiska gränser

En svagare form av gissningen, bevisad av M. Schaefer [4] , säger att varje graf med kromatiskt nummer n har skärningsnummer Ω( n 4 ), eller, ekvivalent, att varje graf med skärningsnummer k har kromatiskt nummer O ( k 1/4 ). Alberson , -kromatisk graf har en minimigrad som inte är mindre ännpublicerade ett bevis för dessa gränser genom att kombinera det faktum att varje minimal[4]Kratson och Fox skärningstalet olikhet , enligt vilken varje graf c har skärningsnummer ). Med samma argument visar de att ett motexempel till Albertsons gissning med kromatiskt tal n (om det finns ett) måste ha färre än 4n hörn.

Särskilda tillfällen

Albertsons gissning är ett sant påstående utan innehåll för  - har skärningsnummer noll och alla grafer har skärningsnummer minst noll. Fallet med Albertsons gissning är ekvivalent med fyrafärgssatsen , att vilken plan graf som helst kan färgas med fyra eller färre färger, och de enda graferna som kräver färre skärningspunkter än grafen K 5 är plana grafer, enligt hypotesen borde de vara högst än 4-kromatisk. Tack vare stödet från vissa grupper av författare är det nu känt att gissningarna är sanna för alla [5] [4] [6] . För vilket heltal som helst presenterade Louis och Richter familjer av (c+1) -färgkritiska grafer som inte innehåller underavdelningar av hela grafen K (c+1) , men som har åtminstone K (c+1) skärningspunkter [7] .

Relaterade hypoteser

Det finns också en koppling till Hadwiger-förmodan , ett viktigt öppet problem inom kombinatorik angående sambandet mellan kromatiskt tal och förekomsten av stora klickar som grafiska biträden [6] . En variant av Hadwiger-förmodan som framförts av György Hajos säger att varje n - kromatisk graf innehåller en underavdelning K n . Om gissningen vore sann, så skulle Albertsons gissning följa därav, eftersom antalet skärningar av hela grafen inte är mindre än antalet skärningar av underavdelningen. Men motexempel till Hayoshs gissning [8] [9] är för närvarande kända , så detta samband gör det inte möjligt att bevisa Albertsons gissning.

Anteckningar

  1. ↑ Enligt Albertson, Cranston och Fox ( Albertson, Cranston, Fox 2009 ) gjordes gissningen av Albertson vid en speciell session av American Mathematical Society i Chicago, som hölls i oktober 2007.
  2. ↑ Hutchinson, 2009 .
  3. ↑ Guy, 1972 .
  4. ↑ 1 2 3 4 Albertson, Cranston, Fox, 2009 .
  5. ↑ Oporowski, Zhao, 2009 .
  6. ↑ 1 2 Barát, Toth, 2010 .
  7. ↑ Louis, Richter, 2014 .
  8. ↑ Catlin, 1979 .
  9. ↑ Erdős, Fajtlowicz, 1981 .

Litteratur