Hedetniemis dohad - Hedetniemis conjecture - Wikipedia

Příklad Hedetniemiho domněnka: tenzorový produkt C5 a C3 (vlevo) vytváří graf, který obsahuje cyklus s délkou 15 (vpravo), takže: výsledný graf vyžaduje 3 barvy.

v teorie grafů, Hedetniemiho domněnka, formuloval Stephen T. Hedetniemi v roce 1966 se týká spojení mezi zbarvení grafu a tenzorový součin grafů. Tato domněnka to říká

${ displaystyle chi (G krát H) = min { chi (G), chi (H) }.}$

Tady ${ displaystyle chi (G)}$ označuje chromatické číslo neorientovaného konečného grafu ${ displaystyle G}$.

Nerovnost χ (G × H) ≤ min {χ (G), χ (H)} je snadné: pokud G je k-barevné, jeden může k-barva G × H použitím stejného zbarvení pro každou kopii G ve výrobku; symetricky, pokud H je k-barevný. Hedetniemiho domněnka tedy znamená tvrzení, že tenzorové produkty nelze obarvit neočekávaně malým počtem barev.

Protiklad k domněnce objevil Yaroslav Shitov (2019 ) (viz Kalai 2019 ), čímž vyvrací domněnku obecně.

Známé případy

Jakýkoli graf s neprázdnou sadou hran vyžaduje alespoň dvě barvy; -li G a H nejsou 1-barevný, to znamená, že oba obsahují hranu, pak jejich produkt také obsahuje hranu, a proto také není 1-barevný. Zejména domněnka je pravdivá, když G nebo H je bipartitní graf, protože jeho chromatické číslo je buď 1 nebo 2.

Podobně, pokud dva grafy G a H nejsou 2barevné, to znamená, že ne bipartitní, pak oba obsahují cyklus liché délky. Protože produkt dvou lichých cyklické grafy obsahuje lichý cyklus, produkt G × H není ani 2-barevný. Jinými slovy, pokud G × H je dvoubarevný, pak alespoň jeden z G a H musí být také 2barevné.

Další případ byl prokázán dlouho po prohlášení dohadu, autor El-Zahar & Sauer (1985): pokud je výrobek G × H je tříbarevný, pak jeden z G nebo H musí být také 3barevné. Zejména domněnka je pravdivá kdykoli G nebo H je 4barevný (od té doby nerovnost χ (G × H) ≤ min {χ (G), χ (H)} může být přísný, pouze když G × H Ve zbývajících případech jsou oba grafy v tenzorovém produktu alespoň 5-chromatické a pokrok byl učiněn pouze ve velmi omezených situacích.

Slabá domněnka Hedetniemi

Následující funkce (známá jako Funkce Poljak-Rödl) měří, jak nízký je chromatický počet produktů z n-chromatické grafy mohou být.

${ displaystyle f (n) = min { chi (G krát H) dvojtečka chi (G) = chi (H) = n }}$

Hedetniemiho domněnka je pak ekvivalentní tomu, že se to říká F(n) = n.v Slabá domněnka Hedetniemi místo toho pouze uvádí, že funkce F(nJinými slovy, pokud lze tenzorový součin dvou grafů obarvit několika barvami, mělo by to znamenat určitou vazbu na chromatické číslo jednoho z faktorů.

Hlavní výsledek (Poljak a Rödl 1981 ), nezávisle vylepšené Poljakem, Jamesem H. Schmerlem a Zhu, uvádí, že pokud je funkce F(n) je ohraničen, pak je ohraničen maximálně 9. Důkaz Hedetniemiho domněnky pro 10-chromatické grafy by tedy již znamenal Slabý Hedetniemi domněnku pro všechny grafy.

Multiplikativní grafy

Domněnka je studována v obecnějším kontextu homomorfismy grafů, zejména kvůli zajímavým vztahům k EU kategorie grafů (s grafy jako objekty a homomorfismy jako šipky). Pro jakýkoli pevný graf K., uvažujeme grafy G které připouštějí homomorfismus K., psaný G → K.. Tito se také nazývají K.-barevné grafy. Toto zobecňuje obvyklou představu o zbarvení grafu, protože z definic vyplývá, že a k-barvení je stejné jako a K._k-barvení (homomorfismus do celého grafu na k vrcholy).

Graf K. je nazýván multiplikativní pokud pro nějaké grafy G, H, Skutečnost, že G × H → K. hold to naznačuje G → K. nebo H → K. Stejně jako u klasických barvení platí vždy reverzní implikace: pokud G (nebo H, symetricky) je K.- tedy barevný G × H je snadno K.-barevné použitím stejných hodnot nezávisle na HHedetniemiho domněnka je potom ekvivalentní tvrzení, že každý úplný graf je multiplikativní.

Výše uvedené známé případy jsou rovnocenné tomu, co se říká K.₁, K.₂, a K.₃ jsou multiplikativní. Případ K.₄ je široce otevřený. Na druhé straně, důkaz El-Zahar & Sauer (1985) byl zobecněn uživatelem Häggkvist a kol. (1988) ukázat, že všechny cyklické grafy jsou multiplikativní. Tardif (2005) obecněji dokázal, že vše kruhové kliky K._{n / k} s n / k <4 jsou multiplikativní. Z hlediska kruhové chromatické číslo χ_C, to znamená, že pokud χ_C(G×H) < 4, pak χ_C(G×H) = min { χ_C(G), χ_C(G)} . Wrochna (2017) ukázal, že grafy bez čtverců jsou multiplikativní.

Příklady non-multiplikativních grafů lze sestrojit ze dvou grafů G a H které nejsou srovnatelné v pořadí homomorfismu (tj. ani G→H ani H→G drží). V tomto případě nechám K.=G×H, máme triviálně G×H→K., ale ani jeden G ani H může přiznat homomorfismus do K., protože skládal s projekcí K.→H nebo K.→G bylo by to v rozporu.

Exponenciální graf

Protože tenzorovým produktem grafů je teoretický produkt kategorie v kategorii grafů (s grafy jako objekty a homomorfismy jako šipky) lze domněnku přeformulovat z hlediska následující konstrukce na grafech K. a G.v exponenciální graf K.^G je graf se všemi funkcemi V (G) → V (K) jako vrcholy (nejen homomorfismy) a dvě funkce F,G sousedící, když

F v) sousedí s g (v ') v K., pro všechny sousední vrcholy proti,v ' z G.

Zejména existuje smyčka u funkce F (přiléhá k sobě) právě tehdy, když funkce dává homomorfismus z G na K.Jinak řečeno, mezi nimi je hrana F a G kdykoli tyto dvě funkce definují homomorfismus z G × K.₂ (dále jen dvojdílný dvojitý kryt z G) až K..

Exponenciální graf je exponenciální objekt v kategorii grafů. To znamená homomorfismy z G × H do grafu K. odpovídají homomorfismům z H na K.^G. Navíc existuje homomorfismus eval: G × K.^G → K. dána eval (proti,F) = F(proti)Tyto vlastnosti umožňují dospět k závěru, že multiplikativita K. je ekvivalentní (El-Zahar & Sauer 1985 ) k prohlášení:

buď G nebo K.^G je K.-barevné, pro každý graf G.

Jinými slovy, Hedetniemiho domněnku lze považovat za prohlášení v exponenciálních grafech: pro každé celé číslo k, graf K._k^G je buď k-barevné, nebo obsahuje smyčku (to znamená G je kJeden může také vidět homomorfismy eval: G × K._k^G → K._k jako nejtěžší případy Hedetniemiho domněnky: je-li produkt G × H byl tedy protikladem G × K._k^G byl by také protikladem.

Zobecnění

Zobecněn na směrované grafy, domněnka má jednoduché protipříklady, jak je pozorováno Poljak & Rödl (1981). Zde je chromatické číslo směrovaného grafu pouze chromatické číslo podkladového grafu, ale tenzorový produkt má přesně poloviční počet hran (pro směrované hrany g → g ' v G a h → h ' v H, tenzorový produkt G × H má pouze jednu hranu, z (g, h) na (g ', h'), zatímco produkt podkladových neorientovaných grafů by měl hranu mezi (g, h ') a (g ', h) také). Ukázalo se však, že slabá domněnka Hedetniemi je ekvivalentní v nasměrovaném i neřízeném nastavení (Tardif & Wehlau 2006 ).

Problém nelze zobecnit na nekonečné grafy: Hajnal (1985) uvedl příklad dvou nekonečných grafů, z nichž každý vyžadoval nespočetné množství barev, takže jejich produkt lze obarvit pouze spočítatelně mnoha barvami. Rinot (2013) dokázal, že v konstruovatelný vesmír, pro každého nekonečného kardinála ${ displaystyle kappa}$, existuje dvojice grafů s chromatickým číslem větším než ${ displaystyle kappa}$, takže jejich produkt může být stále obarven pouze spočítatelně mnoha barvami.

Související problémy

Podobná rovnost pro kartézský součin grafů bylo prokázáno Sabidussi (1957) a znovu objeven několikrát poté. Přesný vzorec je také známý pro lexikografický součin grafů.Duffus, Sands & Woodrow (1985) představil dva silnější domněnky zahrnující jedinečnou barevnost.

Reference

Primární zdroje

• Duffus, D.; Sands, B .; Woodrow, R. E. (1985), „O chromatickém čísle součinu grafů“, Journal of Graph Theory, 9 (4): 487–495, doi:10,1002 / jgt.3190090409, PAN  0890239.
• El-Zahar, M .; Sauer, N. (1985), „Chromatické číslo produktu dvou 4-chromatických grafů je 4“, Combinatorica, 5 (2): 121–126, doi:10.1007 / BF02579374, PAN  0815577.
• Häggkvist, R .; Sakra, P.; Miller, D. J .; Neumann Lara, V. (1988), „O multiplikativních grafech a domněnce produktu“, Combinatorica, 8 (1): 63–74, doi:10.1007 / BF02122553, hdl:1828/1589, PAN  0951994.
• Hajnal, A. (1985), „Chromatické číslo součinu dvou ℵ₁ chromatické grafy lze spočítat ", Combinatorica, 5 (2): 137–140, doi:10.1007 / BF02579376, PAN  0815579.
• Hedetniemi, S. (1966), Homomorfismy grafů a automatů, Technical Report 03105-44-T, University of Michigan.
• Poljak, S .; Rödl, V. (1981), „Na oblouku-chromatické číslo digrafu“, Journal of Combinatorial Theory, Series B, 31 (2): 190–198, doi:10.1016 / S0095-8956 (81) 80024-X.
• Rinot, A. (2013), Hedetniemiho domněnka o nespočetných grafech, arXiv:1307.6841, Bibcode:2013arXiv1307.6841R.
• Sabidussi, G. (1957), „Grafy s danou skupinou a danými graficko-teoretickými vlastnostmi“, Kanadský žurnál matematiky, 9: 515–525, doi:10.4153 / CJM-1957-060-7, PAN  0094810.
• Shitov, Yaroslav (květen 2019), Protiklady k Hedetniemiho domněnce, arXiv:1905.02167.
• Tardif, C. (2005), „Multiplikativní grafy a semi-mřížkové endomorfismy v kategorii grafů“, Journal of Combinatorial Theory, Series B, 95 (2): 338–345, doi:10.1016 / j.jctb.2005.06.002.
• Tardif, C .; Wehlau, D. (2006), „Chromatická čísla produktů grafů: Řízená a neřízená verze funkce Poljak-Rödl“, Journal of Graph Theory, 51 (1): 33–36, doi:10.1002 / jgt.20117.
• Wrochna, M. (2017), „Grafy bez čtverců jsou multiplikativní“, Journal of Combinatorial Theory, Series B, 122: 479–507, arXiv:1601.04551, doi:10.1016 / j.jctb.2016.07.007.

Průzkumy a sekundární zdroje

• Imrich, Wilfried; Klavžar, Sandi (2000), Grafy produktů: Struktura a rozpoznáváníWiley, ISBN  0-471-37039-8.
• Kalai, Gil (10. května 2019), „Senzace v ranních zprávách - Yaroslav Shitov: protipříklady Hedetniemiho domněnky“, Kombinatorika a další.
• Klavžar, Sandi (1996), „Coloring graph products: a survey“, Diskrétní matematika, 155 (1–3): 135–145, doi:10.1016 / 0012-365X (94) 00377-U, PAN  1401366.
• Sauer, N. (2001), „Hedetniemiho domněnka: průzkum“, Diskrétní matematika, 229 (1–3): 261–292, doi:10.1016 / S0012-365X (00) 00213-2, PAN  1815610.
• Tardif, Claude (2008), „Hedetniemiho domněnka, o 40 let později“ (PDF), Teorie grafů z New Yorku, 54: 46–57, PAN  2445666.
• Zhu, Xuding (1998), „Průzkum Hedetniemiho domněnky“, Tchajwanský J. Math., 2 (1): 1–24, PAN  1609464.

externí odkazy

• Průlom v teorii grafů, Numberphile