Нахождение нечетных дыр в круговых графах Пэли

Пэли графы Р _д являются те, вершина которого-множество задается конечным полем GF (Q) для степеней простых чисел q≡1 (мод 4), и где две вершины смежны тогда и только тогда , когда они отличаются на ² для некоторых a ∈ GF (q). В случае, когда q простое, конечное поле GF (q) - это просто множество целых чисел по модулю q.

В недавней статье Маистрелли и Пенман показывают, что единственный идеальный граф Пейли (с хроматическим числом, равным размеру его наибольшей клики) - это тот, что на девяти вершинах. Это, в частности, означает, что ни один из графов Пэли P _q не идеален для q простого числа.

Сильная Идеальный график теорема утверждает , что граф G является совершенным , если и только если оба G и его дополнение не хватают нечетные отверстий (индуцированный подграфа , который представляет собой цикл нечетной длины, а размер по крайней мере , 5.) Пэли графы простого порядка является самодостаточный и несовершенный; поэтому они должны содержать нечетные отверстия.

Вопрос. Для простого q≡1 (mod 4) существует ли алгоритм poly (q) для нахождения нечетной дыры в P _q ? Есть ли алгоритм полилога (q)? Случайность и популярные теоретико-числовые гипотезы допускаются.

Я считаю, что есть известный алгоритм poly (q). Мое понимание алгоритма Чудновского, Корнейоле, Лю, Сеймура и Вушковича, «Распознавание графов Берге», Combinatorica 2005 , заключается в том, что он находит либо нечетную дыру, либо нечетную антихолу в любом неидеальном графе за полиномиальное время. Авторы пишут на странице 2 своей статьи, что проблема нахождения нечетных дыр в графах, у которых они есть, остается открытой, потому что шаги 1 и 3 их алгоритма находят дыры, а шаг 2 вместо этого может найти анти-дыру. Тем не менее, в случае графов Пейли, если вы найдете анти-дыру, просто умножьте все вершины в ней на нерезидент, чтобы вместо этого превратить ее в нечетную дыру.

В качестве альтернативы, по аналогии с графом Радо, для каждого k должно быть N, такое, что графы Пэли на N или более вершинах должны иметь свойство расширения: для любого подмножества, меньшего, чем k вершин, и любой 2-раскраски подмножества, существует другая вершина, смежная с каждой вершиной в одном классе цвета и несмежная с каждой вершиной в другом классе цвета. Если это так, то для k = 5 вы можете жадно построить нечетное 5-луночное отверстие за полиномиальное время на шаг. Может быть, это направление обнадеживает для алгоритма poly (log (q))? Если это сработает, это, по крайней мере, покажет наличие коротких нечетных отверстий, что, по-видимому, является необходимым условием для их быстрого поиска.

На самом деле, меня не удивило бы, если бы ниже был алгоритм poly (log (q)): если q меньше некоторой фиксированной константы, ищите ответ, иначе жадно построите нечетную 5-луночное отверстие, последовательно просматривая числа 0, 1, 2, 3, ... для вершин, которые могут быть добавлены как часть частичного 5-луночного. Но, возможно, для доказательства того, что это работает за время poly (log (q)), потребуется некоторая глубокая теория чисел.

По результатам Chung, Graham и Wilson, «Квазислучайные графы», Combinatorica 1989, следующий рандомизированный алгоритм решает проблему в постоянном ожидаемом количестве испытаний, когда q простое: если q достаточно мало, ищите ответ, иначе несколько раз выберите случайный набор из пяти вершин, проверьте, образуют ли они нечетное отверстие, и, если это так, верните его. Но они не говорят, работает ли он, когда q не является простой, а основной степенью, поэтому, возможно, вам следует быть более осторожным в этом случае.