Znajdowanie nieparzystych dziur w krążących grafach Paleya

Paley wykresy P _P są takie, których wierzchołek osadzone jest przez skończonego GF (q) dla pierwszego mocarstw q≡1 mod (4), w których dwa wierzchołki przylega wtedy i tylko wtedy, gdy różnią się o ² do niektórych a ∈ GF (q). W przypadku, gdy q jest liczbą pierwszą, skończone pole GF (q) jest tylko zbiorem liczb całkowitych modulo q.

W niedawnym artykule Maistrelli i Penman pokazują, że jedynym doskonałym grafem Paleya (posiadającym liczbę chromatyczną równą wielkości największej kliki) jest wykres na dziewięciu wierzchołkach. Oznacza to w szczególności, że żaden z wykresów Paleya P _{q nie} jest idealny dla qpierwszej.

Twierdzenie Strong Perfect Graph twierdzi, że wykres G jest idealny wtedy i tylko wtedy, gdy zarówno G, jak i jego dopełnienie nie mają nieparzystych otworów (indukowany podgraph, który jest cyklem o nieparzystej długości i wielkości co najmniej 5.) Wykresy Paleya pierwszego rzędu są komplementarne i niedoskonałe; dlatego muszą zawierać nieparzyste dziury.

Pytanie. Czy dla liczby pierwszej q mod1 (mod 4) istnieje algorytm poli (q) do znajdowania nieparzystej dziury w P _q ? Czy istnieje algorytm polylog (q)? Dozwolone są losowość i popularne przypuszczenia teoretyczne.

Uważam, że istnieje znany algorytm poli (q). Rozumiem algorytm Chudnovsky'ego, Cornuéjolsa, Liu, Seymour i Vuškovicia, „Recognizing Berge Graphs”, Combinatorica 2005 , jest taki, że znajduje on albo dziwną dziurę, albo dziwną dziurę w dowolnym niezupełnym wykresie w czasie wielomianowym. Autorzy piszą na stronie 2 swojego artykułu, że problem znajdowania nieparzystych dziur na wykresach, które je mają, pozostaje otwarty, ponieważ kroki 1 i 3 ich algorytmu znajdują dziury, ale krok 2 może zamiast tego znaleźć antihole. Jednak w przypadku wykresów Paleya, jeśli znajdziesz antyhole, po prostu pomnóż wszystkie jego wierzchołki przez nieresztę, aby zamiast tego przekształcić go w dziwną dziurę.

Alternatywnie, analogicznie do wykresu Rado, dla każdego k powinno być takie N, że wykresy Paleya na N lub większej liczbie wierzchołków powinny mieć właściwość rozszerzenia: dla dowolnego podzbioru mniejszego niż k wierzchołków i dowolne 2-zabarwienie podzbioru, istnieje inny wierzchołek sąsiadujący z każdym wierzchołkiem w jednej klasie kolorów i nieprzylegający do każdego wierzchołka w drugiej klasie kolorów. Jeśli tak, to dla k = 5 można zbudować dziwnie 5-dołkowe zachłannie w czasie wielomianowym na krok. Może ten kierunek ma nadzieję na algorytm poli (log (q))? Jeśli zadziała, to przynajmniej pokaże, że istnieją krótkie dziwne dziury, co wydaje się niezbędnym warunkiem wstępnym ich szybkiego znalezienia.

Właściwie nie zdziwiłbym mnie, gdyby następujące algorytmy były poli (log (q)): jeśli q jest mniejsze niż jakaś stała stała, poszukaj odpowiedzi, w przeciwnym razie zachłannie zbuduj dziwne 5-dołkowe, przeszukując kolejno liczby 0, 1, 2, 3, ... dla wierzchołków, które można dodać jako część częściowego 5-dołkowego. Ale może udowodnienie, że działa w czasie poli (log (q)), wymagałoby pewnej teorii liczb głębokich.

Na podstawie wyników Chunga, Grahama i Wilsona, „Quasi-losowe wykresy”, Combinatorica 1989, następujący randomizowany algorytm rozwiązuje problem w stałej oczekiwanej liczbie prób, gdy q jest liczbą pierwszą: jeśli q jest wystarczająco małe, to spójrz na odpowiedź, w przeciwnym razie wielokrotnie wybierz losowy zestaw pięciu wierzchołków, sprawdź, czy tworzą one dziwną dziurę, a jeśli tak, zwróć ją. Ale nie mówią, czy to działa, gdy q nie jest liczbą pierwszą, ale siłą główną, więc może trzeba by być bardziej ostrożnym w tym przypadku.