В комбинаторике теорема Диница ( ранее известная как гипотеза Диница ) — это утверждение о расширении массивов до частичных латинских квадратов , предложенное в 1979 году Джеффом Диницем [ 1] и доказанное в 1994 году Фредом Галвином [2] [3] .
Теорема Диница заключается в том, что для квадратного массива n × n , набора из m символов, где m ≥ n , и для каждой ячейки массива набора из n элементов, взятого из пула из m символов, можно выбрать способ маркировки каждой ячейки одним из этих элементов таким образом, чтобы ни одна строка или столбец не повторяли символ. Это также можно сформулировать как результат в теории графов , что списочный хроматический индекс полного двудольного графа равен . То есть, если каждому ребру полного двудольного графа назначен набор цветов, можно выбрать один из назначенных цветов для каждого ребра таким образом, чтобы никакие два ребра, инцидентные одной и той же вершине, не имели одинакового цвета.
Доказательство Гэлвина обобщается до утверждения, что для каждого двудольного мультиграфа списочный хроматический индекс равен его хроматическому индексу . Более общая гипотеза о списочной раскраске рёбер утверждает, что то же самое справедливо не только для двудольных графов, но и для любого мультиграфа без петель. Ещё более общая гипотеза утверждает, что списочное хроматическое число графов без клешней всегда равно их хроматическому числу . [4] Теорема Диница также связана с базисной гипотезой Роты . [5]
