15
$\begingroup$

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.

Is it possible that there exists an absolute constant $C>0$ and polynomial $p\in \mathbb{Q}[x]$ such that for all $k$ (or perhaps for all sufficiently large $k$) $$ R(k) = C^kp(k)? $$

Even the asymptotic behaviour of $R(k$) is not known (it is known that $\sqrt{2}^{k(1+o(1))}\leq R(k)\leq 4^{k(1+o(1)}$.) So a proof of such an exact result is certainly out of reach. But showing that there cannot be such a formula might be possible.

There are exact formulas known for related Ramsey-type functions (e.g. fractional Ramsey numbers [2] and Ramsey numbers restricted to various classes of graphs, such as planar graphs, line graphs, and perfect graphs [1,3].) As far as I can see, however, the question of an exact formula for the classical Ramsey numbers has not been considered.

[1] Belmonte, Heggernes, van't Hof and Saei, Ramsey numbers for line graphs and perfect graphs, Computing and combinatorics, 204–215, Lecture Notes in Comput. Sci., 7434, Springer, Heidelberg, 2012. http://link.springer.com/chapter/10.1007%2F978-3-642-32241-9_18

[2] Brown and Hoshino, Proof of a conjecture on fractional Ramsey numbers, J. Graph Theory 63 (2010), no. 2, 164–178. http://onlinelibrary.wiley.com/doi/10.1002/jgt.20416/pdf

[3] Steinberg and Tovey, Planar Ramsey numbers, J. Combin. Theory Ser. B 59 (1993), no. 2, 288–296

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Somehow, this makes me think of pattern avoidance: en.wikipedia.org/wiki/Permutation_pattern The permutations that avoid the pattern 1324 is still unknown, and finding a formula for these is according to some, a really tough question (I recall Zeilberger compares this to RH).... $\endgroup$
    – Per Alexandersson
    Nov 26, 2014 at 9:14
  • 13
    $\begingroup$ Here it's mandatory to quote Paul Erdős: ”[...] 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, [...], we should marshal all our computers and our mathematicians and attempt to find the value. Suppose, instead, that they ask for R(6,6). In that case, [...], we should attempt to destroy the aliens.” $\endgroup$
    – Pietro Majer
    Nov 26, 2014 at 10:23
  • 5
    $\begingroup$ I see no reason why there can't be an exact formula, but no reason why it should be of the given form. Something involving binomial coefficients is more likely, but of course this is pure speculation. $\endgroup$
    – Brendan McKay
    Nov 26, 2014 at 10:43

1 Answer 1

Reset to default
5
$\begingroup$

Obviously I cannot prove it, but I think the answer is almost surely 'no'. In fact, I don't think any combination of polynomials, exponentials, and factorials will do the job: I believe you should need (at least) to have involvement of the parity mod $2$ function.

My reason for this is of course quite trivial. When you try to find a lower bound example for $R(3,4)$, you observe that neighbourhoods are independent hence the maximum degree of the graph you are constructing is three. Then you note that every vertex has at most five non-neighbours, otherwise you use the value of $R(3,3)$ in the non-neighbourhood. So you think: OK, I should have a $3$-regular graph on $9$ vertices. Unfortunately this doesn't exist because $3$ and $9$ are both odd, and you are forced to use $8$ vertices.

I would expect this kind of parity obstacle to show up quite often.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.