13
$\begingroup$

The Paley graphs Pq 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 a2 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 Pq 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 Pq? Is there a polylog(q) algorithm? Randomness and popular number-theoretic conjectures are allowed.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ References showing that Paley graphs do have the extension property: Paley graphs satisfy all first-order adjacency axioms Andreas Blass, Geoffrey Exoo, Frank Harary, J. Graph. Th. 1981, and Graphs which contain all small graphs, Bollobas and Thomason, Eur. J. Combin. 1981. Unfortunately I don't seem to have subscription access to either of them so I can't say much more about what's in them. $\endgroup$ – David Eppstein Aug 24 '10 at 21:07
  • $\begingroup$ The algorithm in [Chudnovsky+Cornuéjols+Liu+Seymour+Vušković] is actually on page 4 of the paper; but thanks for the pointer! I also find the [Cheung+Graham+Wilson] result somewhat astounding; I'll look into that. $\endgroup$ – Niel de Beaudrap Aug 25 '10 at 11:31
  • $\begingroup$ Reading up on the [Cheung+Graham+Wilson] result: they describe on pages 359-360 that the prime-order Paley graphs are pseudo-random in their sense. If I understand correctly, your suggestion is then that all five-vertex induced labelled subgraphs (of which there are finitely many, and which of course include several specimens of 5-holes) occur approximately as often as each other; this would seem to support your description of a constant-time algorithm. I'd give +10 if I could. Many thanks! $\endgroup$ – Niel de Beaudrap Aug 25 '10 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.