On the clique number of Paley graphs of prime power order

Abstract

Finding a reasonably good upper bound for the clique number of Paley graphs is an open problem in additive combinatorics. A recent breakthrough by Hanson and Petridis using Stepanov's method gives an improved upper bound on Paley graphs defined on a prime field ${\mathbb{F}}_p$, where $p\equiv 1(\mathrm{mod}4)$. We extend their idea to the finite field ${\mathbb{F}}_q$, where $q=p^{2s+1}$ for a prime $p\equiv 1(\mathrm{mod}4)$ and a non-negative integer $s$. We show the clique number of the Paley graph over ${\mathbb{F}}_{p^{2s+1}}$ is at most $\min (p^s\lceil \sqrt{\frac{p}{2}}\rceil ,\sqrt{\frac{q}{2}}+\frac{p^s+1}{4}+\frac{\sqrt{2p}}{32}{p}^{s-1})$.

13 pages; typos corrected

References in corpus (2)

• On the directions determined by Cartesian products and the clique number of generalized Paley graphs
• Vandermonde varieties and relations among Schur polynomials

Cited by in corpus (13)

• On the directions determined by Cartesian products and the clique number of generalized Paley graphs
• On maximal cliques of Cayley graphs over fields
• On eigenfunctions and maximal cliques of generalised Paley graphs of square order
• Positivity preservers over finite fields
• $F$-Diophantine sets over finite fields
• Exact values and improved bounds on the clique number of cyclotomic graphs
• Additive decompositions of large multiplicative subgroups in finite fields
• Gauss sums and the maximum cliques in generalized Paley graphs of square order
• Paley Graphs and Sárközy's Theorem In Function Fields
• Periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs
• Intersective sets over abelian groups
• 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