Speaker：Zhikai Ye (University of British Columbia)

Time：2023-8-31, 14:30

Location：Conference Room 686 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

Let $d \geq 2$ and let $q$ be a prime power such that $q \equiv 1 \pmod {2d}$. The $d$-Paley graph of order $q$ is the graph with is the graph with the vertex set being the finite field $\mathbb{F}_q$, where two vertices are adjacent if and only if their difference is a $d$-th power in $\mathbb{F}_q^*$. In this talk, we show that the clique number of the $d$-Paley graph of order $q$ is at most $\sqrt{q/d}+O(\sqrt{q/p})$, where $q$ is an odd power of a prime $p$. This significantly improves the best-known generic upper bound $\sqrt{q}-o(p)$ and matches with the bound $\sqrt{p/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.