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

2025/05/07 by Yip, Chi Hoi
#11B30 #11T30 #51E15 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2505.04061

Abstract

The well-known Van Lint--MacWilliams' conjecture states that if q is an odd prime power, and A⊆ \mathbbF_q² such that 0,1 ∈ A, |A|=q, and a-b is a square for each a,b ∈ A, then A must be the subfield \mathbbF_q. This conjecture was first proved by Blokhuis and is often phrased in terms of the maximum cliques in Paley graphs of square order. Previously, Asgarli and the author extended Blokhuis' theorem to a larger family of Cayley graphs. In this paper, we give a new simple proof of Blokhuis' theorem and its extensions. More generally, we show that if S ⊆ \mathbbF_q²^* has small multiplicative doubling, and A⊆ \mathbbF_q² with 0,1 ∈ A, |A|=q, such that A-A ⊆ S ∪ \0\, then A=\mathbbF_q. This new result refines and extends several previous works; moreover, our new approach avoids using heavy machinery from number theory.

Citations

• Paley-like quasi-random graphs arising from polynomials
• Exact values and improved bounds on the clique number of cyclotomic graphs
• Character sums over affine spaces and applications
• On the directions determined by a Cartesian product in an affine Galois\n plane
• Freiman's Theorem in an arbitrary abelian group

Related

• Exact values and improved bounds on the clique number of cyclotomic graphs
• Paley-like graphs over finite fields from vector spaces
• Second largest maximal cliques in small Paley graphs of square order
• Proof of a conjecture on monomial graphs
• Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]