We present an approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from combinatorial group theory. It applies to both regular and irregular random graphs.
In the talk, I will focus on regular graphs. Let $G$ be a random $d$-regular graph on $n$ vertices. It was conjectured by Alon (86') and proved by Friedman (08') in a ~100 page-long booklet that the highest non-trivial eigenvalue of $G$ is a.a.s. arbitrarily close to $2\sqrt{d-1}$. Our proof is substantially simpler and nearly recovers Friedman’s result. I will present the main ideas that go into the proof, some of them of independent interest.