Skip to main content
MathOverflow

Return to Question

formatting, added tags
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

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!

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!

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!

fixed speelnig
Source Link
Yemon Choi
Yemon Choi
  • 25.8k
  • 9
  • 69
  • 156

Prove: Random D How to prove a random d-Regular Graphregular graph is an expander w/with prob >= 0.5?

Context:

  Many resources, like

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

state the threomtheorem in the general case, but then prove it only for the bipartite case.

The The full case is supposedly proved in Pinkser'sPinsker'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-necessairlynecessarily-bipartitite graph)?

Thanks!

Prove: Random D-Regular Graph is an expander w/ prob >= 0.5

Context:

  Many resources, like

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

state the threom in the general case, but then prove it only for the bipartite case.

The full case is supposedly proved in Pinkser'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-necessairly-bipartitite graph)?

Thanks!

How to prove a random d-regular graph is an expander with prob >= 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!

Source Link
expanders
expanders
  • 81
  • 3

Prove: Random D-Regular Graph is an expander w/ prob >= 0.5

Context:

Many resources, like

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

state the threom in the general case, but then prove it only for the bipartite case.

The full case is supposedly proved in Pinkser'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-necessairly-bipartitite graph)?

Thanks!