Probabilistic Method – 6
February 10, 2011 Leave a comment
Q.1. Let be non-negative real numbers. If , then .
(the 2nd inequality follows from Chebyshev’s formula)
Taking limits as on both sides, we get the desired result.
Q.2. If , prove that, as approaches infinity, contains a triangle. If , prove that, as approaches infinity, does not contain a triangle.
Let be indicator variables for the corresponding 3-vertex-subsets inducing a triangle in .
(Here, if the corresponding triangles do not share an edge; number of ordered pairs of triangles sharing an edge .)
If , as approaches infinity, proving one part of the question.
Now, from (1) and (2),
which implies that , proving the other part of the question.