CLIQUE NUMBERS OF PALEY GRAPHS

Abstract

The clique number of the Paley graph G(q), where q, is a prime power with q ≡ 1 (mod 4) is known to be Jq, when q, is a square. When q, is a non-square the problem of finding a formula for the clique number seems to be a hard one although its value has been obtained by computer search for prime values of q, satisfying 5 ⋚ q, ⋚ 1601. In this paper we establish a lower bound asymptotically one half of the likely value.