- #1
Discover85
- 9
- 0
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!
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!