Bounds for Ramsey numbers of complete graphs dropping an edge (Q2462320)

In the paper under review, Ramsey numbers \(R(K_n-e)\) are investigated, where \(K_n-e\) is obtained from a complete graph of order \(n\) by dropping an edge. In order to get lower bounds for \(R(K_n-e)\), they use so-called Paley graphs: The Paley graph \(G_p\) of prime order \(p\) is the graph with vertex set \(\{0,1,\dots,p-1\}\), where two distinct vertices \(x\) and \(y\) are connected if and only if \((x-y)^{(p-1)/2} \equiv 1 \pmod p\). The main result states that if the Paley graph \(G_p\) of prime order \(p\), where \(p\equiv 1 \pmod 4\), contains no \(K_n-e\), then \(R(K_{n+1}-e)\geq 2p+1\). In particular, \(R(K_{14}-e)\geq 2987\), improving the old bound \(2557\).