Erdős-Ko-Rado theorem in Peisert-type graphs

Abstract

The celebrated Erdős-Ko-Rado (EKR) theorem for Paley graphs (of square order) states that all maximum cliques are canonical in the sense that each maximum clique arises from the subfield construction. Recently, Asgarli and Yip extended this result to Peisert graphs and other Cayley graphs which are Peisert-type graphs with nice algebraic properties on the connection set. On the other hand, there are Peisert-type graphs for which the EKR theorem fails to hold. In this paper, we show that the EKR theorem of Paley graphs extends to almost all pseudo-Paley graphs of Peisert-type. Furthermore, we establish the stability results of the same flavor.

arXiv comment10 pages, typos corrected

References in corpus (3)

• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
• On eigenfunctions and maximal cliques of generalised Paley graphs of square order
• The EKR-module property of pseudo-Paley graphs of square order

Cited by in corpus (5)

• Extremal Peisert-type graphs without the strict-EKR property
• Distribution of power residues over shifted subfields and maximal cliques in generalized Paley graphs
• A strengthening of McConnel's theorem on permutations over finite fields
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields, II
• The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes