A clique-free pseudorandom subgraph of the pseudo polarity graph

Abstract

We provide a new family of $K_k$-free pseudorandom graphs with edge density $\Theta (n^{-1/(k-1)})$, matching a recent construction due to Bishnoi, Ihringer and Pepe. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field ${\mathbb{F}}_q$. While their construction required $q$ to be odd, we will give the first construction with $q$ even.

8 pages