New computational upper bounds for Ramsey numbers \(R(3,k)\) (Q1953415)

Summary: Using computational techniques we derive six new upper bounds on the classical two-color Ramsey numbers: \(R(3,10) \leq 42\), \(R(3,11) \leq 50\), \(R(3,13) \leq 68\), \(R(3,14) \leq 77\), \(R(3,15) \leq 87\), and \(R(3,16) \leq 98\). All of them are improvements by one over the previously best known bounds. Let \(e(3,k,n)\) denote the minimum number of edges in any triangle-free graph on \(n\) vertices without independent sets of order \(k\). The new upper bounds on \(R(3,k)\) are obtained by completing the computation of the exact values of \(e(3,k,n)\) for all \(n\) with \(k \leq 9\) and for all \(n \leq 33\) for \(k = 10\), and by establishing new lower bounds on \(e(3,k,n)\) for most of the open cases for \(10 \leq k \leq 15\). The enumeration of all graphs witnessing the values of \(e(3,k,n)\) is completed for all cases with \(k \leq 9\). We prove that the known critical graph for \(R(3,9)\) on 35 vertices is unique up to isomorphism. For the case of \(R(3,10)\), first we establish that \(R(3,10)=43\) if and only if \(e(3,10,42)=189\), or equivalently, that if \(R(3,10)=43\) then every critical graph is regular of degree 9. Then, using computations, we disprove the existence of the latter, and thus show that \(R(3,10) \leq 42\).