图计数引理

若相关簇对像相互独立的随机二分图，那么选定 $x_1,\dots ,x_k$ 后，每条所需边以概率 $d_{ij}$ 出现，全部边同时出现的比例便是密度乘积。正则性不提供真正独立性，却保证在逐个选顶点时，除了少量异常选择，候选集合在下一个簇中仍保留预期比例。

逐边替换怎样控制加性误差 ​

先看一个正则簇对 $(A,B)$，令 $M(a,b)={\mathbf{1}}_{ab\in E(G)}-d(A,B)$。对任意 $S\subseteq A,T\subseteq B$，都有

当两子集都达到正则阈值时，结论由密度偏差界得到；若其中一个较小，则用 $|M|\le 1$ 和子集大小直接得到同一上界。空子集的和为零。

同一个估计也适用于 $[0,1]$ 值权函数 $u(a),v(b)$：有限集合上的这种函数可以写成阈值集合指示函数的非负线性组合，系数之和至多一。因此

将计数写成所有跨部顶点选择上的边指示函数乘积之和，逐条把一条边的指示函数换成其密度。固定这一条边的两个端点之外的所有顶点后，其余因子分成两个端点各自的 $[0,1]$ 值权函数，以及一个不依赖这两个端点的 $[0,1]$ 因子；简单图中没有第二条边连接同一对端点。上面的加权估计遂把这一步的总变化限制在 $\epsilon \prod _i|V_i|$。一共替换 $m$ 条边，最后恰为密度乘积，三角不等式就给出 $m\epsilon$ 的归一化误差。

取三个簇 $V_1,V_2,V_3$，大小分别为 $3,4,5$，并把每一对簇之间都完全连接。三对密度均为 $1$，任何跨簇选择都形成三角形，所以尊重分部的标号三角形恰有

个，正好等于密度乘积 $1^3$ 乘顶点选择数。若把同一个无标号三角形在固定三部中的位置视为已确定，就不再额外除以 $6$；计数约定必须与公式一致。

现在令三个簇的大小都是偶数 $N$，各自分成相等的“上、下”两半，只在同标签半块之间完全连接。每个簇对的总体密度都是 $1/2$，但跨三部三角形只能全部选上半或全部选下半，共有

个；朴素密度乘积却预测 $(1/2{)}^3{N}^3=N^3/8$。差一倍的原因不是概率计算错，而是每个簇对都被半块见证为不正则。这个反例准确标出正则性假设承担的工作。

正的密度下界用于从加性估计提取正比例副本，而非加性估计本身。若密度乘积小于误差项，下界可能只是零；要控制相对误差，就必须把正则误差进一步缩小，或采用适当的稀疏条件。引理保证总副本数，不保证副本边不交，也不保证每个顶点参与近似相同数量的副本；后两种需求要用更强的典型顶点或超图匹配论证。

把正则划分压成约化图后，只要约化图含 $F$ 且对应密度高于固定阈值，计数引理便把这一份 $F$ 提升成原图中的 $\mathrm{\Omega }(n^{v(F)})$ 个副本。这是图移除引理理路图移除引理Graph removal lemma · H-removal lemma · 图删除引理固定图的副本数若低于正确幂次的足够小比例，就能删除少量边消灭全部该图副本。证明中的矛盾核心，也是以正则性证明 Erdős–Stone 定理时从约化团恢复禁图复制的桥梁。

计数引理还说明稠密图的有限子图统计可由有限密度矩阵近似，是图极限与采样算法的基础。若目标是诱导副本，需要同时乘入非边簇对的因子 $1-d_{ij}$，并对所有相应的边与非边簇对控制正则误差；若要正比例下界，再要求这些因子都远离零；普通版本不能凭“缺少要求的边”自行完成诱导计数。

图核的三角形连续性理路图核与三角形密度连续性Graphon · 图极限核 · Triangle counting continuity把稠密图写成单位正方形上的对称可测核，以割范数控制三角形密度，并区分同边密度的常值与二部模型。把这一联系写成可直接证明的积分估计：$|t(K_3,U)-t(K_3,W)|\le 3\Vert U-W{\Vert }_{◻}$。证明用阈值指示函数把矩形测试推广到两个有界权函数，再逐条替换三角形的边因子；常值半密度核与平衡二部核的比较说明，相同总边密度仍可对应不同三角形密度。