Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields

Abstract

A well-known conjecture due to van Lint and MacWilliams states that if $A$ is a subset of ${\mathbb{F}}_{q^2}$ such that $0,1\in A$, $|A|=q$, and $a-b$ is a square for each $a,b\in A$, then $A$ must be the subfield ${\mathbb{F}}_q$. This conjecture is often phrased in terms of the maximum cliques in Paley graphs. It was first proved by Blokhuis and later extended by Sziklai to generalized Paley graphs. In this paper, we give a new proof of the conjecture and its variants, and show this Erdős-Ko-Rado property of Paley graphs extends to a larger family of Cayley graphs, which we call Peisert-type graphs, resolving conjectures by Mullin and Yip.

18 pages

Cited by in corpus (11)

• On eigenfunctions and maximal cliques of generalised Paley graphs of square order
• The EKR-module property of pseudo-Paley graphs of square order
• Erdős-Ko-Rado theorem in Peisert-type graphs
• Extremal Peisert-type graphs without the strict-EKR property
• Positivity preservers over finite fields
• Maximality of subfields as cliques in Cayley graphs over finite fields
• Distribution of power residues over shifted subfields and maximal cliques in generalized Paley graphs
• Restricted sumsets in multiplicative subgroups
• A strengthening of McConnel's theorem on permutations over finite fields
• The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields, II