A construction for clique-free pseudorandom graphs

Abstract

A construction of Alon and Krivelevich gives highly pseudorandom $K_k$-free graphs on $n$ vertices with edge density equal to $\Theta (n^{-1/(k-2)})$. In this short note we improve their result by constructing an infinite family of highly pseudorandom $K_k$-free graphs with a higher edge density of $\Theta (n^{-1/(k-1)})$.

minor edits; accepted for publication by Combinatorica