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)?



1 Answer 1


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).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.