Stark perfekt grafteorem - Strong perfect graph theorem

I grafteori är den starka perfekta grafsatsen en förbjuden grafkaraktärisering av de perfekta graferna som exakt de grafer som varken har udda hål (udda längdinducerade cykler ) eller udda antihål (komplement till udda hål). Det antogs av Claude Berge 1961. Ett bevis av Maria Chudnovsky , Neil Robertson , Paul Seymour och Robin Thomas tillkännagavs 2002 och publicerades av dem 2006.

Beviset på den starka perfekta grafsatsen vann för sina författare ett pris på 10 000 dollar som erbjuds av Gérard Cornuéjols från Carnegie Mellon University och Fulkersonpriset 2009 .

Påstående

Ett perfekt diagram är ett diagram där, för varje inducerad subgraf , storleken på den maximala klicken är lika med det minsta antalet färger i en färg på grafen; perfekta grafer inkluderar många välkända grafklasser inklusive tvåpartsdiagram , ackorddiagram och jämförbarhetsdiagram . I sina 1961- och 1963-arbeten som för första gången definierar denna klass av grafer observerade Claude Berge att det är omöjligt för en perfekt graf att innehålla ett udda hål, en inducerad subgraf i form av en udda längdcykeldiagram med längd fem eller mer, för udda hål har klick nummer två och kromatisk nummer tre. På liknande sätt observerade han att perfekta grafer inte kan innehålla udda antihål, inducerade subgrafer kompletterande med udda hål: ett udda antihål med 2 k  + 1 hörn har klickantal k och kromatiskt antal k  + 1, vilket återigen är omöjligt för perfekta grafer. Diagrammen som varken har udda hål eller udda antihål blev kända som Berge-graferna.

Berge antog att varje Berge-graf är perfekt, eller motsvarande att de perfekta graferna och Berge-graferna definierar samma klass av grafer. Detta blev känt som den starka perfekta grafgissningen, fram till dess bevis 2002, då den döptes om till den starka perfekta grafsatsen.

Förhållande till den svaga perfekta grafsatsen

En annan antagande av Berge, bevisad 1972 av László Lovász , är att komplementet till varje perfekt graf också är perfekt. Detta blev känt som den perfekta grafsatsen , eller (för att skilja den från den starka perfekta grafgissningen / satsen) den svaga perfekta grafsatsen. Eftersom Berges förbjudna grafkaraktärisering är självkomplementär följer den svaga perfekta grafsatsen omedelbart från den starka perfekta grafsatsen.

Bevisidéer

Beviset på den starka perfekta grafsatsen av Chudnovsky et al. följer en kontur som antogs 2001 av Conforti, Cornuéjols, Robertson, Seymour och Thomas, enligt vilken varje Berge-graf antingen utgör en av fem typer av grundläggande byggstenar (speciella klasser av perfekta grafer) eller att den har en av fyra olika typer av strukturell nedbrytning i enklare diagram. En minimalt ofullständig Berge-graf kan inte ha någon av dessa nedbrytningar, varifrån det följer att inget motexempel till satsen kan existera. Denna idé baserades på tidigare antagna strukturella nedbrytningar av liknande typ som skulle ha antydt den starka perfekta grafgissningen men visat sig vara falsk.

De fem grundläggande klasserna av perfekta grafer som utgör grundfallet för denna strukturella sönderdelning är tvåpartsdiagram , linjediagram för tvåpartsdiagram, kompletterande diagram för tvåpartsdiagram, komplement till linjediagram för tvåpartsdiagram och dubbeldelade grafer. Det är lätt att se att bipartitdiagram är perfekta: i alla icke-inducerade subgrafer är klickantalet och det kromatiska antalet båda två och därför båda lika. Perfektion av komplement av bipartitdiagram och komplement av linjediagram för bipartitdiagram är båda ekvivalenta med Kőnigs teorem om storlekarna på maximala matchningar , maximala oberoende uppsättningar och minsta toppunktomslag i tvåpartsdiagram. Perfektion av linjediagram för bipartitdiagram kan anges lika med det faktum att bipartitdiagram har kromatiskt index lika med sin maximala grad , bevisat av Kőnig (1916) . Således är alla dessa fyra grundklasser perfekta. De dubbla delade graferna är en släkting till delade grafer som också kan visas vara perfekta.

De fyra typerna av sönderdelningar som beaktas i detta bevis är 2-fogar, komplement till 2-fogar, balanserade skeva partitioner och homogena par.

En 2-skarv är en partition av kurvorna i en graf i två delmängder, med egenskapen att kanterna som spänner över skärningen mellan dessa två delmängder bildar två vertex-sammanhängande kompletta tvåpartsdiagram . När en graf har en 2-koppling kan den sönderdelas i inducerade delbilder som kallas "block", genom att ersätta en av de två delmängderna av vertikaler med en kortaste väg inom den delmängden som förbinder en av de två kompletta tvåpartsdiagrammen med den andra; när ingen sådan väg existerar, bildas blocket istället genom att ersätta en av de två delmängderna av hörn med två hörn, en för varje fullständig bipartit undergraf. En 2-koppling är perfekt om och bara om dess två block är perfekta. Därför, om en minimalt ofullständig graf har en 2-koppling, måste den motsvara ett av sina block, varifrån det följer att det måste vara en udda cykel och inte Berge. Av samma anledning kan en minimalt ofullkomlig graf vars komplement har en 2-koppling inte vara Berge.

En skev partition är en partition av grafens hörn i två delmängder, varav den ena inducerar en frånkopplad delgraf och den andra har ett frånkopplat komplement; Chvátal (1985) hade antagit att inget minimalt motexempel till den starka perfekta grafgissningen kunde ha en skev partition. Chudnovsky et al. införde några tekniska begränsningar för skeva partitioner och kunde visa att Chvátal's antagande är sant för de resulterande "balanserade skew partitionerna". Hela antagandet är en följd av den starka perfekta grafsatsen.

Ett homogent par är relaterat till en moduluppdelning av en graf. Det är en partition av grafen i tre undergrupper V 1 , V 2 , och V 3 så att V 1 och V 2 tillsammans innehåller minst tre hörn, V 3 innehåller åtminstone två hörn, och för varje vertex v i V 3 och varje i i {1,2} antingen v ligger i anslutning till alla hörn i V i eller till ingen av dem. Det är inte möjligt för ett minimalt ofullkomligt diagram att ha ett homogent par. Efter beviset på den starka perfekta grafgissningen förenklade Chudnovsky (2006) det genom att visa att homogena par kunde elimineras från den uppsättning sönderdelningar som användes i beviset.

Beviset för att varje Berge-graf faller i en av de fem grundklasserna eller har en av de fyra typerna av sönderdelning följer en fallanalys, beroende på om det finns vissa konfigurationer i diagrammet: en "bår", en subgraf som kan sönderdelas i tre inducerade banor som är föremål för vissa ytterligare begränsningar, komplementet av en bår och ett "ordentligt hjul", en konfiguration relaterad till ett hjuldiagram , bestående av en inducerad cykel tillsammans med ett navkropp intill åtminstone tre cykelhörn och följer flera ytterligare begränsningar. För varje möjligt val om en bår eller dess komplement eller ett korrekt hjul existerar inom den givna Berge-grafen, kan grafen visas i en av grundklasserna eller vara nedbrytbar. Denna fallanalys kompletterar beviset.

Anteckningar

Referenser

externa länkar