1

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.

TedMosby
  • 503

1 Answers1

2

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.

Misha Lavrov
  • 142,276