13
$\begingroup$

Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.

However, calculating some bounds on Ramsey numbers is not as difficult:

$$ (1 + o(1)) \frac{\sqrt{2} s}{e} 2^{s/2} \leq R(s,s) \leq s^{-c \log s/\log \log s} 4^{s} $$

My question is:

What are the best possible lower and upper bounds on the diagonal Ramsey numbers that can be calculated in polynomial time (where $s$ is given in unary)?

Or more generally, are there any inapproximation results on Ramsey numbers?

$\endgroup$
11
  • 7
    $\begingroup$ One clear obstacle in proving inapproximability is that given s in unary, R(s,s) can be even exactly computed in nonuniform polynomial time (trivially by hardcoding the answer), which means that this problem cannot be NP-hard unless NP⊆P/poly. We need some evidence for difficulty other than NP-hardness. $\endgroup$ – Tsuyoshi Ito Jan 20 '12 at 15:40
  • 1
    $\begingroup$ Valiant’s “second” paper about #P (SICOMP 1979) contains results about class #P_1, which is a subclass of #P where the input is unary. Although it may not be related directly to the current question, it might be still interesting to take a look at them. $\endgroup$ – Tsuyoshi Ito Jan 20 '12 at 15:57
  • $\begingroup$ @TsuyoshiIto I am not sure how to approach this question with $s$ in binary, since $R(s,s)$ is exponential in $s$. I guess we could make a decision problem like $f(s,r) = 1$ if $R(s,s) \leq 2^r$ which would be good enough for approximation. Or do you know a more standard way to make this question more interesting? $\endgroup$ – Artem Kaznatcheev Jan 20 '12 at 16:35
  • $\begingroup$ I am not saying that the question is uninteresting. Just that we need something other than NP-hardness, and this rules out the use of certain common methods which people would first try otherwise. #P_1-hardness is an example of evidences of difficulty which do not imply NP-hardness, although I am not sure if it is possible (or even realistic to try) to prove that computing R(s,s) is #P_1-hard. $\endgroup$ – Tsuyoshi Ito Jan 20 '12 at 18:05
  • 3
    $\begingroup$ @TsuyoshiIto that's an excellent point you make. One thing I'm wondering about is this: Papadimitriou's program for understanding the complexity of search problems identifies certain "templates" that guarantee existence, but for which search is hard (Nash, pigeonhole principle etc). The upper bounds for Ramsey numbers come from the probabilistic method IINM - maybe there are some derandomizations (a la Moser + LLL) that might yield something ? $\endgroup$ – Suresh Venkat Jan 20 '12 at 20:52

Your Answer

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

Browse other questions tagged or ask your own question.