Combinatorics Seminar

The Ramsey number r(3,k) is the least N such that every N-vertex graph contains either a triangle or an independent set of size k. Since 1995 it has been known that r(3,k) has order of magnitude k^2/log(k), and determining the correct leading constant has generated much interest. Shearer obtained an upper bound of r(3,k) <= (1+o(1))k^2/log(k) in 1983 and approximately ten years ago careful analysis of the triangle-free process (where a random graph is evolved under the restriction that no triangles are created) showed that r(3,k) >= (1/4+o(1) )k^2/log(k). In May 2025 Campos, Jenssen, Michelen, and Sahasrabudhe showed that r(3,k) >= (1/3+o(1))k^2/log(k) by modifying (and considerably simplifying) the triangle-free process to obtain a superior construction. We prove that r(3,k) >= (1/2+o(1))k^2/log(k) (the conjectured optimal constant), using a still further simplification that avoids the triangle-free process altogether.