Lower bounds for small diagonal Ramsey numbers (Q1820171)

For p a prime that is congruent to 1 modulo 4, let \(G_ p\) be the self complementary graph with vertices \(\{\) 0,1,...,p-1\(\}\) and edges the pairs whose difference is a quadratic residue modulo p. If \(k=k(p)\) is the order of the largest clique in \(G_ p\), then clearly the diagonal Ramsey number \(r(K_{k+1},K_{k+1})=r(k+1)\) exceeds p. Using the graph \(G_ p\) a graph \(H_ p\) on \(2p+2\) vertices with clique number \(k+1\) is constructed, and this graph implies that \(r(k+2)>2p+2\). Also, for each of the primes \(p\leq 3000\) a computer search to determine the value of k associated with p was made, and these findings are summarized in a table. These results generate some improved lower bounds for diagonal Ramsey numbers.