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$.

Improve this question
$\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$
    – Sam Hopkins
    Commented 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$
    – Sam Hopkins
    Commented Mar 20, 2021 at 20:39
  • $\begingroup$ @SamHopkins Thank you a lot! $\endgroup$
    – ZZP
    Commented Mar 21, 2021 at 15:20

1 Answer 1

Reset to default
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

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

You must log in to answer this question.

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