稀疏图通常能由其谱唯一确定吗？

《European Journal of Combinatorics》：Are sparse graphs typically determined by their spectrum?

　　

研究人员探究稀疏图是否典型地能由其邻接谱（adjacency spectrum）在同构意义下唯一刻画。作为主要结果的铺垫，研究人员首先证明：当平均度（average degree）足够小时，Erd?s–Rényi图的巨分量（giant component）是共谱的（cospectral）。该证明依赖于一个特定悬垂树（pendant tree）的存在性，并结合Schwenk的树交换方法构造共谱配对图（cospectral mate）。悬垂树可能本质上是唯一的障碍，这意味着若通过考虑2-核心（2-core）剪除这些悬垂树，巨分量应以高概率变得由谱刻画。论文的大部分内容致力于支持这一构想的理论与数值证据。研究人员在该方向上的主要定理确立了局部切换方法（local switching methods）无法导致2-核心共谱。研究人员还讨论了广义共谱性（generalized cospectrality）。

谱图理论（spectral graph theory）中的一个基本问题是邻接矩阵（adjacency matrix）的特征值（eigenvalues）是否在同构意义下刻画给定图。这对于某些特殊图类（如环或完全图的不相交并）是已知的。反之，也存在谱相同但不同构的图的例子，称为共谱配对图（cospectral mates）。人们可能想知道这类例子是典型的还是例外的。Schwenk于1973年的一个引人注目的结果确立：几乎所有树都容许一个共谱配对图，从而表明共谱性对树而言是典型的。这自然引出了对一般图可能成立什么的问题，而该问题最终被证明是一个具有挑战性的问题。很长一段时间内，甚至答案的预期方向都不清楚。例如，Godsil在其1993年的书中写道："几乎所有图是否由其特征多项式（characteristic polynomial）刻画仍是一个开放问题。甚至不清楚我们应该试图证明还是证伪这一点。"关于答案方向的证据来自Haemers和Spence对n≤11个顶点的图的穷举搜索，该搜索表明大部分共谱图源自一种特定的共谱图局部构造，称为Godsil–McKay切换（Godsil–McKay switching）。可以证明该特定构造只产生渐近可忽略比例的图，导致人们相信Schwenk结果的反面可能发生。Haemers猜想断言几乎所有图由其谱刻画。证明仍然难以获得，但Wang和Wang最近通过蒙特卡洛采样（Monte Carlo sampling）发现了进一步证据，估计在50个顶点的图中至少99%在同时给出补图（complement graph）的谱时是被刻画的。用概率语言来说，Haemers猜想意味着来自G(n,p)模型、边概率p=1/2的Erd?s–Rényi图以当n→∞时趋于一的概率由其谱刻画。这样的图相当稠密，因为平均度与n成线性关系。因此，Haemers猜想可以解释为：稠密图通常由其谱刻画。本文旨在确定稀疏情形下什么是典型的，研究人员通过考虑p=λ/n情形下的巨分量来做到这一点，其中参数1<λ?n决定平均度。回想巨分量定义为最大分量，并且著名地是当λ>1时以高概率包含线性比例顶点的唯一分量。作为主要分析的序幕，研究人员在定理1.1中证明：若平均度λ足够小，则巨分量是共谱的。这也意味着对于小λ，整个图是共谱的，因为只要一个非连通图的任一分量是共谱的，该图就是共谱的。巨分量共谱性的证明依赖于特定悬垂树作为谱刻画的障碍。本文的大部分内容随后研究无悬垂树的稀疏图的典型性质，研究人员通过考虑巨分量的2-核心来做到这一点。研究人员的主要结果是定理1.7，表明所有可能的局部切换方法在2-核心上都失效。特别地，这排除了有界大小的Godsil–McKay切换，但该断言远比仅排除该特定方法更为一般。定理1.7的证明方法是新的且具有独立意义。研究人员在第1.3节中讨论了由此产生的猜想（即2-核心应由其谱刻画）的额外理论证据。（数值证据在第4节中给出。）论文其余部分在第1.4节中概述。1.1. 巨分量是共谱的。回想两个不同构的图若具有相同的邻接谱则称为共谱的。两个共谱图若其补图也共谱则称为R-共谱的（R-cospectral）。这一推广可追溯到Johnson和Newman 1980年的工作，该工作确立了各种等价表述。除了其独立意义外，与本文的相关性在于这一概念将使数值研究成为可能。定理1.1考虑G(n,p)随机图，其中p=λ/n，参数λ=λn>1在n→∞时保持有界远离一。进一步考虑任意序列h(n)满足h(n)→∞。则：1. 若λ≤ln(n)/8+ln(ln(n))?h(n)，最大分量Cgiant以趋于一的概率容许一个共谱配对图。2. 若λ≤ln(n)/10+ln(ln(n))?h(n)，最大分量Cgiant以趋于一的概率容许一个R-共谱配对图。证明在第2节中给出。其思路可视化于图1，如下所述。Schwenk已知存在9个节点上的有根树（rooted trees）T1,T2，使得对任意图G，通过在某个顶点处将T1连接到G上得到的图与改为在该顶点处连接T2得到的图是共谱的。因此，任何具有T1悬垂副本的图都有一个共谱配对图。定理1.1证明的主要内容是确定在什么λ范围内巨分量中存在T1的悬垂副本，这正是(1.1)中界的来源。条件(1.2)类似地通过使用11个节点上产生R-共谱性的树（由Godsil和McKay给出）得到。交换悬垂树也可用于推导共谱配对图数量的下界。以下结果通过表明当平均度固定时存在指数多个共谱配对图来说明这一原理：命题1.2对每个固定的λ>1，存在c>0使得Cgiant以趋于一的概率具有至少exp(cn)个不同构的R-共谱配对图。这里及所有后续结果中应理解为研究人员使用与定理1.1相同的记号。即Cgiant指G(n,p)图（p=λ/n）中的最大分量。命题1.2证明中需要小心处理的主要点是图的自同构（automorphisms）可能导致悬垂树的不同交换给出同构的图。然而这最终无关紧要，因为具有非平凡轨道的顶点数可以使用Verbitsky和Zhukovskii的结果来控制。细节见第2节。1.2. 悬垂树是唯一的障碍吗？定理1.1和命题1.2表明稀疏图通常因包含悬垂树而是共谱的。研究人员希望提出这可能是该情形下共谱性的唯一原因。一种精确表述方式是考虑2-核心，记为Core2(Cgiant)，即通过移除所有悬垂树得到的图。更一般地，k≥2的k-核心是通过迭代移除所有度1在n→∞时保持有界远离一。固定整数m≥1并假设λ=o(n1/(2m+2))。则以趋于一的概率，从巨分量的2-核心通过大小至多m的切换可得到的每个图H都与它同构。即limn→∞P(Core2(Cgiant)容许一个大小≤m的切换产生不同构的图)=0。定理1.7的证明是本文的主要技术新颖之处，在第3节中给出。研究人员利用这样一个事实：在最小度为2的连通图中，切换只有在存在一些小环（small cycles）时才能被应用。2-核心没有很多这样的小环，但仍可能出现少数几个。因此先验地切换可能是可应用的。证明的主体考虑具有不相交环的情形。研究人员表明这种情况下切换的结果将与原图同构；见图2。假设λ=o(n1/(2m+2))在此用于排除两个环的碰撞。为证明若切换不作用于连通环则结果图为同构图，研究人员利用切换方法也在某些子图上诱导共谱配对。研究人员利用环由谱确定以及其子图的共谱性已被理解来表明诱导的共谱子图必须同构。主要困难出现在证明这些诱导子图的同构也扩展到整个2-核心的同构；见引理3.10的证明。这一新证明策略对其他图类（而非具有最小度2的稀疏连通图）也有潜力。具体而言，该策略的好处是只需理解可能作为小子图出现的特殊图类的共谱性质，如研究人员在第3.2.1节中所做。然后可以利用这一理解来为切换方法构建全局同构。一个潜在瓶颈是理解即使特殊图类的共谱性质也可能非平凡。一些此类性质相对已被充分理解的图类包括完全图、完全二部图（complete bipartite graphs）和谱半径（spectral radius）至多为2的图。图2. 巨分量的2-核心以非零概率包含少数小环。切换方法可能作用于这样的环，但研究人员在第3节定理1.7的证明中表明以这种方式不可能获得不同构的图。1.3. 进一步的理论证据和开放问题。鉴于Haemers猜想是特殊情况，猜想1.3的证明目前似乎难以企及。然而，通过研究其他松弛可能获得对稀疏情形的更多洞察。例如，能否证明对2-核心的任何只改变有界数量边的修改不会产生不同构的共谱图？这不由定理1.7蕴含。（例如，因为切换必须用共谱图替换被修改的子图。）概念上的区别大致是切换只允许保证共谱的修改，意味着共谱性的原因也必须是局部的，而任意边修改可能通过全局巧合也是共谱的。经典共谱性的另一种松弛通过要求正交矩阵具有有理数（rational）元素来产生。若存在具有有理元素的正交矩阵Q使得AH=QTAGQ，则两个图G,H通过有理矩阵共谱。满足?Q∈Zn×n的最小整数?≥1称为Q的层级（level）。有理概念与第1.1节中的R-共谱性相关。事实上，已知对于可控图（controllable graphs），R-共谱性等价于存在有理正交矩阵Q使得AG=QTAGQ且Qe=e，其中e=(1,…,1)T是全一向量（由Wang和Xu给出），而来自G(n,p)模型p=1/2的稠密Erd?s–Rényi图已知是可控的（由O'Rourke和Touri给出）。Wang和Zhao最近证明在固定边概率p∈(0,1)的稠密情形中，固定层级?的共谱性不以高概率发生。事实上，检查[29]中的证明表明它们也扩展到平均度为对数的更稀疏情形：定理1.8 Wang和Zhao。对每个固定的?≥2，存在常数C>0使得以下对p=λ/n的Erd?s–Rényi随机图成立，若Cln(n)≤λ≤n/2：(1.5)limn→∞P(G(n,p)通过层级?的有理矩阵共谱)=0。证明。[29, Eq. (28)]中表明G(n,p)图具有层级?′（?′∣?）的共谱配对图的概率对所有大n至多为εn2/(1?εn)，其中εn≤nc1p?c2n，c1,c2>0为依赖于?的常数，p??max{p,1?p}。利用p?=1?λ/n现在通过取下界Cln(n)≤λ中的常数C足够大确保εn→0。□条件?≥2是必要的，以排除?=1时出现的Q为置换矩阵的平凡情形。因此定理1.8表明若平均度足够大则不可能有具有小分母的非平凡有理共谱性，从而为猜想1.3提供证据。事实上，若平均度为带大常数的对数，则巨分量及其2-核心都与整个图重合。这补充了定理1.7中考虑的λ足够小的情形。进一步回想定理1.1在平均度为带显式常数的对数时产生巨分量的共谱性。与定理1.8结合，这表明对数平均度是图从几乎总是共谱过渡到几乎从不共谱的临界稀疏尺度。人们不禁想知道当平均度分别超过(1.1)或(1.2)中的值时，巨分量的共谱性或R-共谱性是否会出现急剧相变（sharp phase transition）。如果能找到证据澄清那里出现的常数是否应是尖锐的，将是有趣的未来工作。1.4. 概要。定理1.1和命题1.2的证明在第2节中给出。定理1.7的证明在第3节中给出。研究人员最后在第4节中使用Wang和Wang的算法（附加一些优化以支持更大的图）考虑猜想1.3的R-共谱性变体的数值证据。2. 巨分量是共谱的——定理1.1和命题1.2的证明。回想例1.6，对有根图H,K，研究人员用H?K表示通过合并图并识别根得到的图。形如G?H?T（T为某有根树）的图称为具有T的悬垂副本。（另回想图1。）本节的主要内容是确定在什么λ范围内巨分量中存在t个顶点的树T的悬垂副本。然后利用[15],[22]中的树得到所需的共谱性结果。研究人员使用二阶矩计算（second moment calculation）。将T的顶点与{1,…,t}等同使得顶点t为根。进一步，给定顶点v1,…,vt∈{1,…,n}，令T(v1,…,vt)表示原图可分解为G(n,p)=H?T且T的顶点1,…,t分别映射到v1,…,vt的事件。研究人员计数巨分量中T的悬垂副本：(2.1)N?∑v1∈{1,…,n}∑v2≠v1?∑vt?{v1,…,vt?1}1{T(v1,…,vt)且vt∈Cgiant}。研究人员在以下引理2.1、引理2.4中分别确定E[N]和E[N2]。引理2.1固定t≥2个顶点的有根树T。假设λ>1保持有界远离一且p=λ/n在n→∞时趋于零。则令cλ?E[#Cgiant/n]及N如(2.1)，有(2.2)E[N]=(1?o(1))ntcλpt?1(1?p)(t?1)n。特别地，E[N]→∞当且仅当存在序列h(n)满足h(n)→∞使得(2.3)1<λ≤ln(n)/(t?1)+ln(ln(n))?h(n)。证明。事件T(v1,…,vt)意味着vi～vj当且仅当{i,j}∈T，且从i≤t?1的vi到外部顶点v?{v1,…,vt}没有边。这里树T恰有t?1条边和(t2)?(t?1)个非边。进一步，从i≤t?1的vi到{v1,…,vt}的补集恰有(n?t)(t?1)条潜在边。因此，利用G(n,p)模型中边独立，(2.4)P(T(v1,…,vt))=pt?1(1?p)(t?1)(n?t)+(t2)?(t?1)=(1?o(1))pt?1(1?p)(t?1)n，其中第二步使用了1?p=1?o(1)。条件于T(v1,…,vt)，由{1,…,n}?{v1,…,vt?1}诱导的图仍是参数为p的Erd?s–Rényi图。因此，由于λ>1保持有界远离一，后者以高概率再次具有唯一巨分量，包含(1?o(1))cλn个节点且cλ=E[#Cgiant/n]有界远离零。特别地，vt属于该分量的概率为(2.5)P(vt∈Cgiant∣T(v1,…,vt))=(1?o(1))cλ。利用(2.1)中有n(n?1)?(n?t+1)=(1?o(1))nt个求和项，现在得到(2.2)。(2.3)是确保E[N]→∞的充要条件现在通过直接计算得出。注意对λ≤n有(1?λ2/n)exp(?λ)≤(1?λ/n)n≤exp(?λ)。上界意味着若λ=ω(ln(n))则(2.3)右端趋于零。进一步可得若λ=o(n)则(1?λ/n)(t?1)n=(1?o(1))exp(?λ(t?1))。因此，利用ntpt?1=nλt?1表明若λ=o(ln(n))则(2.2)以n1?o(1)的速率趋于无穷，而若λ=Θ(ln(n))且λ=ln(n)/(t?1)+ln(ln(n))?h(n)则具有exp((t?1)h(n))的阶。□注2.2若(2.3)中h(n)替换为常数，则引理2.1表明E[N]为常数阶，更复杂的证明将表明N具有泊松统计（Poissonian statistics）。特别地，此时N以非零概率为零。因此推论2.5中λ的界是确保limn→∞P(N>0)=1所必需的。二阶矩计算的其余部分将表明它也是充分的。引理2.3固定t≥2个顶点的有根树T。考虑至少2t个顶点的连通图G。则G中每对有共享顶点的T的悬垂副本必须共享根。证明。假设给定顶点集{v1,…,vt}∩{w1,…,wt}≠?使得{v1,…,vt}和{w1,…,wt}都在G中产生根分别为vt和wt的T的悬垂副本。断言是必有vt=wt。反设vt≠wt。G连通且至少2t>t个顶点意味着{v1,…,vt}∩{w1,…,wt}至少有一条边通向其补集。假设有这样一条边通向{v1,…,vt}的补集，另一情形类似。则由于悬垂树的定义给出vt是{v1,…,vt}中唯一可连接到外部顶点的顶点，研究人员有vt∈{w1,…,wt}，且由于vt≠wt甚至有vt∈{w1,…,wt?1}。现在考虑邻域：(2.6)N0?{vt}, Ni+1?Ni∪{v∈{v1,…,vt}:?v′∈Ni,v～v′}。则利用wt是{w1,…,wt}中唯一具有外部邻居的顶点，有(2.7)Ni?{w1,…,wt?1}?Ni+1?{w1,…,wt}。注意N0={vt}?{w1,…,wt?1}，但由于T的连通性意味着对大i有Ni={v1,…,vt}基数为t，不可能对所有i都有Ni?{w1,…,wt?1}。因此(2.7)意味着存在i使wt∈Ni。定义(2.6)给出Ni?{v1,…,vt}。这意味着wt∈{v1,…,vt}，且由于vt≠wt故wt∈{v1,…,vt?1}。现在同样利用vt∈{w1,…,wt?1}，可得从{v1,…,vt}∪{w1,…,wt}到其补集没有边。这与G连通且至少2t个顶点的假设矛盾，因为#{v1,…,vt}∪{w1,…,wt}=2t?#{v1,…,vt}∩{w1,…,wt}<2t。研究人员得出结论vt=wt。□引理2.4固定t≥2个顶点的有根树T。假设λ>1保持有界远离一且存在序列h(n)满足h(n)→∞使得(2.3)成立。则(2.8)E[N2]=(1?o(1))E[N]2。证明。类似于(2.4)–(2.5)可得对每对满足{v1,…,vt}∩{w1,…,wt}=?的顶点集，令cλ=E[#Cgiant/n]，有(2.9)P(T(v1,…,vt),T(w1,…,wt),vt∈Cgiant,wt∈Cgiant)=(1?o(1))(cλpt?1(1?p)(t?1)n)2。将定义(2.1)的N代入E[N2]所得的双重求和有(1?o(1))n2t个由满足{v1,…,vt}∩{w1,…,wt}=?的顶点集索引的项。因此，形如(1?o(1))(ntcλpt?1(1?p)(t?1)n)2=(1?o(1))E[N]2的贡献来自这些项。 consequently，(2.10)E[N2]=(1?o(1))E[N]2+∑{v1,…,vt}∩{w1,…,wt}≠?P(T(v1,…,vt),T(w1,…,wt),vt∈Cgiant,wt∈Cgiant)。只需界定(2.10)右端的和。引理2.3确保(2.10)中所有vt≠wt的项为零。进一步，对每个i≤t?1，有O(n2t?i?1)个满足vt=wt且#{v1,…,vt?1}∩{w1,…,wt?1}=i的项。T(v1,…,vt)和T(w1,…,wt)同时发生的唯一可能是{v1,…,vt}∪{w1,…,wt}诱导2t?i?1个顶点上的树且根vt=wt，且除vt=wt外所有顶点没有外部连接。因此类似于(2.4)–(2.5)可得(2.10)中每个这样的项的量级为O(p2t?i?2(1?p)(2t?i?2)n)。因此，利用n2t?i?1p2t?i?2=nλ2t?i?2和(1?p)(2t?i?2)n=O(exp(?λ(2t?i?2)))，(2.11)E[N2]=(1+o(1))E[N]2+O(∑i≤t?1nλ2t?i?2exp(?λ(2t?i?2)))。由(2.2)及(2.5)后的讨论，研究人员有E[N]=(1?o(1))ncλλt?1exp(?λ(t?1))。这里cλ>0由λ保持有界远离一的假设保持有界远离零。由此可得nλ2t?i?2exp(?λ(2t?i?2))/E[N]2=O(n?1λ?iexp(iλ))。若λ=o(ln(n))则当然n?1λ?iexp(iλ)→0，研究人员可得出结论(2.11)中所有项为o(1)E[N]2阶。现在假设λ=Θ(ln(n))。通过修改序列h，研究人员可进一步假设(2.3)中取等号。则(2.12)nλ2t?i?2exp(?λ(2t?i?2))/E[N]2=O(exp(iλ)/nλi)=O(exp(i?(t?1)/(t?1)ln(n)?ih(n)))。注意对i≤t?1有exp[(i?(t?1))ln(n)/(t?1)]=O(1)，并回想h(n)→∞以得出结论(2.11)中所有项为o(1)E[N]2阶。这证明了(2.8)。□推论2.5固定t≥2个顶点的有根树T。假设λ>1保持有界远离1且存在序列h(n)满足h(n)→∞使得(2.3)成立。则G(n,p)中的巨分量以趋于一的概率具有T的悬垂副本：(2.13)limn→∞P(?H:Cgiant?H?T)=1。证明。引理2.1、引理2.4给出E[N]→∞且E[N2]=(1+o(1))E[N]2。因此，切比雪夫不等式（Chebychev's inequality）给出N→∞依概率成立。特别地，研究人员有N>0以趋于一的概率成立，这给出(2.13)。□定理1.1的证明。Schwenk给出了9个顶点上的有根树T1,T2使得对每个有根图H，图G1=H?T1和G2=H?T2是共谱的；另见[14, p. 65]。此外，Godsil和McKay找到了11个顶点上的有根树T1′,T2′使得H?T1′和H?T2′是R-共谱的。因此所需结果立即由推论2.5得到。□回想命题1.2假设λ>1固定，并断言巨分量具有指数多个共谱配对图。这再次通过交换悬垂树得到：命题1.2的证明。令T1,T2为Godsil和McKay给出的产生R-共谱性的树。记VT1为2-核心中附有T1悬垂副本的顶点集。则研究人员断言存在c1>0使得limn→∞P(#VT1≥c1n)=1。这可由类似于定理1.1的二阶矩计算推导，也可直接由Ding、Lubetzky和Peres的结果推出，该结果确立对固定λ>1巨分量与一个在2-核心顶点上附着独立Galton–Watson树的模型是邻接的（contiguous）。对任意S?VT1，令GS表示从Cgiant通过将所有以S为根的T1副本替换为T2副本得到的图。则GS与Cgiant是R-共谱的。进一步，若Vaut表示2-核心中在自同构下容许非平凡轨道的顶点集，则图{GS:S?VT1?Vaut}都是两两不同构的。因此，(2.14)#{G:G与Cgiant是R-共谱的}≥#{GS:S?VT1?Vaut}=2#VT1?#Vaut。Verbitsky和Zhukovskii已知#Vaut依概率有界，即limC→∞lim supn→∞P(#Vaut>C)=0。因此，对任意ε>0有limn→∞P(#VT1?#Vaut≥(c1?ε)n)=1。结合(2.14)得出结论。□3. 2-核心中的切换方法需要至少两个环——定理1.7的证明。回想定义1.4，大小≤m的切换方法涉及用Q⊕In?m对邻接矩阵进行共轭，其中Q是某个m×m正交矩阵。这里允许Q具有整数行，这是不等号的原因，因为研究人员可能用更小的矩阵实现相同操作。更精确地说，由于正交性，Q的任何整数行只有一个±1元素，其余为零。若Q的所有行都是整数，则它只是带符号置换矩阵（signed permutation matrix），符号可取正。此时切换将得到与原图同构的图。因此假设Q具有非整数行，并记Q?为Q的最大主子矩阵（principal submatrix）不含整数行。则研究人员称该操作为Q?-切换。G中对应于该子矩阵的顶点称为切换集（switching set）。因此，在例1.5的Godsil–McKay切换中切换集为X。此后，研究人员的主要焦点是非整数子矩阵Q?。因此研究人员从此处起省略波浪号。研究人员的主要技术结果是定理3.1：定理3.1设G是连通图且最小度≥2，考虑正交矩阵Q∈Rk×k没有整数非零元素。假设G通过Q-切换具有不同构的共谱配对图。则G具有至多2k+1个顶点且边数严格多于顶点数的连通子图。注意边数多于顶点数的连通图必须至少有两个环。因此，研究人员也可将定理3.1视为陈述G必须具有至少两个环的'小'连通子图。在定理3.1的证明中，所需子图在切换集X的邻域图（neighborhood graph）中找到；见定义3.2。研究人员在第3.2节中表明若邻域图是不相交环的并则切换方法将得到同构图，这在定理3.1的证明中用于确保不同构的切换需要邻域图中至少一个度≥3的顶点。后者用作构造定理3.1陈述中连通子图的起点；见第3.3节。给定定理3.1，定理1.7的证明 readily follows，因为当λ小时边数多于顶点数的小子图是罕见的。细节见第3.3节。3.1. 切换方法在子图上诱导共谱性。回想切换方法只修改一个小子图及连接到该子图的边。这将使用以下定义3.2精确表述，可视化于图3。定义3.2设G=(V,E)是图，X是顶点子集。G关于X的邻域图是图GX，其顶点集为X∪N(X)，其中N(X)?∪x∈X{v∈V:v～x}，边集为{e∈E:e∩X≥1}。当研究人员在后续论证中考虑通过切换操作从G得到的图H时，总是也给H配备定义1.4中提到的与切换方法相关的顶点排序。研究人员认为顶点集相同。特别地，给定顶点集S?V，诱导子图（记为G[S]和H[S]）对G和H都有定义。图3. X的邻域图包括至少一个端点在X中的边。若图容许Q-切换，则包含切换集邻域图的每个子图也容许Q-切换：引理3.3考虑图G=(V,E)和通过切换集X的Q-切换从G得到的H。若Y?V?X且F是G[X∪Y]的边集满足F∩E(GX)=?，则Q-切换可应用于G[X∪Y]?F，结果为共谱图H[X∪Y]?F。证明。重排顶点后Q-切换由对角块为Q、?I、I的块对角矩阵表示。考虑对应于该顶点排序的邻接矩阵的块矩阵分解：(3.1)A(G)?[B U W; UT C11 C12; WT C21 C22]。则应用于G的Q-切换可表示为共轭(3.2)diag(Q,?I,I)T A(G) diag(Q,?I,I)=[QTBQ ?QTU QTW; ?UTQ C11 ?C12; WTQ ?C21 C22]=A(H)。G[X∪Y]的邻接矩阵通过移除(3.1)中所有与X∪Y中顶点无关的行和列得到。因此，例如(3.1)中第一块行中研究人员完整保留第一块B因为对应切换集X，只保留U和W中与Y相关的列。此外，移除F中的边只将C子矩阵中的元素从一变为零。因此，(3.3)A(G[X∪Y]?F)=[B ?Y W?Y; ?YT C?11 C?12; W?YT C?21 C?22]，其中?Y和W?Y是从U和W移除相应列得到的矩阵，C?i,j是从Ci,j移除行和列并可能将某些元素置零得到的。现在考虑从diag(Q,?I,I)只保留与X∪Y相关的行和列得到的正交矩阵。该矩阵具有形式diag(Q,?Ia,Ib)且a+b=#Y。则由(3.2)可得H[X∪Y]?F的邻接矩阵正是用diag(Q,?Ia,Ib)共轭(3.3)得到的矩阵。因此，G[X∪Y]?F和H[X∪Y]?F确实通过Q-切换相关联。□3.2. 不相交环的并导致同构。定理3.1证明中的困难情形将出现在GX是不相交环的并时。这一挑战不能忽视，因为多个相距甚远的小环可以以非零概率出现在2-核心中。研究人员在此的目标是表明这种情况下切换总是得到同构图，这在引理3.10中完成。3.2.1. 为最大度2的图生成共谱性。研究人员将分析GX的子图，当GX是不相交环的并时这些子图是最大度至多2的图。以下定理3.5表明这些图中所有共谱图由一小集共谱配对在以下意义上生成：定义3.4设F={(Fi,Fi′):i∈I}是共谱配对集。若存在I的多重子集J使得G⊕j∈J Fj?H⊕j∈J Fj′，则称图G和H之间的共谱性由F生成。这里⊕表示不相交并。生成所有作为环的并的子图的共谱图这一具体问题已由Cvetkovi?、Simi?和Stani?分析。然而，那里的陈述结果只识别了'极小非DS图'（minimal non-DS graphs）。先验地这不排除存在一对共谱图（都是路径和环的并）不在[7, Theorem 3.1]列表中，因为两个图都不是极小非DS。然而无极小性的断言 readily follows from [6]关于生成所有谱半径至多2的图的较旧结果：定理3.5 Cvetkovi?和Gutman。设Γ,Γ′是一对最大度有界的共谱图。则共谱性由{(C2n+2P1,C4+2Pn?1):n≥3}∪{(C4+2Pn?1,C2n+2P1):n≥3}生成。证明。谱半径由最大度界定，所以研究人员考虑的图谱半径至多2。[6]中的方程(2a)-(2i)给出了生成谱半径至多2的图中所有共谱性的图对集F。因此存在某些(Fj,Fj′)j∈J∈F使得Γ⊕j∈J Fj?Γ′⊕j∈J Fj′。不是环或路径的每个分量只出现在(2a)-(2i)中的一个方程中。因此，由于Γ,Γ′的最大度有界为2，对任何包含此类分量的配对(Fj,Fj′)（j∈J）必有k∈J使得(Fk,Fk′)=(Fj′,Fj)。研究人员可从J中移除j,k并仍保持有效同构。只有[6]中的方程(2c)（涉及Fj?C2n+2P1和Fj′?C4+2Pn?1）不涉及任何最大度≥3的分量。研究人员得出结论该配对必须生成最大度有界为2的所有共谱图对。□由此可得最大度2的共谱配对图至少相差三个分量：引理3.6设Γ,Γ′是不同构的共谱图且最大度都有界为2。则存在n,k≥2且n≠k使得Γ比Γ′至少多一个C2n和两个Pk?1分量，且Γ′比Γ至少多一个C2k和两个2Pn?1分量。证明。令Γ=∑i=1s aiCi+∑j=1s bjPj和Γ′=∑i=1s ai′Ci+∑j=1s bj′Pj（s足够大）。研究人员断言由此可得(3.4)2a2i+bi?1=2a2i′+bi?1′对所有1≤i≤s+1成立。事实上，若Γ=C2n+2P1和Γ′=C4+2Pn?1则(3.4)成立，一般情形由定理3.5考虑并得到；回想定义3.4。图Γ和Γ′共谱且具有相同数量的环分量但不同构。定理3.5意味着它们不能在奇环上不同，且(3.4)意味着它们不能只在路径上不同，所以存在n≥2使得a2n>a2n′且k≠n使得a2k2的顶点v0。现在取GX中包含v0的环C0。由GX的定义，X外没有两个顶点相邻。因此，(3.6)#(C0∩X)≥#(C0?X)。研究人员接下来扩展C0以获得至多2#X+1个顶点且边数多于顶点数的图。图5. 定理3.1的证明通过考虑GX中包含度≥3顶点v0的环C0并考虑从v0的邻居v1开始的GX?C0中极大路径来构造所需子图。在 depicted example 中，可通过取v6为 circled vertices 之一找到这样的路径v1v2…v6。鉴于v0在GX中度>2，必存在C0外的顶点v1与v0相邻。考虑GX?C0中从v1开始且不能延伸为更长路径的路径P=v1v2,…,vi。路径不能延伸意味着vi在GX中的所有邻居都在C0∪{v1,…,vi?1}中。鉴于GX最小度≥2，则必有vi在C0∪{v1,…,vi?1}中至少有两个邻居。（见图5。）无论哪种情况，由C0∪{v1,…,vi}诱导的GX子图连通且至少有#C0+i+1条边，因为路径P有i?1条边，且从与v1和vi的连接中获得两条边。进一步，路径满足#(P∩X)+1≥#(P?X)，因为X外每个顶点后必须跟一个X中顶点，可能最后一个除外。因此，构造的子图中顶点数满足(3.7)#C0∪P=#(C0∪P)∩X+#(C0∪P)?X≤2#(C0∪P)∩X+1≤2#X+1。因此，G具有≤2#X+1个顶点且边数严格多于顶点数的连通子图，即由C0∪P诱导的图。这完成了证明。□注3.11图具有最小度2的条件在定理3.1中是本质的。即使只有一个度数为1的顶点，切换方法也可能在邻域图GX中只有一个环的情况下产生不同构的图；见图6示例。定理1.7的证明。回想第3节开头，任何大小≤m的切换对应于某个k×k正交矩阵Q的Q-切换，k≤m。因此，由于连通图的2-核心总是连通图且最小度≥2，由定理3.1可得(3.8)P(Core2(Cgiant)容许大小≤m的切换产生不同构的图)≤∑k≤2m+1P(Core2(Cgiant)具有k个顶点和≥k+1条边的子图)。这里，对任何k个顶点e条边的图H，令G为原G(n,p)图，(3.9)P(H?G)≤∑v1,…,vk=1nP(G[v1,…,vk]至少有e条边)=O(nkpe)。注意若λ=o(ne?ke)则nkpe=λe/ne?k趋于零。特别地，对任何固定k，若λ=o(n1/(k+1))则以高概率G(n,p)图（因此其巨分量的2-核心）没有≤k个节点和≥k+1条边的子图。假设λ=o(n1/(2m+2))现在给出(3.8)当n→∞时趋于零，完成证明。□图6. (a) 此例中邻域图GX中有一个环和一个度数为1的节点。不同构的悬垂图K1,…,K4附着到N(X)。(b) Godsil–McKay切换产生不同构的图，可通过考虑唯一具有悬垂K4的顶点的邻居度数验证。4. 数值证据。研究人员最后考虑猜想1.3的变体的数值证据，其中邻接共谱性替换为R-共谱性。这一设置允许应用Wang和Wang的算法，该算法可以证明给定图由其R-谱确定，或在不是时搜索R-共谱配对图。这些算法适用于可控或几乎可控的图，意味着矩阵W∈Zn×n（列为e,Ae,…,An?1e）必须满足rank(W)≥n?1，其中A是邻接矩阵，e=(1,…,1)T。4.1. 主要发现。研究人员对变化的平均度λ>1和节点数n生成随机图，并应用[27]中的算法，附加一些优化在第4.2节中讨论。结果呈现在表1中。研究人员的结论如下：关于R-共谱性的频率。从总共100×22个采样图中，巨分量的2-核心仅对总共6个样本被证明是R-共谱的，而许多样本被证明由R-谱确定。主要警告是对于小λ存在非平凡比例的图算法不确定。对于中等大小的平均度，研究人员看到算法证明许多图由其R-谱确定；对λ=5除一个样本外所有样本都是这种情况。非可控性。不确定情况的主要原因是对小λ，rank(W)

相关新闻