A construction for clique-free pseudorandom graphs
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:QRFN2E76record.jsonopen to challenge →
classification
math.CO
keywords
graphspseudorandomconstructiondensityedgefreehighlytheta
read the original 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)})$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.