Gauss sums and the maximum cliques in generalized Paley graphs of square order

Abstract

Let $GP(q,d)$ be the $d$-Paley graph defined on the finite field ${\mathbb{F}}_q$. It is notoriously difficult to improve the trivial upper bound $\sqrt{q}$ on the clique number of $GP(q,d)$. In this paper, we investigate the connection between Gauss sums over a finite field and the maximum cliques of their corresponding generalized Paley graphs. We show that the trivial upper bound on the clique number of $GP(q,d)$ is tight if and only if $d\mid (\sqrt{q}+1)$, which strengthens the previous related results by Broere-Döman-Ridley and Schneider-Silva. We also obtain a new simple proof of Stickelberger's theorem on evaluating semi-primitive Gauss sums.

17 pages

References in corpus (5)

• On the clique number of Paley graphs of prime power order
• On the directions determined by Cartesian products and the clique number of generalized Paley graphs
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
• On maximal cliques of Cayley graphs over fields
• Pure Gauss sums and skew Hadamard difference sets

Cited by in corpus (2)

• The EKR-module property of pseudo-Paley graphs of square order
• Maximality of subfields as cliques in Cayley graphs over finite fields