A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\) (Q1204480): Difference between revisions

The Ramsey number \(R(s,t)\) is the smallest integer \(n\) for which every graph on \(n\) vertices contains either a clique of size \(s\) or an independent set of size \(t\). In this paper, the authors present a simple constructive proof that \[ R(3,t)>{5\over 6}\left({t-1\over 2}\right)^{\log 6/\log 4}\in\Omega(t^{1.29}). \] This improves the best previous constructive lower bound of \[ R(3,t)>t^{(2\log 2)/3(\log 3-\log 2)}\in\Omega(t^{1.13}), \] due to \textit{P. Erdős} [J. Comb. Theory 1, 149-153 (1966; Zbl 0144.454)]. Moreover, the authors' result yields an explicit construction of a triangle-free \(k\)-chromatic graph of size \[ O(k^{\log 6/(\log 6-\log 4)}){\subset O(k^{4.42})}. \] {}.