<p>Calculating the diagonal <a href="http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers">Ramsey numbers</a> R(s,s) is hard. There is a famous quote from Joel Spencer:</p>

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

<p>However, calculating some bounds on Ramsey numbers is not as difficult:</p>

<p>$$
 (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}
$$</p>

<p>My question is:</p>

<blockquote>
  <p>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)?</p>
</blockquote>

<p>Or more generally, are there any inapproximation results on Ramsey numbers?</p>

CC BY-SA 3.0
2012-01-20T15:40:43.083Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-20T15:57:00.360Z
Valiant’s “second” paper about #P ([SICOMP 1979](http://dx.doi.org/10.1137/0208032)) 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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-20T16:35:46.130Z
@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?
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-20T18:05:19.817Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-20T20:52:41.493Z
@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 ?
Suresh Venkat
CC BY-SA 3.0
2012-01-21T05:37:44.200Z
@Suresh: Are you talking about deterministic construction of a graph witnessing a lower bound of R(s,s)?  That is an interesting topic in itself, but I fail to see a connection to the current question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-21T08:02:59.463Z
there are upper bounds obtainable via the probabilistic method. I was thinking if there's a way to make them constructive and efficient.
Suresh Venkat
CC BY-SA 3.0
2012-01-23T15:22:22.587Z
@Suresh: That is something different from this question.  A proved upper bound is a proved upper bound, and how it is proved has nothing to do with the complexity of computing or approximating the Ramsey number.  How it is proved becomes relevant only when you try to construct the graph witnessing a lower bound or the algorithm to find a clique/anti-clique witnessing an upper bound.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-23T15:29:53.247Z
Slightly related to the question: [Sparse problems in NP thought to not be in P](http://blog.computationalcomplexity.org/2010/07/spares-problems-in-np-thought-to-not-be.html) by Bill Gasarch on the Computational Complexity blog, July 2010.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-29T20:53:49.733Z
@TsuyoshiIto I think I still don't have a clear understanding of how to think about the complexity of computing R(s,s), let alone approximating it, especially in light of your comments. I kind of want to ask the simpler question of the complexity of computing R(s,s) but not sure if it is a better fit for cstheory.SE, cs.SE, math.SE, or MO. I.e. is it too basic? Is it too math-y?
Artem Kaznatcheev
CC BY-SA 3.0
2012-03-29T21:40:39.223Z
I do not have a clear understanding, either.  I personally think that your simpler question is appropriate here on cstheory, although I have no idea whether a useful answer is known.  For example, it would be interesting if computing R(s,s) given s in _binary_ is known to be NP-hard.  By the way, it seems that there is a generalization of the notion of Ramsey number for which some hardness is known: [Schaefer JCSS 2001](http://www.sciencedirect.com/science/article/pii/S002200000091729X).
Tsuyoshi Ito
<cc.complexity-theory><co.combinatorics><approximation-hardness><ramsey-theory>
Approximating and bounding Ramsey numbers
Artem Kaznatcheev
# Approximating and bounding Ramsey numbers

(Asked by: username_0 on 2012-01-20)

Calculating the diagonal [Ramsey numbers](http://en.wikipedia.org/wiki/Ramsey%27s_theorem#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?

**Tags:** cc.complexity-theory, co.combinatorics, approximation-hardness, ramsey-theory

> **Comments:**
> **username_1**: 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.  
> **username_1**: Valiant’s “second” paper about #P ([SICOMP 1979](http://dx.doi.org/10.1137/0208032)) 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.  
> **username_0**: @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?  
> **username_1**: 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.  
> **username_2**: @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 ?  
> **username_1**: @Suresh: Are you talking about deterministic construction of a graph witnessing a lower bound of R(s,s)?  That is an interesting topic in itself, but I fail to see a connection to the current question.  
> **username_2**: there are upper bounds obtainable via the probabilistic method. I was thinking if there's a way to make them constructive and efficient.  
> **username_1**: @Suresh: That is something different from this question.  A proved upper bound is a proved upper bound, and how it is proved has nothing to do with the complexity of computing or approximating the Ramsey number.  How it is proved becomes relevant only when you try to construct the graph witnessing a lower bound or the algorithm to find a clique/anti-clique witnessing an upper bound.  
> **username_1**: Slightly related to the question: [Sparse problems in NP thought to not be in P](http://blog.computationalcomplexity.org/2010/07/spares-problems-in-np-thought-to-not-be.html) by Bill Gasarch on the Computational Complexity blog, July 2010.  
> **username_0**: @TsuyoshiIto I think I still don't have a clear understanding of how to think about the complexity of computing R(s,s), let alone approximating it, especially in light of your comments. I kind of want to ask the simpler question of the complexity of computing R(s,s) but not sure if it is a better fit for cstheory.SE, cs.SE, math.SE, or MO. I.e. is it too basic? Is it too math-y?  
> **username_1**: I do not have a clear understanding, either.  I personally think that your simpler question is appropriate here on cstheory, although I have no idea whether a useful answer is known.  For example, it would be interesting if computing R(s,s) given s in _binary_ is known to be NP-hard.  By the way, it seems that there is a generalization of the notion of Ramsey number for which some hardness is known: [Schaefer JCSS 2001](http://www.sciencedirect.com/science/article/pii/S002200000091729X).  

---

## 0 answers

