Why does the threshold for most properties in Erdős-Rényi graphs tend to decrease with increasing nodes?

228 Views Asked by At

The threshold (edge probability) for certain properties such as diameter two ($\sqrt{2\frac{lnn}{n}}$) are dependent on number of nodes in Erdős-Rényi graphs. Because of which as $n \to \infty$, the threshold edge probability seems to be lower and lower. How does that make any sense? How does small edge probability ensure that the graph is not just connected but also has two hops? What am I missing here?

1

There are 1 best solutions below

1
On

The property you chose, diameter 2, is a good example. There are two competing considerations: For two fixed nodes $x,y$, there are about $n$ (more precisely, $n-2$) potential paths between them; the threshold for one of these paths being available (retained, or open) is $n^{-1/2}$. Guaranteeing such a path for every pair is what costs the additional logarithmic factor.