2. Let 0 < p < 1/2 and let T be the random variable counting triangles in a randomly chosen graph G from Gin,p). (a) Sho

[answerhappygod]

2 Let 0 P 1 2 And Let T Be The Random Variable Counting Triangles In A Randomly Chosen Graph G From Gin P A Sho 1 (37.34 KiB) Viewed 41 times

2. Let 0 < p < 1/2 and let T be the random variable counting triangles in a randomly chosen graph G from Gin,p). (a) Show that PCT = 0) 2 (1 – pº 2 e pim. Hint; if a graph has no edges, then it's triangle-free. (b) Show that PCT = 0) 2 (1 - p3) > e-p*r Hint; for a fixed 3-subset of [n] let Y, be the Boolean r.v. which takes on the value 1 iff the triangle with vertex set t is in G. Note that 1 - Y,, viewed as a function F(X1,...,xn) of the random edges, is coordinatewise increasing. What do you conclude about the upper bound on P(T = 0) we obtained from Janson's inequal- ity?