Cliques in Paley graphs of square order and in Peisert graphs

Andries E. Brouwer; Chi Hoi Yip; Leonid Shalaginov; Sergey Goryainov

arxiv: 2503.09914 · v2 · submitted 2025-03-13 · 🧮 math.CO

Cliques in Paley graphs of square order and in Peisert graphs

Andries E. Brouwer , Sergey Goryainov , Leonid Shalaginov , Chi Hoi Yip This is my paper

Pith reviewed 2026-05-23 00:59 UTC · model grok-4.3

classification 🧮 math.CO

keywords maximal cliquescollinearity graphsDesarguesian netsPaley graphsPeisert graphs

0 comments

The pith

In Desarguesian nets a point x and its neighbors on a distant line L lie in a unique maximal clique whose size and automorphism group are determined explicitly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines maximal cliques in the collinearity graphs of Desarguesian nets. It establishes that for any point x and line L not containing x, the set of x together with its neighbors on L lies inside exactly one maximal clique. The sizes of these cliques and the groups of automorphisms that preserve them are calculated completely. This provides concrete structural and numerical information about the cliques in these particular graphs arising from finite fields.

Core claim

For Desarguesian nets, the set consisting of a point x together with all its neighbors on a line L (with x not on L) is contained in a unique maximal clique C_{x,L} and the sizes and automorphism groups of such maximal cliques C_{x,L} are determined in all cases.

What carries the argument

The unique maximal clique C_{x,L} containing a point x and all its collinear neighbors on an external line L inside the collinearity graph of a Desarguesian net.

Load-bearing premise

The nets under study arise from a finite field vector space equipped with the standard incidence structure.

What would settle it

A Desarguesian net in which some point-plus-neighbors set on a distant line belongs to two or more distinct maximal cliques, or whose clique sizes deviate from the stated values.

read the original abstract

We study maximal cliques in the collinearity graphs of Desarguesian nets, give some structural results and some numerical information. In particular, we show for Desarguesian nets that the set consisting of a point $x$ together with all its neighbors on a line $L$ (with $x$ not on $L$) is contained in a unique maximal clique $C_{x,L}$ and determine the sizes and automorphism groups of such maximal cliques $C_{x,L}$ in all cases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper determines sizes and automorphism groups for a family of maximal cliques in Desarguesian nets and shows uniqueness for the construction from a point and its neighbors on a distant line.

read the letter

The main takeaway is that in Desarguesian nets the set consisting of a point x and its neighbors on a line L not through x lies in a unique maximal clique C_{x,L}, and the paper computes the order of C_{x,L} and its automorphism group in every case. This is a concrete structural result rather than an existence or bound statement. The authors stay inside the Desarguesian setting, which lets them carry out the calculations explicitly. That choice keeps the claims verifiable and avoids overreach. The work supplies numerical information that people studying cliques in graphs coming from finite fields or designs can use directly. The title links the material to Paley graphs of square order and Peisert graphs, so the clique data presumably feeds into those families, though the abstract focuses on the net incidence structure. The authors are experienced in this area, and the scoped claim shows no internal contradictions or circular steps. The main limitation is that the abstract gives no proof outline, so the reader must consult the full text to see how the cases are handled and whether the automorphism calculations rely on standard field arithmetic or something more involved. If the proofs turn out to be routine case analysis, the result remains useful but incremental; if they introduce a new reduction, that would strengthen it. No free parameters or invented entities appear in the stated claim. This paper is aimed at specialists already working on strongly regular graphs or finite geometries. A reader looking for explicit clique sizes in these constructions will find value; someone outside the subfield will not. It is worth sending to peer review because the statements are precise, the scope is clear, and the results are the sort that can be checked or extended by others in the area.

Referee Report

1 major / 1 minor

Summary. The manuscript studies maximal cliques in the collinearity graphs of Desarguesian nets. It establishes structural results, in particular that for a point x not on a line L the set consisting of x together with all its neighbors on L is contained in a unique maximal clique C_{x,L}, and determines the sizes and automorphism groups of such maximal cliques C_{x,L} in all cases.

Significance. If the results hold, the explicit classification of these cliques C_{x,L} (including sizes and automorphism groups) supplies concrete structural information on the collinearity graphs of Desarguesian nets. This is a targeted contribution in finite geometry that may connect to the clique structure of Paley graphs of square order and Peisert graphs referenced in the title.

major comments (1)

Abstract: the central claims (uniqueness of C_{x,L} and determination of sizes and Aut(C_{x,L}) in all cases) are asserted without any proof, derivation, or supporting data in the provided text, so the soundness of the main theorem cannot be evaluated.

minor comments (1)

Title vs. abstract: the title emphasizes Paley graphs of square order and Peisert graphs, while the abstract is scoped exclusively to Desarguesian nets; the manuscript should make the precise relationship between these objects explicit.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report. We address the major comment point by point below.

read point-by-point responses

Referee: Abstract: the central claims (uniqueness of C_{x,L} and determination of sizes and Aut(C_{x,L}) in all cases) are asserted without any proof, derivation, or supporting data in the provided text, so the soundness of the main theorem cannot be evaluated.

Authors: The abstract is intended only as a concise summary of the paper's contributions. The full manuscript contains the detailed proofs and derivations establishing that, in Desarguesian nets, the configuration of a point x not on line L together with its neighbors on L lies in a unique maximal clique C_{x,L}, along with explicit computations of the clique sizes and automorphism groups in every case. These arguments appear in the body of the text following the abstract. revision: no

Circularity Check

0 steps flagged

No significant circularity; direct structural result in finite geometry

full rationale

The paper's central claim is a classification of maximal cliques in the collinearity graphs of Desarguesian nets, asserting that {x} union neighbors of x on L lies in a unique maximal clique C_{x,L} whose size and automorphism group are determined explicitly. This is presented as a direct consequence of the incidence structure arising from AG(2,q), with the Desarguesian assumption stated upfront as the scope. No fitted parameters are renamed as predictions, no self-citations are invoked to justify uniqueness or sizes, and no ansatz or renaming of known results is used to derive the result. The derivation is therefore self-contained within the geometry of the net and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no specific free parameters, axioms, or invented entities can be identified.

pith-pipeline@v0.9.0 · 5620 in / 1042 out tokens · 38707 ms · 2026-05-23T00:59:49.011980+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Asgarli & C

S. Asgarli & C. H. Yip, Van Lint-MacWilliams’ conjecture and maximum cliques in Cayley graphs over ﬁnite ﬁelds , J. Combin. Th. (A) 192 (2022) 105667

work page 2022
[2]

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

work page 1996
[3]

Ball, The number of directions determined by a function over a ﬁnit e ﬁeld, J

S. Ball, The number of directions determined by a function over a ﬁnit e ﬁeld, J. Combin. Th. (A) 104 (2003) 341–350

work page 2003
[4]

Blokhuis, On subsets of GF (q2) with square diﬀerences , Indag

A. Blokhuis, On subsets of GF (q2) with square diﬀerences , Indag. Math. 46 (1984) 369–372

work page 1984
[5]

Blokhuis, S

A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme & T. Sz˝ onyi, On the number of slopes of the graph of a function deﬁned on a ﬁnite ﬁeld , J. Combin. Th. (A) 86 (1999) 187–196

work page 1999
[6]

A. E. Brouwer, A. M. Cohen & A. Neumaier, Distance-regular graphs, Springer, 1989

work page 1989
[7]

A. E. Brouwer & H. Van Maldeghem, Strongly regular graphs , Cambridge Univ. Press, 2022

work page 2022
[8]

Carlitz, A theorem on permutations in a ﬁnite ﬁeld , Proc

L. Carlitz, A theorem on permutations in a ﬁnite ﬁeld , Proc. Amer. Math. Soc. 11 (1960) 456–459

work page 1960
[9]

Goryainov, V

S. Goryainov, V. V. Kabanov, L. Shalaginov & A. Valuzhenich, On eigen- functions and maximal cliques of Paley graphs of square orde r, Finite Fields Appl. 52 (2018) 361–369

work page 2018
[10]

Goryainov, A

S. Goryainov, A. Masley & L. Shalaginov, On a correspondence between maximal cliques in Paley graphs of square order , Discr. Math. 345 (2022) 112853

work page 2022
[11]

Goryainov & C

S. Goryainov & C. H. Yip, Extremal Peisert-type graphs without the strict- EKR property, J. Combin. Th. (A) 206 (2024) 105887

work page 2024
[12]

D. R. Hughes & F. C. Piper, Projective planes, Springer, 1973

work page 1973
[13]

Kiermaier & S

M. Kiermaier & S. Kurz, Maximal integral point sets in aﬃne planes over ﬁnite ﬁelds , Discr. Math. 309 (2009) 4564–4575

work page 2009
[14]

Martin & C

G. Martin & C. H. Yip, Distribution of power residues over shifted subﬁelds and maximal cliques in generalized Paley graphs , Proc. Amer. Math. Soc. 153 (2025) 109–124. 12

work page 2025
[15]

Muzychuk & I

M. Muzychuk & I. Kov´ acs, A solution of a problem of A. E. Brouwer , Des. Codes Cryptogr. 34 (2005) 249–264

work page 2005
[16]

Mullin, Self-complementary arc-transitive graphs and their impos ters, M

N. Mullin, Self-complementary arc-transitive graphs and their impos ters, M. Sc. Thesis, Univ. of Waterloo, 2009

work page 2009
[17]

Peisert, All self-complementary symmetric graphs , J

W. Peisert, All self-complementary symmetric graphs , J. Algebra 240 (2001) 209–229

work page 2001
[18]

Sziklai, On subsets of GF(q2) with dth power diﬀerences , Discr

P. Sziklai, On subsets of GF(q2) with dth power diﬀerences , Discr. Math. 208/209 (1999) 547–555. 13

work page 1999

[1] [1]

Asgarli & C

S. Asgarli & C. H. Yip, Van Lint-MacWilliams’ conjecture and maximum cliques in Cayley graphs over ﬁnite ﬁelds , J. Combin. Th. (A) 192 (2022) 105667

work page 2022

[2] [2]

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

work page 1996

[3] [3]

Ball, The number of directions determined by a function over a ﬁnit e ﬁeld, J

S. Ball, The number of directions determined by a function over a ﬁnit e ﬁeld, J. Combin. Th. (A) 104 (2003) 341–350

work page 2003

[4] [4]

Blokhuis, On subsets of GF (q2) with square diﬀerences , Indag

A. Blokhuis, On subsets of GF (q2) with square diﬀerences , Indag. Math. 46 (1984) 369–372

work page 1984

[5] [5]

Blokhuis, S

A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme & T. Sz˝ onyi, On the number of slopes of the graph of a function deﬁned on a ﬁnite ﬁeld , J. Combin. Th. (A) 86 (1999) 187–196

work page 1999

[6] [6]

A. E. Brouwer, A. M. Cohen & A. Neumaier, Distance-regular graphs, Springer, 1989

work page 1989

[7] [7]

A. E. Brouwer & H. Van Maldeghem, Strongly regular graphs , Cambridge Univ. Press, 2022

work page 2022

[8] [8]

Carlitz, A theorem on permutations in a ﬁnite ﬁeld , Proc

L. Carlitz, A theorem on permutations in a ﬁnite ﬁeld , Proc. Amer. Math. Soc. 11 (1960) 456–459

work page 1960

[9] [9]

Goryainov, V

S. Goryainov, V. V. Kabanov, L. Shalaginov & A. Valuzhenich, On eigen- functions and maximal cliques of Paley graphs of square orde r, Finite Fields Appl. 52 (2018) 361–369

work page 2018

[10] [10]

Goryainov, A

S. Goryainov, A. Masley & L. Shalaginov, On a correspondence between maximal cliques in Paley graphs of square order , Discr. Math. 345 (2022) 112853

work page 2022

[11] [11]

Goryainov & C

S. Goryainov & C. H. Yip, Extremal Peisert-type graphs without the strict- EKR property, J. Combin. Th. (A) 206 (2024) 105887

work page 2024

[12] [12]

D. R. Hughes & F. C. Piper, Projective planes, Springer, 1973

work page 1973

[13] [13]

Kiermaier & S

M. Kiermaier & S. Kurz, Maximal integral point sets in aﬃne planes over ﬁnite ﬁelds , Discr. Math. 309 (2009) 4564–4575

work page 2009

[14] [14]

Martin & C

G. Martin & C. H. Yip, Distribution of power residues over shifted subﬁelds and maximal cliques in generalized Paley graphs , Proc. Amer. Math. Soc. 153 (2025) 109–124. 12

work page 2025

[15] [15]

Muzychuk & I

M. Muzychuk & I. Kov´ acs, A solution of a problem of A. E. Brouwer , Des. Codes Cryptogr. 34 (2005) 249–264

work page 2005

[16] [16]

Mullin, Self-complementary arc-transitive graphs and their impos ters, M

N. Mullin, Self-complementary arc-transitive graphs and their impos ters, M. Sc. Thesis, Univ. of Waterloo, 2009

work page 2009

[17] [17]

Peisert, All self-complementary symmetric graphs , J

W. Peisert, All self-complementary symmetric graphs , J. Algebra 240 (2001) 209–229

work page 2001

[18] [18]

Sziklai, On subsets of GF(q2) with dth power diﬀerences , Discr

P. Sziklai, On subsets of GF(q2) with dth power diﬀerences , Discr. Math. 208/209 (1999) 547–555. 13

work page 1999