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

(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:
http://hdl.handle.net/1854/LU-3235132

- author
- Jan Goedgebeur UGent and Stanisław P Radziszowski
- organization
- year
- 2013
- 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.