高维空间中Erd?s–Rényi随机图G(n,p)的d-刚性阈值与两阶段机制

《European Journal of Combinatorics》：On the rigidity of random graphs in high-dimensional spaces

　　

研究人员研究Erd?s–Rényi G(n,p)随机图成为d-刚性（d-rigid）的最大维度d=d(n,p)。主要结果揭示了G(n,p)中由p_c=C^?logn/n（C^?=2/(1?log2)）分隔的两种不同刚性机制；该点对应于图的最小度（minimum degree）超过其平均度（average degree）一半的位置。研究人员证明，若p<(1??)p_c，则d(n,p)渐近几乎必然（asymptotically almost surely，a.a.s.）等于G(n,p)的最小度。相反，若p_c≤p=o(n^?1/2)，则d(n,p) a.a.s.等于(1/2+o(1))np。第二项结果在该机制下证实了Krivelevich、Lew和Michaeli的一个猜想。

研究背景与问题：图G=(V,E)在R^d中称为d-刚性（d-rigid），若对generic嵌入（generic embedding）p（其d|V|个坐标在有理数上代数独立（algebraically independent）），任何从p出发、保持所有边长不变的连续运动都不改变任意两顶点间距离；Asimow和Roth证明该定义等价于无穷小generic刚性（infinitesimal generic rigidity），并可由刚性矩阵（rigidity matrix）的秩条件刻画。d=1时刚性等价于图连通，Laman给出平面刚性组合刻画；d>2时d-刚性图的组合结构远未理解。随机图G(n,p)的固定维数刚性阈值与最小度（minimum degree，δ(G)）至少d一致：d=1为Erd?s和Rényi的连通阈值，d=2由Jackson、Servatius和Servatius解决，d>2由Király和Theran、Jordán和Tanigawa、Lew、Nevo、第一作者和Raz解决，阈值形式为np?(logn+(d?1)loglogn)→∞时a.a.s. d-刚性，趋于?∞时a.a.s.非d-刚性。由此，当np=logn+O(loglogn)时最小度成为刚性瓶颈；Krivelevich、Lew和Michaeli猜想当np=ω(logn)时边数成为瓶颈，并证明较弱的(c?np/lognp)-刚性。该研究要回答：随n→∞，G(n,p)为d-刚性的最大维度d=d(n,p)是多少。研究人员通过比较两个显然瓶颈，得到分界p_c=C^?logn/n（C^?=2/(1?log2)≈6.518），并证明两个regime的最大维度；结论揭示随机图高维刚性的两阶段机制，在p_c≤p=o(n^?1/2)内证实上述猜想，并给出全局刚性推论，方法可推广到所有1-extendable abstract rigidity matroids。

关键技术方法：该研究为理论概率与组合刚性研究，无样本队列来源。主要采用随机图G(n,p)与渐近几乎必然（a.a.s.）分析；刚性矩阵秩、d-刚性拟阵（d-rigidity matroid）及其闭包（closure）C_d(G)；正交补（orthogonal complement）与投影（projection）P_WA下的C_d,A(G)；Villányi关于Lovász-Yemini猜想的论证以从稠密闭包提取大团；Chernoff不等式（Chernoff’s inequalities）、最小度二阶矩估计；随机图大子集间匹配（matching）的贪心构造；以及Henneberg步骤（Henneberg steps）等组合刚性工具。

研究结果（保留原文小标题）：
1 Introduction：通过定义高维d-刚性并比较最小度与边数两个必要条件，提出最大维度问题，给出p_c分界及两个主定理。
1.1 Generic global rigidity and reconstruction：通过引入全局d-刚性（globally d-rigid），指出全局d-刚性图最小度至少d+1、且Jordán证明(d+1)-刚性蕴含全局d-刚性，由主定理推出全局(δ(G)?1)-刚性及d<(1/2??)np的全局刚性结论。
2 Preliminaries：建立刚性与随机图预备，包括刚性矩阵、闭包、投影、Chernoff不等式、最小度与匹配。
2.1 Generic infinitesimal rigidity：通过generic嵌入与刚性矩阵秩，得d-刚性等价于rankR=d|V|?\(\binom{d+1}{2}\)，并定义d-刚性拟阵闭包C_d(G)；G为d-刚性当且仅当C_d(G)为完全图。
2.1.1 The structure of closed graphs：通过Villányi的引理等，得闭图最小度至少d(d+1)时存在顶点其邻居诱导团；并给出Fact 2.3和Claim 2.4的团扩展与合并结论。
2.1.2 Projections of the rigidity matrix：通过正交补与投影构造C_d,A(G)，得若A在C_d(G)中诱导团，则C_d,A(G)?C_d(G)，并将相应投影拟阵解释为收缩（contraction）。
2.2 Chernoff’s inequalities：使用Chernoff不等式给出二项随机变量的上尾与下尾界，用于后续概率估计。
2.3 Minimum degree in random graphs：通过函数φ_c(t)及其最小非负根a(c)，得p=clogn/n时δ(G)=(a(c_n)+o(1))logn a.a.s.；解a=c/2得C^?≈6.518，c?时最小度瓶颈更紧，否则边数瓶颈更紧。
2.3.1 Matchings in random graphs：通过概率估计与贪心构造，得p=ω(n^?1)时任意两个大小至少δn的不相交顶点集间a.a.s.存在至少δn/2条边的匹配。
3 Proofs of the main theorems：通过闭包稠密性、大团提取及团扩展证明主定理。
3.1 A well-spread dense closure：通过将稠密闭包估计同时应用于所有|A|≤0.9n的C_d,A(G)，得a.a.s. |C_d,A(G)|≥?n²/15；再结合Villányi引理、匹配和Claim 2.4，得C_d(G) a.a.s.含至少0.9n个顶点的团。
3.2 Proofs of main theorems：通过条件化δ(G)上界、0.9n大团和Claim 3.6（每个小集合B有顶点外邻至少(a+δ)logn，或B内部边少于b/2），用Fact 2.3扩展团，得Theorem 1：在1?p=ω(n^?2)下，p<(1??)p_c时G a.a.s.为δ(G)-刚性，p>(1+?)p_c时概率趋于0；Theorem 2：p_c≤p=o(n^?1/2)时，d<(1/2??)np概率趋于1，d>(1/2+?)np概率趋于0。
4 Discussion and open problems：通过讨论证明边界、后续结果与反例，提出开放问题并总结研究结论。

讨论部分总结与结论翻译：研究结论为：在p<(1??)p_c时，最大维度a.a.s.为δ(G)；在p_c≤p=o(n^?1/2)时，a.a.s.为(1/2+o(1))np，从而在该regime证实Krivelevich、Lew和Michaeli猜想；非刚性结论直接来自维度计数。讨论指出：(1) Conjecture 1的精确形式在Ω(n^?1/2)≤p<1仍开放；Theorem 2的证明在两处使用p=o(n^?1/2)：使用Villányi的Lemma 2.2，以及在G中任意两个线性大小不相交顶点集间建立\(\binom{d+1}{2}\)条边的匹配；自初版以来，Krivelevich、Lew和Michaeli在稀疏regime p=o(1)给出相差乘法常数的部分答案，证明p≥2logn/n时G(n,p) a.a.s.为?cnp?-刚性（某绝对常数c>0）。(2) 稠密regime（p远离0和1）具有显著挑战；初版曾问G(n,1/2)是否a.a.s.为(?n)-刚性，Jordán、Liu和Villányi肯定回答d～7n/32，确定正确常数仍为开放问题。(3) 在pc时研究人员能精确得到最大d=δ(G)；在p>p_c时研究人员猜想并由数值实验验证：a.a.s. G为d-刚性当且仅当事件|E(G)|≥dn?\(\binom{d+1}{2}\)发生；但其概率方法（Lemma 3.1）仅在d远离np/2时有意义，故不足以解决该猜想。(4) 当前证明适用于所有1-extendable abstract rigidity matroids；这些定理是否对所有abstract rigidity matroids成立仍开放，而已有相关结果对所有abstract rigidity matroids成立。