I am reading a paper about Ramsey number. There is a statement as following:
It is known that $R(3,t)\le(1+\mathcal{o}(1))\frac{t^2}{\log t}.$ This upper bound easily gives an upper bound of $\chi(G_n^{(3)}),$ $$\max_{G_n^{(3)}}\chi(G_n^{(3)})\le (1+\mathcal{o}(1))2\sqrt{2}\sqrt{\frac{n}{\log n}}$$ where $\chi(G_n^{(3)})$ means a triangle-free graph on $n$ vertices.

The trivial upper bound of $\chi(G_n^{(3)})$ is we find independent number $\alpha(G_n^{(3)})$ (maximum size of independent sets), if we set $n=\frac{t^2}{\log t},$ then the independent number is at least $t$. Then the chromatic number is less than $n-t+1$ meaning that we can color the maximum independent set by 1 color and each remaining vertex by distinct color. But it seems not matched the upper bound given by the author. So I wonder why the upper bound of the chromatic number is true.

  • $\begingroup$ Is their some reason for not revealing the author and title of the paper you are quoting from? $\endgroup$
    – bof
    Apr 4, 2017 at 3:46
  • $\begingroup$ @bof Yes, I don't find a downloadable link for public of this paper. It is by Jeong Han Kim in his famous paper of R(3,t) if someone feels interested. $\endgroup$
    – Connor
    Apr 4, 2017 at 3:54

1 Answer 1


Let $f(t) = (1+o(1))\frac{t^2}{\log t}$ be our upper bound on $R(3,t)$, and let $g(n)$ be its inverse: $g(f(t))=t$. Some work yields the estimate $g(n) = (1+o(1))\sqrt{\frac12 n \log n}$.

The idea is that if $G$ is triangle-free on $n$ vertices, then it contains an independent set of size $g(n)$, and then once you remove that independent set (by assigning it a color), then you get a graph that's triangle-free on $n - g(n)$ vertices. So we can keep doing that repeatedly.

For a bound that probably won't get the right constant factor in the end, suppose we keep doing this until we are down to fewer than $\frac n2$ vertices. Then at each step, we got to remove at least $g(\frac n2)$ vertices, obtaining fewer than $\frac{n/2}{g(\frac n2)}$ independent sets. This gives us the recursion $$M(n) \le \frac{n/2}{g(\frac n2)} + M(\tfrac{n}{2})$$ where I define $M(n) = \displaystyle{\max_{G_n^{(3)}}\chi(G_n^{(3)})}.$ Note that $\frac{n/2}{g(\frac n2)} = (1+o(1))\sqrt{\frac{n}{\log n}}$. Therefore $$M(\tfrac{n}{2}) \le (1+o(1)) C\sqrt{\frac{n/2}{\log (n/2)}} \implies M(\tfrac{n}{2}) \le (1 + o(1))\left(\frac{C}{\sqrt 2} + 1\right)\sqrt{\frac{n}{\log n}}$$ and by some mix of induction and asymptotic analysis we can get $C = 2 + \sqrt 2$.

I assume that doing this more carefully (for example, jumping from $n$ to $(1-\epsilon)n$ instead of all the way to $\frac n2$, and then taking $\epsilon \to 0$) improves the constant. Also, there's probably a better way to analyze this recursion, but you see how it gets us bounds on the order of $O(\frac{n}{g(n)})$.


You must log in to answer this question.

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