Finding odd holes in circulant Paley graphs

Question

The Paley graphs P_q are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a² for some a ∈ GF(q). In the case that q is prime, the finite field GF(q) is just the set of integers modulo q.

In a recent paper, Maistrelli and Penman show that the only Paley graph which is perfect (having a chromatic number equal to the size of its largest clique) is the one on nine vertices. This implies, in particular, that none of the Paley graphs P_q are perfect for q prime.

The Strong Perfect Graph Theorem asserts that a graph G is perfect if and only if both G and its complement lacks odd holes (an induced subgraph which is a cycle of odd length, and size at least 5.) The Paley graphs of prime order are self-complementary, and imperfect; therefore they must contain odd holes.

Question. For q≡1 (mod 4) prime, is there a poly(q) algorithm for finding an odd hole in P_q? Is there a polylog(q) algorithm? Randomness and popular number-theoretic conjectures are allowed.

Answer 1

I believe there is a known poly(q) algorithm. My understanding of the algorithm by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, "Recognizing Berge Graphs", Combinatorica 2005, is that it finds either an odd hole or an odd antihole in any non-perfect graph in polynomial time. The authors write on page 2 of their paper that the problem of finding odd holes in graphs that have them remains open, because steps 1 and 3 of their algorithm find holes but step 2 might find an antihole instead. However, in the case of Paley graphs, if you find an antihole, just multiply all the vertices in it by a nonresidue to turn it into an odd hole instead.

Alternatively, by analogy to the Rado graph, for each k there should be an N such that Paley graphs on N or more vertices should have the extension property: for any subset of fewer than k vertices, and any 2-coloring of the subset, there exists another vertex adjacent to every vertex in one color class and nonadjacent to every vertex in the other color class. If so, then for k=5 you could build an odd 5-hole greedily in polynomial time per step. Maybe this direction is hopeful for a poly(log(q)) algorithm? If it works it would at least show that there are short odd holes, seemingly a necessary prerequisite to finding them quickly.

Actually, it wouldn't surprise me if the following were a poly(log(q)) algorithm: if q is smaller than some fixed constant, look up the answer, else greedily build an odd 5-hole by searching sequentially through the numbers 0, 1, 2, 3, ... for vertices that can be added as part of a partial 5-hole. But maybe proving that it works in poly(log(q)) time would require some deep number theory.

By results of Chung, Graham, and Wilson, "Quasi-random graphs", Combinatorica 1989, the following randomized algorithm solves the problem in a constant expected number of trials when q is prime: if q is sufficiently small then look up the answer, else repeatedly choose a random set of five vertices, check whether they form an odd hole, and if so return it. But they don't say whether it works when q is not a prime but a prime power, so maybe you'd need to be more careful in that case.