Coloring sparse random Cayley graphs

It is shown that there exists $c>0$ so that the Cayley graph over any finite abelian group $Z$ generated by $c\log \mathrm{\mid }Z\mathrm{\mid }$ random elements is properly 3-colorable with high probability (as $\mathrm{\mid }Z\mathrm{\mid }\to \mathrm{\infty }$). This is asymptotically tight and improves the best-known bound due to Alon of $\frac{1}{4}\log \log \mathrm{\mid }Z\mathrm{\mid }$ elements. It also makes progress toward Alon’s suggestion that a bound of $c\log \mathrm{\mid }G\mathrm{\mid }$ may hold for any finite solvable group $G$.