Гипотеза цереседаса - Cerecedas conjecture - Wikipedia

Нерешенная проблема в математике:

Может каждые два

{ displaystyle (d + 2)}

-раскраски

{ displaystyle d}

-вырожденные графы преобразовывать друг в друга квадратично множеством шагов, меняющих цвет одной вершины за раз?

(больше нерешенных задач по математике)

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)$ ) для раскрасок, использующих не менее $2 d + 1$ цвета. Он писал, что «осталось определить», является ли диаметр полиномиальным для числа цветов между этими двумя крайностями или «возможно, даже квадратичным».^[5]

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

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

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

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

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

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

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

[mb-1] Матула, Дэвид В .; Бек, Л. Л. (1983), "Алгоритмы наименьшего последнего упорядочения, кластеризации и раскраски графов", Журнал ACM, 30 (3): 417–427, Дои:10.1145/2402.322385, МИСТЕР 0709826

[2] Видеть Цереседа (2007), замечание к предложению 2.6, с. 26.

[3] Цереседа (2007), п. 37.

[dffv-4] Дайер, Мартин; Flaxman, Abraham D .; Frieze, Alan M .; Вигода, Эрик (2006), «Случайная окраска разреженных случайных графов меньшим количеством цветов, чем максимальная степень», Случайные структуры и алгоритмы, 29 (4): 450–465, Дои:10.1002 / rsa.20129, МИСТЕР 2268231. См., В частности, лемму 2 данной статьи и Цереседа (2007), Теорема 2.7, с. 26.

[cereceda-5] Сереседа, Луис (2007), Смешивание раскрасок графиков, докторская диссертация, Лондонская школа экономики. См. Особенно страницу 109.

[ef-6] Эйбен, Эдуард; Фегали, Карл (2018), К гипотезе Сереседы для плоских графов, arXiv:1810.00731

[bh-7] а ^б ^c Буске, Николя; Генрих, Марк (2019), Полиномиальная версия гипотезы Сереседы, arXiv:1903.05619

[bbfj-8] а ^б Бонами, Марта; Буске, Николя; Фегали, Карл; Джонсон, Мэтью (2019), «О гипотезе Мохара об эквивалентности по Кемпе регулярных графов», Журнал комбинаторной теории, Серия B, 135: 179–199, Дои:10.1016 / j.jctb.2018.08.002, МИСТЕР 3926265

[bb-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

[bjlpp-10] Бонами, Марта; Джонсон, Мэтью; Лигнос, Иоаннис; Патель, Виреш; Паулюсма, Даниэль (2014), "Графы реконфигурации для раскраски вершин хордовых и хордовых двудольных графов", Журнал комбинаторной оптимизации, 27 (1): 132–143, Дои:10.1007 / s10878-012-9490-у, МИСТЕР 3149109. См., В частности, теорему 11, стр. 141.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]