Pojdi na vsebino

Hedetniemijeva domneva

Iz Wikipedije, proste enciklopedije
Zgled Hedetniemijeve domneve: tenzorski produkt cikličnih grafov in (na levi) tvori graf, ki vsebuje cikel z dolžino 15 (na desni) – nastali graf za barvanje po točkah potrebuje 3 barve.

Hedetniemijeva domneva je v teoriji grafov domneva, ki jo je formuliral Stephen Travis Hedetniemi leta 1966. Obravnava povezavo med barvanjem grafov po točkah in tenzorskim produktom grafov. Domneva pravi, da velja:

kjer χ(G) označuje kromatično število neusmerjenega končnega grafa G.

Neenakost χ(G × H) ≤ min {χ(G), χ(H)} je enostavno razumljiva – če je graf G k-pobarvan, se lahko produkt G × H k-pobarva z enakim barvanjem za vsako kopijo G v produktu, ter simetrično, če je H k-pobarvan. Tako Hedetniemijeva domneva pomeni, da se tenzorskih produktov ne da pobarvati z nepričakovano majhnim številom barv.

Protiprimer domneve je odkril Jaroslav Nikolajevič Šitov leta 2019 in tako v splošnem ovrgel domnevo.[1][2] Dokaz Šitova je zgoščen in napisan na treh straneh.[3]

Znani primeri

[uredi | uredi kodo]

Vsak graf z neprazno množico povezav zahteva vsaj dve barvi: če grafa G in H nista 1-pobarvljiva, oziroma, da, če vsebujeta povezavo, tudi njun produkt vsebuje povezavo in prav tako ni 1-pobarvljiv. Še posebej domneva velja, če sta grafa G ali H dvodelna, saj je njuno kromatično število enako 1 ali 2.

Podobno, če dva grafa G in H nista 2-pobarvljiva, oziroma nista dvodelna, potem oba vsebujeta cikel s sodo dolžino. Ker produkt dveh sodih cikličnih grafov vsebuje sodi cikel, prav tako tudi produkt G × H ni 2-pobarvljiv. Z drugimi besedami, če je produkt G × H 2-pobarvljiv, mora biti tudi vsaj eden od grafov G in H 2-pobarvljiv.

Naslednji primer sta dokazala El-Zahar in Sauer leta 1985 dolgo časa po formulaciji domneve: če je produkt G × H 3-pobarvljiv, mora biti tudi eden od grafov G ali H 3-pobarvljiv. Še posebej velja domneva kadar sta graf G ali H 4-pobarvljiva, saj neenakost strogo velja, če je produkt G × H 3-pobarvljiv.[4] V peostalih primerih sta grafa v tenzorskem produktu vsaj 5-kromatična, napredek pa so dosegli le za zelo omejene primere.

Šibka Hedetniemijeva domneva

[uredi | uredi kodo]

Naslednja funkcija (znana kot Poljak-Rödlova funkcija) meri kako majhno je lahko kromatično število produkta n-kromatičnih grafov:

Hedetniemijeva domneva je potem enakovredna izjavi, da je .

Šibka Hedetniemijeva domneva pravi samo, da je funkcija neomejena. Z drugimi besedami, če se tenzorski produkt dveh grafov lahko pobarva z malo barvami, mora to obsegati neko mejo za kromatično število enega od faktorjev.

Glavni rezultat, ki so ga neodvisno izboljšali Svatopluk Poljak, James H. Schmerl in Zhu, pravi, da, če je funkcija omejena, je omejena največ za kromatično število 9.[5] Tako bi dokaz Hedetniemijeve domneve za 10-kromatične grafe obsegal tudi šibko Hedetniemijevo domnevo za vse grafe.

Multiplikativni grafi

[uredi | uredi kodo]

Domneva se obravnava v splošnejšem kontekstu homomorfizmov grafov, še posebej zaradi zanimivih povezav s kategorijo grafov (z grafi kot objekti in homomorfizmi kot puščicami). Za poljubni fiksni graf K se obravnava graf G, ki dodovoljuje homomorfizem h grafu K, kar se napiše kot GK. Takšni grafi se imenujejo tudi K-pobarvljivi grafi. To posplošuje običajno predstavo barvanja grafov, saj sledi iz definicije, da je k-barvanje enako Kk-barvanju (homomorfizmu v polni graf na k točkah).

Graf K se imenuje multiplikativen, da, če za poljubna dva grafa G in H velja G × HK, potem od tod izhaja, da velja GK ali HK. Kakor pri klasičnem barvanju vedno velja obratna posledica: če je graf G (ali simetrično graf H) K-pobarvljiv, je enostavno produkt G × H K-pobarvan s pomočjo enakih vrednosti neodvisno od grafa H. Hedetniemijeva domneva je potem enakovredna izjavi, da je vsak polni graf multiplikativen.

Zgornji znani primeri so enakovredni izjavi, da so K1, K2 in K3 multiplikativni. Primer za K4 je nerešen. Na drugi strani so dokaz El-Zaharja in Sauerja[4] posplošili Häggkvist, Hell, Miller in Neumann-Lara leta 1988 in pokazali, da so vsi ciklični grafi multiplikativni.[6] Kasneje je Tardiff leta 2005 dokazal splošneje, da so vse ciklične klike Kn/k z n/k < 4 multiplikativne.[7] Glede na ciklično kromatično število χc to pomeni, da če velja χc(G×H) < 4, potem velja χc(G×H) = min {χc(G), χc(G)} .

Zgledi nemultiplikativnih grafov se lahko skonstruirajo iz dveh grafov G in H, ki nista primerljiva v redu homomorfizma (pri čemer ne velja GH niti HG). V tem primeru, če je K = G × H, trivialno izhaja G × HK, vendar tako G ali H ne moreta dovoljevati homomorfizma v K, ker bi sestavljena s projekcijo KH ali KG vodila do protislovja.

Eksponentni graf

[uredi | uredi kodo]

Ker je tenzorski produk grafov produkt teorije kategorij v kategoriji grafov (z grafi kot objekti in homomorfizmi kot puščicami), se lahko domneva na novo formulira glede na naslednjo konstrukcijo na grafih K in G. Eksponentni graf KG je graf z vsemi funkcijami V(G)V(K) kot točkami (ne samo homomorfizmi) in dvema funkcijama f in g, sosednjima kadar je

f(v) sosednja z g(v') v K za vse sosednje točke v,v ' grafa G.

Pri funkciji f še posebej obstaja zanka (je sosednja sama s seboj) tedaj in le tedaj, če funkcija da homomorfizem iz G v K. Ali drugače, med f in g obstaja povezava kadarkoli dve funkciji definirata homomorfizem iz G × K2 (dvodelno dvojno pokritje G) h K.

Eksponentni graf je eksponencial v kategoriji grafov. To pomeni, da homomorfizmi iz G × H v graf K odgovarjajo homomorfizmom iz H v KG. Velja še naprej, da obstaja homomorfizem eval : G × KGK, dan z eval(v,f) = f(v). Te značilnosti dovoljujejo sklep, da je multiplikativnost K enakovredna izjavi El-Zaharja in Sauerja:[4]

graf G ali KG je K-pobarvljiv za vsak graf G.

Hedetniemijeva domneva se lahko z drugimi besedami obravnava kot izjava na eksponentnih grafih: za vsako celo število k je graf KkG ali k-pobarvljiv, ali pa vsebuje zanko (kar pomeni, da je graf G k-pobarvljiv). Homomorfizmi eval : G × KkGKk se lahko imajo za najmočnejše primere Hedetniemijeve domneve: če je bil G × H protiprimer, bo tudi G × KkG.

Posplošitve

[uredi | uredi kodo]

Domneva posplošena na usmerjene grafe ima enostavne protiprimere, kakor sta odkrila Poljak in Rödl.[5] Tukaj je kromatično število usmerjenega grafa le kromatično število osnovnega grafa, tenzorski produkt pa ima natanko polovico števila povezav (za usmerjene povezave gg' v G in hh' v H ima tenzorski produkt G × H le eno povezavo, iz (g, h) v (g', h'), produkt osnovnih neusmerjenih grafov pa bi imel tudi povezavo med(g, h') in (g', h)). Izkaže se vseeno, da je šibka Hedetniemijeva domneva enakovredna pri usmerjenih in neusmerjenih grafih.[8]

Problema se ne da posplošiti na neskončne grafe: Hajnal je leta podal zgled dveh neskončnih grafov, ki sta vsak zase zahtevala neštevno mnogo barv, tako da se je njun produkt lahko pobarval samo s števno mnogo barvami.[9] Rinot je leta 2013 dokazal, da v konstruktibilnem univerzumu za vsako neskončno kardinalno število obstaja par grafov s kromatičnim številom večjim od , tako da se njun produkt še vedno lahko pobarva samo s števno mnogo barvami.[10]

Sorodni problemi

[uredi | uredi kodo]

Podobno neenakost za kartezični produkt grafov je dokazal Sabidussi leta 1957, drugi pa so ga večkrat ponovno neodvisno dokazali:[11][2][12]

Tudi za leksikografski produkt grafov je znana eksaktna formula. Duffus, Sands in Woodrow so leta 1985 uvedli dve močnejši domnevi, ki vsebujeta edinstveno pobarvljivost.[13]

Sklici

[uredi | uredi kodo]
Osnovni viri
  • Duffus, Dwight; Sands, B.; Woodrow, R. E. (1985), »On the chromatic number of the product of graphs«, Journal of Graph Theory, 9 (4): 487–495, doi:10.1002/jgt.3190090409, MR 0890239
  • El-Zahar, Mohamed; Sauer, Norbert (1985), »The chromatic number of the product of two 4-chromatic graphs is 4«, Combinatorica, 5 (2): 121–126, doi:10.1007/BF02579374, MR 0815577
  • Foniok, Jan; Tardif, Claude (9. avgust 2016), Hedetniemi's conjecture and adjoint functors in thin categories, arXiv:1608.02918
  • Häggkvist, R.; Hell, Pavol; Miller, D. J.; Neumann-Lara, Victor (1988), »On multiplicative graphs and the product conjecture«, Combinatorica, 8 (1): 63–74, doi:10.1007/BF02122553, MR 0951994
  • Hajnal, András (1985), »The chromatic number of the product of two ℵ1 chromatic graphs can be countable«, Combinatorica, 5 (2): 137–140, doi:10.1007/BF02579376, MR 0815579
  • Hedetniemi, Stephen Travis (1966), Homomorphisms of graphs and automata, Technical Report 03105-44-T, Univerza Michigana
  • Poljak, Svatopluk; Rödl, Vojtěch (1981), »On the arc-chromatic number of a digraph«, Journal of Combinatorial Theory, Series B, 31 (2): 190–198, doi:10.1016/S0095-8956(81)80024-X
  • Rinot, Assaf (2013), Hedetniemi's conjecture for uncountable graphs, arXiv:1307.6841, Bibcode:2013arXiv1307.6841R
  • Sabidussi, Gert (1957), »Graphs with given group and given graph-theoretical properties«, Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810
  • Šitov, Jaroslav Nikolajevič (Maj 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
  • Tardif, Claude (2005), »Multiplicative graphs and semi-lattice endomorphisms in the category of graphs«, Journal of Combinatorial Theory, Series B, 95 (2): 338–345, doi:10.1016/j.jctb.2005.06.002
  • Tardif, Claude; Wehlau, David (2006), »Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function«, Journal of Graph Theory, 51 (1): 33–36, doi:10.1002/jgt.20117
Pregledi in drugi viri