Гипотеза Сереседы
В математике графов раскраски гипотеза Сереседа представляет собой нерешённую проблему о расстоянии между парами раскрасок разрежённых графов . Он утверждает, что для двух разных раскрасок графа вырождения d , использующих не более d + 2 цветов, должна быть возможность переконфигурировать одну раскраску в другую, изменяя цвет одной вершины за раз, используя несколько шагов, квадратичный по размеру графика. Гипотеза названа в честь Луиса Сереседа, который сформулировал ее в своей докторской диссертации 2007 года.
Фон
[ редактировать ]Вырождение — это неориентированного графа G наименьшее число d такое, что каждый непустой подграф G имеет хотя бы одну вершину степени не выше d . Если повторно удалить вершину минимальной степени из G до тех пор, пока не останется ни одной вершины, то наибольшая из степеней вершин на момент их удаления будет равна ровно d , и этот метод повторного удаления можно использовать для вычисления вырождения любого графа за линейное время . Жадная раскраска вершин в порядке, обратном этому порядку удаления, автоматически приведет к раскраске не более чем в d + 1 цвет, а для некоторых графов (таких как полные графы нечетной длины и графы циклов ) это количество цветов является оптимальным. [ 1 ]
Для раскрасок с d + 1 цветами может оказаться невозможным переход от одной раскраски к другой путем изменения цвета одной вершины за раз. В частности, никогда нельзя перемещаться таким способом между 2-раскрасками леса ( графами вырождения 1) или между ( d + 1) -раскрасками полного графа; Говорят, что их окраска заморожена. [ 2 ] Графы циклов длины, отличной от четырех, также имеют несвязные семейства ( d + 1) -раскрасок. [ 3 ] Однако при наличии одного дополнительного цвета, используя раскраски с d + 2 цветами, все пары раскрасок можно соединить между собой последовательностями ходов этого типа. Отсюда следует, что правильно спроектированное случайное блуждание по пространству ( d + 2) -раскрасок с использованием ходов такого типа является перемешиванием. Это означает, что случайное блуждание в конечном итоге сходится к дискретному равномерному распределению этих раскрасок как к своему устойчивому состоянию , в котором все раскраски имеют равную вероятность выбора. Точнее, случайное блуждание происходит путем многократного выбора равномерно случайной вершины и равномерно случайного выбора среди всех доступных цветов для этой вершины, включая цвет, который у нее уже был; этот процесс называется глауберовой динамикой . [ 4 ]
Заявление
[ редактировать ]Тот факт, что глауберовая динамика сходится к равномерному распределению на ( d + 2) -раскрасках, естественно ставит вопрос о том, насколько быстро она сходится. То есть каково время смешивания ? Нижняя граница времени смешивания — это диаметр пространства раскрасок, максимальное (по парам раскрасок) число шагов, необходимое для смены одной раскраски пары на другую. Если диаметр экспоненциально велик по числу n вершин в графе, то глауберовская динамика раскрасок, конечно, не является быстрым перемешиванием. С другой стороны, когда диаметр ограничен полиномиальной функцией от n , это предполагает, что время смешивания также может быть полиномиальным. В своей докторской диссертации 2007 года Сереседа исследовал эту проблему и обнаружил, что (даже для связных компонентов пространства цветов) диаметр может быть экспоненциальным для ( d + 1) -раскрасок d -вырожденных графов. С другой стороны, он доказал, что диаметр цветового пространства не более чем квадратичен (или, в обозначении большого О, , На 2 ) ) для раскрасок, в которых используется минимум 2 d +1 цвета. Он писал, что «осталось определить», является ли диаметр полиномом для числа цветов между этими двумя крайностями или «возможно, даже квадратичным». [ 5 ]
Хотя Сереседа задала этот вопрос для ряда цветов и не сформулировала его как гипотезу, к 2018 году форма этого вопроса стала известна как гипотеза Сереседы. Эта недоказанная гипотеза является самой оптимистичной возможностью среди вопросов, поставленных Сереседой: что для графов с вырождением не более d , и для ( d +2) -раскрасок этих графов диаметр пространства раскрасок равен O ( n 2 ) . [ 6 ] [ 7 ] [ 8 ] [ 9 ] Если это правда, то это было бы лучше всего, поскольку пространство 3-раскрасок графа путей имеет квадратичный диаметр. [ 10 ]
Частичные и связанные результаты
[ редактировать ]Хотя сама гипотеза Сереседа остается открытой даже для вырождения d = 2 , известно, что при любом фиксированном значении d диаметр пространства ( d + 2) -раскрасок полиномиален (с разным полиномом для разных значений d ). Точнее, диаметр равен O ( n д + 1 ) . Когда количество раскрасок не менее (3 d + 3)/2 , диаметр квадратичен. [ 7 ]
Связанный с этим вопрос касается возможности того, что для числа цветов, большего d + 2 , диаметр пространства раскрасок может уменьшиться с квадратичного до линейного. [ 7 ] Буске и Бартье (2019) предполагают, что это может быть верно, если количество цветов не менее d + 3 . [ 9 ]
Глауберовская динамика — не единственный способ поменять раскраски графов друг на друга. Альтернативы включают динамику Кемпе, в которой можно неоднократно находить и менять цвета цепочек Кемпе , [ 8 ] и динамика «тепловой ванны», в которой выбираются пары соседних вершин и допустимое перекрашивание этой пары. Оба этих типа ходов включают одновершинные ходы Глаубера как особый случай, поскольку изменение цвета одной вершины аналогично замене цветов в цепочке Кемпе, которая включает только эту одну вершину. Эти ходы могут иметь более сильные перемешивающие свойства и меньший диаметр пространства раскрасок. Например, и динамика Кемпе, и динамика тепловой бани быстро смешиваются на 3-раскрасках графов циклов, тогда как динамика Глаубера даже не связана, когда длина цикла не равна четырем.
Ссылки
[ редактировать ]- ^ Матула, Дэвид В .; Бек, Л.Л. (1983), «Алгоритмы упорядочения, кластеризации и раскраски графов наименьшего прошлого», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826 , S2CID 4417741
- ^ См. Cereceda (2007) , замечание после предложения 2.6, с. 26.
- ^ Сереседа (2007) , с. 37.
- ^ Дайер, Мартин; Флаксман, Авраам Д.; Фриз, Алан М.; Вигода, Эрик (2006), «Случайная раскраска разреженных случайных графов с меньшим количеством цветов, чем максимальная степень», Random Structures & Algorithms , 29 (4): 450–465, doi : 10.1002/rsa.20129 , MR 2268231 , S2CID 5342223 . См., в частности, лемму 2 этой статьи и Cereceda (2007) , теорема 2.7, с. 26.
- ^ Сереседа, Луис (2007), Смешивание раскрасок графа (доктор философии), докторская диссертация, Лондонская школа экономики . См. особенно страницу 109.
- ^ Эйбен, Эдуард; Фегхали, Карл (2018), К гипотезе Сереседы для плоских графов , arXiv : 1810.00731
- ^ Jump up to: а б с Буске, Николя; Генрих, Марк (2019), Полиномиальная версия гипотезы Сереседы , arXiv : 1903.05619
- ^ Jump up to: а б Бонами, Марта; Буске, Николя; Фегали, Карл; Джонсон, Мэтью (2019), «О гипотезе Мохара относительно эквивалентности Кемпе регулярных графов» , Журнал комбинаторной теории , серия B, 135 : 179–199, arXiv : 1510.06964 , doi : 10.1016/j.jctb.2018.08.002 , МИСТЕР 3926265 , S2CID 5465047
- ^ Jump up to: а б Буске, Николя; Бартье, Валентин (2019), «Линейные преобразования между раскрасками в хордальных графах», в Бендере, Майкл А.; Свенссон, Ола; Герман, Гжегож (ред.), 27-й ежегодный европейский симпозиум по алгоритмам, ESA 2019, 9–11 сентября 2019 г., Мюнхен/Гархинг, Германия , LIPics, vol. 144, Замок Дагштуль — Центр компьютерных наук Лейбница, стр. 24:1–24:15, doi : 10.4230/LIPIcs.ESA.2019.24 , ISBN 9783959771245 , S2CID 195791634
- ^ Бонами, Марта; Джонсон, Мэтью; Лигнос, Иоаннис; Патель, Виреш; Паулусма, Даниэль (2014), «Графы реконфигурации для раскрасок вершин хордальных и хордальных двудольных графов» (PDF) , Journal of Combinatorial Optimization , 27 (1): 132–143, doi : 10.1007/s10878-012-9490-y , МР 3149109 , S2CID 254648357 . См., в частности, теорему 11, стр. 141.