Lower bounds for small diagonal ramsey numbers

Abstract

Let p = 4r + 1 be a prime. Let G be the graph on the p points 0, 1,..., p-1 formed by connecting two points with an edge iff their difference is a quadratic residue mod p. Let k be the size of the largest clique contained in G. Then it is well known that the diagonal Ramsey number R2(k + 1) > p. We show R2(k + 2) > 2p + 2. We also compute k for all p < 3000. © 1986.