Lecture 1. Introduction to Paley graphs

In this lecture, we introduce Paley graphs and discuss their elementary properties with a central focus on their clique numbers. Let q=1 (mod 4) be an odd prime power. Consider the graph Pq , whose vertices are elements of the finite field F_q, where the two vertices x and y are adjacent if x–y is a square in F_q.The resulting graph P_q is called the Paley graph of order q. Paley graphs possess a high degree of symmetry; for example, they are strongly regular (see Section 5.8 in [GM16]). Recall that the clique number of a given graph G, denoted by ω(G), is the size of the largest clique contained in G. Finding reasonable upper bounds on ω(Pq) is a notoriously difficult and open problem. As the first step, we discuss the so-called trivial upper bound ω(Pq) ≤ q. We also mention the lower bound ω(P_q)≫ log(q) obtained by S. Cohen where q is an odd power of a prime. If q=p is a prime, Graham and Ringrose showed the stronger result ω(P_p)≫Ω(log p log log log p) in [GR90]. Returning to the upper bound, Hanson and Petridis [HP21] proved that ω(P_p) ≤ p/2 + 1. The latter result is a recent breakthrough, and our eventual goal in this lecture series is to present a proof of this result.