Semidefinite Programming and Ramsey Numbers
Date
2021-01
Authors
Pfender, Florian
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Abstract
Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values R(K−4, K−4, K−4) = 28, R(K8,C5) = 29, R(K9,C6) = 41, R(Q3,Q3) = 13, R(K3,5,K1,6) = 17, R(C3,C5,C5) = 17, and R(K−4, K−5; 3) = 12. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
Series Number
Journal Issue
Is Version Of
Versions
Article
Semidefinite Programming and Ramsey Numbers
(
2020-09-11)
Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper.
We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values R(K−4, K−4, K−4) = 28, R(K8,C5)=29, R(K9,C6)=41, R(Q3,Q3)=13, R(K3,5,K1,6)=17, R(C3,C5,C5)=17, and R(K−4, K−5; 3) = 12.
We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
Series
Academic or Administrative Unit
Type
Article
Comments
This article is published as Lidicky, Bernard, and Florian Pfender. "Semidefinite programming and Ramsey numbers." SIAM Journal on Discrete Mathematics 35, no. 4 (2021): 2328-2344. https://doi.org/10.1137/18M1169473. Posted with permission.
Rights Statement
© 2021, Society for Industrial and Applied Mathematics