Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-36/3/a/solution

Each unordered triple of vertices is a triangle in a graph with probability . Consequently the triangle count in a binomial random graph satisfies . If , the Markov inequality gives . Hence
the sparse direction of the triangle-existence threshold in a binomial random graph.

New to topics? Read the docs here!