Up

Paley graphs

Paley graphs are named after Raymond E.A.C. Paley (1907-1933). Paley was an MIT mathematician. He worked together with Norbert Wiener. He died in an avalanche in 1933 while skiing in the Canadian Rockies.

The graphs that bear his name are constructed as follows: Given a finite field F with q elements, make a graph with vertex set F where two vertices are joined when their difference is a square in the field. This is an undirected graph when q is congruent 1 (mod 4).

For q = 4t + 1, the parameters are v = 4t + 1, k = 2t, λ = t − 1, μ = t.

Examples (q = 5 and q = 9):

For q = 13 the Paley graph is locally a hexagon, so that the graph is a quotient of the hexagonal grid:

(More generally, the graph on the elements of GF(q), where q=6t+1, where x and y are adjacent when (y−x)6 = 1, is locally a hexagon, unless q is a power of 7.)

Group of automorphisms

Let q = pe where p is prime. The Paley graph of order q has full group of order eq(q−1)/2 generated by the linear transformations x ↦ ax+b where a is a nonzero square, and the field automorphisms (Carlitz, 1960).

Paley graphs are isomorphic to their complements: if a is a nonsquare, then the map that sends x to ax is an isomorphism from the graph to its complement.

The subgraph induced on the neighbors of 0 (that is, on the set of squares) has full group generated by the maps x ↦ ax where a is a nonzero square, the field automorphisms, and the map x ↦ x−1 (Muzychuk & Kovácz, 2005). If q > 9 it has order e(q−1).

Independence and chromatic number

The independence numbers of the Paley graphs of prime order less than 7000 were computed by James Shearer. Geoffrey Exoo extended that table beyond order 16000.

A small table with independence numbers and chromatic numbers:

q 59131725 293741495361 73818997101109 113121125137149157 169173181193197
α 23335 445755 595656 7117777 138778
χ 33565 810971113 15918172119 171118202223 1322262825

The chromatic numbers for q=125,173,197 are due to Geoffrey Exoo (pers. comm.).

Since the Paley graphs are self-complementary, their clique numbers equal their independence numbers. By the Hoffman bound, the independence number is at most sqrt(q). For prime q, Hanson and Petridis improved this upper bound to roughly sqrt(q/2), more precisely (1+sqrt(2q−1))/2. Equality holds for q=5, 13, 41.

The case of square q

In I. Broere, D. Döman, J. N. Ridley, The clique numbers and chromatic numbers of certain Paley graphs, Quaestiones Math. 11 (1988) 91-93, it is shown that when q is an even power of a prime, the clique and chromatic number are both sqrt(q). (Indeed, this is trivial: the subfield gives a clique, and its translates give a partitions into cliques. No larger cliques exist by the Hoffman bound.)

A much stronger result is found in A. Blokhuis, On subsets of GF(q2) with square differences, Indag. Math. 46 (1984) 369-372. This paper shows that if a subset of GF(q) has size sqrt(q) and all differences are squares, or all differences are nonsquares, then the subset is the affine image of a subfield. In particular, this determines all cliques and all cocliques of size sqrt(q) in the Paley graph of order q.

For q = r2 with r = 4t±1, smaller maximal cliques (of size 2t+1) are constructed in R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph of square order, J. Statist. Plann. Inference 56 (1996) 33-38. They conjecture that no maximal clique in the Paley graph of order r2 has size strictly between 2t+1 and r.

See also M. Kiermaier & S. Kurz, Maximal integral point sets in affine planes over finite fields, Discr. Math. 309 (2009) 4564-4575, and S. Goryainov, V. V. Kabanov, L. Shalaginov & A. Valyuzhenich, On eigenfunctions and maximal cliques of Paley graphs of square order, Finite Fields Appl. 52 (2018) 361–369, and S. Goryainov, A. Masley & L. Shalaginov, On a correspondence between maximal cliques in Paley graphs of square order, Discr. Math. 345 (2022) 112853.

Dominating sets

The size of the smallest dominating set in the Paley graph P(q) is less than 1 + log q (found by picking greedily), and at least (0.5 − ε) log q (use the randomness of the Paley graph), where the logarithms have base 2. For q < 2048 one has:

sizeq
2 5
3 9-25
4 29-81
5 89-373, 401-409, 433, 457, 569, 953
6 389-397, 421, 449, 461-557, 577-941, 961-1213,
1229, 1249-1289, 1321, 1369, 1409, 1553, 1669
7 1217, 1237, 1297-1301, 1361, 1373-1381,
1429-1549, 1597-1657, 1681-2029

Similarly, for Paley tournaments P(q) one has:

sizeq
2 3
3 7-11
4 19-59, 103
5 67-83, 107-311, 343, 379
6 331, 347-367, 383-1151, 1171, 1223, 1331, 1723
7 1163, 1187, 1231-1327, 1367-1699, 1747-2039

See Changwoo Lee, The domination number of a tournament, Kangweon-Kyungki Math. J. 9 (2001) 21-28.