In the notation of Garey and Johnson [1], two problems related to Ramsey Problem were defined:

$\textbf{ARROWING}$

Instance: (Finite) graphs $F$, $G$ and $H$.

Question: Does $F\rightarrow (G, H)$?

$\textbf{STRONG ARROWING}$

Instance: (Finite) graphs $F$, $G$ and $H$.

Question: Does $F\rightarrowtail(G, H)$?

Arrowing: given graphs $F$, $G$, $H$, does every edge-coloring of $F$ with red and blue contains either a red $G$ or a blue $H$?

This problem is $coNP$ for fixed $G$ and $H$, $\Pi_2^p$-complete (i.e. $coNP^{NP}$) [2] in general.

Strong Arrowingg: given graphs $F$, $G$, $H$, does every edge-coloring of $F$ with red and blue contains either a red $G$ or a blue $H$ as an Induced Subgraph? This version is also $\Pi_2^p$-complete in general [2].

However, the proof of Schaefer [2] relied heavily on constructing a suitable graph $F$, thus it is unlikely that a similar construction could be used for the case when $F$ is a complete graph. The computational complexity of determining Ramsey numbers is still open. Some discussions about this problem can be found in [3][4][5], but it is still not clear.

My question: what is the complexity of determining exact Ramsey Number? Can we find a PTAS of it?

As most of the existing related results highly depend on constructions, I am looking for the readers who are familiar with constructions (although a lot of constructions are not known where they are from) of Ramsey Number to give some hints or discussions. Suggestions and comments from TCS scientists are also highly welcome.

[1] Garey, Michael R., and David S. Johnson. "Computer and intractability." A Guide to the Theory of NP-Completeness (1979).

[2] Schaefer, Marcus. "Graph Ramsey theory and the polynomial hierarchy." Proceedings of the thirty-first annual ACM symposium on Theory of computing. ACM, 1999.

[3] Haanpää, Harri. Computational methods for Ramsey numbers. Helsinki University of Technology, 2000.

[4]Schweitzer, Pascal. Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Diss. Saarbrücken, Univ., Diss., 2009, 2009.

[5]Rosta, Vera. "Ramsey theory applications." The Electronic Journal of Combinatorics 1000 (2004): DS13-Dec.

1more comment