Department of
Applied
Mathematics

Bounding small Ramsey numbers

Bernard Lidický

Abstract

(joint work with Florian Pfender)

Bounding exact Ramsey numbers is a problem restricted to relatively small graphs. The flag algebra method can only 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. This technique may be adapted to address other questions for smaller graphs with the flag algebra method.

We use the theory of flag algebras to find new upper bounds for several small graph and hypergraph Ramsey numbers. In particular, we prove the exact values R(K_4^-,K_4^-,K_4^-)=28, R(K_8,C_5)= 29, R(K_9,C_6)= 41, R(Q_3,Q_3)=13, R(K_{3,5},K_{1,6})=17, R(C_3, C_5, C_5)= 17, and R(K_4^-,K_5^-;3)= 12, and improve many additional upper bounds.