1
$\begingroup$

We have: $$R(\underbrace{3,\ldots,3}_{n\ 3's})=m\implies R(\underbrace{3,\ldots,3}_{n+1\ 3's})\leq(n+1)m-n+1$$

And:

$$R(l,l)=m\implies R(l+1,l+1)\geq m+\left\lceil\frac{m-l}{l-1}\right\rceil$$

Can we do any better ( these were using pigeonhole principle)

$\endgroup$
1

1 Answer 1

2
+50
$\begingroup$

I looked at two survey sources about Ramsey numbers: the article "Ramsey's_theorem" from Wikipedia and "Small Ramsey numbers" by Stanisław P. Radziszowski. The latter is a dynamic survey from Electronic Journal of Combinatorics, the last revision is #16: January 15, 2021. The respective references are copied from these sources.

According to Wikipedia, the best known values or bounding ranges for diagonal Ramsey numbers $R(s,s)$ with $s\le 10$ are the following

$$\begin{matrix} s & 1 & 2 & 3 & 4 & 5 \\ R(s,s) & 1 & 2 & 6 & 18 & 43-48 \\ \\ s & 6 & 7 & 8 & 9 & 10 \\ R(s,s) & 102-161 & 205-497 & 282-1532 & 565-5366 & 798-17730 \end{matrix} $$

According to the Radziszowski's survey (2.1.i), "there are really only two general upper bound inequalities useful for small parameters, namely 2.3.a and 2.3.b. Stronger upper bounds for specific parameters were difficult to obtain, and they often involved massive computations, like those for the cases of $(3,8)$ [McZ], $(3,10)$ [GoR1], $(4,5)$ [MR4], $(4,6)$ and $(5,5)$ [MR5, AnM1]. The bound $R(6, 6) \le 166$, only $1$ more than in [Mac], is an easy consequence of a theorem in [Walk] (2.3.b) and $R (4, 6) \le$ 41. Since 2020, we know that $R (6, 6) \le 161$ [AnM2]". The referred bounds 2.3.a and 2.3.b are $R (k, l) \le R (k −1, l) + R (k, l −1)$, with strict inequality when both terms on the right hand side are even [GG] and $R (k, k) \le 4R (k, k − 2) + 2$ [Walk], respectively.

According to Wikipedia, the first of these inequalities may be applied inductively to prove that $$R(r,s)\le {r+s-2\choose r-1}.$$ In particular, this result, due to Erdős and Szekeres, implies that when $r = s$, $$\displaystyle R(s,s)\leq (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.$$

An exponential lower bound,

$${\displaystyle R(s,s)\geq (1+o(1)){\frac {s}{{\sqrt {2}}e}}2^{s/2},}$$

was given by Erdős in 1947 and was instrumental in his introduction of the probabilistic method. There is a huge gap between these two bounds: for example, for $s = 10$, this gives $$101 \le R(10, 10) \le 48,620.$$ Nevertheless, the exponential growth factors of either bound were not improved for a long time, and for the lower bound it still stands at $\sqrt{2}$. There is no known explicit construction producing an exponential lower bound. The best known lower and upper bounds for diagonal Ramsey numbers are

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

due to Spencer and Conlon, respectively; a 2023 preprint by Morris, Campos, Griffiths and Sahasrabudhe claims to have made exponential progress using an algorithmic construction relying on a graph structure called a "book",[18][19] improving the upper bound to $R(s,s)\leq (4-\varepsilon )^{s}$ ... with $\varepsilon =2^{-7}$ and it is believed that the parameter $\varepsilon$ can be optimized.

Radziszowski's survey in (2.3.7) provides the following upper bounds. In 2009, Conlon [Con1] obtained the best until then upper bound for the diagonal case $$R(k+1,k+1)\le {2k \choose k}k^{-c\log k/\log \log k}.$$ In 2020, Sah [Sah] improved it to $$R(k+1,k+1)\le {2k \choose k}k^{-c(\log k)^2}.$$


According to the survey, until 2016, the only known value of a multicolor classical Ramsey number was: $R_3(3) = R (3, 3, 3) = R (3, 3, 3 ; 2) = 17$. [GG] Known lower bounds for small parameter diagonal multicolor Ramsey numbers $R_r(m)$, with references can be seen in Table X. In particular, $R_4(3)\le 51$, $R_5(3)\le 162$, $R_6(3)\le 538$, $R_7(3)\le 1682$, and $R_8(3)\le 5288$.

(6.2.b) $R_r(3)\ge 3R_{r-1}(3)+R_{r-3}(3)-3$ [Chu1].

(6.2.c) $R_r(m) \ge c_m(2m − 3)^r$, and some slight improvements of this bound for small values of $m$ were described in [AbbH, Gi1, Gi2, Song2]. For $m = 3$, the best known lower bound is $R_r (3) \ge (3.199\dots)^r$ [XXER].

(6.2.d) $R_r(3) \le r !(e − e^{− 1} + 3 ) / 2 \approx 2.67 r !$ [Wan] improved over the classical upper bound $3r !$ in [GG, GRS]. This was further improved to $R_r (3) \le r ! (e −1/ 6) + 1 \approx 2.55 r !$ for all $r \ge 4$ [XuXC]. Drawing from the latter, further conditional upper bounds depending on the value of $R_4(3)$ were obtained in [Eli]. In particular, assuming that $R_4(3) = 51$, we have $R_r (3) \le r ! (e −5/ 8) + 1 \approx 2.09 r !$ for all $r \ge 4.$

(6.2.e) The limit $L =\lim_{r\to\infty} R_r(3)^{1/ r}$ exists, though it can be infinite [ChGri]. It is known that $3.199 < L$, as implied by (c) above. The lower bounds on the limits ... The best lower bounds for $R_r (k)$ from the $k$ -th residue Paley graphs for $k = 3$ and $k = 4$ are described in [LocMc], though they are much weaker than those in Table X.

(6.2.w) In 2020, Conlon and Ferber [ConFer] showed constructively that $R_3(k) > 2^{7k / 8 + o (k)}$ and $R_4(k) > 2^{k / 2}3^{3k / 8 + o (k)}$, and they discussed more general best known lower and upper bounds on $R_r(k)$. An improvement to their construction by Wigderson [Wig] yields $R_r(k) \ge \left(2^{3r / 8−1/4}\right)^{k − o (k)}$, for any fixed $r\ge 2$.

$\endgroup$
1
  • 1
    $\begingroup$ I knew (3,3,3) was 17. Thanks for the read though. $\endgroup$ Commented Jan 26 at 1:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .