WikiDer > Гипотеза Цереседаса - Википедия

Cerecedas conjecture - Wikipedia
Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Может каждые два -раскраски -вырожденные графы преобразовывать друг в друга квадратично множеством шагов, меняющих цвет одной вершины за раз?
(больше нерешенных задач по математике)
3-раскраски граф путей, имеющий вырождение один. Диаметр этого пространства раскрасок равен четырем: требуется четыре шага, чтобы перейти от одного из двух верхних цветов к нижнему.

В математике раскраска графика, Гипотеза Сереседы - нерешенная проблема о расстоянии между парами раскрасок разреженные графики. В нем говорится, что для двух разных раскрасок графа вырождение d, оба используют не более d + 2 цвета, должно быть возможно переконфигурировать одна раскраска в другую путем изменения цвета одной вершины за раз, используя количество шагов, квадратичное по размеру графа. Гипотеза названа в честь Луиса Сереседы, который сформулировал ее в своей докторской диссертации 2007 года.

Фон

В вырождение неориентированного графа грамм это наименьшее число d такой, что каждый непустой подграф грамм имеет хотя бы одну вершину степени не выше d. Если несколько раз удалить вершину минимальной степени из грамм пока не останется ни одной вершины, тогда наибольшая из степеней вершин на момент их удаления будет точно d, и этот метод повторного удаления может быть использован для вычисления вырожденности любого графа в линейное время. Жадная раскраска вершины в обратном порядке удаления автоматически произведут раскраску не более d + 1 цвета, а также для некоторых графиков (например, полные графики и нечетной длины графики цикла) это количество цветов оптимально.[1]

Для окраски с d + 1 цвета, может быть невозможно перейти от одной раскраски к другой, изменяя цвет одной вершины за раз. В частности, невозможно переключаться между 2-мя раскрасками лес (графики вырождения 1) или между (d + 1)-раскраска полного графа таким способом; их окраска считается замороженной.[2] Графы циклов длины, отличной от четырех, также имеют несвязные семейства (d + 1)-раскраски.[3]Однако с одним дополнительным цветом, используя раскраски с d + 2 цвета, все пары раскрасок могут быть связаны друг с другом последовательностями ходов этого типа. Из этого следует, что правильно спроектированный случайная прогулка на пространстве (d + 2)-краски, использующие ходы этого типа, смешиваются. Это означает, что случайное блуждание в конечном итоге сведется к дискретное равномерное распределение на эти раскраски как на его устойчивое состояние, в котором все раскраски имеют равную вероятность выбора. Точнее, случайное блуждание происходит путем многократного выбора равномерно случайной вершины и равномерного случайного выбора из всех доступных цветов для этой вершины, включая цвет, который она уже имела; этот процесс называется Глауберова динамика.[4]

Заявление

Тот факт, что динамика Глаубера сходится к равномерному распределению на (d + 2)-раскраски естественно поднимают вопрос, насколько быстро она сходится. То есть что такое время смешивания? Нижняя граница времени перемешивания - это диаметр пространства раскрасок - максимальное (по парам раскрасок) количество шагов, необходимых для смены одной раскраски пары на другую. Если диаметр экспоненциально велик в количестве п вершин в графе, то глауберовская динамика при раскрасках, конечно, не будет быстро перемешиваться. С другой стороны, когда диаметр ограничен полиномиальной функцией от п, это говорит о том, что время перемешивания также может быть полиномиальным. В своей докторской диссертации 2007 года Сереседа исследовал эту проблему и обнаружил, что (даже для связанных компонентов пространства цветов) диаметр может быть экспоненциальным для (d + 1)-расцветки d-вырожденные графы. С другой стороны, он доказал, что диаметр цветового пространства не более чем квадратичный (или, в нотация большой O, О(п2)) для раскрасок, использующих не менее 2d + 1 цвета. Он писал, что «осталось определить», является ли диаметр полиномиальным для числа цветов между этими двумя крайностями или «возможно, даже квадратичным».[5]

Хотя Цереседа задавала этот вопрос для ряда цветов и не формулировала его как гипотезу, к 2018 году форма этого вопроса стала известна как гипотеза Цереседы. Эта недоказанная гипотеза - самая оптимистическая возможность среди вопросов, поставленных Сереседой: для графов с вырождением не более d, и для (d + 2)-раскраски этих графов диаметр пространства раскрасок равен О(п2).[6][7][8][9]Если это так, то это было бы лучше всего, так как пространство трех раскрасок граф путей имеет квадратичный диаметр.[10]

Частичные и связанные результаты

Хотя сама гипотеза Сереседы остается открытой даже для вырождения. d = 2, известно, что для любого фиксированного значения d диаметр пространства (d + 2)-раскраски полиномиальны (с разными полиномами для разных значений d). Точнее диаметр О(пd + 1). Когда количество раскрасок не менее (3d + 3)/2, диаметр квадратичный.[7]

Связанный с этим вопрос касается возможности того, что для количества цветов больше, чем d + 2, диаметр пространства раскраски может уменьшиться от квадратичного до линейного.[7] Буске и Бартье (2019) предполагают, что это может быть правдой, если количество цветов не менее d + 3.[9]

Динамика Глаубера - не единственный способ поменять раскраски графиков друг на друга. Альтернативы включают динамику Кемпе, в которой постоянно находят и меняют цвета Цепи кемпе,[8] и динамика "тепловой ванны", в которой выбираются пары соседних вершин и допустимое изменение цвета этой пары. Оба этих типа ходов включают в себя одновершинные ходы Глаубера как особый случай, поскольку изменение цвета одной вершины аналогично замене цветов в цепи Кемпе, которая включает только эту одну вершину. Эти ходы могут иметь более сильные смешивающие свойства и меньший диаметр пространства раскраски. Например, и динамика Кемпе, и динамика термостата быстро смешиваются на трехцветных графиках цикла, тогда как динамика Глаубера даже не связана, если длина цикла не равна четырем.

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

  1. ^ Матула, Дэвид В .; Бек, Л. Л. (1983), "Алгоритмы наименьшего последнего упорядочения, кластеризации и раскраски графов", Журнал ACM, 30 (3): 417–427, Дои:10.1145/2402.322385, МИСТЕР 0709826
  2. ^ Видеть Цереседа (2007), замечание к предложению 2.6, с. 26.
  3. ^ Цереседа (2007), п. 37.
  4. ^ Дайер, Мартин; Flaxman, Abraham D .; Frieze, Alan M .; Вигода, Эрик (2006), «Случайная окраска разреженных случайных графов меньшим количеством цветов, чем максимальная степень», Случайные структуры и алгоритмы, 29 (4): 450–465, Дои:10.1002 / rsa.20129, МИСТЕР 2268231. См., В частности, лемму 2 данной статьи и Цереседа (2007), Теорема 2.7, с. 26.
  5. ^ Сереседа, Луис (2007), Смешивание раскрасок графиков, докторская диссертация, Лондонская школа экономики. См. Особенно страницу 109.
  6. ^ Эйбен, Эдуард; Фегали, Карл (2018), К гипотезе Сереседы для плоских графов, arXiv:1810.00731
  7. ^ а б c Буске, Николя; Генрих, Марк (2019), Полиномиальная версия гипотезы Сереседы, arXiv:1903.05619
  8. ^ а б Бонами, Марта; Буске, Николя; Фегали, Карл; Джонсон, Мэтью (2019), «О гипотезе Мохара об эквивалентности по Кемпе регулярных графов», Журнал комбинаторной теории, Серия B, 135: 179–199, Дои:10.1016 / j.jctb.2018.08.002, МИСТЕР 3926265
  9. ^ а б Буске, Николя; Бартье, Валентин (2019), «Линейные преобразования между раскрасками в хордовых графах», в Bender, Michael A .; Свенссон, Ола; Герман, Гжегож (ред.), 27-й ежегодный европейский симпозиум по алгоритмам, ESA 2019, 9-11 сентября 2019 г., Мюнхен / Гархинг, Германия, LIPIcs, 144, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 24: 1–24: 15, Дои:10.4230 / LIPIcs.ESA.2019.24
  10. ^ Бонами, Марта; Джонсон, Мэтью; Лигнос, Иоаннис; Патель, Виреш; Паулюсма, Даниэль (2014), "Графы реконфигурации для раскраски вершин хордовых и хордовых двудольных графов", Журнал комбинаторной оптимизации, 27 (1): 132–143, Дои:10.1007 / s10878-012-9490-у, МИСТЕР 3149109. См., В частности, теорему 11, стр. 141.