<p>Perhaps what's implicit after "there are" is "asymptotically almost surely", which means that the property holds with probability tending to 1 as n tends to infinity; this is stronger than "in expectation".  You might want to check out a standard textbook on random graphs (e.g. by Alon-Spencer, Bollobas, or Janson-Luczak-Rucinski).</p>

CC BY-SA 3.0
2011-06-05T01:29:23.583Z
2011-06-05T01:29:23.583Z
RJK
<p>In Luca Trevisan's paper "Psuedorandomness and Combinatorial Constructions", he says that in a graph drawn from $G_{n,1/2}$, for every two disjoint sets A and B there are $(1/2 + o_n(1)) |A||B|$ edges between A and B. </p>

<p>I'm confused as to the exact meaning of this statement. Is it saying that given two disjoint subsets of n vertices selected at random, that's the expected value of the number of edges between them? If so, then doesn't linearity of expectation give |A||B|/2? What is this extra factor of o(1)?</p>

<p>Thanks!</p>

<graph-theory><co.combinatorics>
Size of cuts in graphs drawn from $ G_{n,1/2}$
Tom Yens
# Size of cuts in graphs drawn from $ G_{n,1/2}$

(Asked by: username_0 on 2011-06-04)

In Luca Trevisan's paper "Psuedorandomness and Combinatorial Constructions", he says that in a graph drawn from $G\_{n,1/2}$, for every two disjoint sets A and B there are $(1/2 + o\_n(1)) |A||B|$ edges between A and B.

I'm confused as to the exact meaning of this statement. Is it saying that given two disjoint subsets of n vertices selected at random, that's the expected value of the number of edges between them? If so, then doesn't linearity of expectation give |A||B|/2? What is this extra factor of o(1)?

Thanks!

**Tags:** graph-theory, co.combinatorics

---

## 1 answers

### Answer by username_1 on 2011-06-05. Score: 8

Perhaps what's implicit after "there are" is "asymptotically almost surely", which means that the property holds with probability tending to 1 as n tends to infinity; this is stronger than "in expectation". You might want to check out a standard textbook on random graphs (e.g. by Alon-Spencer, Bollobas, or Janson-Luczak-Rucinski).


---

