The Ramsey number R(3, K10e) and computational bounds for R(3,G)
 Author
 Jan Goedgebeur (UGent) and Stanisław P Radziszowski
 Organization
 Project
 HPCUGent: the central High Performance Computing infrastructure of Ghent University
 Abstract
 Using computer algorithms we establish that the Ramsey number R(3, K10  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, Kk  e) for 11 <= k <= 16, and show by construction a new lower bound 55 <= R(3, K13  e). The new upper bounds on R(3, Kk  e) are obtained by using the values and lower bounds on e(3, Kl  e, n) for l <= k, where e(3, Kk  e, n) is the minimum number of edges in any trianglefree graph on n vertices without Kk  e in the complement. We complete the computation of the exact values of e(3, Kk  e, n) for all n with k <= 10 and for n <= 34 with k = 11, and establish many new lower bounds on e(3, Kk  e, n) for higher values of k. Using the maximum trianglefree graph generation method, we determine two other previously unknown Ramsey numbers, namely R(3, K10  K3  e) = 31 and R(3, K10  P3  e) = 31. For graphs G on 10 vertices, besides G = K10, this leaves 6 open cases of the form R(3, G). The hardest among them appears to be G = K10  2K(2), for which we establish the bounds 31 <= R(3, K10  2K(2)) <= 33.
 Keywords
 computation, almostcomplete graphs, trianglefree graphs, Ramsey number, GRAPHS
Downloads

368485421PB.pdf
 full text
 
 open access
 
 
 334.65 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU5722595
 Chicago
 Goedgebeur, Jan, and Stanisław P Radziszowski. 2013. “The Ramsey Number R(3, K10e) 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, K10e) and computational bounds for R(3,G). ELECTRONIC JOURNAL OF COMBINATORICS, 20(4).
 Vancouver
 1.Goedgebeur J, Radziszowski SP. The Ramsey number R(3, K10e) 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, K10e) 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, K10  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, Kk  e) for 11 <= k <= 16, and show by construction a new lower bound 55 <= R(3, K13  e). The new upper bounds on R(3, Kk  e) are obtained by using the values and lower bounds on e(3, Kl  e, n) for l <= k, where e(3, Kk  e, n) is the minimum number of edges in any trianglefree graph on n vertices without Kk  e in the complement. We complete the computation of the exact values of e(3, Kk  e, n) for all n with k <= 10 and for n <= 34 with k = 11, and establish many new lower bounds on e(3, Kk  e, n) for higher values of k. Using the maximum trianglefree graph generation method, we determine two other previously unknown Ramsey numbers, namely R(3, K10  K3  e) = 31 and R(3, K10  P3  e) = 31. For graphs G on 10 vertices, besides G = K10, this leaves 6 open cases of the form R(3, G). The hardest among them appears to be G = K10  2K(2), for which we establish the bounds 31 <= R(3, K10  2K(2)) <= 33.}, articleno = {P19}, author = {Goedgebeur, Jan and Radziszowski, Stanisław P}, issn = {10778926}, journal = {ELECTRONIC JOURNAL OF COMBINATORICS}, keywords = {computation,almostcomplete graphs,trianglefree graphs,Ramsey number,GRAPHS}, language = {eng}, number = {4}, pages = {25}, title = {The Ramsey number R(3, K10e) and computational bounds for R(3,G)}, volume = {20}, year = {2013}, }