## Lecture 5: Expanders, Probabilistic Proof of Existence

We gave a proof showing that most regular graphs are good (edge/vertex) expanders. In terms of edge-expansion, Bella Bollobas in this paper showed that, for every , most random -regular graphs have edge-expansion rate (i.e. edge-isoperimetric number) at least for some constant . (Specifically, we can set . On the other hand, given any -regular graph of order , if we select a random subset of vertices of size , then the expected number of edges crossing the cut is

So the edge-isoperimetric number is bounded above by . Thus, for large graphs the edge expansion rate is (roughly) at most .

Better yet, Noga Alon proved in this paper that there is a constant such that the edge-isoperimetric number of any -regular graph (with sufficiently large number of vertices) is at most .

In summary, we can roughly think of edge-isoperimetric numbers of random -regular graphs to be about .

For small values of , Bollobas’ analysis yields the following. For every sufficiently large ,

- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander

leave a comment