Semidefinite Programming and Ramsey Numbers
arXiv:1704.03592 · doi:10.1137/18M1169473
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 , , , , , , and . We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
arXiv comment17 pages, 2 figures
References in corpus (6)
- On the Number of Pentagons in Triangle-Free Graphs
- The Clique Density Theorem
- Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
- Minimum number of monotone subsequences of length 4 in permutations
- Crossing numbers of complete tripartite and balanced complete multipartite graphs
- Pentagons in triangle-free graphs