Probabilistic method for Graphs

[Discover85]

We have been using the probabilistic method in class to show that there exists graphs with very interesting properties. Our most recent assignment would like us to apply the method but I'm having great difficulty in doing so. The question is as follows:

We say that a pair of vertices in a graph G with n vertices is bad if the subgraph induced by their common neighbourhood does not contain at least n^(7/4) edges. Show that for any p > 0, the probability that G contains a bad pair of vertices goes to zero as n tends to infinity.

I'm having difficulty in finding the expected number of bad pairs of vertices for a graph of size n. Once a loose bound is found though it should be a straightforward application of Markov's inequality or some other probabilistic tool.

Any helps or hints would be greatly appreciated!

 

[Valkarie]

To solve this problem, we first need to calculate the expected number of bad pairs of vertices in a graph of size n. Let E_n be the expected number of bad pairs in a graph with n vertices. Since each pair of vertices has the same probability of being bad, we can calculate E_n by counting the total number of pairs of vertices, and multiplying by the probability that each pair is bad. The total number of pairs of vertices in a graph with n vertices is \binom{n}{2} = \frac{n(n-1)}{2}. Now, for any given pair of vertices, the probability that their common neighbourhood does not contain at least n^(7/4) edges is (1 - \frac{1}{n^{3/4}})^{n-2}, since the probability of a single edge existing between any two vertices is \frac{1}{n^{3/4}}. Therefore, the expected number of bad pairs of vertices in a graph with n vertices is:E_n = \binom{n}{2}\left(1 - \frac{1}{n^{3/4}}\right)^{n-2}Now, we can use Markov's inequality to show that the probability of there being at least one bad pair of vertices in a graph with n vertices tends to zero as n tends to infinity. Specifically, we have:P(G contains a bad pair of vertices) = P(E_n \ge 1) \le \frac{E_n}{1} = E_n As n tends to infinity, E_n tends to zero, which implies that the probability of G containing a bad pair of vertices goes to zero as n tends to infinity.