Гипотеза диница - Dinitz conjecture

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

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

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

Рекомендации

  1. ^ Эрдеш, П.; Рубин, А.; Тейлор, Х. (1979). «Возможность выбора в графиках». Proc. Конференция Западного побережья по комбинаторике, теории графов и вычислениям, Арката (PDF). Congressus Numerantium. 26. С. 125–157. Архивировано из оригинал (PDF) на 2016-03-09. Получено 2017-04-22.
  2. ^ Ф. Гэлвин (1995). «Списочный хроматический индекс двудольного мультиграфа». Журнал комбинаторной теории. Серия Б. 63 (1): 153–158. Дои:10.1006 / jctb.1995.1011.
  3. ^ Зейльбергер, Д. (1996). «Метод неопределенного обобщения и специализации, проиллюстрированный удивительным доказательством гипотезы Диница Фредом Гэлвином». Американский математический ежемесячный журнал. 103 (3): 233–239. arXiv:математика / 9506215. Дои:10.2307/2975373.
  4. ^ Гравье, Сильвен; Маффре, Фредерик (2004). «О выборе количества совершенных графов без клешней». Дискретная математика. 276 (1–3): 211–218. Дои:10.1016 / S0012-365X (03) 00292-9. МИСТЕР  2046636.
  5. ^ Чоу, Т. Ю. (1995). «О гипотезе Диница и связанных с ней гипотезах» (PDF). Дискретная математика. 145 (1–3): 73–82. Дои:10.1016 / 0012-365X (94) 00055-N.

внешняя ссылка