Paley graphs
David Penman
Essex
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.