Advanced search
1 file | 331.28 KB

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

Author
Organization
Project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
Abstract
Using computational techniques we derive six new upper bounds on the classical two-color 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 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 <= 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

  • 2824-5606-1-PB.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 331.28 KB

Citation

Please use this url to cite or link to this publication:

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 two-color 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 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 {\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         = {1077-8926},
  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},
}

Web of Science
Times cited: