6. 子图密度间的不等式

研究图极限的动机之一是图极限提供了一种有效的语言来考虑图不等式. 例如, 我们可以回答以下问题:

问题 6.1. 如果 $t\left(K_2,G\right)=1/2$, $t\left(C_4,G\right)$ 的最小可能值是多少?

我们知道这个问题的答案. 如前所述, 根据定理!!4.1, 我们可以考虑一个拟随机图序列, 他们的极限是一个满足 $t\left(K_2,W\right)=2^{-4}$ 的 graphon $W$.

在本节中, 我们将研究此类关于同态密度不等式的问题. 本书前面已经讨论了两个图不等式, 分别为 Mantel 定理 (定理 1.0.2) 和 Turán 定理 (定理 2.3) :

定理 6.2 (Mantel 定理). 令 $W:[0,1{]}^2\to [0,1]$ 是一个 graphon. 如果 $t\left(K_3,W\right)=0$, 则 $t\left(K_2,W\right)\le 1/2$.

定理 6.3 (Turán 定理). 让 $W:[0,1{]}^2\to [0,1]$ 是一个 graphon. 如果 $t\left(K_{r+1},W\right)=0$, 则 $t\left(K_2,W\right)\le 1-1/r$.

我们在本节的目标是确定 graphon $W$ 的所有可行的边密度、三角形密度构成的对的集合, 我们将其正式地写成: $$D_{2,3}=\left\{\left(t\left(K_2,W\right),t\left(K_3,W\right)\right):\text{ graphon }W\right\}\subseteq [0,1{]}^2$$

我们知道图序列的极限点是一个 graphon (定理 1.22 ) , 因此 $D_{2,3}$ 是闭集. 此外, Mantel 定理 (定理 6.2) 告诉我们, 当三角形密度为零时, 该区域的水平可行线最多延伸到点 $(\frac{1}{2},0)\in [0,1{]}^2$ (见图 ??).

(...)Mantel 定理在 $D_{2,3}$ 中的示意图

我们可以通过区域的横截面来描述 $D_{2,3}$. 下面的一个简单的结论表明 $D_{2,3}$ 的每个垂直截面都是一条 “竖直” 的线段:

命题 6.4. 对于所有的 $0\le r\le 1$, 集合 $D_{2,3}\cap \{r\}\times [0,1]$ 都是一条没有间隙的线段.

证明. 考虑两个具有相同边密度的 graphon $W_0,W_1$. 则我们有一个 graphon: $$W_t=(1-t)W_0+t{W}_1$$随着 $t$ 从 0 变化到 1 , 它的三角形密度是 $t$ 的连续映射. $t\left(K_3,W_t\right)$ 的初值和终值分别是 $t\left(K_3,W_0\right)$ 和 $r\left(K_3,W_1\right)$, 所以三角形密度可以取到对应区间里的所有值.

$\square$

为了更好地认识 $D_{2,3}$ , 我们想确定在给定边密度的情况下可以达到的最小子图和最大子图密度. 我们从解决下面这个问题开始:

问题 6.5. $n$ 顶点 $m$ 条边图中的最大三角形数是多少?

一个直观的想法是边应该排列成团的形式. 事实证明这是正确的. Kruskal-Katona 定理 ¹告诉我们一个带有 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ 条边的图最多有 $\left(\genfrac{}{}{0ex}{}{k}{3}\right)$ 个三角形. 在这里, 我们证明比这个上界稍弱的版本.

定理 6.6. 对于任意的 graphon $W:[0,1{]}^2\to [0,1]$, 有$$t\left(K_3,W\right)\le t{\left(K_2,W\right)}^{\frac{3}{2}}$$

笔记 6.7. 这个通过图 6.7 中所示的图来达到该上界, 它是 $G$ 中团的图极限, 其边密度和三角形的密度分别为, $$t\left(K_2,W\right)=a^2,t\left(K_3,W\right)=a^3$$(...) 达到 $D_{2,3}$ 上界的 Graphon: $t\left(K_2,W\right)=a^2$ , $t\left(K_3,W\right)=a^3$ (左上角为原点)

因此, $D_{3,2}$ 区域的上边界由曲线 $y=x^{3/2}$ 给出, 如图 6 所示. (...) $D_{2,3}$ 上边界, 曲线为 $y=x^{3/2}$

定理 6.6.

我们证明任意图 $G$ 中下面的不等式成立即可. $$t\left(K_3,G\right)\le t{\left(K_2,G\right)}^{3/2}$$回顾 hom$\left(K_3,G\right)$ 和 hom $\left(K_2,G\right)$, 他们分别表示图中长度为 3 和 2 的闭环的数量. 这些值对应于图 $G$ 频谱的二阶矩和三阶矩: $$\mathrm{hom}\left(K_3,G\right)=\sum _{i=1}^k{\lambda }_i^3\mathrm{hom}\left(K_2,G\right)=\sum _{i=1}^k{\lambda }_i^2$$其中 ${\left\{{\lambda }_i\right\}}_{i=1}^n$ 是邻接矩阵 $A_G$ 的特征值. $$\mathrm{hom}\left(K_3,G\right)=\sum _{i=1}^n{\lambda }_i^3\le {\left(\sum _{i=1}^n{\lambda }_i^2\right)}^{3/2}=\mathrm{hom}{\left(K_2,G\right)}^{3/2}$$其中不等号成立是因为对于 $t>1$, $a_1,\cdots ,a_n\ge 0$ 下述不等式成立 (这里我们取 $a_i={\lambda }_i^2$ , $t=3/2$) : $$a_1^t+\cdots +a_n^t\le {\left(a_1+\cdots +a_n\right)}^t$$两边除以 $|V(G){|}^3$ 后, 我们得到 $t\left(K_3,W\right)\le t{\left(K_2,W\right)}^{3/2}$.

$\square$

您可能想知道, 是否有一种方法可以在不使用图 $G$ 的特征值的情况下证明这个结论. 事实上我们有以下结论, 其证明不需要用到谱图理论:

定理 6.8.

对于任意对称的 $W:[0,1{]}^2\to \mathbb{R}$, $$t\left(K_3,W\right)\le t{\left(K_2,W^2\right)}^{3/2}$$其中 $W^2$ 是 $W$ 逐点平方后得到的 graphon.

注意, 当 $W$ 是一个 graphon 时, 所有点都在 0 和 1 之间, 因此 $W^2$ 是一个更 “小” 的 graphon (01 之间的小数平方后更小) . 因此, 上述定理比定理 6.6 更紧. 这个定理的证明是对 Cauchy-Schwarz 不等式的三次应用, 每一次对应于三角形 $K_3$ 的一条边.

证明. 我们知道$$t\left(K_3,W\right)={\int }_{[0,1{]}^3}W(x,y)W(x,z)W(y,z)dxdydz$$现在, 我们放弃积分区间的记号. 我们可以将 Cauchy-Schwarz 不等式应用于下面的积分. 首先是关于变量 $dx$, 然后是关于变量 $dy,dz$, 每次保持其他两个变量不变: $$\begin{array}{rl}t\left(K_3,W\right)& =\int W(x,y)W(x,z)W(y,z)dxdydz\\ & \le \int {\left(\int W(x,y{)}^{2}dx\right)}^{1/2}{\left(\int W(x,z{)}^{2}dx\right)}^{1/2}W(y,z)dydz\\ & \le \int {\left(\int W(x,y{)}^{2}dxdy\right)}^{1/2}{\left(\int W(x,z{)}^{2}dx\right)}^{1/2}{\left(\int W(y,z{)}^{2}dy\right)}^{1/2}dz\\ & \le {\left(\int W(x,y{)}^{2}dxdy\right)}^{1/2}{\left(\int W(x,z{)}^{2}dxdz\right)}^{1/2}{\left(\int W(y,z{)}^{2}dydz\right)}^{1/2}\\ & =\Vert W{\Vert }_2^3\\ & =t{\left(K_2,W^2\right)}^{3/2}\end{array}$$证毕.

$\square$

笔记 6.9. 如果我们没有 $W$ 对称的条件, 我们仍然可以使用 Hölder 不等式得到一个较弱的陈述. 在这种情况下, Hölder 不等式告诉我们$${\int }_{[0,1{]}^3}f(x,y)g(x,z)h(y,z)dxdydz\le \Vert f{\Vert }_3\Vert g{\Vert }_3\Vert h{\Vert }_3$$设置 $f=g=h=W$, 我们可以推导出一个比定理 6.8 更弱的上界, 因为一般来说, $\Vert W{\Vert }_2\le \Vert W{\Vert }_3$.

下一个定理我们将证明团密度之间的线性不等式.

定理 6.10 (Bollobás 1986). 取 $c_1,\cdots ,c_n\in \mathbb{R}$. 下面不等式对任意的图 $G$ $$\sum _{r=1}^n{c}_{r}t\left(K_r,G\right)\ge 0$$成立当且仅当它对所有的 $G=K_m$ ($m\ge 1$) 成立.

更明确地说, 不等式 ${\sum }_{r=1}^n{c}_r\cdot \frac{m(m-1)\cdots (m-r+1)}{m^r}\ge 0$ 对任意的图 $G$ 成立当且仅当$$\sum _{r=1}^n{c}_r\cdot \frac{m(m-1)\cdots (m-r+1)}{m^r}\ge 0$$对所有的 $m\ge 1$ 都成立.

证明. 命题的一个方向可以立刻得到, 因为团是图全集的子集.

我们现在证明另一个方向. 因为图全集在 ${\tilde{W}}_0$ (切割距离度量下) 中是稠密的. 所以该不等式对于所有图成立当且仅当它对所有的 graphon 成立. 现在我们考虑顶点加权简单图的集合 $\mathcal{S}$, 其中 $\sum a_i=1$.

[htbp] [width=0.3]proof-561.png figure 四顶点上的节点加权图示例, 其权重和为 1, 及其对应的 graphon.

每个节点加权图可以用一个 graphon 来表示. 注意到集合 $\mathcal{S}$ 在 ${\tilde{W}}_0$ 中是稠密的, 所以我们只需证明 $\mathcal{S}$ 中的图的满足这个不等式即可.

使用反证法, 假设存在节点加权简单图 $H$ 使得$$f(H):=\sum _{r=1}^n{c}_{r}t\left(K_r,H\right)<0$$在所有这些 $H$ 中, 我们选择一个节点数最小的图, 最小节点数记为 $m$ . 我们选择节点权重 $a_1,\cdots ,a_m$, 他们的总和等于 1 并且使 $f(H)$ 最小化. 因为我们的参数数量是有限的, 并且 $f$ 是紧集上的连续函数, 所以我们一定可以找到这样的 $H$.

显然, 我们有 $a_i>0$ . 否则我们删除该节点后 $f(H)<0$ 仍然成立, 矛盾.

此外, $H$ 是一个完全图; 否则存在 $i,j$ 满足 $ij\notin E(H)$. 注意, 团密度是关于节点权重的多项式; 这个多项式没有 $a_i^2$ 项, 因为 graphon 的集合 $\mathcal{S}$ 对应于简单图, 并且顶点 $i$ 不会与其自身相邻. 这个多项式也没有 $a_i{a}_j$ 项, 因为 $i$ 和 $j$ 并不相邻. 因此, $f(H)$ 在变量 $a_i$ 和 $a_j$ 中是多重线性的.

固定所有其他节点的权重并考虑将 $a_i,a_j$ 作为我们的多元线性函数 $f(H)$ 的变量, 我们假设该函数取 $a_i=0$ 或 $a_j=0$ 时得到最小值. 我们可以移动 $a_i$ 和 $a_j$ 同时保证两者之和 $a_i+a_j$ 不变. 这两权重之一将变为零, 此时 $f(H)$ 值变小了, 同时这也意味着节点数量减少. 这与 $H$ 中节点数量的最小相矛盾. 因此这种假设情况不会发生.

换句话说, $H$ 必须是一个完全图; 变量 $a_i$ 上的多项式 $f(H)$ 必须是对称的: $$f(H)=\sum _{r=1}^n{c}_{r}r!s_r$$其中每个 $s_r$ 是一个阶数为 $r$ 的基本对称多项式$$s_r=\sum _{i_1<\cdots <i_r}{a}_{i_1}\cdots a_{i_r}$$特别地, 通过使除 $a_1,a_2$ 之外的所有变量保持不变, 多项式 $f(H)$ 可以写为$$f(H)=A+B_1{a}_1+B_2{a}_2+C{a}_1{a}_2$$其中 $A,B_1,B_2,C$ 是常量. 根据对称性, 我们有 $B_1=B_2$. 另外, 由于 $\sum a_i=1$, 我们知道 $a_1+a_2$ 是常数, 所以$$f(H)=A^{\prime }+C{a}_1{a}_2$$如果 $C>0$, 则 $f$ 将在 $a_1=0$ 或 $a_2=0$ 时取最小, 因为 $H$ 中的节点数量最少所以这并不会发生. 如果 $C=0$ 那么 $a_1,a_2$ 的任何取值都将产生与 $f(H)$ 相同的最小值. 因此, 常数 $C$ 必须为负, 这意味着当 $a_1=a_2$ 时 $f(H)$ 最小. 所以所有的 $a_i$ 必须相等, $H$ 可以被看作是一个未加权的图.

换句话说, 如果不等式对于某个图 $H$ 不成立, 那么对于某个未加权的团 $H$, 它一定也不成立. 证毕.

$\square$

笔记 6.11. 在上面的证明中我们只考虑了团的密度, 不等式对于其他类型的图不一定成立.

有了上面的定理, 测试密度之间的线性不等式变得简单, 因为我们只需要验证它们对团是否成立. 我们有以下推论:

推论 6.12. 对于任意的 $n$, 凸包的极值点$$\left\{\left(t\left(K_2,W\right),t\left(K_3,W\right),\cdots ,t\left(K_n,W\right)\right):W\text{ graphon }\right\}\subset [0,1{]}^{n-1}$$由 $W=K_m$ ($m\ge 1$ ) 给出.

注意, 上述结论可以推出 Turán 定理, 因为定理 6.10 告诉我们, 凸包的极值点在 $W$ 为一个团时取到. 如果 $\left(K_{r+1},W\right)=0$, 则在较高维立方体 $[0,1{]}^r$ 中的横截面有上界 $t\left(K_2,W\right)=t\left(K_2,K_r\right)=1-\frac{1}{r}$. 特别的, 我们考虑凸包 $D_{2,3}\subset [0,1{]}^2$ 中的极值点, 它们为$$p_m=\left(\frac{m-1}{m},\frac{(m-1)(m-2)}{m^2}\right)$$所有这样形式的点都落在曲线 $y=x(2x-1)$ 上.

因为 $D_{2,3}$ 包含在红点 ${\left\{p_m\right\}}_{m\ge 0}$ 构成的凸包中, 红点落在 $y=x(2x-1)$ 上. 我们可以在凸包点之间连线, 从而得到一个多边形区域.

[htbp] [width=0.3]k2k3-point.png figure$D_{2,3}$ 的下界点, 均在曲线 $y=x(2x-1)$ 上

Razborov 最终确定了 $D_{2,3}$ 的模样, 他用数理逻辑中的模型论 (Model Theory) 开发了旗代数 (flag algebras) 理论, 这一理论给计算平方和不等式提供了一个有效的框架. 简单来说, 我们可大量、系统性地使用柯西-施瓦茨不等式来证明图密度不等式.

定理 6.13 (Razborov 2008). 对于属于以下区间的固定的边密度 $t\left(K_2,W\right)$ $$t\left(K_2,W\right)\in \left[1-\frac{1}{k-1},1-\frac{1}{k}\right],k\in \mathbb{N}$$可行的最小 $t\left(K_3,W\right)$ 是通过一个唯一确定的阶跃函数 graphon 得到的, 它对应于一个具有节点权重 $a_1,a_2,\cdots ,a_k$ 的图, 其中权重总和等于 1 并且 $a_1=\cdots =a_{k-1}\ge a_k$.

完整模样的 $D_{2,3}$ 见图 0. 为了更好的视觉效果, 我们放大了区域下界的凹形 (使凹型曲线变得更明显) .

[htbp] [width=0.3]k2k3-razborov.png figure $D_{2,3}\subset [0,1{]}^2$ 的完整模样

值得一提的是, 在 Turán 定理中, 极值对应的图的构造是唯一的; 然而, 在所有中间值 $t\left(t_2,W\right)\ne 1-1/k$ 中, 该定理为我们提供了非唯一的构造. graphon 的非唯一性意味最小化 $t\left(K_3,W\right)$ 在实际操作中会很困难. 在给定边密度的图中最小化 $K_r$ 密度的问题由 Nikiforov (2011) 和 Reiher (2016) 解决, 他们分别解决了 $r=4$ 和 $r$ 任意取值的情形.

更一般地, 考虑各种子图密度之间的不等式, 我们能否确定这种不等式是否适用于所有 graphon? 对于同态密度之间的多项式不等式, 只考虑线性密度就已经足够了, 因为 $t(H,W)t\left(H^{\prime },W\right)=$ $t\left(H\bigsqcup H^{\prime },W\right)$.

问题 6.14. 给定一个多元多项式 $p\in \mathbb{R}\left[x_1,x_2,\cdots ,x_n\right]$, 对于所有的 $x=\left(x_1,\cdots ,x_n\right)$, 是否有 $p(x)\ge 0$?

这个问题是可判定的, Tarski 已经告诉我们实数的所有一阶逻辑都是可判定的. 事实上, 非负实多项式有以下特征.

定理 6.15 (Artin). 多项式 $p\in \mathbb{R}\left[x_1,x_2,\cdots ,x_n\right]$ 是非负的当且仅当它可以写成有理函数的平方和.

然而, 当我们将目标转化为一组格点时, 情况发生了变化:

问题 6.16. 给定一个多元多项式 $p\in \mathbb{R}\left[x_1,x_2,\cdots ,x_n\right]$, 能否确定 $p\left(x_1,\cdots ,x_n\right)\ge 0$ 对所有 $x\in {\mathbb{Z}}^n$ 成立?

上述问题的答案是否定的. 它与下面的事实有关. 人们无法求解丢番图方程, 甚至无法判断是否有解:

定理 6.17 (Matiyasevich 2011; Hilbert’s ioth problem). 一个一般的丢番图方程的求解是一个不可判定的问题, 甚至仅确定其是否存在整数解也是不可判定的.

回到我们最初感兴趣的问题, 我们想知道以下问题是否可判定:

问题 6.18. 对于一组给定的图 ${\left\{H_i\right\}}_{i\in [k]}$ 和 $a_1,\cdots ,a_k\in \mathbb{R}$, 对于所有的图 $G$ 来说, ${\sum }_{i=1}^k{a}_{i}t\left(H_i,G\right)\ge 0$ 是否成立?

下面的定理给出了这个问题的答案:

定理 6.19 (Hatami - Norine 2011). 给定一组图 ${\left\{H_i\right\}}_{i\in [k]}$ 和 $a_1,\cdots ,a_k\in \mathbb{R}$ , 不等式$$\sum _{i=1}^k{a}_{i}t\left(H_i,G\right)\ge 0$$是否对于所有图 $G$ 都成立是不可判定的.

上述定理成立的一个粗略的直觉是, 我们实际上在 $D_{2,3}$ 的下界上有一组离散点, 然后我们可以将上述问题简化为证明红色曲线与区域的交点. 这个交点构成一个离散集合, 我们的思路是利用 $D_{2,3}$ 下界上的特殊点将整数不等式 (不可判定的) 编码为图不等式.

另一种有趣的问题是询问特定的不等式是否正确; 这种类型有几个尚未解决的问题. 下面是极值图论中的一个重要猜想:

命题 6.20 (Sidorenko’s Conjecture 1993). 如果 $H$ 是一个二部图, 则$$t(H,W)\ge t{\left(K_2,W\right)}^{e(H)}$$

我们在讨论伪随机性时遇到了上述不等式的一个 $H=C_4$ 的实例. 但是, 上述问题是开放的. 现在让我们考虑 Möebius 带状图——它从完整的二部图 $K_{5,5}$ 中删除一个长度为 10 的圈. 对于该图不等式是否成立是未知的.

即使一般线性图不等式的非负性是不可判定的, 如果人们想在 $\epsilon$ -误差之内钱确定它们是否为真, 问题就变得更容易解决:

定理 6.21. 存在一个算法, 对于任意 $\epsilon >0$, 该算法能够正确地作出选择: 是认为对于所有的图 $G$ $$\sum _{i=1}^n{c}_{i}t\left(H_i,G\right)\ge -\epsilon$$成立; 还是输出一个图 $G$, 满足$$\sum _{i=1}^n{c}_{i}t\left(H_i,G\right)<0$$

概要.

由于弱正则性引理, 我们可以采用弱 $\epsilon$ -正则划分. 所有关于边密度的信息都可以用这个划分来表示. 换句话说, 我们只需要在带有 $\le M(\epsilon )$ 部分的加权节点图上测试, 这些部分的边权重是 $\epsilon$ 的倍数. 如果对于从弱正则引理得到的辅助图对应的图密度加权总和的估计是正确的, 那么对于原始图也是正确的, 最多有 $\epsilon$ 的误差; 否则, 我们可以输出一个反例.

$\square$

1.	^ Kruskal-Katona 定理可以使用 “压缩” 的方法来证明: 我们反复将边 “推” 向团, 并说明在此过程中三角形的数量永远不会减少.