The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes

Abstract

Blokhuis showed that all maximum cliques in Paley graphs of square order have a subfield structure. Recently, it has been shown that in Peisert-type graphs, all maximum cliques are affine subspaces, and yet some maximum cliques do not arise from a subfield. In this paper, we investigate the existence of a clique of size $\sqrt{q}$ with a subspace structure in pseudo-Paley graphs of order $q$ from unions of semi-primitive cyclotomic classes. We show that such a clique must have an equal contribution from each cyclotomic class and that most such pseudo-Paley graphs do not admit such cliques, suggesting that the Delsarte bound $\sqrt{q}$ on the clique number can be improved in general. We also prove that generalized Peisert graphs are not isomorphic to Paley graphs or Peisert graphs, confirming a conjecture of Mullin.

arXiv comment29 pages, revised based on referee comments

References in corpus (7)

• Refined Estimates Concerning Sumsets Contained in the Roots of Unity
• On the clique number of Paley graphs of prime power order
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
• On maximal cliques of Cayley graphs over fields
• Recognizing and testing isomorphism of Cayley graphs over an abelian group of order $4p$ in polynomial time
• The EKR-module property of pseudo-Paley graphs of square order
• Erdős-Ko-Rado theorem in Peisert-type graphs