# Paley graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Paley_graph
> Markdown URL: https://mediated.wiki/source/Paley_graph.md
> Source: https://en.wikipedia.org/wiki/Paley_graph
> Source revision: 1337487988
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{infobox graph
 | name = Paley graph
 | image = Paley13.svg
 | image_caption = The Paley graph of order 13
 | namesake = [Raymond Paley](/source/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](/source/Strongly_regular_graph)<br>[Conference graph](/source/Conference_graph)<br>[Self-complementary](/source/Self-complementary_graph)
 | notation = QR(''q'')
}}
{{Short description|Graph of numbers differing by a square}}
In [mathematics](/source/mathematics), '''Paley graphs''' are [undirected graph](/source/undirected_graph)s constructed from the members of a suitable [finite field](/source/finite_field) by connecting pairs of elements that differ by a [quadratic residue](/source/quadratic_residue). The Paley graphs form an infinite family of [conference graph](/source/conference_graph)s, which yield an infinite family of symmetric [conference matrices](/source/conference_matrix). Paley graphs allow [graph-theoretic](/source/graph-theoretic) tools to be applied to the [number theory](/source/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](/source/Raymond_Paley).  They are closely related to the [Paley construction](/source/Paley_construction) for constructing [Hadamard matrices](/source/Hadamard_matrix) from quadratic residues.{{r|paley}}
They were introduced as graphs independently by {{harvtxt|Sachs|1962}} and {{harvtxt|Erdős|Rényi|1963}}. [Sachs](/source/Horst_Sachs) was interested in them for their self-complementarity properties,{{r|sachs}} while [Erdős](/source/Paul_Erd%C5%91s) and [Rényi](/source/Alfr%C3%A9d_R%C3%A9nyi) studied their symmetries.{{r|er}}

'''Paley digraphs''' are [directed](/source/directed_graph) analogs of Paley graphs that yield antisymmetric [conference matrices](/source/conference_matrix). They were introduced by {{harvtxt|Graham|Spencer|1971}} (independently of Sachs, Erdős, and Rényi) as a way of constructing [tournaments](/source/tournament_(graph_theory)) with a property previously known to be held only by random tournaments: in a Paley digraph, every small [subset](/source/subset) of vertices is dominated by some other vertex.{{r|gs}}

== Definition ==
Let ''q'' be a [prime power](/source/prime_power) such that <math display="inline">q \equiv 1 \pmod 4</math>. That is, ''q'' should either be an arbitrary power of a prime congruent to 1&nbsp;mod&nbsp;4 (a [Pythagorean prime](/source/Pythagorean_prime)) 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](/source/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''.

The sequence of orders of the Paley graphs begins

:1, 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, ... {{oeis|A085759}}

== 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](/source/Self-complementary_graph): 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 quadratic nonresidue {{math|mod ''q''}}.{{r|sachs}}

Paley graphs are [strongly regular graph](/source/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 [arc-transitive](/source/Symmetric_graph) and self-complementary. The strongly regular graphs with parameters of this form (for an arbitrary {{mvar|q}}) are called [conference graph](/source/conference_graph)s, so the Paley graphs form an infinite family of conference graphs. The [adjacency matrix](/source/adjacency_matrix) of a conference graph, such as a Paley graph, can be used to construct a [conference matrix](/source/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](/source/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](/source/quadratic_Gauss_sum) or by using the theory of strongly regular graphs.{{r|bh}}

If {{mvar|q}} is prime, the [isoperimetric number](/source/Cheeger_constant_(graph_theory)) {{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](/source/Hamiltonian_cycle) [circulant graph](/source/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](/source/locally_linear_graph), a [rook's graph](/source/rook's_graph), and the graph of the [3-3 duoprism](/source/3-3_duoprism).
* The Paley graph of order 13 has [book thickness](/source/book_thickness) 4 and [queue number](/source/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 number](/source/Ramsey_theory) ''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](/source/Horrocks%E2%80%93Mumford_bundle).{{r|sey}}

==Paley digraphs==
Let ''q'' be a [prime power](/source/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](/source/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](/source/tournament_(graph_theory)) 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](/source/conference_matrix) and [biplane geometries](/source/biplane_geometries).

== Genus ==
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 [locally cyclic](/source/Neighborhood_(graph_theory)). Therefore, this graph can be embedded as a [Whitney triangulation](/source/Triangulation_(topology)) of a [torus](/source/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](/source/Euler_characteristic) as <math>\tfrac{1}{24}(q^2 - 13q + 24)</math>. [Bojan Mohar](/source/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 ==
<references>

<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](/source/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](/source/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](/source/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](/source/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
 | article-number = 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.](/source/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
 | issue = 3–4 | 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>

</references>

==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

---
Adapted from the Wikipedia article [Paley graph](https://en.wikipedia.org/wiki/Paley_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Paley_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.