<p>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", <a href="http://dx.doi.org/10.1007/s00493-005-0012-8" rel="noreferrer">Combinatorica 2005</a>, 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-24T21:07:52.457Z
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.
David Eppstein
CC BY-SA 2.5
2010-08-25T11:31:06.540Z
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.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-25T13:36:25.410Z
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!
Niel de Beaudrap
CC BY-SA 2.5
2010-08-24T18:54:38.723Z
2010-08-24T21:14:17.037Z
2010-08-24T21:14:17.037Z
David Eppstein
<p>The <a href="http://en.wikipedia.org/wiki/Paley_graph" rel="nofollow">Paley graphs</a> P<sub>q</sub> are those whose vertex-set is given by the <a href="http://en.wikipedia.org/wiki/Finite_field" rel="nofollow">finite field</a> GF(q), for prime powers q&equiv;1&nbsp;(mod&nbsp;4), and where two vertices are adjacent if and only if they differ by a<sup>2</sup> for some a&nbsp;&isin;&nbsp;GF(q). In the case that q is prime, the finite field GF(q) is just the set of integers modulo q.</p>

<p>In a <a href="http://dx.doi.org/10.1016/j.disc.2005.10.018" rel="nofollow">recent paper</a>, Maistrelli and Penman show that the only Paley graph which is <a href="http://en.wikipedia.org/wiki/Perfect_graph" rel="nofollow"><em>perfect</em></a> (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<sub>q</sub> are perfect for q prime.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Perfect_graph_theorem#Characterizations_and_the_perfect_graph_theorems" rel="nofollow">Strong Perfect Graph Theorem</a> asserts that a graph G is perfect if and only if both G and its complement lacks <em>odd holes</em> (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.</p>

<p><strong>Question.</strong> For q&equiv;1&nbsp;(mod&nbsp;4) prime, is there a poly(q) algorithm for finding an odd hole in P<sub>q</sub>? Is there a polylog(q) algorithm? Randomness and popular number-theoretic conjectures are allowed.</p>

<ds.algorithms><graph-theory>
Finding odd holes in circulant Paley graphs
Niel de Beaudrap
# Finding odd holes in circulant Paley graphs

(Asked by: username_0 on 2010-08-17)

The [Paley graphs](http://en.wikipedia.org/wiki/Paley_graph) Pq are those whose vertex-set is given by the [finite field](http://en.wikipedia.org/wiki/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](http://dx.doi.org/10.1016/j.disc.2005.10.018), Maistrelli and Penman show that the only Paley graph which is [*perfect*](http://en.wikipedia.org/wiki/Perfect_graph) (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](http://en.wikipedia.org/wiki/Perfect_graph_theorem#Characterizations_and_the_perfect_graph_theorems) 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.

**Tags:** ds.algorithms, graph-theory


---

## 1 answers

### Answer by username_1 on 2010-08-24. Score: 10 | Accepted answer

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](http://dx.doi.org/10.1007/s00493-005-0012-8), 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.

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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!  

---

