In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally. Paley graphs are named after Raymond Paley. They are closely related to the Paley construction for constructing Hadamard matrices from quadratic residues. They were introduced as graphs independently by Sachs (1962) and Erdős & Rényi (1963). Sachs was interested in them for their self-complementarity properties, while Erdős and Rényi studied their symmetries. Paley digraphs are directed analogs of Paley graphs that yield antisymmetric conference matrices. They were introduced by Graham & Spencer (1971) (independently of Sachs, Erdős, and Rényi) as a way of constructing tournaments with a property previously known to be held only by random tournaments: in a Paley digraph, every small subset of vertices is dominated by some other vertex.
Definition Let q be a prime power such that q ≡ 1 ( mod 4 ) {\textstyle q\equiv 1{\pmod {4}}} . That is, q should either be an arbitrary power of a prime congruent to 1 mod 4 (a Pythagorean prime) or an even power of an odd non-Pythagorean prime. This choice of q implies that in the unique finite field Fq of order q, the element −1 has a square root. Now let V = Fq and let
E = { { a , b } : a − b ∈ ( F q × ) 2 } {\displaystyle E=\left\{\{a,b\}\ :\ a-b\in (\mathbf {F} _{q}^{\times })^{2}\right\}} . If a pair {a,b} is included in E, it is included under either ordering of its two elements. For, a − b = −(b − a), and −1 is a square, from which it follows that a − b is a square if and only if b − a is a square. By definition G = (V, E) is the Paley graph of order q. The sequence of orders of the Paley graphs begins
1, 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, ... (sequence A085759 in the OEIS)
Example For q = 13, the field Fq is just integer arithmetic modulo 13. The numbers with square roots mod 13 are:
±1 (square roots ±1 for +1, ±5 for −1) ±3 (square roots ±4 for +3, ±6 for −3) ±4 (square roots ±2 for +4, ±3 for −4). Thus, in the Paley graph, we form a vertex for each of the integers in the range [0,12], and connect each such integer x to six neighbors: x ± 1 (mod 13), x ± 3 (mod 13), and x ± 4 (mod 13).
Properties The Paley graphs are self-complementary: the complement of any Paley graph is isomorphic to it. One isomorphism is via the mapping that takes a vertex x to xk (mod q), where k is any quadratic nonresidue mod q. Paley graphs are strongly regular graphs, with parameters
s r g ( q , 1 2 ( q − 1 ) , 1 4 ( q − 5 ) , 1 4 ( q − 1 ) ) . {\displaystyle srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1)\right).}
This in fact follows from the fact that the graph is arc-transitive and self-complementary. The strongly regular graphs with parameters of this form (for an arbitrary q) are called conference graphs, so the Paley graphs form an infinite family of conference graphs. The adjacency matrix of a conference graph, such as a Paley graph, can be used to construct a conference matrix, and vice versa. These are matrices whose coefficients are ±1, with zero on the diagaonal, that give a scalar multiple of the identity matrix when multiplied by their transpose. The eigenvalues of Paley graphs are 1 2 ( q − 1 ) {\displaystyle {\tfrac {1}{2}}(q-1)} (with multiplicity 1) and 1 2 ( − 1 ± q ) {\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})} (both with multiplicity 1 2 ( q − 1 ) {\displaystyle {\tfrac {1}{2}}(q-1)} ). They can be calculated using the quadratic Gauss sum or by using the theory of strongly regular graphs. If q is prime, the isoperimetric number i(G) of the Paley graph satisfies the following bounds:
When q is prime, the associated Paley graph is a Hamiltonian circulant graph. Paley graphs are quasi-random: the number of times each possible constant-order graph occurs as a subgraph of a Paley graph is (in the limit for large q) the same as for random graphs, and large sets of vertices have approximately the same number of edges as they would in random graphs.
… excerpt ends here. Continue reading the full article.
