Гипотеза Диница

В комбинаторике теорема Диница (ранее известная как гипотеза Диница ) представляет собой утверждение о расширении массивов до частичных латинских квадратов, предложенный в 1979 году Джеффом Диницем и доказанный в 1994 году Фредом Гэлвином.

Теорема Диница состоит в том, что для квадратного массива n × n набор из m символов с m ≥ n, и для каждой ячейки массива набор из n элементов, взятый из пула из m символов, можно выбрать способ пометить каждую ячейку одним из этих элементов таким образом, чтобы ни одна строка или столбец не повторяли символ. Это также может быть сформулировано в результате в теории графов, что хроматический индекс списка полного двудольного графа $K\; n,\; n\; \{\backslash \; displaystyle\; K\_\; \{n,\; n\}\}$равно $n\; \{\backslash \; displaystyle\; n\}$. То есть, если каждому ребру полного двудольного графа назначен набор цветов $n\; \{\backslash \; displaystyle\; n\}$, можно выбрать один из назначенных цветов для каждого ребра так, чтобы не было двух ребра, инцидентные одной вершине, имеют один цвет.

Доказательство Гальвина обобщает утверждение, что для каждого двудольного мультиграфа хроматический индекс списка равен его хроматическому индексу. Более общая гипотеза раскраски списка ребер утверждает, что то же самое верно не только для двудольных графов, но и для любого мультиграфа без петель. Еще более общая гипотеза утверждает, что хроматическое число списка графов без когтей всегда равно их хроматическому числу. Теорема Диница также связана с гипотезой о базисе Роты.

• Вайсштейн, Эрик У. «Проблема Диница». MathWorld. Проверено 17 августа 2008 г.

.