Exact values and improved bounds on the clique number of cyclotomic graphs

MaRDI QIDQ6434355FDO

Authors Chi Hoi Yip

Publication date 25 April 2023

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Arithmetic combinatorics; higher degree uniformity (11B30) Finite affine and projective planes (geometric aspects) (51E15)

Abstract: We show that the clique number of the $d$-Paley graph of order $q$ is at most $sqrtq/d+O(sqrtq/p)$, where $q$ is an odd power of a prime $p$. This significantly improves the best-known generic upper bound $sqrtq-o(p)$ and matches with the bound $sqrtp/d+O(1)$ for primes $p$ in a recent breakthrough work of Hanson and Petridis. Moreover, our new bound is asymptotically sharp for an infinite family of graphs, which leads to the further discovery of the first nontrivial instance of families of generalized Paley graphs where the clique number can be explicitly determined. One key ingredient in our proof is a new lower bound on the number of directions determined by a Cartesian product in the affine Galois plane $AG(2,q)$, which is of independent interest.

This page was built for publication: Exact values and improved bounds on the clique number of cyclotomic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6434355)