Paley graph

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
Diameter	2
Properties	Strongly regular ; Conference graph ; Self-complementary
Notation	QR(q)
	Table of graphs and parameters

Last updated December 14, 2023

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 ( 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. This choice of q implies that in the unique finite field F_q of order q, the element −1 has a square root.

Now let V = F_q and let

{\displaystyle E=\left\{\{a,b\}\

.

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.

Example

For q = 13, the field F_q 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 nonresidue mod q( Sachs 1962 ).

Paley graphs are strongly regular graphs, with parameters

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. In addition, Paley graphs form an infinite family of conference graphs.^{[ citation needed ]}

The eigenvalues of Paley graphs are ${\tfrac {1}{2}}(q-1)$ (with multiplicity 1) and ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ (both with multiplicity ${\tfrac {1}{2}}(q-1)$ ). They can be calculated using the quadratic Gauss sum or by using the theory of strongly regular graphs.^{[ citation needed ]}

If q is prime, the isoperimetric number i(G) of the Paley graph is known to satisfy the following bounds:

{\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\sqrt {\left(q+{\sqrt {q}}\right)\left({\frac {q-{\sqrt {q}}}{2}}\right)}}.

^{[ citation needed ]}

When q is prime, the associated Paley graph is a Hamiltonian circulant graph.

Paley graphs are quasi-random (Chung et al. 1989): 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.

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 ( Wolz 2018 ).
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 (Evans et al. 1981). It follows that the Ramsey number R(4, 4) = 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.

Paley digraphs

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

{\displaystyle A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\

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.

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let $r$ and $s$ be any two positive integers. Ramsey's theorem states that there exists a least positive integer $R (r, s)$ for which every blue-red edge colouring of the complete graph on $R (r, s)$ vertices contains a blue clique on $r$ vertices or a red clique on $s$ vertices. (Here $R (r, s)$ signifies an integer that depends on both $r$ and $s$ .)

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the form

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex $v$ in a graph is a vertex that is connected to $v$ by an edge. The neighbourhood of a vertex $v$ in a graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$ , i.e., the graph composed of the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$ .

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of $vertices from an n -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.$

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.$

In graph theory and statistics, a graphon is a symmetric measurable function $, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.$

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

In mathematics, a quasirandom group is a group that does not contain a large product-free subset. Such groups are precisely those without a small non-trivial irreducible representation. The namesake of these groups stems from their connection to graph theory: bipartite Cayley graphs over any subset of a quasirandom group are always bipartite quasirandom graphs.

References

Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. (1996). "Maximal cliques in the Paley graph of square order". J. Statist. Plann. Inference. 56: 33–38. doi:10.1016/S0378-3758(96)00006-7.
Broere, I.; Döman, D.; Ridley, J. N. (1988). "The clique numbers and chromatic numbers of certain Paley graphs". Quaestiones Mathematicae. 11: 91–93. doi:10.1080/16073606.1988.9631945.
Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). "Quasi-random graphs". Combinatorica . 9 (4): 345–362. doi:10.1007/BF02125347.
Erdős, P.; Rényi, A. (1963). "Asymmetric graphs". Acta Mathematica Academiae Scientiarum Hungaricae . 14 (3–4): 295–315. doi:10.1007/BF01895716. MR 0156334.
Evans, R. J.; Pulham, J. R.; Sheehan, J. (1981). "On the number of complete subgraphs contained in certain graphs". Journal of Combinatorial Theory . Series B. 30 (3): 364–371. doi: 10.1016/0095-8956(81)90054-X .
Graham, R. L.; Spencer, J. H. (1971). "A constructive solution to a tournament problem". Canadian Mathematical Bulletin . 14: 45–48. doi:10.4153/CMB-1971-007-1. MR 0292715.
Mohar, Bojan (2005). "Triangulations and the Hajós conjecture". Electronic Journal of Combinatorics. 12: N15. doi: 10.37236/1982 . MR 2176532.
Paley, R.E.A.C. (1933). "On orthogonal matrices". J. Math. Phys. 12 (1–4): 311–320. doi:10.1002/sapm1933121311.
Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. doi: 10.5486/PMD.1962.9.3-4.11 . MR 0151953.
Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka (1993). "Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle". Proc. Japan Acad., Ser. A. 69 (5): 144–148. doi: 10.3792/pjaa.69.144 .
White, A. T. (2001). "Graphs of groups on surfaces". Interactions and models. Amsterdam: North-Holland Mathematics Studies 188.
Wolz, Jessica (2018). Engineering Linear Layouts with SAT. Master's Thesis. University of Tübingen.

External links

Brouwer, Andries E. "Paley graphs".
Mohar, Bojan (2005). "Genus of Paley graphs".

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.