Random graph thresholds and components

In G(n,p), the vertex set is labeled and every possible edge is included independently with probability p, which may depend on n. For an increasing graph property, a threshold function f means probability tends to zero whenever p/f tends to zero, and tends to one whenever p/f tends to infinity. Neither clause specifies the limiting probability at a fixed constant multiple of f. A sharp threshold requires additional relative-window information and should not be inferred merely from the existence of a threshold function.

For containing an edge, the number of edges is binomial with mean approximately $n^2p/2$. If this mean tends to zero, Markov gives absence with high probability. If it tends to infinity, the exact empty-graph probability is at most the exponential of minus that mean, which tends to zero. Thus the edge threshold is of order $n^{-2}$. This elementary example already demonstrates why the same parameter p must be interpreted together with the number of available opportunities.

Let X count triangles. Its mean is the number of vertex triples times the probability of their three edges. Below p of order 1/n, the mean tends to zero. Above that scale, a second-moment calculation works: distinct triangles sharing no edge have independent indicators, even if they share a vertex. The correlated pairs share exactly one edge, hence require five edges in their union. There are order n to the fourth such pairs, while the diagonal contributes at most the mean.

Dividing these contributions by the squared mean gives a bound of order the reciprocal of $n^3p^3$ plus the reciprocal of $n^2p$. Both terms vanish whenever np tends to infinity. This establishes the threshold 1/n without claiming the probability is near one at every fixed multiple of 1/n. In the constant-multiple regime the number of triangles can have a nontrivial limiting law. The first and second moments deliberately leave that transition window unresolved.

For p=c/n with fixed c, an early component exploration resembles a branching process with approximately Poisson(c) offspring. This approximation describes a small exploration before collisions become significant; it is not an identity for an entire finite component. The resulting established random-graph theorem says that for fixed c<1 every component has logarithmic size with high probability, whereas fixed c>1 yields a unique component with a positive limiting vertex fraction. The critical case c=1 needs its own scaling analysis.

The giant fraction for c>1 is the positive solution rho of $\rho=1-e^{-c\rho}$; the zero solution must not be mistaken for the supercritical survival probability. Even a giant need not contain every vertex. A particular vertex is isolated with exact probability $(1-p)^{n-1}$, so the expected number of isolates is easy to calculate. Connectivity occurs near the larger scale log(n)/n. An expected isolate count alone does not prove typical disconnection, but it exposes why a mean degree near one is no certificate of connectivity.