Advanced search
1 file | 334.65 KB

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

Author
Organization
Project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
Abstract
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.
Keywords
computation, almost-complete graphs, triangle-free graphs, Ramsey number, GRAPHS

Downloads

  • 3684-8542-1-PB.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 334.65 KB

Citation

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

Chicago
Goedgebeur, Jan, and Stanisław P Radziszowski. 2013. “The Ramsey Number R(3, K10-e) and Computational Bounds for R(3,G).” Electronic Journal of Combinatorics 20 (4).
APA
Goedgebeur, J., & Radziszowski, S. P. (2013). The Ramsey number R(3, K10-e) and computational bounds for R(3,G). ELECTRONIC JOURNAL OF COMBINATORICS, 20(4).
Vancouver
1.
Goedgebeur J, Radziszowski SP. The Ramsey number R(3, K10-e) and computational bounds for R(3,G). ELECTRONIC JOURNAL OF COMBINATORICS. 2013;20(4).
MLA
Goedgebeur, Jan, and Stanisław P Radziszowski. “The Ramsey Number R(3, K10-e) and Computational Bounds for R(3,G).” ELECTRONIC JOURNAL OF COMBINATORICS 20.4 (2013): n. pag. Print.
@article{5722595,
  abstract     = {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.},
  articleno    = {P19},
  author       = {Goedgebeur, Jan and Radziszowski, Stanisław P},
  issn         = {1077-8926},
  journal      = {ELECTRONIC JOURNAL OF COMBINATORICS},
  keywords     = {computation,almost-complete graphs,triangle-free graphs,Ramsey number,GRAPHS},
  language     = {eng},
  number       = {4},
  pages        = {25},
  title        = {The Ramsey number R(3, K10-e) and computational bounds for R(3,G)},
  volume       = {20},
  year         = {2013},
}

Web of Science
Times cited: