ヘデトニエミの予想

グラフ理論において、 1966年にスティーブン・T・ヘデトニエミによって定式化されたヘデトニエミの予想は、グラフの色付けとグラフのテンソル積の関係に関するものである。この予想は、

\chi (G\times H)=\min\{\chi (G),\chi (H)\}.

ここでは無向有限グラフの彩色数を表します。 $\chi (G)$ $G$

不等式 χ( G × H ) ≤ min {χ( G ), χ( H )} は簡単です。G が k 色の場合、積内の G の各コピーに同じ色付けを使用して、G × H を k 色付けできます。Hが k 色の場合は対称的です。したがって、ヘデトニエミの予想は、テンソル積は予想外に少ない色数で色付けできないという主張に相当します。

この予想に対する反例がヤロスラフ・シトフ（2019）によって発見され（Kalai 2019を参照）、これによってこの予想は一般に反証されました。

既知の事例

空でないエッジの集合を持つグラフには、少なくとも 2 つの色が必要です。GとHが1色化可能でない場合、つまり、両方にエッジが含まれている場合、それらの積にもエッジが含まれており、したがって 1 色化可能ではありません。特に、GまたはHが 2 部グラフの場合、その彩色数は 1 または 2 であるため、この予想は当てはまります。

同様に、2 つのグラフGとHが 2 色可能でない場合、つまり二部グラフでない場合、両方とも奇数長のサイクルを含みます。2 つの奇数サイクルグラフの積には奇数サイクルが含まれるため、積G × Hも 2 色可能ではありません。言い換えると、G × Hが 2 色可能であれば、 GとHの少なくとも 1 つは2 色可能である必要があります。

次のケースは、予想が述べられてからずっと後に、El-Zahar & Sauer (1985) によって証明されました。積G × Hが 3 色可能である場合、GまたはHの 1 つも 3 色可能である必要があります。特に、この予想は、GまたはHが4 色可能である場合に常に当てはまります (そのため、不等式 χ( G × H ) ≤ min {χ( G ), χ( H )} は、 G × Hが 3 色可能である場合にのみ厳密になります)。残りのケースでは、テンソル積の両方のグラフが少なくとも 5 色であり、非常に限られた状況でのみ進歩が遂げられています。

弱いヘデトニエミ予想

次の関数 ( Poljak-Rödl 関数として知られています) は、 n彩色グラフの積の彩色数がどれだけ低くなるかを測定します。

f(n)=\min\{\chi (G\times H)\colon \chi (G)=\chi (H)=n\}

$ヘデトニエミの予想は、 f (n) = n$ と言っているのと同じです。弱いヘデトニエミの予想は、関数f ( n ) が無限大であることを単に述べています。言い換えると、2 つのグラフのテンソル積を少数の色で色付けできる場合、これは因子の 1 つの彩色数に何らかの制限があることを意味します。

(Poljak & Rödl 1981) の主な結果は、Poljak、James H. Schmerl、Zhu によって独立に改良され、関数f ( n ) が有界である場合、その有界性は最大で 9 であると述べています。したがって、10 彩色グラフに対するヘデトニエミ予想の証明は、すべてのグラフに対する弱いヘデトニエミ予想をすでに意味しています。

乗法グラフ

この予想は、グラフ準同型性のより一般的な文脈で研究されている。特に、グラフのカテゴリ（グラフをオブジェクト、準同型性を矢印とする）との興味深い関係のためである。任意の固定グラフKに対して、 Kへの準同型性（ G → Kと表記）を許容するグラフGを考える。これらはK彩色可能グラフとも呼ばれる。これは、定義からk彩色はK _k彩色（ k頂点上の完全グラフへの準同型）と同じであることが分かるため、グラフ彩色の通常の考え方を一般化するものである。

グラフK は、任意のグラフG、Hについて、 G × H → Kが成り立つという事実がG → KまたはH → Kが成り立つことを意味する場合、乗法的と呼ばれます。古典的な彩色と同様に、逆の含意が常に成り立ちます。つまり、G (または対称的にH ) がK彩色可能である場合、G × H はHとは独立して同じ値を使用して簡単にK彩色されます。ヘデトニエミの予想は、各完全グラフが乗法的であるというステートメントと同等です。

上記の既知のケースは、K ₁、K ₂、およびK ₃が乗法的であると言うことと同等です。 K ₄の場合は広く未解決です。一方、 El-Zahar & Sauer (1985) の証明は、 Häggkvist ら (1988) によって一般化され、すべてのサイクルグラフが乗法的であることが示されました。その後、 Tardif (2005) は、n/k < 4のすべての円形クリーク K _n/kが乗法的であることをより一般的に証明しました。円形彩色数χ _cに関して、これは、 $χ$ $c$ $($ $G$ $\times$ $H$ $) < 4$ の場合、 $χ$ $c$ $($ $G$ $\times$ $H$ $) = min {$ $χ$ $c$ $($ $G$ $),$ $χ$ $c$ $($ $G$ $)}$ を意味します。 Wrochna (2017) は、正方形のないグラフが乗法的であることを示しました。

非乗法グラフの例は、準同型順序で比較できない（つまり、G → HもH → Gも成り立たない）2つのグラフGとHから構築できます。この場合、K = G × Hとすると、 G × H → Kが自明になりますが、GもHもKへの準同型を許容しません。これは、射影K → HまたはK → Gと合成すると矛盾が生じるためです。

指数グラフ

グラフのテンソル積はグラフの圏における圏論的積（グラフをオブジェクト、準同型を矢印とする）なので、この予想はグラフKとG上の次の構成で言い換えることができる。指数グラフ $K G$ は、すべての関数 $V(G) \to V(K)$ を頂点（準同型だけでなく）とし、2つの関数f、g が隣接するグラフである。

Gのすべての隣接頂点v、v 'について、 f(v)はK内のg(v')に隣接しています。

特に、関数fにループが存在する（関数 f はそれ自身に隣接している）のは、関数がGからKへの準同型を与える場合のみです。別の見方をすると、 2 つの関数がG × K ₂ （Gの二部二重被覆）からKへの準同型を定義するときはいつでも、fとgの間にエッジが存在します。

指数グラフは、グラフのカテゴリにおける指数オブジェクトです。つまり、 G × HからグラフKへの準同型は、 HからK ^Gへの準同型に対応します。さらに、 $eval($ $v$ $,$ $f$ $) =$ $f$ $($ $v$ $)$ で与えられる準同型 $eval : G \times K G \to K$ があります。これらの特性から、 Kの乗法性は次のステートメントと同等であると結論付けることができます (El-Zahar & Sauer 1985)。

すべてのグラフGに対して、G またはK Gは^K色可能です。

言い換えれば、ヘデトニエミの予想は指数グラフに関するステートメントとして見ることができます。つまり、すべての整数kに対して、グラフK _k^{G は}k色可能であるか、ループを含みます (つまり、Gはk色可能です)。準同型 $eval : G \times K k G \to K k$ もヘデトニエミの予想の最も難しい例と見なすことができます。つまり、積G × Hが反例である場合、G × K _k^Gも反例になります。

一般化

この予想を有向グラフに一般化すると、Poljak & Rödl (1981) が指摘したように、簡単な反例が存在します。ここで、有向グラフの彩色数は基になるグラフの彩色数とまったく同じですが、テンソル積の辺の数はちょうど半分になります ( Gの有向辺g→g'とH の有向辺h→h'の場合、テンソル積G × Hには(g,h)から(g',h')への辺が 1 つだけありますが、基になる無向グラフの積には(g,h')と(g',h)の間にも辺があります)。ただし、弱いヘデトニエミ予想は有向設定と無向設定で同等であることが判明しています (Tardif & Wehlau 2006)。

この問題は無限グラフに一般化することはできません。Hajnal (1985) は、それぞれが無数の色を必要とする 2 つの無限グラフの例を示しました。これらのグラフの積は可算な色でしか彩色できません。Rinot (2013) は、構成可能な宇宙において、すべての無限基数に対して、より大きい彩色数のグラフのペアが存在し、これらのグラフの積は可算な色でしか彩色できないことを証明しました。 $\kappa$ $\kappa$

参考文献

一次資料

Duffus, D. ; Sands, B.; Woodrow, RE (1985)、「グラフの積の彩色数について」、Journal of Graph Theory、9 (4): 487–495、doi :10.1002/jgt.3190090409、MR 0890239。
El-Zahar, M.; Sauer, N. (1985)、「2 つの 4 色グラフの積の彩色数は 4 である」、Combinatorica、5 (2): 121–126、doi :10.1007/BF02579374、MR 0815577、S2CID 7659747。
Häggkvist, R.; Hell, P .; Miller, DJ; Neumann Lara, V. (1988)、「乗法グラフと積の予想について」、Combinatorica、8 (1): 63–74、doi :10.1007/BF02122553、hdl : 1828/1589、MR 0951994、S2CID 39731578。
Hajnal, A. (1985)、「2 つの ℵ ₁彩色グラフの積の彩色数は可算である」、Combinatorica、5 (2): 137–140、doi :10.1007/BF02579376、MR 0815579、S2CID 27087122。
Hedetniemi, S. (1966)、グラフとオートマトンにおける準同型性、技術レポート 03105-44-T、ミシガン大学。
Poljak, S.; Rödl, V. (1981)、「有向グラフの弧彩色数について」、Journal of Combinatorial Theory、シリーズ B、31 (2): 190–198、doi : 10.1016/S0095-8956(81)80024-X。
Rinot, A. (2013)、Hedetniemi の非可算グラフ予想、arXiv : 1307.6841、Bibcode :2013arXiv1307.6841R。
サビドゥッシ、G. (1957)、「与えられた群と与えられたグラフ理論的特性を持つグラフ」、Canadian Journal of Mathematics、9 : 515–525、doi :10.4153/CJM-1957-060-7、MR 0094810、S2CID 124514137。
シトフ、ヤロスラフ（2019年5月）、ヘデトニエミ予想に対する反例、arXiv：1905.02167。
Tardif, C. (2005)、「グラフのカテゴリにおける乗法グラフと半格子自己準同型」、Journal of Combinatorial Theory、シリーズ B、95 (2): 338–345、doi : 10.1016/j.jctb.2005.06.002。
Tardif, C.; Wehlau, D. (2006)、「グラフの積の彩色数: Poljak-Rödl 関数の有向バージョンと無向バージョン」、Journal of Graph Theory、51 (1): 33–36、doi :10.1002/jgt.20117、S2CID 17489968。
Wrochna, M. (2017)、「スクエアフリーグラフは乗法性がある」、Journal of Combinatorial Theory、シリーズ B、122 : 479–507、arXiv : 1601.04551、doi :10.1016/j.jctb.2016.07.007、S2CID 205930734。

調査と二次資料

イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000）、プロダクトグラフ：構造と認識、Wiley、ISBN 0-471-37039-8。
カライ、ギル（2019年5月10日）「朝のニュースで話題に – ヤロスラフ・シトフ：ヘデトニエミ予想に対する反例」、組合せ論とその他。
Klavžar, Sandi (1996)、「グラフ積の色付け：概観」、離散数学、155 (1–3): 135–145、doi : 10.1016/0012-365X(94)00377-U、MR 1401366。
Sauer, N. (2001)、「ヘデトニエミの予想：概観」、離散数学、229 (1–3): 261–292、doi : 10.1016/S0012-365X(00)00213-2、MR 1815610。
Tardif, Claude (2008)、「Hedetniemi の予想、40 年後」(PDF)、Graph Theory Notes of New York、54 : 46–57、MR 2445666、2021-07-12にオリジナル(PDF)からアーカイブ、 2017-02-23 に取得。
朱旭定 (1998)、「ヘデトニエミ予想に関する調査」、台湾数学誌、2 (1): 1–24、doi : 10.11650/twjm/1500406890、MR 1609464。

外部リンク

グラフ理論の画期的な進歩、Numberphile