組合せ論において、ディニッツ定理（以前はディニッツ予想と呼ばれていた）は、配列の部分ラテン方陣への拡張に関する命題であり、1979年にジェフ・ディニッツによって提案され、[1] 1994年にフレッド・ガルビンによって証明された。[2] [3]
ディニッツの定理は、n × nの正方配列、m個のシンボル（m ≥ n）の集合、および配列の各セルにm個のシンボルのプールから抽出されたn要素の集合が与えられた場合、行または列でシンボルが繰り返されないように、各セルをそれらの要素の 1 つでラベル付けする方法を選択できるというものです。また、グラフ理論の結果として、完全二部グラフのリスト彩色指数はに等しいと定式化することもできます。つまり、完全二部グラフの各辺に色の集合が割り当てられている場合、同じ頂点に接続する 2 つの辺が同じ色にならないように、各辺に割り当てられた色の 1 つを選択することができます。
ガルビンの証明は、任意の二部グラフに対して、リスト彩色指数 はその彩色指数に等しいという命題に一般化される。より一般的なリスト辺彩色予想は、二部グラフだけでなく、任意のループのない多重グラフにも同様のことが成り立つことを述べている。さらに一般的な予想は、クローフリーグラフのリスト彩色数は常にその彩色数に等しいことを述べている。[4]ディニッツ定理は、ロータの基底予想とも関連している。[5]
参考文献
- ^ Erdős, P. ; Rubin, AL ; Taylor, H. (1979). 「グラフにおける選択可能性」 Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF) . Congressus Numerantium. Vol. 26. pp. 125– 157. 2016年3月9日時点のオリジナル(PDF)からのアーカイブ。 2017年4月22日閲覧。
- ^ F. Galvin (1995). 「二部多重グラフのリスト彩色指数」. Journal of Combinatorial Theory . Series B. 63 (1): 153– 158. doi : 10.1006/jctb.1995.1011 .
- ^ Zeilberger, D. (1996). 「フレッド・ガルビンによるディニッツ予想の驚くべき証明で示される未確定の一般化と特殊化の方法」アメリカ数学月刊誌. 103 (3): 233– 239. arXiv : math/9506215 . doi :10.2307/2975373. JSTOR 2975373.
- ^ グラヴィエ, シルヴァン; マフレー, フレデリック (2004). 「クローフリー完全グラフの選択数について」.離散数学. 276 ( 1–3 ): 211– 218. doi : 10.1016/S0012-365X(03)00292-9 . MR 2046636.
- ^ Chow, TY (1995). 「ディニッツ予想と関連予想について」(PDF) .離散数学. 145 ( 1–3 ): 73–82 . doi : 10.1016/0012-365X(94)00055-N .
外部リンク
- ワイスタイン、エリック・W.「ディニッツ問題」。マスワールド。
