Hedetniemis hypotese

Hedetniemis formodning er en matematisk hypotese , generelt tilbagevist, en antagelse om forholdet mellem graffarvning og graftensorprodukt :

{\displaystyle \chi (G\ gange H)=\min\{\chi (G),\chi (H)\))

hvor er det kromatiske tal for en urettet finit graf . $\chi (G)$ $G$

Formuleret af Stephen Hedetniemi i 1966 .

I 2019 afviste den russiske matematiker Yaroslav Shitov formodningen ved at foreslå et modeksempel til den [1] [2] .

Uligheden er let at bekræfte - hvis grafen er farvet i farver, kan den farves i farver ved at bruge den samme farve for hver kopi i produktet, det symmetriske ræsonnement indebærer en begrænsning på . Hedetniemis formodning siger således, at tensorprodukter ikke kan farves med et uventet lille antal farver. ${\displaystyle \chi (G\ gange H)\leqslant \min\{\chi (G),\chi (H)\))$ $G$ $k$ $G\ gange H$ $k$ $G$ $H$

Særlige tilfælde, hvor hypotesen er sand

Enhver graf med et ikke-tomt kantsæt kræver mindst to farver. Hvis og ikke er 1-farvet, det vil sige begge indeholder en kant, så indeholder deres produkt også en kant, og er derfor heller ikke 1-farvet. Især er formodningen sand, når eller er todelte grafer, da deres kromatiske tal er enten 1 eller 2. $G$ $H$ $G$ $H$

Tilsvarende, hvis to grafer og ikke er 2-farvede, dvs. ikke todelte , så indeholder begge en cyklus med ulige længde. Da produktet af to ulige cyklusser indeholder en ulige cyklus, kan produktet heller ikke være 2-farvet. Med andre ord, hvis det er 2-farverbart, så skal mindst én af graferne eller være 2-farverbart. $G$ $H$ $G\ gange H$ $G\ gange H$ $G$ $H$

Følgende tilfælde blev bevist meget senere ved formuleringen af formodningen af El-Zahar og Sauer [3] - hvis et produkt kan farves med 3 farver, så en af graferne eller skal også tillade farvning med 3 farver. Især er formodningen sand, når eller tillader en 4-farvet farvning (fordi så kan uligheden kun være streng, når den tillader en 3-farvet farvning). Ellers skal begge grafer i et tensorprodukt være mindst 5-farvede, og der sker kun yderligere fremskridt i meget begrænsede situationer. $G\ gange H$ $G$ $H$ $G$ $H$ ${\displaystyle \chi (G\ gange H)\leqslant \min\{\chi (G),\chi (H)\))$ $G\ gange H$

Hedetniemis svage formodning

Den følgende funktion (kendt som Polak-Rödl-funktionen ) måler, hvor lille det kromatiske antal af et produkt af -kromatiske grafer kan være. $n$

{\displaystyle f(n)=\min\{\chi (G\ gange H):\chi (G)=\chi (H)=n\))

Hedetniemi-formodningen svarer da til at sige, at . Hedetniemis svage formodning siger i stedet blot, at funktionen er ubegrænset. Med andre ord, hvis tensorproduktet af to grafer kan farves med flere farver, bør dette indebære en begrænsning af det kromatiske antal af en af faktorerne. $f(n)=n$ $f(n)$

Polak og Rödls hovedresultat [4] , uafhængigt forbedret af Polak, Schmerl og Zu, siger, at hvis en funktion er begrænset, så er den højst afgrænset af 9. Så ville beviset for Hedetniemis formodning for 10-kromatiske grafer indebære Hedetniemis svage formodning for alle grafer. $f(n)$

Multiplikative grafer

Formodningen studeres i den mere generelle kontekst af grafhomomorfismer , især i lyset af dens sammenhæng med kategorien grafer (med grafer som objekter og homomorfier som pile). For enhver fast graf betragter vi grafer , der indrømmer en homomorfi til , som er skrevet som . Sådanne grafer kaldes også -farverbare . Dette generaliserer den sædvanlige opfattelse af graffarvning, da det følger af definitionen, at en -farvning er det samme som en -farvning (en homomorfi til en komplet graf med hjørner). $K$ $G$ $K$ $G\to K$ $K$ $k$ $K_k$ $k$

En graf kaldes multiplikativ , hvis for nogen grafer og udførelse følger eller . Som med klassisk farvning er det omvendte altid sandt - hvis (eller symmetrisk ) -farverbar, så let -farverbar ved at bruge de samme farveværdier for alle kopier af . Hedetniemis formodning svarer da til at sige, at enhver komplet graf er multiplikativ. $K$ $G$ $H$ $G\times H\to K$ $G\to K$ $H\to K$ $G$ $H$ $K$ $G\ gange H$ $K$ $H$

De velkendte tilfælde nævnt ovenfor svarer til udsagn om, at graferne , og er multiplikative. Sagen er vidt åben. På den anden side blev beviset for El-Zahara og Sauer [3] generaliseret af Heggquist, Hell, Miller og Neumann-Lara [5] , hvilket beviser, at alle cyklusgrafer er multiplikative. Senere beviste Tardif [6] et mere generelt resultat, at alle cykliske kliker med er multiplikative. Med hensyn til det cykliske kromatiske tal betyder det, at hvis , så . $K_1$ $K_{2}$ $K_{3}$ $K_{4}$ $K_{\tfrac {n}{k))$ ${\tfrac {n}{k}}<4$ $\chi _{c}$ $\chi _{c}(G\ gange H)<4$ ${\displaystyle \chi _{c}(G\ gange H)=\min\{\chi _{c}(G),\chi _{c}(G)\))$

Eksempler på ikke-multiplikative grafer kan konstrueres ud fra to grafer og , som er uforlignelige i rækkefølgen af homomorfismer (det vil sige , ingen af dem gælder). I dette tilfælde danner , Vi opnår trivielt , men hverken , eller har en homomorfi i , da, danner projektionen eller , Vi får en modsigelse. $G$ $H$ $G\to H$ $H\to G$ $K=G\ gange H$ $G\times H\to K$ $G$ $H$ $K$ $K\to H$ $K\to G$

Eksponentiel graf

Da tensorproduktet af grafer er et kategoriteoretisk produkt i kategorien grafer (med grafer som objekter og homomorfier som pile), kan formodningen omformuleres i forhold til følgende konstruktion på grafer og . En eksponentiel graf er en graf med alle funktioner som toppunkter (ikke kun homomorfismer) og to funktioner og er tilstødende, hvis et toppunkt støder op til et toppunkt i for alle tilstødende hjørner af grafen . Især en funktion har en løkke (den støder op til sig selv), hvis og kun hvis der er en homomorfi fra til . Set fra en anden vinkel kan vi sige, at der er en kant mellem og når to funktioner definerer en homomorfi fra ( Dobbelt todelt grafomslag af en graf ) til . $K$ $G$ $K^{G}$ $V(G)\til V(K)$ $f$ $g$ $f(v)$ $g(v')$ $K$ $v,v'$ $G$ $f$ $G$ $K$ $f$ $g$ ${\displaystyle G\ gange K_{2))$ $G$ $K$

En eksponentiel graf er en eksponentiel i kategorien grafer. Det betyder, at homomorfier fra til en graf svarer til homomorfier fra til . Desuden er der en homomorfi givet af . Disse egenskaber giver os mulighed for at konkludere, at multiplikativiteten af en graf svarer til udsagnet [3] : for alle grafer og enten , eller er -farverbar. $G\ gange H$ $K$ $H$ $K^{G}$ $\mathrm {eval} :G\ gange K^{G}\to K$ $\mathrm {eval} (v,f)=f(v)$ $K$ $G$ $K$ $G$ $K^{G}$ $K$

Med andre ord kan Hedetniemis formodning ses som et udsagn om eksponentielle grafer - for ethvert heltal er grafen enten -farverbar eller indeholder en loop (hvilket betyder, at den er -farverbar). Man kan også se homomorfismer som de sværeste tilfælde af Hedetniemis formodning – hvis produktet var et modeksempel, så ville det være et modeksempel. $k$ ${\displaystyle K_{k}^{G))$ $k$ $G$ $k$ ${\displaystyle \mathrm {eval} :G\ gange K_{k}^{G}\til K_{k))$ $G\ gange H$ $G\times K_{k}^{G}$

Generaliseringer

Generaliseringen til rettede grafer har et simpelt modeksempel, som vist af Polyak og Rödl [4] . Det kromatiske tal for en rettet graf er ganske enkelt det kromatiske tal for den tilsvarende urettede graf, men tensorproduktet har nøjagtigt halvdelen af antallet af kanter (for buer ved og til tensorproduktet har kun én kant fra til , mens produktet af urettet grafer har også en kant mellem og ). Det viser sig dog, at Hedetniemis svage formodning svarer til urettede og rettede grafer [7] . $g\to g'$ $G$ $h\to h'$ $H$ $G\ gange H$ $(g,h)$ $(g',h')$ $(g,h')$ $(g',h)$

Problemet kan ikke generaliseres til uendelige grafer - Heinl [8] gav et eksempel på to uendelige grafer, som hver kræver et uendeligt antal farver for at farvelægge, men deres produkt kan farves med et endeligt sæt af farver. Rhinoth [9] beviste, at der i det konstruktive univers for enhver uendelig kardinal eksisterer et par grafer med et kromatisk tal større end , således at produktet kun kan farves af et endeligt antal farver. $\kappa$ $\kappa$

Relaterede problemer

En lignende lighed for det direkte produkt af grafer blev bevist af Sabidoussi [10] og er blevet genopdaget flere gange siden da. Den nøjagtige formel er kendt for det leksikografiske produkt af grafer . Duffus, Sands og Woodrow [11] foreslog to stærkere formodninger med unik farve.

Noter

↑ Vladimir Potapov. På jagt efter kromatisk tal . N+1 (30. maj 2019). Hentet 30. maj 2019. Arkiveret fra originalen 30. maj 2019. (ubestemt)
↑ Yaroslav Shitov. Modeksempler til Hedetniemis formodning // Annals of Mathematics . - 2019. - September ( bind 190 , udg. 2 ). - s. 663-667. doi : 10.4007 / annals.2019.190.2.6 . - arXiv : 1905.02167 .
↑ 1 2 3 El-Zahar, Sauer, 1985 .
↑ 1 2 Poljak, Rödl, 1981 .
↑ Häggkvist, Hell, Miller, Neumann-Lara, 1988 .
↑ Tardif, 2005 .
↑ Tardif, Wehlau, 2006 .
↑ Hajnal, 1985 .
↑ Rinot, 2013 .
↑ Sabidussi, 1957 .
↑ Duffus, Sands, Woodrow, 1985 .

Litteratur

hovedkilder

Duffus D., Sands B., Woodrow RE Om det kromatiske tal for produktet af grafer // Journal of Graph Theory. - 1985. - T. 9 , no. 4 . — S. 487–495 . - doi : 10.1002/jgt.3190090409 .
El-Zahar M., Sauer N. Det kromatiske tal for produktet af to 4-kromatiske grafer er 4 // Combinatorica. - 1985. - V. 5 , no. 2 . — S. 121–126 . - doi : 10.1007/BF02579374 .
Häggkvist R., Hell P., Miller DJ, Neumann-Lara V. Om multiplikative grafer og produktformodningerne // Combinatorica . - 1988. - T. 8 , no. 1 . — S. 63–74 . - doi : 10.1007/BF02122553 .
Hajnal A. Det kromatiske antal af produktet af to ℵ 1 kromatiske grafer kan tælles // Combinatorica . - 1985. - V. 5 , no. 2 . — S. 137–140 . - doi : 10.1007/BF02579376 .
Hedetniemi S. Homomorfismer af grafer og automater. - University of Michigan, 1966. - (Teknisk rapport 03105-44-T).
Poljak S., Rödl V. Om det buekromatiske nummer af en digraf // Journal of Combinatorial Theory, Series B. - 1981. - T. 31 , nr. 2 . - S. 190-198 . - doi : 10.1016/S0095-8956(81)80024-X .
Rinot A. Hedetniemis formodning om utallige grafer. - 2013. - . - arXiv : 1307.6841 .
Sabidussi G. Grafer med given gruppe og givne grafteoretiske egenskaber // Canadian Journal of Mathematics . - 1957. - T. 9 . — S. 515–525 . - doi : 10.4153/CJM-1957-060-7 .
Tardif C. Multiplikative grafer og semi-gitter-endomorfismer i kategorien grafer // Journal of Combinatorial Theory, Series B . - 2005. - T. 95 , nr. 2 . - S. 338-345 . - doi : 10.1016/j.jctb.2005.06.002 .
Tardif C., Wehlau D. Kromatiske antal af produkter af grafer: De rettede og urettede versioner af Poljak-Rödl-funktionen // Journal of Graph Theory . - 2006. - T. 51 , nr. 1 . - S. 33-36 . - doi : 10.1002/jgt.20117 .

Anmeldelser og andre kilder

Wilfried Imrich, Sandi Klavzar. Produktgrafer: Struktur og anerkendelse. - Wiley, 2000. - ISBN 0-471-37039-8 .
Sandy Klavzar. Farvegrafprodukter: en undersøgelse // Diskret matematik . - 1996. - T. 155 , no. 1-3 . — S. 135–145 . - doi : 10.1016/0012-365X(94)00377-U .
Sauer N. Hedetniemis formodning: en undersøgelse // Diskret matematik . - 2001. - T. 229 , udg. 1-3 . — S. 261–292 . - doi : 10.1016/S0012-365X(00)00213-2 .
Claude Tardif. Hedetniemis formodning, 40 år senere // Graph Theory Notes of New York. - 2008. - T. 54 . - S. 46-57 .
Xuding Zhu. En undersøgelse af Hedetniemis formodning // Taiwanese J. Math.. - 1998. - Vol. 2 , nr. 1 . — S. 1–24 .
Et gennembrud i grafteori - Numberphile på YouTube