Skip to main content
3 of 3
formatting, added tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

How to prove a random d-regular graph is an expander with prob >= 0.5?

How to prove a random $d$-regular graph is an expander with prob $\ge 0.5$?

Context: Many resources, like

http://math.mit.edu/~fox/MAT307-lecture22.pdf

state the theorem in the general case, but then prove it only for the bipartite case. The full case is supposedly proved in Pinsker's 1973 paper. However, I can't dig up a copy.

Anyone know of a proof for the general case (i.e. d-regular, undirected, not-necessarily-bipartitite graph)?

Thanks!