Paley graph: Difference between revisions

Revision as of 03:34, 28 May 2012

Definition

Suppose $q$ is a prime power such that $q \equiv 1 (\mod 4)$ . The Paley graph on $q$ vertices is defined as follows:

The vertex set is identified with the elements of the field $F_{q}$ of $q$ elements. This field is unique up to field isomorphism.
Given any two distinct vertices $a, b \in F_{q}$ , $a$ and $b$ are defined to be adjacent if and only if $a - b$ is a square in $F_{q}^{*}$ .

The significance of $q \equiv 1 (\mod 4)$ is that this forces -1 to be a square, hence $a - b$ is a square if and only if $b - a$ is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.

For a prime power $q \equiv 3 (\mod 4)$ , we can consider instead the Paley digraph.

Revision as of 03:31, 28 May 2012 (view source) Vipul (talk \| contribs) (Created page with "==Definition== Suppose <math>q</math> is a prime power such that <math>q \equiv 1 \pmod 4</math>. The '''Paley graph''' on <math>q</math> vertices is defined as follows: ...")		Revision as of 03:34, 28 May 2012 (view source) Vipul (talk \| contribs) No edit summary Newer edit →
Line 7:		Line 7:

	The significance of <math>q \equiv 1\pmod 4</math> is that this forces -1 to be a square, hence <math>a - b</math> is a square if and only if <math>b - a</math> is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.		The significance of <math>q \equiv 1\pmod 4</math> is that this forces -1 to be a square, hence <math>a - b</math> is a square if and only if <math>b - a</math> is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.

			For a prime power <math>q \equiv 3 \pmod 4</math>, we can consider instead the [[Paley digraph]].