ディニッツ予想

組合せ論において、ディニッツの定理（ディニッツのせいり、英: Dinitz theorem 、旧称ディニッツ予想）は、配列の部分ラテン方陣への拡張に関する定理であり、1979年にジェフ・ディニッツによって提案され、^[1] 1994年にフレッド・ガルビンによって証明された。^{[2] [3]}

ディニッツの定理は、n × nの正方配列、m個のシンボル（m ≥ n ）の集合、および配列の各セルに対してm個のシンボルのプールから抽出されたn要素の集合が与えられた場合、行または列でシンボルが繰り返されないように、各セルをそれらの要素の 1 つでラベル付けする方法を選択できるというものです。また、グラフ理論の結果として、完全二部グラフのリスト彩度指数はに等しいと定式化することもできます。つまり、完全二部グラフの各辺に色の集合が割り当てられている場合、同じ頂点に接続する 2 つの辺が同じ色にならないように、各辺に割り当てられた色の 1 つを選択できます。 ${\displaystyle K_{n,n}}$${\displaystyle n}$${\displaystyle n}$

ガルビンの証明は、あらゆる二部グラフに対して、リスト彩色指数はその彩色指数に等しいという主張に一般化される。より一般的な辺リスト彩色予想は、同じことが二部グラフだけでなく、任意のループのない多グラフにも当てはまると述べている。さらに一般的な予想は、クローフリーグラフのリスト彩色数は常にその彩色数に等しいと述べている。^{[4]ディニッツの定理は、}ロータの基底予想とも関連している。^[5]

• ワイスタイン、エリック・W.「ディニッツ問題」。マスワールド。