Frankl–Rödl graf

Frankl–Rödl-grafen ${\displaystyle \operatorname {FR} _{1/3}^{3}} ,$ bildad genom att förbinda hörn på två avstånd från varandra i en tredimensionell kub

I grafteori och beräkningskomplexitetsteori är en Frankl–Rödl-graf en graf som definieras genom att koppla ihop par av hörn i en hyperkub som är på ett specificerat jämnt avstånd från varandra. Graferna av denna typ parametriseras av hyperkubens dimension och av avståndet mellan intilliggande hörn.

Frankl–Rödl-grafer är uppkallade efter Péter Frankl och Vojtěch Rödl , som bevisade 1987 att de (för vissa intervall av grafparametrarna) har ett litet oberoendetal och högt kromatiskt tal . De har sedan dess blivit intressanta för beräkningskomplexitetsteoretiker, som svåra exempel på semidefinite programmeringsbaserade approximationsalgoritmer för problem med vertextäckning och graffärgning . Deras egenskaper med avseende på dessa algoritmer har använts för att ifrågasätta den unika spelförmodan .

Definition och exempel

Frankl–Rödl-grafen $\operatorname {FR} _{1/2}^{4}$ består av två kopior av cocktailpartygrafen K _2,2,2,2 .

Frankl–Rödl-grafen $\operatorname {FR} _{1/5}^{5}$ består av två kopior av den 5-regelbundna Clebsch-grafen .

Låt n vara ett positivt heltal och låt γ vara ett reellt tal i enhetsintervallet 0 ≤ γ ≤ 1 . Antag dessutom att (1 − γ ) n är ett jämnt tal . Då är Frankl–Rödl-grafen FR $\displaystyle \operatorname {FR} _{\gamma }^{n}}$ grafen på de 2 ⁿ hörnen av en n -dimensionell enhetshyperkub [0,1] ⁿ där två hörn ligger intill varandra när deras Hamming-avstånd (antalet koordinater där de två skiljer sig åt) är exakt (1 − γ ) n . Här är kravet att (1 − γ ) n är jämnt nödvändigt för att förhindra att resultatet blir en tvådelad graf . Frankl–Rödl-grafen kommer nödvändigtvis att kopplas bort (med minst en ansluten komponent för var och en av de två sidorna av bipartitionen av motsvarande hyperkubgraf ) men detta är icke-problematiskt för dess tillämpningar.

Som ett exempel, Frankl–Rödl-grafen $\operatorname {FR} _{1/3}^{3}$ kopplar hörn två steg ifrån varandra i en vanlig tredimensionell kub, som visas i illustration. Geometriskt bildar detta anslutningsmönster en form som kallas stella octangula ; grafteoretiskt sett bildar den två sammankopplade komponenter, som var och en är en komplett graf med fyra vertex . På liknande sätt kopplar Frankl–Rödl-grafen $\operatorname {FR} _{1/2}^{4}$ samman hörn två steg ifrån varandra i en fyrdimensionell hyperkub, och resulterar i en graf som består av två exemplar av cocktailpartygrafen K _2,2,2,2 . De två Frankl–Rödl-graferna av dimension fem, $\operatorname {FR} _{1/5}^{5}$ och $\operatorname {FR} _{ 3/5}^{5}$ , är var och en bildad av två kopior av de två kompletterande Clebsch-graferna av grad fem respektive tio.

Egenskaper

Frankl–Rödl-grafen $\operatorname {FR} _{\gamma }^{n}$ är en vanlig graf , av grad

${\binom {n}{(1-\gamma )n}}.$

Den ärver symmetrierna i sin underliggande hyperkub, vilket gör den till en symmetrisk graf .

Som Frankl & Rödl (1987) visade, när γ ≤ 1/4 , storleken på en maximal oberoende mängd i en Frankl–Rödl-graf $\operatorname {FR} _{\gamma }^{n}$ är

$n(2-\Omega (\gamma )^{2})^{n}.$

Ω i denna formel är en instans av stor Ω notation . För konstanta värden på γ och variabeln n är denna oberoende uppsättningsstorlek en liten del av grafens 2 ^{n hörn.} Närmare bestämt är denna bråkdel omvänt proportionell mot en exponentialfunktion av n och en polynomfunktion av grafstorleken. Eftersom varje färg i korrekt färgning av Frankl–Rödl-grafen bildar en oberoende uppsättning med få hörn, måste antalet färger vara stort (återigen, en polynomfunktion av grafstorleken).

I beräkningskomplexitet

med vertextäckning innebär att hitta en uppsättning hörn som rör vid varje kant av grafen. Det är NP-hårt men kan approximeras till inom ett approximationsförhållande på två, till exempel genom att ta slutpunkterna för de matchade kanterna i någon maximal matchning . Bevis på att detta är det bästa möjliga approximationsförhållandet för en polynom-tidsapproximationsalgoritm tillhandahålls av det faktum att, när det representeras som ett semidefinite program , har problemet ett integralitetsgap på två; detta gap är förhållandet mellan lösningsvärdet för heltalslösningen (ett giltigt vertextäcke) och dess semidefinita relaxation . Enligt den unika spelförmodan , för många problem som detta tillhandahålls det optimala approximationsförhållandet av integritetsgapet för deras semidefinita avslappning. Frankl–Rödl-graferna tillhandahåller dock de enda kända fallen av vertextäckning för vilka integralitetsgapet kan vara så dåligt som två.

Frankl–Rödl-grafer har också använts för att studera semidefinita approximationer för graffärgning. Särskilt i denna applikation har forskare studerat graf 3-färgbarhet i samband med Frankl–Rödl-graferna med parametern γ = 1/4 . Även om Frankl–Rödl-graferna med detta parametervärde har högt kromatiskt tal, kan semidefinite programmering inte skilja dem från 3-färgbara grafer. Men för dessa grafer kan algebraiska metoder baserade på polynomsummor av kvadrater ge starkare gränser som bekräftar deras behov av många färger. Detta resultat utmanar optimaliteten av semidefinite programmering och riktigheten av den unika spelförmodan.