H. Van Maldeghem

Optimally pseudorandom $K_4$-free graphs

We show that optimally pseudorandom $K_4$-free graphs of order $n$ and degree $d = \Theta(n^{4/5})$ exist by constructing a graph in the split Cayley hexagon, matching the known upper bound. This resolves the first open case for $K_k$-free graphs after $k=3$ for which Alon gave a tight construction in 1994. This has a...