Hedetniemis gissning

Exempel på Hedetniemis gissning : tensorprodukten av C5 och C3 (till vänster) producerar en graf som innehåller en cykel med längden 15 (till höger) så: den resulterande grafen kräver 3 färger.

Inom grafteorin rör Hedetniemis gissning , formulerad av Stephen T. Hedetniemi 1966, sambandet mellan graffärgning och grafers tensorprodukt . Denna gissning säger det

Här betecknar kromatiska talet för en oriktad finit graf .

Olikheten χ( G × H ) ≤ min {χ( G ), χ( H )} är lätt: om G är k -färgad kan man k -färga G × H genom att använda samma färg för varje kopia av G i produkten; symmetriskt om H är k -färgad. Hedetniemis gissning motsvarar alltså påståendet att tensorprodukter inte kan färgas med ett oväntat litet antal färger.

Ett motexempel till gissningen upptäcktes av Yaroslav Shitov ( 2019 ) (se Kalai 2019 ), vilket motbevisar gissningen i allmänhet.

Kända fall

Varje graf med en icke-tom uppsättning kanter kräver minst två färger; om G och H inte är 1-färgbara, det vill säga de båda innehåller en kant, så innehåller deras produkt också en kant, och är därför inte 1-färgbar heller. I synnerhet är gissningen sann när G eller H är en tvådelad graf, eftersom dess kromatiska tal är antingen 1 eller 2.

På liknande sätt, om två grafer G och H inte är 2-färgbara, det vill säga inte tvådelade , innehåller båda en cykel med udda längd. Eftersom produkten av två grafer med udda cykel innehåller en udda cykel, är produkten G × H inte heller 2-färgbar. Med andra ord, om G × H är 2-färgbar, måste minst en av G och H också vara 2-färgbar.

Nästa fall har bevisats långt efter antagandets uttalande, av El-Zahar & Sauer (1985) : om produkten G × H är 3-färgbar, måste en av G eller H också vara 3-färgbar. I synnerhet är gissningen sann närhelst G eller H är 4-färgbar (eftersom olikheten χ( G × H ) ≤ min {χ( G ), χ( H )} endast kan vara strikt när G × H är 3- färgbar). I de återstående fallen är båda graferna i tensorprodukten minst 5-kromatiska och framsteg har endast gjorts för mycket begränsade situationer.

Svag Hedetniemi gissning

Följande funktion (känd som Poljak-Rödl-funktionen ) mäter hur lågt det kromatiska antalet produkter av n -kromatiska grafer kan vara.

Hedetniemis gissning motsvarar då att f ( n ) = n . Den svaga Hedetniemi-förmodan säger istället bara att funktionen f ( n ) är obegränsad. Med andra ord, om tensorprodukten av två grafer kan färgas med få färger, bör detta innebära en viss gräns för det kromatiska numret för en av faktorerna.

Huvudresultatet av ( Poljak & Rödl 1981 ), oberoende förbättrat av Poljak, James H. Schmerl och Zhu, säger att om funktionen f ( n ) är begränsad, så är den begränsad av högst 9. Alltså ett bevis på Hedetniemis gissningar för 10-kromatiska grafer skulle redan innebära den svaga Hedetniemi-förmodan för alla grafer.

Multiplikativa grafer

Gissningarna studeras i det mer allmänna sammanhanget av grafhomomorfismer , särskilt på grund av intressanta relationer till kategorin grafer (med grafer som objekt och homomorfismer som pilar). För varje fast graf K , betraktar man grafer G som medger en homomorfism till K , skrivna G → K. Dessa kallas även K -färgbara grafer. Detta generaliserar den vanliga uppfattningen om graffärgning, eftersom det följer av definitioner att en k -färgning är detsamma som en K k -färgning (en homomorfism till hela grafen på k hörn).

En graf K kallas multiplikativ om för några grafer G , H , det faktum att G × H → K gäller innebär att G → K eller H → K gäller. Som med klassiska färger gäller alltid den omvända implikationen: om G (eller H , symmetriskt) är K -färgbar, så är G × H lätt K -färgad genom att använda samma värden oberoende av H . Hedetniemis gissning motsvarar då påståendet att varje komplett graf är multiplikativ.

Ovanstående kända fall är ekvivalenta med att säga att K 1 , K 2 och K 3 är multiplikativa. Fallet med K 4 är vida öppet. Å andra sidan har beviset från El-Zahar & Sauer (1985) generaliserats av Häggkvist et al. (1988) för att visa att alla cykeldiagram är multiplikativa. Senare Tardif (2005) mer generellt att alla cirkulära klick K n/k med n/k < 4 är multiplikativa. När det gäller det cirkulära kromatiska talet χ c betyder detta att om χ c ( G × H ) < 4 , så är χ c ( G × H ) = min { χ c ( G ), χ c ( G )} . Wrochna (2017) har visat att kvadratfria grafer är multiplikativa.

Exempel på icke-multiplikativa grafer kan konstrueras från två grafer G och H som inte är jämförbara i homomorfismordningen (det vill säga, varken G → H eller H → G gäller). I det här fallet, om vi låter K = G × H , har vi trivialt G × H → K , men varken G eller H kan erkänna en homomorfism till K , eftersom det skulle ge en motsägelse, sammansatt med projektionen K → H eller K → G.

Exponentiell graf

Eftersom tensorprodukten av grafer är den kategoriteoretiska produkten i kategorin grafer (med grafer som objekt och homomorfismer som pilar), kan gissningen omformuleras i termer av följande konstruktion på graferna K och G . Exponentialgrafen K G är grafen med alla funktioner V(G) → V(K) som hörn (inte bara homomorfismer) och två funktioner f , g intill när

f(v) är intill g(v') i K , för alla angränsande hörn v , v ' i G.

I synnerhet finns det en slinga vid en funktion f (den ligger intill sig själv) om och endast om funktionen ger en homomorfism från G till K . Sett på olika sätt finns det en kant mellan f och g närhelst de två funktionerna definierar en homomorfism från G × K 2 (det tvådelade dubbelhöljet av G ) till K .

Den exponentiella grafen är det exponentiella objektet i kategorin grafer. Detta betyder att homomorfismer från G × H till en graf K motsvarar homomorfier från H till K G . Dessutom finns det en homomorfism eval : G × K G → K ges av eval( v , f ) = f ( v ) . Dessa egenskaper gör det möjligt att dra slutsatsen att multiplikativiteten av K är ekvivalent ( El-Zahar & Sauer 1985) med påståendet:

antingen G eller K G är K -färgbar, för varje graf G .

Med andra ord kan Hedetniemis gissning ses som ett påstående om exponentiella grafer: för varje heltal k är grafen K k G antingen k -färgbar, eller så innehåller den en slinga (vilket betyder att G är k -färgbar). Man kan också se homomorfismerna eval : G × K k G → K k som de svåraste exemplen på Hedetniemis gissningar: om produkten G × H var ett motexempel, så skulle G × K k G också vara ett motexempel.

Generaliseringar

Generaliserad till riktade grafer har gissningen enkla motexempel, som observerats av Poljak & Rödl (1981) . Här är det kromatiska talet för en riktad graf bara det kromatiska numret för den underliggande grafen, men tensorprodukten har exakt hälften av antalet kanter (för riktade kanter g→g' i G och h →h' i H , tensorn produkt G × H har bara en kant, från (g,h) till (g',h') , medan produkten av de underliggande oriktade graferna skulle ha en kant mellan (g,h') och (g',h) också). Den svaga Hedetniemi-förmodan visar sig dock vara likvärdig i de riktade och oriktade inställningarna ( Tardif & Wehlau 2006) .

Problemet kan inte generaliseras till oändliga grafer: Hajnal (1985) gav ett exempel på två oändliga grafer, som var och en kräver ett oräkneligt antal färger, så att deras produkt kan färgas med bara oräkneligt många färger. Rinot (2013) bevisade att i det konstruerbara universum , för varje oändlig kardinal , finns det ett par grafer med ett kromatiskt tal större än , så att deras produkt fortfarande kan färgas med bara oräkneligt många färger.

Relaterade problem

En liknande likhet för den kartesiska produkten av grafer bevisades av Sabidussi (1957) och återupptäcktes flera gånger efteråt. En exakt formel är också känd för den lexikografiska produkten av grafer . Duffus, Sands & Woodrow (1985) introducerade två starkare gissningar som involverade unik färgbarhet.

Primära källor
Undersökningar och sekundära källor

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Hedetniemi%27s_conjecture&oldid=1032101281 "