2
$\begingroup$

The Ramsey function $R(k,x)$ is defined as the minimal integer $n$ such that any graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $x$. Miklós Ajtai, János Komlós and Endre Szemerédi(1980) shows that $R(3,x)≤cx^2/\ln x$ and further that, for each $k$, $R(k,x)\leq c_kx^{k−1}/(\ln x)^{k−2}$, here $c_k>0$ is a constant. It is well known that $c'x^2/\ln x \leq R(3,x)\leq cx^2/\ln x$ for some $c>c'>0$.

I want to know for $k\ge 4$, is there any better upper bounds for the Ramsey function $R(k,x)$? I care more about the order of the upper bound instead of the value of $c_k$.

$\endgroup$
3
  • $\begingroup$ I think this recent improvement to the diagonal Ramsey number upper bound was a big deal: arxiv.org/abs/2005.09251 $\endgroup$ Mar 20, 2021 at 20:38
  • $\begingroup$ But I guess if you're looking at the regime of $k$ fixed and $x$ growing, that's a different question... $\endgroup$ Mar 20, 2021 at 20:39
  • $\begingroup$ @SamHopkins Thank you a lot! $\endgroup$
    – ZZP
    Mar 21, 2021 at 15:20

1 Answer 1

2
$\begingroup$

I don't have the reputation to comment, but I don't think there has been any improvement on the result you mentioned. See pg 5 of this survey by Conlon, Fox and Sudakov from 2015 https://arxiv.org/pdf/1501.02474.pdf

$\endgroup$
1
  • 1
    $\begingroup$ No need to comment! This is a perfectly good answer! $\endgroup$ Mar 22, 2021 at 16:00

Your Answer

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

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