图核与三角形密度连续性

形式陈述

图核（graphon）是对称可测函数

W:[0,1]^2\longrightarrow[0,1], \qquad W(x,y)=W(y,x).

本页均使用 Lebesgue 测度，忽略零测集上的差别；对称性也只需几乎处处成立。区间中的点扮演顶点类型， $W(x,y)$ 表示两种类型之间的连接强度。图核首先是确定的分析对象，不必预先来自一次随机采样。

边与三角形的同态密度分别定义为

t(K_2,W)=\int_{[0,1]^2}W(x,y)\,dx\,dy,

t(K_3,W)= \int_{[0,1]^3}W(x,y)W(x,z)W(y,z)\,dx\,dy\,dz. \tag{1}

所有被积函数都有界，因而绝对可积，可用Fubini 定理交换积分次序。这里的三角形密度没有除以 $6$ ；有序的三个采样点分别对应 $K_3$ 的三个标号顶点。

对可积核 $D:[0,1]^2\to\mathbb R$ ，其割范数是

\|D\|_\square =\sup_{S,T\subseteq[0,1]\text{ 可测}} \left|\int_{S\times T}D(x,y)\,dx\,dy\right|.

$S,T$ 不要求不交或相等。它比较任意两类顶点之间的总连接量，满足 $\|D\|_\square\le\int|D|$ 。

本页的三角形计数连续性为

\boxed{|t(K_3,U)-t(K_3,W)| \le3\|U-W\|_\square} \tag{2}

对任意两个 $[0,1]$ 值图核成立。右侧只比较同一坐标中的核；若允许重新标记顶点类型，还可定义

W^\phi(x,y)=W(\phi(x),\phi(y)),\qquad \delta_\square(U,W)=\inf_\phi\|U-W^\phi\|_\square,

其中 $\phi$ 遍历保 Lebesgue 测度、且有保测逆映射的可测重标记，允许忽略零测集。由密度在重标记下不变，(2) 进一步给出

|t(K_3,U)-t(K_3,W)|\le3\delta_\square(U,W). \tag{3}

割距离在未作等价识别的图核上允许不同函数的距离为零；本页不把它当作区分每一个函数写法的距离。

直觉

有限简单图的邻接矩阵可以画成黑白小方块，放大后就是阶梯图核。单独比较总黑色面积只能看出边密度；割范数还允许选择行、列子集，观察连接是否集中在特定块中。

三角形的三个边因子是连续性证明的关键。把 $U$ 的三条边逐条换成 $W$ ，每次只剩一个差核。固定第三个顶点后，另两条边给出两个取值在 $[0,1]$ 的权函数，它们可以由集合指示函数平均得到。一次替换的误差因此不超过割范数，三次替换给出系数 $3$ 。

例子与边界

相同边密度，不同三角形密度

令 $C(x,y)\equiv1/2$ 。直接积分得

t(K_2,C)=\frac12,\qquad t(K_3,C)=\frac18.

再把区间分为等测度两半 $A=[0,1/2)$ 、 $B=[1/2,1]$ ，定义平衡二部图核

H(x,y)= \begin{cases} 1,&(x,y)\in A\times B\ \text{或}\ B\times A,\\ 0,&\text{其他情形}. \end{cases}

两块非零区域各有面积 $1/4$ ，所以 $t(K_2,H)=1/2$ 。任意三个点至少有两个在同一半区，它们之间的边因子为零，故

t(K_3,H)=0.

这两个模型的边密度完全相同，三角形密度却相差 $1/8$ 。只知道平均边数，不能把连接结构视为常值核。

常值半密度图核与平衡二部图核具有相同积分边密度，但三角形密度分别为八分之一和零 — 同边密度不能决定三角形密度

图中横轴为 $x$ 、纵轴为 $y$ ，格内数字给出核值。左侧虚线只标出两半区的位置，核值始终为 $1/2$ ；右侧只在异侧半区之间取值一。

还能精确计算它们的割范数差。令 $h=1_A-1_B$ ，则

H-C=-\frac12h(x)h(y),

所以对任意 $S,T$ ，

\left|\int_{S\times T}(H-C)\right| =\frac12\left|\int_S h\right|\left|\int_T h\right| \le\frac12\cdot\frac12\cdot\frac12=\frac18.

取 $S=T=A$ 达到等号，故 $\|H-C\|_\square=1/8$ 。任意保测重标记仍把 $A,B$ 变成测度各为 $1/2$ 的分部，同一计算给出 $\|H^\phi-C\|_\square=1/8$ ；因而 $\delta_\square(C,H)=1/8$ 。三角形差已足以排除这两个核的割距离为零，但连续性常数不要求这个例子取等。

有限图的归一化

给 $n\ge1$ 个顶点的简单图 $G$ 依次分配长度 $1/n$ 的区间 $I_1,\ldots,I_n$ ，在 $I_i\times I_j$ 上令 $W_G$ 等于邻接矩阵条目。自环不存在，因此同一顶点对应的对角方块取零。

若 $e(G)$ 为边数， $T(G)$ 为无序三顶点集计数的三角形数，则

t(K_2,W_G)=\frac{2e(G)}{n^2},\qquad t(K_3,W_G)=\frac{6T(G)}{n^3}. \tag{4}

第一式中每条边占两个有序方块。第二式中每个三角形有六种顶点标号，每个对应体积 $n^{-3}$ ；有两个顶点重合的映射必用到对角零块，不贡献积分。

因此三角形同态密度与 $T(G)/\binom n3$ 在有限 $n$ 时不同。二者关系为

t(K_3,W_G) =\frac{n(n-1)(n-2)}{n^3}\, \frac{T(G)}{\binom n3} \qquad(n\ge3).

例如完全二部图 $K_{m,m}$ 的图核正是 $H$ ，同态边密度恰为 $1/2$ ；通常按全部可能边归一化的比例却是 $m^2/\binom{2m}{2}=m/(2m-1)$ ，只在极限趋于 $1/2$ 。

推论与应用

从矩形指示函数到有界权函数

设 $f,g:[0,1]\to[0,1]$ 可测。用阈值集合逐点写成

f(x)=\int_0^1 1_{\{f(x)>s\}}\,ds,\qquad g(y)=\int_0^1 1_{\{g(y)>t\}}\,dt.

对可积 $D$ ，四重被积函数的绝对值由 $|D(x,y)|$ 控制，可以交换积分。于是

\begin{aligned} \left|\int_{[0,1]^2}D(x,y)f(x)g(y)\,dx\,dy\right| &=\left|\int_0^1\int_0^1 \int_{\{f>s\}\times\{g>t\}}D(x,y)\,dx\,dy\,ds\,dt\right|\\ &\le\int_0^1\int_0^1\|D\|_\square\,ds\,dt\\ &=\|D\|_\square. \end{aligned} \tag{5}

反过来，指示函数本身也是允许的 $f,g$ ，所以在 (5) 左侧对所有这样的权函数取上确界，恰好得到原割范数。 $[0,1]$ 的值域承担了系数一的作用。

三条边逐条替换

记 $D=U-W$ ，以下下标只表示函数的两个输入。逐项展开得

U_{xy}U_{xz}U_{yz}-W_{xy}W_{xz}W_{yz} =D_{xy}U_{xz}U_{yz} +W_{xy}D_{xz}U_{yz} +W_{xy}W_{xz}D_{yz}.

第一项固定 $z$ ，在 (5) 中取 $f(x)=U(x,z)$ 、 $g(y)=U(y,z)$ 。对几乎所有 $z$ ，截面可测且属于 $[0,1]$ ，所以对 $x,y$ 积分的绝对值不超过 $\|D\|_\square$ ，再积分 $z$ 仍不超过这个数。

第二项固定 $y$ ，对差核的变量 $x,z$ 使用权函数 $W(x,y)$ 、 $U(y,z)$ ；第三项固定 $x$ ，对变量 $y,z$ 使用 $W(x,y)$ 、 $W(x,z)$ 。各项得到同一个上界，三角不等式便给出 (2)。

保测重标记保持乘积测度：先对矩形的指示函数逐坐标核对，再由简单函数逼近推广到有界可测函数。因此 $t(K_3,W^\phi)=t(K_3,W)$ 。将 (2) 应用于 $U,W^\phi$ ，对所有 $\phi$ 取下确界，即得 (3)；不需要假设最优重标记存在。

与有限计数和随机图的连接

若 $\delta_\square(W_{G_n},W)\to0$ ，(3) 立即推出

\frac{6T(G_n)}{|V(G_n)|^3}\longrightarrow t(K_3,W).

这与正则对计数引理相呼应：二者都用局部连接控制来稳定小图计数，但这里的假设是割距离接近，证明直接使用积分中的三条边替换。本页只证明这个方向的三角形结论；单独知道三角形密度收敛，不能据此断定图核在割距离下收敛。

在$G(n,p)$中，常值核 $W\equiv p$ 预测三角形密度为 $p^3$ 。二阶矩页从有限样本的共享边协方差出发，证明

\operatorname{Var}T =\binom n3p^3(1-p^3)+12\binom n4p^5(1-p),

并由此得到固定 $p$ 时 $6T/n^3\to p^3$ 的均方与依概率收敛。这里是对同一三角形统计的直接验证，不把这一项统计的极限充当一般割距离收敛定理。

参考资料

Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, 作者书稿第4章，印刷页132–140的定义，以及 pp. 144–146 的 Theorem 4.5.1、Lemma 4.5.3、Proposition 4.5.4：图核、割距离、同态密度与三角形连续性。书稿页码按链接版本。

形式陈述 ​

相同边密度，不同三角形密度 ​

有限图的归一化 ​

从矩形指示函数到有界权函数 ​

三条边逐条替换 ​

与有限计数和随机图的连接 ​