Graph Ramsey theory and the polynomial hierarchy (Q5943091)

One of the usual ways to formulate Ramsey theory statements for graphs is by using arrowing notation. \(F\to (G,H)\) means that if the edges of \(F\) are colored red and blue, either a red \(G\) or a blue \(H\) must occur. \textit{S. A. Burr} [Algorithms Comb. 5, 46-52 (1990; Zbl 0715.68035)] proved that arrowing, the problem of deciding \(F \rightarrow (G, H)\), lies in \(\Pi_2^p:= \text{coNP}^{\text{NP}}\) and it is coNP-hard. In this paper it is shown that arrowing is \(\Pi_2^p\)-complete, proving Burr's conjecture. Using Chvátal's result in graph Ramsey theory [cf. \textit{A. Chvátal}, J. Graph Theory 1, 93 (1977; Zbl 0351.05120)] it is shown that deciding \(F \rightarrow (T, K_n)\) is \(\Pi_2^p\)-complete for any fixed tree \(T\) of size at least two. Deciding \(F\rightarrowtail(P_3, P_n)\), the induced subgraph version of arrowing, is also \(\Pi_2^p\)-complete. These results are important in complexity theory as they are among the very few natural examples of problems complete for a class in a higher level of the polynomial hierarchy, justifying its existence.