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

arXiv2110.07176MaRDI QIDQ6380301FDOQ6380301

Authors: Shamil Asgarli, Chi Hoi Yip 

Publication date: 14 October 2021

Abstract: Blokhuis showed that all maximum cliques in Paley graphs of square order have a subfield structure. Recently it is shown that in Peisert-type graphs, some maximum cliques do not have a subfield structure, and yet all maximum cliques have a subspace structure. In this paper, we investigate the existence of a clique of size $sqrtq$ 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 pseudo-Paley graphs do not admit such cliques, suggesting that the Delsarte bound $sqrtq$ 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.

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Association schemes, strongly regular graphs (05E30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Arithmetic combinatorics; higher degree uniformity (11B30) Other character sums and Gauss sums (11T24) Cyclotomy (11T22)

This page was built for publication: The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380301)