連通門檻（the connectivity threshold）

連通門檻是隨機圖不再被切成片塊、變成一個連通整體的邊密度。它位於遠高於巨大連通分量門檻的密度：一張圖可以有含 99% 頂點的巨人卻仍不連通，因為還殘留著幾個孤立頂點。它回答的問題是：要的不只是有一個大團塊，而是把每一個頂點都繫進一個分量，需要多少邊？

此定理（厄多斯-雷尼）既銳且優雅。設 p = (log n + c)/n（常數 c）。則 P(G(n,p) 連通) 隨 n 增長趨於 e^(-e^(-c))。特別地，若 p = (log n - omega(n))/n 且 omega 趨於無窮，圖 whp 不連通；若 p = (log n + omega(n))/n，圖 whp 連通。故門檻為 p* = (log n)/n，且為銳門檻，窗口寬度 1/n。其機制是：連通性本質上由最後消失的障礙控制，而那就是孤立頂點。孤立頂點數目的期望為 n (1-p)^(n-1)，在 p = (log n + c)/n 時約為 n e^(-np) = e^(log n - np) = e^(-c)；孤立頂點數目漸近服從均值 e^(-c) 的卜瓦松（由斯坦因-陳方法），故 P(無孤立頂點) 趨於 e^(-e^(-c))。深刻之處在於：橫亙在不連通與連通之間的最後一物，真的就是孤立頂點：在 (log n)/n 之上，whp 除一個巨人外的每個分量都已被吸收，故「連通」與「無孤立頂點」在極限中重合。

此門檻在任何需要完全可達（而不只是大部分可達）的網路中都重要：隨機金鑰分發方案、容錯網路，以及一個類似集郵問題的現象——完全覆蓋的成本比宏觀覆蓋的成本高一個 log n 因子。誠實的微妙處是：「連通」與「無孤立頂點」的等價本身是定理，且是此夠稠密區間所特有的；在更稀疏的區間，連通性的障礙真的是小分量，而不只是單點。也要注意一個密切平行的敘述對於度數低於任一固定 k 的頂點之消失成立：G(n,p) 的最小度數至少為 k，恰在門檻 p = (log n + (k-1) log log n + c)/n 處，低度數頂點的數目同樣有卜瓦松極限。