Paley graph

Paley graph

The Paley graph of order 13
Named after Raymond Paley
Vertices q ≡ 1 mod 4,
q prime power
Edges q(q − 1)/4
Properties Strongly regular
Conference graph
Self-complementary
Notation QR(q)

In mathematics, and specifically graph theory, Paley graphs, named after Raymond Paley, are dense 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 closely related to the Paley construction for constructing Hadamard matrices from quadratic residues (Paley 1933). 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). That is, q should either be an arbitrary power of a Pythagorean prime (a prime congruent to 1 mod 4) or an even power of an odd non-Pythagorean prime. Note that this implies that the unique finite field of order q, Fq, has a square root of −1.

Now let V = Fq and

E= \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ a-b\in (\mathbf{F}_q^{\times})^2 \right \}.

This set is well defined since a − b = −(b − a), and since  −1 is a square, 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.

Example

For q = 13, the field Fq is just integer arithmetic modulo 13. The numbers with square roots mod 13 are:

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

srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).
In addition, Paley graphs actually form an infinite family of conference graphs.
\frac{q-\sqrt{q}}{4}\leq i(G) \leq \sqrt { \left (q+\sqrt{q} \right ) \left (\frac{q-\sqrt{q}}{2} \right ) }
This implies that i(G)~O(q), and Paley graph is an Expander graph.

Applications

Paley digraphs

Let q be a prime power such that q = 3 (mod 4). Thus, the finite field of order q, Fq, has no square root of −1. Consequently, for each pair (a,b) of distinct elements of Fq, either a − b or b − a, but not both, is a square. The Paley digraph is the directed graph with vertex set V = Fq and arc set

A = \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ b-a\in (\mathbf{F}_q^{\times})^2 \right \}.

The Paley digraph is a tournament because each pair of distinct vertices is linked by an arc in one and only one direction.

The Paley digraph leads to the construction of some antisymmetric conference matrices and biplane geometries.

Genus

The six neighbors of each vertex in the Paley graph of order 13 are connected in a cycle; that is, the graph is locally cyclic. Therefore, this graph can be embedded as a Whitney triangulation of a torus, in which every face is a triangle and every triangle is a face. More generally, if any Paley graph of order q could be embedded so that all its faces are triangles, we could calculate the genus of the resulting surface via the Euler characteristic as \tfrac{1}{24}(q^2 - 13q + 24). Mohar (2005) conjectures that the minimum genus of a surface into which a Paley graph can be embedded is near this bound in the case that q is a square, and questions whether such a bound might hold more generally. Specifically, Mohar conjectures that the Paley graphs of square order can be embedded into surfaces with genus

(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),

where the o(1) term can be any function of q that goes to zero in the limit as q goes to infinity.

White (2001) finds embeddings of the Paley graphs of order q ≡ 1 (mod 8) that are highly symmetric and self-dual, generalizing a natural embedding of the Paley graph of order 9 as a 3×3 square grid on a torus. However the genus of White's embeddings is higher by approximately a factor of three than Mohar's conjectured bound.

References

External links