Starka gissningar om perfekta grafer

Den starka perfekta grafförmodan  är streckgrafkarakteriseringen av perfekta grafer som exakt de grafer som varken har udda hål ( genererade cykler med udda längder) eller udda antihål (komplement till udda hål). Gissningen gjordes av Berge 1961. Beviset för Maria Chudnovskaya , Neil Robertson , Paul Seymour och Robin Thomas angavs 2002 [1] [2] och publicerades av dem 2006.

För att bevisa den starka perfekta grafsatsen fick författarna ett pris på 10 000 dollar från Gerard Cornijols från Carnegie Mellon University [1] och 2009 års Fulkerson-pris [3] .

Uttalande av satsen

En perfekt graf  är en graf där, för alla genererade subgrafer , storleken på den största klicken är lika med det minsta antal färger som behövs för att färga grafen. Perfekta grafer inkluderar välkända klasser av grafer som tvådelade grafer , ackordsgrafer och jämförbarhetsgrafer . 1961 och 1963, när han definierade dessa klasser av grafer för första gången, noterade Berge att perfekta grafer inte kan innehålla ett udda hål, den genererade subgrafen i form av en cykel med udda längd fem eller mer, eftersom udda hål har klick nummer två, och den kromatiska nummer tre. På samma sätt märkte han att perfekta grafer inte kan innehålla udda antihål, genererade subgrafer som är komplementära till udda hål - ett udda antihål med hörn har ett klicknummer k och ett kromatiskt tal , vilket återigen är omöjligt för perfekta grafer. Grafer med varken udda hål eller udda antihål blev kända som Berge-grafer.

Berge förmodade att vilken Berge-graf som helst är perfekt, eller, på motsvarande sätt, att perfekta grafer och Berge-grafer definierar samma klass av grafer. Denna gissning var känd som den starka perfekta grafförmodan fram till dess bevis 2002, då den döptes om till den starka perfekta grafsatsen.

Koppling till den svaga perfekta grafsatsen

En annan Berges gissning, bevisad 1972 av Laszlo Lovas , säger att komplementet till varje perfekt graf också är perfekt. Satsen blev känd som den perfekta grafsatsen eller (för att skilja den från den starka gissningen/perfekt grafsatsen) den svaga perfekta grafsatsen. Eftersom karakteriseringen av förbjudna Berge-grafer är självdual, följer den svaga perfekta grafsatsen omedelbart av den starka perfekta grafsatsen.

Idéer för beviset

Beviset för den starka perfekta grafsatsen av Chudnovskaya et al följer en kontur som föreslagits 2001 av Conforti, Cornijols, Robertson, Seymour och Thomas. Enligt denna disposition bildar varje Berge-graf antingen en av fem typer av grundläggande block (speciella klasser av perfekta grafer) eller har en av fyra andra typer av strukturella uppdelningar till enklare grafer. En minimal imperfekt Berge-graf kan inte ha någon av dessa nedbrytningar, vilket antyder att ett motexempel till satsen inte kan existera [4] . Denna idé baserades på den strukturella nedbrytningsförmodan av liknande typer, från vilken den starka gissningen om perfekta grafer skulle följa, men förmodan visade sig inte vara sann [5] [6] [7] [8] .

De fem huvudklasserna av perfekta grafer som utgör huvudfallen av denna strukturella nedbrytning är tvådelade grafer , linjediagram av tvådelade grafer, komplement till tvådelade grafer, komplement till linjediagram av tvådelade grafer och dubbeldelade grafer. Det är lätt att se att tvådelade grafer är perfekta – i alla icke-triviala genererade subgrafer är både klicknumret och det kromatiska talet lika med två. Perfektion av komplement till tvådelade grafer och komplement till linjediagram av tvådelade grafer är ekvivalent med Königs teorem angående storlekarna på de största matchningarna , de största oberoende uppsättningarna och de största vertextäckena i tvådelade grafer. Perfektionen av linjegrafer av tvådelade grafer kan formuleras på samma sätt som det faktum att tvådelade grafer har ett kromatiskt index som är lika med deras största styrka , vilket bevisats av König [9] . Således är alla fyra av dessa basklasser perfekta. Dubbeldelade grafer är relaterade till delade grafer genom att de också kan visas vara perfekta [10] .

De fyra typerna av sönderdelning som beaktas i detta bevis är 2-fogar, 2-fogade komplement, balanserade skevpartitioner och homogena par.

En 2-join är en uppdelning av en grafs hörn i två delmängder med egenskapen att kanterna som drar ihop skärningen mellan dessa två delmängder bildar två-hörn som inte skär (vid hörnen) kompletta tvådelade grafer . När en graf har en 2-koppling kan den delas upp i genererade subgrafer som kallas "block" genom att ersätta en av de två delmängderna av hörn med en kortaste väg inom den delmängden som förbinder en av de två kompletta tvådelade graferna till den andra. Om det inte finns någon sådan väg, bildas blocket istället genom att en av vertexdelmängderna ersätts med två hörn, en för varje komplett tvådelad subgraf. En 2-join är perfekt om och bara om båda dess block är perfekta. Således, om en minimal imperfekt graf har en 2-koppling, måste den vara lika med ett av dess block, vilket innebär att det måste vara en udda cykel och inte en Berge-graf. Av samma anledning kan en minimal imperfekt graf vars komplement har en 2-join inte vara en Berge-graf [11] [12] .

En skev partition  är en partition av toppen av en graf i två delmängder, varav en genererar en frånkopplad subgraf och den andra har ett frånkopplat komplement. Chvatal [13] förmodade att inget minimalt motexempel till den starka perfekta grafförmodan kan ha en skev partition. Chudnovskaya et al introducerade några tekniska begränsningar för snedställningspartitioner och kunde visa att Chvatals gissningar är sanna för de resulterande "balanserade skevpartitionerna". Den fullständiga gissningen är en följd av den starka perfekta grafsatsen [14] [15] [16] .

Homogena par är relaterade till den modulära nedbrytningen av en graf. Detta är en nedbrytning av grafen i tre delmängder så att och tillsammans innehåller minst tre hörn, innehåller minst två hörn, och för varje hörn v från och valfritt i från {1,2}, är antingen v intill alla hörn i , eller ingen av dem. Det är omöjligt för en minimal imperfekt graf att ha ett homogent par [17] [18] . Efter att ha bevisat den starka perfekta grafförmodan, förenklade Chudnovskaya [19] beviset genom att visa att homogena par kan uteslutas från uppsättningen av nedbrytningar som används i beviset.

Beviset på att någon Berge-graf faller i någon av de fem klasserna eller har någon av de fyra typerna av nedbrytning följer analysen av enskilda fall, enligt vilka det finns en viss konfiguration i grafen - en "sträcka", en subgraf som kan delas upp i tre genererade banor enligt vissa ytterligare begränsningar, förlängningsförlängning och "eget hjul", en konfiguration associerad med ett hjul som består av en genererad cykel med en central vertex intill åtminstone tre fälgtoppar och som uppfyller några ytterligare begränsningar. Beroende på om det finns en sträcka, ett sträckkomplement eller ett riktigt hjul inom en given Berge-graf, kan det visas att grafen tillhör en av basklasserna, eller så kan den brytas ned [20] [21] . Denna fallstudie kompletterar beviset.

Anteckningar

  1. ↑ 12 Mackenzie , 2002 .
  2. ↑ Cornuejols, 2002 .
  3. ↑ 2009 Fulkerson-priser, 2011 , sid. 1475–1476
  4. ↑ Cornuejols, 2002 , sid. Förmodan 5.1.
  5. ↑ Reed, 1986 .
  6. ↑ Hougardy, 1991 .
  7. ↑ Rusu, 1997 .
  8. ↑ Roussel, Rusu, Thuillier, 2009 , sid. avsnitt 4.6 De första gissningarna.
  9. ↑ Kőnig, 1916 .
  10. ↑ Roussel, Rusu, Thuillier, 2009 , sid. Definition 4.39.
  11. ↑ Cornuejols, Cunningham, 1985 .
  12. ↑ Cornuejols, 2002 , sid. Sats 3.2 och konsekvens 3.3.
  13. ↑ Chvatal, 1985 .
  14. ↑ Seymour, 2006 .
  15. ↑ Roussel, Rusu, Thuillier, 2009 , sid. avsnitt 4.7 Skevpartitionen.
  16. ↑ Cornuejols, 2002 , sid. Satserna 4.1 och 4.2.
  17. ↑ Chvatal, Sbihi, 1987 .
  18. ↑ Cornuejols, 2002 , sid. Sats 4.10.
  19. ↑ Chudnovsky, 2006 .
  20. ↑ Cornuejols, 2002 , sid. Satserna 5.4, 5.5, 5.6.
  21. ↑ Roussel, Rusu, Thuillier, 2009 , sid. Sats 4.42.

Litteratur

Länkar