Ghent University Academic Bibliography

Advanced

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

Jan Goedgebeur UGent and Stanisław P Radziszowski (2013) ELECTRONIC JOURNAL OF COMBINATORICS. 20(1).
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.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Ramsey number, upper bound, computation, GRAPHS
journal title
ELECTRONIC JOURNAL OF COMBINATORICS
Electron. J. Comb.
volume
20
issue
1
article number
P30
pages
28 pages
Web of Science type
Article
Web of Science id
000320331900007
JCR category
MATHEMATICS
JCR impact factor
0.568 (2013)
JCR rank
158/302 (2013)
JCR quartile
3 (2013)
ISSN
1077-8926
project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
language
English
UGent publication?
yes
classification
A1
copyright statement
I have retained and own the full copyright for this publication
id
3235132
handle
http://hdl.handle.net/1854/LU-3235132
date created
2013-06-04 15:30:31
date last changed
2017-05-29 12:26:46
@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},
}

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.