 |
 |
26 of 32 |  |
 |
 |
MIT
Conclusion
l
How much of “random graphs”
generalizes to “random subgraphs?”
l
Can threshold for G
(p)
be tightened?
l
Evolutionary model/giant component?
l
Showed: cuts have expected values
»
same principle as expanders
»
is there a deterministic construction of a
“good sample”?