Dense triangle-free $(n,d,\lambda )$-graphs for all orders

Abstract

In 1994, Alon construct a triangle-free $(n,d,\lambda )$-graph with $d=\Omega (n^{2/3})$ and $\lambda =O(d^{1/2})$ for an exponentially increasing sequence of integers $n$. Using his ingenious construction, we deduce that there exist triangle-free $(n,d,\lambda )$-graphs with $d=\Omega (n^{2/3})$ and $\lambda =O((d\log n{)}^{1/2})$ for all sufficiently large $n$.

9 pages