On the directions determined by Cartesian products and the clique number of generalized Paley graphs

Abstract

It is known that the number of directions formed by a Cartesian product $A\times B\subset AG(2,p)$ is at least $|A||B|-\min \{|A|,|B|\}+2$, provided $p$ is prime and $|A||B|<p$. This implies the best known upper bound on the clique number of the Paley graph over ${\mathbb{F}}_p$. In this paper, we extend this result to $AG(2,q)$, where $q$ is a prime power. We also give improved upper bounds on the clique number of generalized Paley graphs over ${\mathbb{F}}_q$. In particular, for a cubic Paley graph, we improve the trivial upper bound $\sqrt{q}$ to $0.769\sqrt{q}+1$. In general, as an application of our key result on the number of directions, for any positive function $h$ such that $h(x)=o(x)$ as $x\to \infty$, we improve the trivial upper bound $\sqrt{q}$ to $\sqrt{q}-h(p)$ for almost all non-squares $q$.

26 pages, reference added

References in corpus (1)

• On the clique number of Paley graphs of prime power order

Cited by in corpus (8)

• On the clique number of Paley graphs of prime power order
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
• On maximal cliques of Cayley graphs over fields
• On eigenfunctions and maximal cliques of generalised Paley graphs of square order
• Asymptotics for the number of directions determined by $[n]\times [n]$ in ${\mathbb{F}}_p^2$
• Restricted sumsets in multiplicative subgroups
• Gauss sums and the maximum cliques in generalized Paley graphs of square order
• Additive decompositions of large multiplicative subgroups in finite fields