Critical Scaling Near Mean Degree One

Why Mean Degree One Has a Window

In a random graph, a small change in edge probability can change the typical sizes of connected components. The value \(p=1/n\) is the boundary between two familiar behaviors: below it, components tend to be small; above it, a component containing a positive fraction of the vertices appears. The transition is not confined to the single value \(1/n\). There is a window of probabilities around it where the largest components have an intermediate scale.

Throughout, \(G(n,p)\) is the random simple graph on \(n\) labelled vertices in which each possible edge is included independently with probability \(p\). A component is a maximal connected subgraph, and \(L_1(G)\) denotes the number of vertices in a largest component. The expected degree of any vertex is \((n-1)p\), while \(np\) is a convenient approximation used to locate the transition.

The window has width \(n^{-4/3}\) in \(p\): rewriting the definition gives \(p_n=1/n+\lambda n^{-4/3}\). Equivalently, \(np_n-1=\lambda n^{-1/3}\). Thus the mean-degree excess is of order \(n^{-1/3}\), not a fixed positive or negative constant.

How Exploration Produces the \(n^{2/3}\) Scale

Explore a component by maintaining a queue of discovered but not yet explored vertices. When a vertex is processed, reveal its edges to vertices that have not yet been discovered. If there are \(U_k\) undiscovered vertices at step \(k\), the number \(X_k\) newly discovered at that step has conditional distribution \(\operatorname{Bin}(U_k,p_n)\): the relevant edges have not previously been revealed. The queue changes by \(X_k-1\), because one vertex is removed for processing and \(X_k\) are added.

Suppose \(k\) vertices have been processed and the queue currently contains \(A_k\) vertices. Then \(U_k=n-k-A_k\). During a component exploration, conditional on the history so far, the expected queue change at the next step is therefore

This identity explains the competing effects in the critical window. The term \(\lambda n^{-1/3}\) is the initial excess above the branching threshold. As vertices are explored, the supply of undiscovered vertices decreases; the term \(-p_n k\) records that depletion. The active-queue term also contributes, but it is smaller in the leading scale calculation.

This is a scaling argument, not a proof of a component-size limit. In particular, the queue is random, components begin at different times, and the exploration must account for all vertices. The rigorous limiting result requires substantially more work.

The Critical Random Graph Scaling Result

The scaling argument is made precise by a standard theorem in the theory of random graphs. To state its limiting object, let \(B(t)\), \(t\geq0\), be standard Brownian motion, and define \(W_\lambda(t)=B(t)+\lambda t-t^2/2\). Reflect this path at its running minimum: \(R_\lambda(t)=W_\lambda(t)-\min_{0\leq s\leq t}W_\lambda(s)\). An excursion is a maximal interval on which \(R_\lambda(t)>0\); its length is the interval's duration.

The theorem makes the scale statement precise: for fixed \(\lambda\), the largest component is of order \(n^{2/3}\) in the probabilistic sense, with a nontrivial random limiting size after normalization. It does not assert that every component has that size. Many components are much smaller, while the largest few are represented by the largest excursions in the limit.

The parameter \(\lambda\) affects the limiting process through its linear drift. Positive \(\lambda\) favors longer explorations, negative \(\lambda\) favors shorter ones, and \(\lambda=0\) is the centre of the window. All fixed values of \(\lambda\), however, remain in the same \(n^{-1/3}\) mean-degree range and have the same \(n^{2/3}\) component scale.

How the Three Regimes Differ

The critical window is best understood by comparing it with probabilities whose mean degree stays a fixed distance from one.

Here “with high probability” means with probability tending to one as \(n\) tends to infinity. The subcritical and supercritical descriptions are the fixed-\(c\) regimes; they should not be applied unchanged when \(c\) approaches one as \(n\) grows. The critical window resolves that approach: its width in \(p\) is \(n^{-4/3}\), and its largest components are much larger than logarithmic but smaller than linear in \(n\).

Common Pitfall: Confusing \(np\) with Expected Degree

A common error is to treat \(np\) as the exact expected degree. For \(G(n,p)\), a vertex has \(n-1\) possible neighbors, so its expected degree is \((n-1)p\), not \(np\). For example, with \(n=1000\) and \(p=0.0012\), \(np=1000(0.0012)=1.2\), but the expected degree is \(999(0.0012)=1.1988\). The difference is small here, but it matters when stating exact finite-\(n\) quantities. The critical-window parameterization is defined through \(np=1+\lambda n^{-1/3}\); the actual expected degree is \((1-1/n)(1+\lambda n^{-1/3})\).

A second error is to interpret the scale \(n^{2/3}\) as a deterministic formula for the largest component. The theorem gives a random limiting size after normalization. At finite \(n\), the largest component fluctuates, and the value of \(\lambda\) changes its limiting distribution. The scale describes the magnitude of those fluctuations, not an exact component size.