The Ramsey number R(3, K10-e) and computational bounds for R(3,G)

Using computer algorithms we establish that the Ramsey number R(3, K-10 - e) is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of R(3, K-k - e) for 11 <= k <= 16, and show by construction a new lower bound 55 <= R(3, K-13 - e). The new upper bounds on R(3, K-k - e) are obtained by using the values and lower bounds on e(3, K-l - e, n) for l <= k, where e(3, K-k - e, n) is the minimum number of edges in any triangle-free graph on n vertices without K-k - e in the complement. We complete the computation of the exact values of e(3, K-k - e, n) for all n with k <= 10 and for n <= 34 with k = 11, and establish many new lower bounds on e(3, K-k - e, n) for higher values of k. Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely R(3, K-10 - K-3 - e) = 31 and R(3, K-10 - P-3 - e) = 31. For graphs G on 10 vertices, besides G = K-10, this leaves 6 open cases of the form R(3, G). The hardest among them appears to be G = K-10 - 2K(2), for which we establish the bounds 31 <= R(3, K-10 - 2K(2)) <= 33.

from #MedicinebyAlexandrosSfakianakis via xlomafota13 on Inoreader http://ift.tt/2r3QroG
via IFTTT