A Note on Constructive Lower Bounds for the Ramsey Numbers R(3, t)

We present a simple explicit construction, in terms of t, of a graph that is triangle-free, has independence number t, and contains more than 56((t − 1)/2)log 6/log 4 ∈ Ω(t1.29) vertices. This result is a (feasibly) constructive proof that the Ramsey number R(3, t) ∈ Ω(t1.29). This improves the best previous constructive lower bound of R(3, t) > t(2 log 2)/3(log 3 − log 2) ∈ Ω(t1.13) , due to P. Erdős (1966. J. Combin. Theory17, 149-153). Also, our result yields a simple explicit construction, in terms of k, of a triangle-free k-chromatic graph whose size is O(klog 6/(log 6 − log 4)) ⊂ O(k4.42).