View source for Paley graph

{{infobox graph
 | name = Paley graph
 | image = Paley13.svg
 | image_caption = The Paley graph of order 13
 | namesake = [[Raymond Paley]]
 | vertices = ''q'' ≡ 1 mod 4,<br>''q'' prime power
 | edges = ''q''(''q'' − 1)/4
 | diameter = 2
 | automorphisms 
 | chromatic_number =
 | chromatic_index =
 | properties = [[Strongly regular graph|Strongly regular]]<br>[[Conference graph]]<br>[[Self-complementary graph|Self-complementary]]
 | notation = QR(''q'')
}}
In [[mathematics]], '''Paley graphs''' are [[undirected graph]]s 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 graph]]s, which yield an infinite family of symmetric [[conference matrix|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 matrix|Hadamard matrices]] from quadratic residues.{{r|paley}}
They were introduced as graphs independently by {{harvtxt|Sachs|1962}} and {{harvtxt|Erdős|Rényi|1963}}. [[Horst Sachs|Sachs]] was interested in them for their self-complementarity properties,{{r|sachs}} while [[Paul Erdős|Erdős]] and [[Alfréd Rényi|Rényi]] studied their symmetries.{{r|er}}

'''Paley digraphs''' are [[directed graph|directed]] analogs of Paley graphs that yield antisymmetric [[conference matrix|conference matrices]]. They were introduced by {{harvtxt|Graham|Spencer|1971}} (independently of Sachs, Erdős, and Rényi) as a way of constructing [[tournament (graph theory)|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.{{r|gs}}

== 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&nbsp;mod&nbsp;4) or an even power of an odd non-Pythagorean prime. This choice of ''q'' implies that in the unique finite field '''F'''<sub>''q''</sub> of order ''q'', the element &nbsp;−1 has a square root.

Now let ''V'' = '''F'''<sub>''q''</sub> and let

:<math>E= \left \{\{a,b\} \ : \ a-b\in (\mathbf{F}_q^{\times})^2 \right \}</math>.
If a pair {''a'',''b''} is included in ''E'', it is included under either ordering of its two elements. For, ''a''&nbsp;−&nbsp;''b'' =&nbsp;−(''b''&nbsp;−&nbsp;''a''), and &nbsp;−1 is a square, from which it follows that ''a''&nbsp;−&nbsp;''b'' is a square [[if and only if]] ''b''&nbsp;−&nbsp;''a'' is a square.

By definition ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') is the Paley graph of order&nbsp;''q''.

== Example ==
For ''q'' = 13, the field '''F'''<sub>''q''</sub> is just integer arithmetic modulo 13.  The numbers with square roots mod 13 are:
* ±1 (square roots ±1 for +1, ±5 for &minus;1)
* ±3 (square roots ±4 for +3, ±6 for &minus;3)
* ±4 (square roots ±2 for +4, ±3 for &minus;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''&nbsp;±&nbsp;1&nbsp;(mod&nbsp;13), ''x''&nbsp;±&nbsp;3&nbsp;(mod&nbsp;13), and ''x''&nbsp;±&nbsp;4&nbsp;(mod&nbsp;13).

== Properties ==
The Paley graphs are [[Self-complementary graph|self-complementary]]: the complement of any Paley graph is isomorphic to it.   One isomorphism is via the mapping that takes a vertex {{mvar|x}} to {{math|''xk'' (mod ''q'')}}, where {{mvar|k}} is any nonresidue {{math|mod ''q''}}.{{r|sachs}}

Paley graphs are [[strongly regular graph]]s, with parameters 
:<math>srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).</math>
This in fact follows from the fact that the graph is [[Symmetric graph|arc-transitive]] and self-complementary. The strongly regular graphs with parameters of this form (for an arbitrary {{mvar|q}}) are called [[conference graph]]s, 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 {{math|&pm;1}}, with zero on the diagaonal, that give a scalar multiple of the [[identity matrix]] when multiplied by their transpose.{{r|bcm}}

The eigenvalues of Paley graphs are <math>\tfrac{1}{2}(q-1)</math> (with multiplicity 1) and <math>\tfrac{1}{2} (-1 \pm \sqrt{q})</math> (both with multiplicity <math>\tfrac{1}{2}(q-1)</math>).  They can be calculated using the [[quadratic Gauss sum]] or by using the theory of strongly regular graphs.{{r|bh}}

If {{mvar|q}} is prime, the [[Cheeger constant (graph theory)|isoperimetric number]] {{math|''i''(''G'')}} of the Paley graph satisfies the following bounds:
{{bi|left=1.6|<math>\displaystyle\frac{q-\sqrt{q}}{4}\leq i(G) \leq \frac{q-1}{4}.</math>{{r|ckssv}}}}

When {{mvar|q}} is prime, the associated Paley graph is a [[Hamiltonian cycle|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 {{mvar|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.{{r|cgw}}

* The Paley graph of order 9 is a [[locally linear graph]], a [[rook's graph]], and the graph of the [[3-3 duoprism]].
* The Paley graph of order 13 has [[book thickness]] 4 and [[queue number]] 3.{{r|wolz}}
* The Paley graph of order 17 is the unique largest graph ''G'' such that neither ''G'' nor its complement contains a complete 4-vertex subgraph.{{r|eps}}  It follows that the [[Ramsey theory|Ramsey number]] ''R''(4,&nbsp;4)&nbsp;=&nbsp;18.
* The Paley graph of order 101 is currently the largest known graph ''G'' such that neither ''G'' nor its complement contains a complete 6-vertex subgraph.
* Sasukara et al. (1993) use Paley graphs to generalize the construction of the [[Horrocks–Mumford bundle]].{{r|sey}}

==Paley digraphs==
Let ''q'' be a [[prime power]] such that ''q'' = 3 (mod 4). Thus, the finite field of order ''q'', '''F'''<sub>''q''</sub>, has no square root of &minus;1.  Consequently, for each pair (''a'',''b'') of distinct elements of '''F'''<sub>''q''</sub>, either ''a'' − ''b'' or ''b'' − ''a'', but not both, is a square.  The '''Paley digraph''' is the [[directed graph]] with vertex set ''V'' = '''F'''<sub>''q''</sub> and arc set 
:<math>A = \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ b-a\in (\mathbf{F}_q^{\times})^2 \right \}.</math>

The Paley digraph is a [[tournament (graph theory)|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 matrix|conference matrices]] and [[biplane geometries]].

== Genus ==
[[File:Paley-13 torus.svg|thumb|Torus embedding of the order-13 Paley graph, obtained by gluing each pair of parallel sides of a hexagon]]
The six neighbors of each vertex in the Paley graph of order 13 are connected in a cycle; that is, the graph is [[Neighborhood (graph theory)|locally cyclic]]. Therefore, this graph can be embedded as a [[Triangulation (topology)|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 <math>\tfrac{1}{24}(q^2 - 13q + 24)</math>. [[Bojan Mohar]] 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
:<math>(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),</math>
where the o(1) term can be any function of ''q'' that goes to zero in the limit as ''q'' goes to infinity.{{r|mohar}}

{{harvtxt|White|2001}} finds embeddings of the Paley graphs of order ''q''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;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.{{r|white}}

== References ==
{{reflist|refs=

<ref name=bcm>{{cite book
 | last1 = Brouwer | first1 = A. E.
 | last2 = Cohen | first2 = A. M.
 | last3 = Neumaier | first3 = A.
 | contribution = Conference matrices and Paley graphs
 | doi = 10.1007/978-3-642-74341-2
 | isbn = 3-540-50619-5
 | mr = 1002568
 | page = 10
 | publisher = Springer-Verlag | location = Berlin
 | series = Ergebnisse der Mathematik und ihrer Grenzgebiete
 | title = Distance-regular graphs
 | volume = 18
 | year = 1989}}</ref>

<ref name=bh>{{cite book
 | last1 = Brouwer | first1 = Andries E.
 | last2 = Haemers | first2 = Willem H.
 | contribution = 9.1.2 The Paley graphs
 | doi = 10.1007/978-1-4614-1939-6
 | isbn = 978-1-4614-1938-9
 | mr = 2882891
 | pages = 114–115
 | publisher = Springer | location = New York
 | series = Universitext
 | title = Spectra of graphs
 | year = 2012}} For obtaining the spectrum from strong regularity, see Theorem 9.1.3, p. 116. For the connection to Gauss sums, see Section 9.8.5 Cyclotomy, pp. 138–140.</ref>

<ref name=cgw>{{cite journal
  | last1 = Chung | first1 = Fan R. K. | author1-link = Fan Chung
  | author2-link = Ronald Graham | last2 = Graham | first2 = Ronald L.
  | last3 = Wilson | first3 = R. M.
  | title = Quasi-random graphs
  | journal = [[Combinatorica]]
  | year = 1989
  | volume = 9
  | issue = 4
  | pages = 345–362
  | doi = 10.1007/BF02125347 | doi-access =  }}</ref>

<ref name=ckssv>{{cite journal
 | last1 = Cramer | first1 = Kevin
 | last2 = Krebs | first2 = Mike
 | last3 = Shabazi | first3 = Nicole
 | last4 = Shaheen | first4 = Anthony
 | last5 = Voskanian | first5 = Edward
 | doi = 10.2140/involve.2016.9.293
 | issue = 2
 | journal = Involve
 | mr = 3470732
 | pages = 293–306
 | title = The isoperimetric and Kazhdan constants associated to a Paley graph
 | volume = 9
 | year = 2016}}</ref>

<ref name=er>{{Cite journal
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Rényi | first2 = A. | author2-link = Alfréd Rényi
 | doi = 10.1007/BF01895716 | doi-access = 
 | mr = 0156334
 | journal = [[Acta Mathematica Academiae Scientiarum Hungaricae]]
 | pages = 295–315
 | title = Asymmetric graphs
 | volume = 14
 | year = 1963
 | issue = 3–4 }}</ref>

<Ref name=eps>{{cite journal
  | last1 = Evans | first1 = R. J. | last2 = Pulham | first2 = J. R. | last3 = Sheehan | first3 = J.
  | title = On the number of complete subgraphs contained in certain graphs
  | journal = [[Journal of Combinatorial Theory]] | series = Series B
  | volume = 30
  | pages = 364–371
  | year = 1981
  | doi = 10.1016/0095-8956(81)90054-X
  | issue = 3 | doi-access = free}}</ref>

<ref name=gs>{{Cite journal
 | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham
 | last2 = Spencer | first2 = J. H. | author2-link = Joel Spencer
 | mr = 0292715
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 45–48
 | title = A constructive solution to a tournament problem
 | volume = 14
 | year = 1971
 | doi = 10.4153/CMB-1971-007-1 | doi-access = }}</ref>

<ref name=mohar>{{cite journal
 | last = Mohar | first = Bojan | author-link = Bojan Mohar
 | journal = Electronic Journal of Combinatorics
 | mr = 2176532
 | page = N15
 | title = Triangulations and the Hajós conjecture
 | url = http://www.combinatorics.org/Volume_12/Abstracts/v12i1n15.html
 | volume = 12
 | year = 2005
 | doi = 10.37236/1982 | doi-access = free
 }}</ref>

<ref name=paley>{{Cite journal
  | last = Paley | first = R.E.A.C. | author-link = Raymond Paley
  | title = On orthogonal matrices
  | journal = [[J. Math. Phys.]]
  | volume = 12
  | issue = 1–4 | year = 1933
  | doi = 10.1002/sapm1933121311
  | pages = 311–320 }}</ref>

<ref name=sachs>{{Cite journal
 | last = Sachs | first = Horst | author-link = Horst Sachs
 | mr = 0151953
 | journal = Publicationes Mathematicae Debrecen
 | pages = 270–288
 | title = Über selbstkomplementäre Graphen
 | volume = 9
 | year = 1962
 | doi = 10.5486/PMD.1962.9.3-4.11| doi-access = free
 }}</ref>

<ref name=sey>{{cite journal
  | last1 = Sasakura | first1 = Nobuo | last2 = Enta | first2 = Yoichi | last3 = Kagesawa | first3 = Masataka
  | title = Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle
  | journal = Proc. Japan Acad., Ser. A
  | volume = 69
  | issue = 5
  | pages = 144–148
  | year = 1993
  | doi = 10.3792/pjaa.69.144 | doi-access = free}}</ref>

<ref name=white>{{cite conference
  | last = White | first = A. T.
  | title = Graphs of groups on surfaces
  | book-title = Interactions and models
  | publisher = North-Holland Mathematics Studies 188
  | location = Amsterdam
  | year = 2001 }}</ref>

<ref name=wolz>{{cite book | first = Jessica | last = Wolz | title = Engineering Linear Layouts with SAT | series = Master's Thesis | publisher = University of Tübingen | year = 2018 }}</ref>

}}

==Further reading==
*{{cite journal
  | last1 = Baker | first1 = R. D. | last2 = Ebert | first2 = G. L. | last3 = Hemmeter | first3 = J. | last4 = Woldar | first4 = A. J.
  | title = Maximal cliques in the Paley graph of square order
  | journal = J. Statist. Plann. Inference
  | volume = 56
  | year = 1996
  | pages = 33–38
  | doi = 10.1016/S0378-3758(96)00006-7 }}
*{{cite journal
  | doi = 10.1080/16073606.1988.9631945
  | last1 = Broere | first1 = I. | last2 = Döman | first2 = D. | last3 = Ridley | first3 = J. N.
  | title = The clique numbers and chromatic numbers of certain Paley graphs
  | journal = Quaestiones Mathematicae
  | volume = 11
  | year = 1988
  | pages = 91–93 }}

== External links ==
*{{cite web
  | author= Brouwer, Andries E.
  | title = Paley graphs
  | url = http://www.win.tue.nl/~aeb/drg/graphs/Paley.html}}
*{{cite web
  | author = Mohar, Bojan
  | author-link = Bojan Mohar
  | title = Genus of Paley graphs
  | year = 2005
  | url = http://www.fmf.uni-lj.si/~mohar/Problems/P0506_PaleyGenus.html}}

[[Category:Number theory]]
[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]
[[Category:Strongly regular graphs]]