Erdős–Rényi 随机图

$G(n,p)$ 可以看成同时拨动 $N$ 个独立开关，每个开关决定一条边是否存在。模型只在最底层边选择上独立；连通、出现三角形、存在孤立点等全局事件共享大量开关，通常强烈相关。$G(n,m)$ 则先锁定开关总数再随机选择位置：选中一条边会略微降低另一条边被选中的条件概率，这正是固定总量带来的依赖。

随机图的阈值描述的是随 $n$ 增大、参数 $p=p(n)$ 改变时，某个单调性质从高概率不出现转为高概率出现的尺度。它不是声称有限 $n$ 上存在没有过渡区的物理相变，也不是每个性质都共享同一阈值。

三角形数可写为

固定顶点成为孤立点的概率是 $(1-p{)}^{n-1}$，所以孤立点数 $I$ 满足 $\mathbb{E}I=n(1-p{)}^{n-1}$。这两个计算展示同一阶矩工具的不同作用：$\mathbb{E}T<1$ 可帮助证明存在无三角形样本，孤立点期望接近零则提示连通性阈值附近的障碍，但单凭期望很大并不能保证变量以高概率为正，通常还需要二阶矩或集中论证。

二阶矩页公理库二阶矩方法Second moment method从非负变量的二阶矩证明正概率与相对集中，并逐类计算随机图三角形的精确方差、有限分布和密度极限。进一步按共享边分类，证明精确方差 $\mathrm{Var}T=(\genfrac{}{}{0ex}{}{n}{3})p^3(1-p^3)+12(\genfrac{}{}{0ex}{}{n}{4})p^5(1-p)$，并列全 $G(4,1/2)$ 的三角形数分布，复算方差 $5/8$。固定 $p$ 时，三角形比例趋于 $p^3$；按图核同态密度公理库图核与三角形密度连续性Graphon · 图极限核 · Triangle counting continuity把稠密图写成单位正方形上的对称可测核，以割范数控制三角形密度，并区分同边密度的常值与二部模型。归一化则是 $6T/n^3$，有限规模下需保留与 $T/(\genfrac{}{}{0ex}{}{n}{3})$ 的系数差。

两条相邻边在 $G(n,p)$ 中独立；当 $n\ge 4$ 且 $0<p<1$ 时，“三角形 $123$ 出现”和“三角形 $124$ 出现”共享边 $12$，并不独立。在 $G(n,m)$ 中，若 $N\ge 2$ 且 $m\ge 1$，任意两条不同边 $e,f$ 满足

通常不等于 $m/N$。退化参数 $p=0,1$ 分别给出空图和完全图，仍是合法模型。这里默认标号、简单、无向图；无标号随机图或允许自环、重边的模型拥有不同样本空间。

Erdős–Rényi 模型是概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。中最基本的随机组合对象。一阶矩公理库一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。可排除稀有坏结构，二阶矩公理库二阶矩方法Second moment method从非负变量的二阶矩证明正概率与相对集中，并逐类计算随机图三角形的精确方差、有限分布和密度极限。处理多个候选结构间的依赖，图连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。、巨分量、着色数与固定子图出现都可据此研究各自的渐近尺度。

模型还提供算法与网络的平均情形基线，但真实网络若有重尾度分布、聚团或社区结构，就不应因边缘密度相同而直接套用 $G(n,p)$。选择模型时应先问独立边与同质顶点是否符合机制，再解释由模型得到的概率结论。

若目标是邻接矩阵的全部方向误差，矩阵 Bernstein 不等式公理库矩阵 Bernstein 不等式Matrix Bernstein inequality · 矩阵伯恩斯坦不等式用逐项谱范数与矩阵方差控制独立中心化 Hermitian 矩阵和，借助 Lieb 凹性完成非交换指数矩证明，并计算随机图邻接矩阵的统一方向误差。把 $G(n,p)$ 的每条候选边写成独立中心化对称矩阵，算出方差参数 $(n-1)p(1-p)$，从而控制 $\Vert A-p(J-I){\Vert }_2$。该页完整计算 $G(1000,0.1)$ 的置信阈值；固定边数的 $G(n,m)$ 因缺少边独立性，不能原样套入。