New computational upper bounds for Ramsey numbers R(3,k)
 Author
 Jan Goedgebeur (UGent) and Stanisław P Radziszowski
 Organization
 Project
 HPCUGent: the central High Performance Computing infrastructure of Ghent University
 Abstract
 Using computational techniques we derive six new upper bounds on the classical twocolor Ramsey numbers: R(3, 10) <= 42, R(3, 11) <= 50, R(3,13) <= 68, R(3,14) <= 77,R(3,15) <= 87, and R(3,16) <= 98. All of them are improvements by one over the previously best published bounds. Let e(3,k,n) denote the minimum number of edges in any trianglefree 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 <= 9 and for all n <= 33 for k = 10, and by establishing new lower bounds on e(3,k,n) for most of the open cases for 10 <= k <= 15. The enumeration of all graphs witnessing the values of e(3,k,n) is completed for all cases with k <= 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) <= 42.
 Keywords
 Ramsey number, upper bound, computation, GRAPHS
Downloads

282456061PB.pdf
 full text
 
 open access
 
 
 331.28 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU3235132
 Chicago
 Goedgebeur, Jan, and Stanisław P Radziszowski. 2013. “New Computational Upper Bounds for Ramsey Numbers R(3,k).” Electronic Journal of Combinatorics 20 (1).
 APA
 Goedgebeur, J., & Radziszowski, S. P. (2013). New computational upper bounds for Ramsey numbers R(3,k). ELECTRONIC JOURNAL OF COMBINATORICS, 20(1).
 Vancouver
 1.Goedgebeur J, Radziszowski SP. New computational upper bounds for Ramsey numbers R(3,k). ELECTRONIC JOURNAL OF COMBINATORICS. 2013;20(1).
 MLA
 Goedgebeur, Jan, and Stanisław P Radziszowski. “New Computational Upper Bounds for Ramsey Numbers R(3,k).” ELECTRONIC JOURNAL OF COMBINATORICS 20.1 (2013): n. pag. Print.
@article{3235132, abstract = {Using computational techniques we derive six new upper bounds on the classical twocolor Ramsey numbers: R(3, 10) {\textlangle}= 42, R(3, 11) {\textlangle}= 50, R(3,13) {\textlangle}= 68, R(3,14) {\textlangle}= 77,R(3,15) {\textlangle}= 87, and R(3,16) {\textlangle}= 98. All of them are improvements by one over the previously best published bounds. Let e(3,k,n) denote the minimum number of edges in any trianglefree 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 {\textlangle}= 9 and for all n {\textlangle}= 33 for k = 10, and by establishing new lower bounds on e(3,k,n) for most of the open cases for 10 {\textlangle}= k {\textlangle}= 15. The enumeration of all graphs witnessing the values of e(3,k,n) is completed for all cases with k {\textlangle}= 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) {\textlangle}= 42.}, articleno = {P30}, author = {Goedgebeur, Jan and Radziszowski, Stanis\unmatched{0142}aw P}, issn = {10778926}, journal = {ELECTRONIC JOURNAL OF COMBINATORICS}, keyword = {Ramsey number,upper bound,computation,GRAPHS}, language = {eng}, number = {1}, pages = {28}, title = {New computational upper bounds for Ramsey numbers R(3,k)}, volume = {20}, year = {2013}, }