关于诺萨尔谱定理的更多内容：书籍与4-循环

《Journal of Combinatorial Theory, Series B》：More on Nosal's spectral theorem: Books and 4-cycles

　　李永涛|张圣通 摘要 光谱图论研究图的特征值与图的结构属性之间的关系。本文解决了光谱极值图论中的三个未解问题，这些问题推广了经典的Turán型过饱和结果。•我们证明了：对于任意满足谱半径λ(G)>m的m边图G，其中至少存在124m个共享一条边的三角形。这一结果证实了Nikiforov以及李和彭的猜想。此外，该上界在常数因子范围内是最优的。•对于满足λ(G)>(1?1/r)2m的m边图G，我们证明它必须包含Ωr(m)个共享r个公共顶点的Kr+1结构。这验证了李、刘和冯的猜想，并统一了一系列关于书籍图和团的光谱极值结果。此外，我们还证明了这样的图G还包含Ωr(mr?12)个Kr+1结构，这一结果扩展了宁和翟关于计数三角形的成果。•我们证明了：对于任意满足λ(G)>m的m边图G，其中至少存在(18?o(1))m2个4-圈，同时给出了两种构造方法，表明18这个常数已是最佳值。这一结果解决了宁和翟提出的一个问题，同时也给出了计算退化二分图的首个渐近式。我们证明的关键在于得到了两个与具有大谱半径的图的度数以及存在大型结构化子图相关的结果，我们认为这些结果本身也具有重要的研究价值。引言 我们研究极值图论中过饱和现象的光谱问题。由于光谱极值图论与其他众多领域的联系和应用，它在过去几十年里取得了飞速发展。在本文中，对于图G，我们用n和m分别表示其顶点数和边数。我们的出发点是Nosal[52]的一个经典结果（参见[42]），该结果表明：如果G是无三角图的，那么其谱半径满足λ(G)≤m。Nosal的定理强化了Mantel的基本结果（参见[4]），即如果G是无三角图，那么m≤?n2/4?，当且仅当G为Tn,2时等号成立，其中Tn,r是指顶点数为n的完全r部分图，各部分的规模尽可能均衡。实际上，利用瑞利公式，我们有2m/n≤λ(G)≤m，由此可得m≤?n2/4?=e(Tn,2)，同时λ(G)≤?n2/4?=λ(Tn,2)。为了纪念这一基础性成果，本文将满足λ(G)>m的m边图G称为Nosal图。在文献中，已有许多针对其他禁止子图F的Nosal定理的推广；关于团的情况可参见[42]、[6]、[36]、[59]，关于完全二分图可参见[2]、[47]，关于环可参见[10]、[29]、[28]、[60]，关于树可参见[9]、[20]，其他情况则可参见[11]、[57]、[45]、[34]、[30]。过饱和现象出现在极值组合数学的诸多问题中，指的是当超过极值阈值时，不仅会出现一个实例，还会出现大量禁止结构。例如，Rademacher（未发表，参见Erd?s [14]、[16]）指出，任意顶点数为n且边数至少为?n2/4?+1的图都至少包含?n/2?个三角形。这类问题吸引了大量研究兴趣；关于过饱和现象的最新进展可参见[39]、[40]、[41]、[53]、[25]、[38]。过饱和现象的光谱问题最早由Bollobás和Nikiforov在2007年提出。他们特别证明了三角形个数t(G)满足t(G)≥n212(λ(G)?n2)以及t(G)≥13λ(G)(λ2(G)?m)。第二个不等式后来被Cioab?、冯、Tait和张独立证明[11]。此外，宁和翟[51]指出，当且仅当G为完全二分图时等号成立。而且，宁和翟还证明了：如果G是具有m条边的Nosal图，那么t(G)≥?12(m?1)?，这一上界已是最优的。对于顶点数为n的图G，当λ(G)>λ(Tn,2)时，也研究了光谱过饱和问题；近期的相关进展可参见[51]、[55]、[30]、[31]。本文旨在研究Nosal图中的过饱和现象。大小为k的书籍图，记作Bk，是由k个共享一条边的三角形构成的图。对于图G，用bk(G)表示其所包含的最大书籍图的大小。Erd?s[15]证明了，任意顶点数为n且边数至少为?n2/4?+1的图都满足bk(G)=Θ(n)，并猜测bk(G)>n/6，这一猜测后来被Edwards（未发表，参见[17]，引理4）以及Khad?iivanov和Nikiforov[26]独立证明。Bollobás和Nikiforov[5]以及李、冯和彭[30，第4.3节]还提供了两种不同的证明方法。关于书籍图的问题也引起了广泛关注；相关文献可参见[22]、[12]、[13]、[55]及其中的参考文献。最近，翟、林和舒[56]证明了：如果G是具有m条边的Nosal图，那么G必然包含一个R2,r结构，其中r>14m。需要注意的是，Br是指多出一条边的K2,r结构。翟、林和舒[56]猜测G还包含一个大型书籍图。这一猜测后来被Nikiforov[48]证实，他证明了所有m边Nosal图都满足bk(G)>112m4。在同一篇论文中，Nikiforov指出：“bk(G)的上界似乎远非最优，因为乘法常数以及1/4这个指数都有可能得到改进。”支持Nikiforov的推测，李和彭[35]猜测该指数可以改进为1/2。猜想1.1 Nikiforov[48]、李–彭[35] 对于每一个具有m条边的Nosal图G，都有bk(G)=Ω(m)。我们的第一个结果证实了这一猜想，并表明m这个阶数已是最佳值。定理1.2 如果G是具有m条边的Nosal图，那么bk(G)>124m。此外，存在一些具有m条边的Nosal图，其中不存在大小超过(13+o(1))m的书籍图。1941年，Turán[4]扩展了Mantel的定理，指出：如果G是顶点数为n且不含Kr+1结构的图，那么e(G)≤(1?1r)n22，当且仅当r能整除n且G为Tn,r时等号成立。1986年，Wilf[54]证明了其光谱版本，即如果G是顶点数为n且不含Kr+1结构的图，那么λ(G)≤(1?1r)n，当且仅当r能整除n且G为Tn,r时等号成立。2002年，Nikiforov[42]进一步扩展了这一结论，指出如果G是具有m条边且不含Kr+1结构的图，那么λ2(G)≤(1?1r)2m，而这些极值图后来在[43]中被明确描述：当r=2时，它们为完全二分图；当r≥3时，它们为规则的完全r部分图。广义书籍图Br,k=Kr∨Ik是指将团Kr的每个顶点与大小为k的独立集Ik的每个顶点相连而得到的图。自然而然地，人们会思考猜想1.1是否可以扩展到广义书籍图上。这一问题在[33]的猜想1.20中被提出。猜想1.3 李–刘–冯[33] 设r≥2，k≥1为固定值，m足够大。如果G是具有m条边且不含Br,k结构的图，那么λ2(G)≤(1?1r)2m。猜想1.3为三角形、书籍图和团的光谱极值结果提供了统一的扩展形式。我们的下一个结果从强意义上解决了猜想1.3，确定了在具有大谱半径的图中最大广义书籍图的正确阶数。定理1.4 对于每一个满足λ2(G)>(1?1r)2m的m边图G，其中都存在大小为k=Ωr(m)的Br,k结构。此外，还存在一些图，其最大的广义书籍图大小为Or(m)。作为定理1.4的应用，我们可以很容易地得出：如果G是顶点数为n的图，且满足以下条件之一：要么边数m>(1?1r)n22，要么λ(G)>(1?1r)n，那么G就包含一个大小为k=Ωr(n)的Br,k结构。这可以视为对翟和林[55]结果的扩展，他们在该研究中证明了：如果λ(G)>λ(Tn,2)，那么G就包含一个大小为k=Ω(n)的书籍图B2,k。现在我们将注意力转向二分图中的过饱和结果。需要注意的是，星形图K1,m满足λ(K1,m)=m，且不包含任何4-圈。Nikiforov[44]的一个结果指出：如果G是具有m≥10条边的Nosal图，那么G就包含一个4-圈；相关文献可参见[56]、[58]。最近，宁和翟[50]证明了相应的过饱和结果，他们指出：如果G是具有m≥3.6×109条边的Nosal图，那么G至少包含m2/2000个C4结构。设f(m)=min?{#C4?in?G:e(G)=m?and?λ(G)>m}，表示每个m边Nosal图中必然存在的C4结构数量。宁和翟[50]的结果可以表示为f(m)>m2/2000。宁和翟提出了以下问题。问题1.5 宁–翟[50] 确定极限limm→∞?f(m)m2。我们需要指出，通过类似[50]中的论证，该常数1/2000是有可能被改进的。不过，似乎很难使用宁和翟的方法精确确定这一极限。我们采用了不同的方法来解决这个问题。定理1.6 每个具有m条边的Nosal图都至少包含(18?o(1))m2个C4结构。此外，18这个常数已是最优的。换言之，我们有limm→∞?f(m)m2=18。证明定理1.6的关键在于我们为Nosal图得到的两个结构结果，我们认为这些结果本身具有重要的研究价值，也可能有进一步的应用。第一个结果限定了Nosal图的最大度数。定理1.7 如果G是具有m条边的Nosal图，那么当m足够大时，Δ(G)≤m2+m0.99。证明定理1.7的一个难点在于K1,m的谱半径恰好等于m，因此需要证明对K1,m进行微调只会使其谱半径降低。另一个难点在于存在两种外观差异极大的图（见例4.1、例4.2），它们在较低阶项上都是极值图。我们需要指出，虽然m0.99这个数值远非最优，但对我们而言已经足够。第二个结果是关于Nosal图的结构二分性，它指出任何Nosal图都存在一个较大的子图，该子图要么是二分图，要么其最大度数为o(m)。例如，在例4.1中，团图的最大度数为o(m)，而例4.2中的图可以通过删除一条边变成二分图。定理1.8 对于任意ε>0，都存在一个常数N(ε)，使得以下条件成立：如果G是具有m条边的Nosal图，那么G存在一个子图G′，满足λ(G′)>(1?ε)m?N(ε)，并且G′满足以下条件之一：(a)G′是二分图；(b)G′的最大度数至多为εm。我们想要指出，Nosal图与顶点数大于n2/4的n顶点图之间存在有趣的类比。在我们的框架下，一个新的研究方向是寻找某些图参数在e(G)从?n2/4?变为?n2/4?+1时会出现相变/跃变的规律，并将这些规律扩展到Nosal图上。一些已知的例子包括：(i) 三角形个数从0跃变为Ω(n)，参见[14]、[16]；(ii) 书籍图大小从0跃变为Ω(n)，参见[26]、[5]、[30]；(iii) 三角边个数从0跃变为Ω(n)，参见[17]；(iv) 最大弦图的大小从0跃变为Ω(n)，参见[18]；(v) C4+结构的个数从0跃变为Ω(n2)，参见[41]；(vi) 能够使图达到K4饱和状态的边数从0跃变为Ω(n2)，参见[3]。作为我们结果的推论，我们得到了这些参数在Nosal图中的光谱类比现象。详细的讨论内容将在第5节中给出。最后，我们需要指出，在边谱条件λ(G)>m的前提下得到的Nosal图结果，实际上是密度条件e(G)>?n2/4?和顶点谱条件λ(G)>?n2/4?的推广。实际上，如前所述，根据瑞利公式，满足后两个条件之一的图必然属于Nosal图。更重要的是，顶点谱条件下的结果仅适用于那些边数呈二次增长的密集图，而边谱条件下的扩展则可适用于所有密度的图（例如例4.1、例4.2中的稀疏图）。如果能得到更多极值结果的边谱扩展，那将是非常有趣的；关于联合图的一个此类例子可见定理3.2，相关推论可见定理3.3。我们的研究方法。对于定理1.2，我们首先证明了Edwards–Khad?iivanov–Nikiforov关于密集图中大型书籍图出现的结果的加权版本（引理2.6）。实现这一目标的主要工具是一种新的随机放大论证方法。随后，我们对Nosal图G引入了权重机制，按照Perron–Frobenius特征向量x为图中的顶点赋值。而为边赋值则更为复杂。如果我们给G的边赋予自然的均匀权重，那么根据谱半径条件，这样的加权图G将是密集图，因此我们可以找到一个较大的加权书籍图。然而，由于无法控制x的?∞-范数，我们无法将这个加权书籍图还原为G中的实际（未加权）书籍图。我们证明的关键步骤是精心设计一组边权重来规避这一问题。为证明更一般的定理1.4，我们首先扩展定理1.2中的论证，找出一个大的联合结构（定理3.2），即由共享一条边的团组成的集合。然后，利用Kruskal–Katona定理从该大联合结构中得到所需的大规模广义书结构。对于定理1.6，由于图G的特征值的四阶矩可以统计图G中4步路径的数量，因此可以通过结合谱信息和度信息来估算图G中4环的数量（引理4.3）。遗憾的是，仅凭这一估算还不足以保证Nosal图中至少存在一个C4结构（见式(3)）。这时，两个结构性结果（定理1.7、定理1.8）就派上了用场。我们转而用定理1.8对大子图G′中的C4数量下界进行限制。如果G′是二分图，那么特征值的四阶矩以及度序列的?2范数都能得到2倍的改善，进而可得出所需的C4数量。若G′的最大度为o(m)，则度序列的?2范数可以被限制在o(m2)范围内，这也足以完成证明。

结构安排：我们在第2节证明定理1.2，第3节则将我们的方法扩展用于证明定理1.4。定理1.6和定理1.8的证明分别在第4节给出。第5节介绍了我们的结果在Nosal图相变研究中的某些应用，第6节则总结了与谱图相关的一些问题。

符号说明：本文中的所有图都是简单无向图。其中，G表示顶点集为V、边集为E的图。除非另有说明，n表示G的顶点数，m表示G的边数。顶点i∈V的度记为di，G的最大度记为Δ(G)。顶点i∈V的邻居集合记为N(i)。图G的邻接矩阵A(G)是一个V×V矩阵，当且仅当{i,j}∈E(G)时ai,j=aj,i=1，否则ai,j=aj,i=0。由于A(G)是实对称矩阵，其所有特征值均为实数，且可按λ1≥λ2≥?≥λn的顺序排列。设λ(G)为G的最大特征值，即G的谱半径。根据Perron–Frobenius定理，对任意i∈[n]都有λ(G)≥|λi|，并且存在一个与非负单位特征向量x=(xi)i∈V对应于λ(G)（称为Perron–Frobenius特征向量）。特别地，对于每个i∈V，有λ(G)xi=∑j=1nai,jxj=∑j∈N(i)xj。后续文中，我们将用∑{i,j}∈E表示对E中每条边求和一次。

定理1.2的证明：我们首先给出三种不同的构造方法，以证明定理1.2中所说的量级m已是最优值。不失一般性，假设m是一个完全平方数。

示例2.1：设s=m+1，t=m?(s2)≈m/2。我们选择H为任意具有t条边的无三角形图。定义Ks°H为通过将Ks和H的一个顶点重合得到的图。可以看出，λ(Ks°H)>λ(Ks)=m，且该图的“书大小”bk(Ks°H)=m?1。

示例2.2：我们定义H=Ks,t+为在完全二分图Ks,t的基础上添加一条边得到的图。

定理1.4的证明：r-联合结构是指由共享一条边的r个团组成的族。设jsr(G)表示G的某个r-联合结构中r团的最大数量。例如，js3(G)=bk(G)。Erd?s [19]的研究表明，一个具有超过e(Tn,r)条边的n顶点图G，不仅包含一个Kr+1结构，还包含一个大的(r+1)-联合结构，即Ωr(nr?1)个共享一条边的Kr+1结构。

引理3.1：参见[19]、[7]。如果G是一个具有n个顶点且边数e(G)>(1?1r)n2/2的图，那么jsr+1(G)=Ωr(nr?1)。更准确地说，Erd?s [19]证明了jsr+1(G)≥nr?1/(10r)^{6r}。Bollobás等人也……

定理1.6 – 1.8的证明：在本节中，用#C4表示Nosal图G中C4结构的数量。对于顶点集A，用G[A]表示其诱导子图，E[A]表示该子图的边集。类似地，对于不相交的顶点集A和B，用G[A,B]表示它们所构成的诱导二分子图，E[A,B]表示该子图的边集。

为证明定理1.6，我们首先给出两种构造方法，以此证明上界f(m)≤(18+o(1))m2。

示例4.1：设s=?m?+1，t=m?(s2)。设G=Ks°K1,t为在完全图基础上通过某种操作得到的图。

应用部分：在本节中，我们将介绍我们主要结果的一些推论。重点探讨Nosal图中若干图参数相变的谱学类比。其中一些结果在我们之前就已经被知晓。例如，Ning和Zhai [51]、[50]的最新研究表明，每个Nosal图都包含Ω(m)个三角形以及Ω(m2)个C4结构。2021年，Zhai、Lin和Shu [56]证明了每个Nosal图都包含一个大型完全二分子图K2,t，其中t=Ω(m)。定理1.2实际上重现了这些结论。

总结与展望：我们在定理1.2中已经证明，对于每一个具有m条边的Nosal图G，都有bk(G)>124m。不过示例2.3表明，也存在某些Nosal图使得bk(G)≤(13+o(1))m。确定这个合适的常数数值会很有意义。

问题6.1：是否每一个具有m条边的Nosal图都包含大小为13m的“书”结构？需要提醒的是，Edward定理指出，当m>n2/4时，有bk(G)>n/6。此处我们想指出，如果问题6.1成立，那么它实际上可以推出Edward定理，因为谱条件λ(G)>m比边条件m>n2/……更为宽松。

致谢：作者们要感谢匿名审稿人对本工作的深刻评论与建议。尤其要感谢其中一位审稿人，他提出了对定理1.2中常数值进行大幅改进的建议。我们还要感谢Yuval Wigderson让我们了解到[19]这篇文献，同时也要感谢Ting-Wei Chao、Fei Peng和Zhuo Wu进行的宝贵讨论。这项工作最初是在2023年秋季的第一届IBS ECOPRO学生研究项目中启动的。第一作者和第三作者将……