Random graph: Difference between revisions

Revision as of 07:41, 12 January 2015

Revision as of 07:44, 12 January 2015

Line 59:

:#<math>X_{i}</math> and <math>X_{j}</math> are independent if <math>\left |VT_{i} \cap VT_{j}\right |</math> ≤ 1.

LetWhen <math>p_{n}</math> ≪ <math>1/n</math>, then

:<math>Pr(X \ge 1) \le E(X) = {n \choose 3}p_{n}^{3} \le (\frac{p_{n}}{1/n})^{3} \to 0</math>, as <math>n \to \infty</math>.

LetWhen <math>p_{n}</math> ≫ <math>1/n</math>, then

:<math>\begin{align}

Pr(X=0) &\le Pr(|X-E(X)| \ge E(X)) \\