Graph Ramsey theory and the polynomial hierarchy

In the Ramsey theory of graphs F --> (G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H. Arrowing, the problem of deciding whether F --> (G, H), lies in Pi (p)(2) = coNP(NP) and it was shown to be coNP-hard by Burr [Bur90]. We prove that Arrowing is Pi (p)(2)-complete, simultaneously settling a conjecture of Burr and providing a rare natural example of a problem complete for a higher level of the polynomial hierarchy. We also show that Strong Arrowing, the induced subgraph version of Arrowing, is TB-complete, and that the complexity of not arrowing stars is the same as that of finding a perfect matching. (C) 2001 Academic Press.