Paley graphs

David Penman

The Paley graph $P_{q}$ has vertex set the finite field with $q=p^{n}$ elements, two vertices $x$ and $y$ being adjacent if and only if $x-y$ is a (non-zero) square in the field. Although these are in some sense very concrete objects, we shall see reasons for believing that they often act as a guide to the typical behaviour of a random graph $G(n,1/2)$ for large $n$. (Here $G(n,1/2)$ is the random graph on $n$ labelled vertices, each potential edge being present or absent equiprobably). An attractive feature of Paley graphs is the number of other parts of mathematics they interact with, including first-order logic and surface topology. I shall give a broad overview of their properties and discuss some new results and open problems as well.