1
$\begingroup$

If we want a specific example, then how about the Erdos-Renyi random graph?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ "Expander graphs" is not a class of random objects; they can be constructed deterministically. $\endgroup$
    – Jeffε
    Apr 4, 2013 at 9:01
  • $\begingroup$ Can you suggest a refinement of the question? What about Erdos-Renyi graphs? Is there a common random class of graphs known to be expanders for which this is not true with high probability? $\endgroup$
    – Elliot JJ
    Apr 4, 2013 at 23:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.