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

CC BY-SA 3.0
2013-04-04T09:01:22.873Z
"Expander graphs" is not a class of random objects; they can be constructed deterministically.
Jeffε
CC BY-SA 3.0
2013-04-04T23:58:00.883Z
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?
Elliot JJ
<graph-theory><co.combinatorics><expanders><max-flow-min-cut>
Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?
Elliot JJ
# Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

(Asked by: username_0 on 2013-04-03)

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

**Tags:** graph-theory, co.combinatorics, expanders, max-flow-min-cut

> **Comments:**
> **username_1**: "Expander graphs" is not a class of random objects; they can be constructed deterministically.  
> **username_0**: 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?  

---

## 0 answers

