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