Question

Random graphs. In a random graph on n vertices for each pair of vertices i and j we independently include the edge {i, j} in the graph with probability 1/2. Show that with high probability every two vertices have at least n/4 - squareroot n log n common neighbors.

Answer 1

Let x be the number of isolated vertices in G (n, p). Then, E (x) = n (1 − p) n−1 . Since we believe the threshold to be ln n n , consider p = c ln n n . Then, limn→∞ E (x) = limn→∞ n 1 − c ln n n n = limn→∞ ne−c ln n = limn→∞ n 1−c . If c >1, the expected number of isolated vertices, goes to zero. If c < 1, the expected number of isolated vertices goes to infinity. If the expected number of isolated vertices goes to zero, it follows that almost all graphs have no isolated vertices. On the other hand, if the expected number of isolated vertices goes to infinity, a second moment argument is needed to show that almost all graphs have an isolated vertex and that the isolated vertices are not concentrated on some vanishingly small set of graphs with almost all graphs not having isolated vertices. Assume c < 1. Write x = I1 +I2 +· · ·+In where Ii is the indicator variable indicating whether vertex i is an isolated vertex. Then E (x 2 ) = Pn i=1 E (I 2 i ) + 2 P i 1 there almost surely are no isolated vertices, and when c < 1 there almost surely are isolated vertices.