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

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

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

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

Внешние ссылки

• Вайсштейн, Эрик В. «Проблема Диница» . Математический мир .