In any random graph on n vertices for each pair of vertices i and j, we include the edge {i,j} in the graph with probability 1/2. Show that with high probability every 2 vertices have at least n/4 - √nlogn common neighbors.
I do not really know where to start, do we use a Chernoff bound to solve this?
Thanks for your help.
Given two vertices $i$ and $j$, there are $n-2$ other vertices $k$ that they could possibly have as common neighbors. The probability that any given $k$ is a common neighbor is $\frac14$, so the distribution we're interested in is $\operatorname{Bin}(n-2, \frac14)$.
At that point, yes, a Chernoff bound will finish the job.