Paley graph
Overview
 
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, and specifically graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, Paley graphs, named after Raymond Paley
Raymond Paley
Raymond Edward Alan Christopher Paley was an English mathematician. Paley was born in Bournemouth, England. He was educated at Eton. From there he entered Trinity College, Cambridge where he showed himself the most brilliant student among a remarkable collection of fellow undergraduates...

, are dense
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...

 undirected graphs constructed from the members of a suitable finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 by connecting pairs of elements that differ in a quadratic residue. The Paley graphs form an infinite family of conference graph
Conference graph
In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, and It is the graph associated with a symmetric conference matrix, and consequently its order v must be 1 and a sum of two squares....

s, which yield an infinite family of symmetric conference matrices
Conference matrix
In mathematics, a conference matrix is a square matrix C with 0 on the diagonal and +1 and −1 off the diagonal, such that CTC is a multiple of the identity matrix I...

. Paley graphs allow graph-theoretic tools to be applied to the number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

 of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

Paley graphs are closely related to the Paley construction for constructing Hadamard matrices
Hadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...

 from quadratic residues .
They were introduced as graphs independently by and .
 
x
OK