前几天科学网博客遭攻击，我的博文“值得有志者征服的概率问题：Aldous-Lyons猜想”已无法读取；现重发，供有志者参考。

Aldous-Lyons猜想：单模随机网络的有限逼近

向开南  2014年9月

随机图极限一方面诞生于概率学者O. Schramm（SLE理论开创者、ICM 1小时报告者）（2001[7]、2003 [4]、2007 [33] Section 4）、D. Aldous（美国科学院外籍院士、英国皇家学会会员、ICM 1小时报告者）等（2004 [3]、2007 [2]）的研究中。另一方面它诞生于组合图论学者L. Lovasz（Wolf奖得主）、B.Bollobas（匈牙利科学院院士)等最近5至9年的研究中([26]、[25]、[8])。由于在信息与计算机科学、统计物理、生物等中存在着大量的各种各样的巨型离散结构（图结构），而（随机）图极限可以研究这些巨型离散结构的渐近行为、各种巨型离散结构间的“相似性”与“接近度”、极限离散结构上的随机过程与概率模型（随机游走、渗流等其它的统计物理/力学模型）。图极限对概率论、组合图论、统计物理均具有十分重大的理论意义及应用价值；例如，对诸多spin glass模型（一类离散结构上的概率模型）而言，归一化的配分函数的对数的极限，即spin glass模型的热力学极限，实际上是一种关于赋权图的图极限。

（随机）图极限理论是一个充满挑战的极具发展前景的处于成长期的研究领域（[24]）。由L. Lovasz等发起，2014年6月在[匈牙利]布达佩斯举办了如下的summer school：

“Graphlimits,groupsandstochasticprocesses”at the MTA Renyi Institute in  Budapest, June

    22-27, 2014. See http://www.renyi.hu/conferences/grgrst/.

此暑期学校的专题反映出图极限具有强劲的生命力。

图极限有两种重要的极端情形：稠密图极限、极端稀疏图极限。前者主要为图论组合专家所感兴趣，稀疏图极限（现实网络往往是稀疏图）则同时为概率、图论组合学者所感兴趣；概率学者尤其对极端稀疏图极限感兴趣。（极端）稀疏图极限主要由Benjamini与Schramm [7]（亦见[6]），Aldous与Steele [3]，Aldous与Lyons [2]，Bollobas与Riordan [8]（亦见[32]）所发展。Aldous、Schramm等([7]、[4]、[3]、[2])研究的是极端稀疏图极限。

为叙述Aldous-Lyons猜想（2007）([2] p. 1500 Question 10.1)（简记为AL猜想），设(G_n)_n是一有限网络序列；其中网络是指顶点与边具有标记的图，是图的一种推广。令U_n是G_n的均匀随机顶点。若对任给的rooted有限网络F，rooted网络(G_n,U_n)同构于F的概率收敛，则称(G_n)_n局部收敛或具有随机弱极限。显然此时的极限是一随机rooted网络；且易证它满足质量运输原理，即它是单模的。反之，自然地，这诞生了AL猜想：

             任一单模随机图（网络）均是某有限图（网络）序列的随机弱极限（即局部极限）。

此猜想在一定意义上由Lovasz [25]命名，见[25] Conjecture 7.2(Aldous-Lyons)。对此猜想的理解，见[2]pp. 1458-1459、pp. 1500-1501，[7] Sections 3与7，[32] p. 2574以及[30] Chapter 14。基于如下事实，AL猜想是随机图极限理论中十分基本且相当重要的问题。（i）与稠密图相比，稀疏图极限理论发展得不够完善。原因在于还不清楚相关的极限对象如何刻画（这诞生了AL猜想）；以及相关的收敛是一种局部性质，不保持图的某些整体性质。（ii）注意在稀疏图极限理论中，图（网络）序列的收敛往往是前述随机弱极限（即局部极限）的加强。（iii）诸多无穷图上的统计物理模型是通过有限图序列上相应模型取局部极限来定义。（iv）AL猜想的解决能推出任一可数群都是sofic的，这能导致几个重要猜想的解决；而“每一可数群是sofic群？”是可数群论中的central问题。对AL猜想，有如下的评论：它是随机图极限理论中的“fundamental problem”（O. Schramm）、“one of the most important open problems”与“a central unsolved problem”（L. Lovasz）、“especially important open question”（D. Aldous）、“a famous open problem”（B. Virag）。

关于另一类型的随机图极限（随机平面地图的scaling极限）见J. F. Le Gall（法国科学院院士、M.Loeve奖与Fermat奖得主）等的[21]-[23]、[28]、[29]；及S. Sheffield（M. Loeve奖得主）[34]。Le Gall因这方面的成就而在ICM2014作大会报告。

AL猜想对概率论、图论的意义不言而喻。它的解决对群论起推动作用，即可推出“任一有限生成群是sofic的”，进一步，“任一可数群是sofic的”。sofic群由Wolf 奖、Abel奖得主M. Gromov 1999 [19]引进；诞生于他对符号动力系统中的Gottschalk Surjunctivity猜想（[18]）的研究；名字“sofic”由B. Weiss [35]所取。在可数群理论中，有如下两个Central Open Question（[31]）：任一可数群都是sofic 群？都是hyperlinear 群？注意sofic群是hyperlinear群。此外它的解决还可证明算子理论中十分著名的有30多年历史的A. Connes（Fields奖得主）嵌入猜想对群von Neumann代数成立，即弱形式的Connes嵌入猜想成立。Connes嵌入猜想（[13]）是算子理论中最重要的猜想之一，与算子代数版本的Hilbert第17问题等价；其近况见[12]。

D. Aldous、R. Lyons曾在一2004年预印本中对AL猜想给出了一个错误的证明；见[27] p. 494 lines-8,-9与-10。Lovasz、Bollobas认为对度有界的单模随机图（网络），此猜想成立（[25]、[8]）；此情形下的AL猜想仍可推出“任一可数群是sofic群”、Gottschalk Surjunctivity猜想与弱形式的Connes嵌入猜想。[16]借鉴[10]研究双曲平面的circle packing的一个想法，证明了此猜想对任一度有界的单模随机树成立。[17]将[16]的结论推广至网络。最近[5]利用不变渗流重证了Elek的结论[16]、[17]：AL猜想对支撑在树上的单模随机网络成立。此外，O. Schramm（2008）证明了超有限情形的AL猜想；见[24]。

AL猜想值得有志者去征服。

                                                  参考文献

[1] D.J. Aldous. Exchangeability and continuum limits of discrete random structures. Proceedings. ICM 2010.Vol. I (2010), 141-  

    153. Hindustan BookAgency, 2011.

[2] D.J. Aldous, R. Lyons. Processes on unimodular random networks. Electron. J. Probab.12 (2007), paper no. 54, 1454-1508.

[3] D.J. Aldous, J. M. Steele. The objective method: probabilistic combinatorialoptimization and local weak convergence. In: Discrete and Combinatorial  

     Probability (H. Kesten, ed.), 1-72.Springer, 2004.

[4] O.Angel, O. Schramm. Uniform infinite planar triangulations. Comm. Math. Phy.241(2003), 191-213.

[5] I.Benjamini, R. Lyons, O. Schramm. Unimodular random trees. Ergodic Theory Dynamical Systems. (2014).  To appear.

[6] I.Benjamini. Random planar metrics. Proceedings.ICM2010.Vol. IV (2010),2177-2187. Hindustan Book Agency, 2010.

[7] I.Benjamini, O. Schramm. Recurrence of distributional limits of finite planargraphs. Electron. J. Probab.6 (2001), paper no. 23, 1-13.

[8] B.Bollobas, O. Riordan. Sparse graphs: metrics and random models. Random Structures Algorithms. 39 (2011), no. 1, 1-38.[9] C.Borgs, J. T. Chayes, L. Lovasz, V. T. Sos, K. Vesztergombi. Convergentsequences of dense graphs II. Multiway cuts and statistical physics.

     Ann. Math.176 (2012), no. 1, 151-219.

[10] L.Bowen. Periodicity and circle packings of the hyperbolic plane. Geom. Dedicata.102 (2003), 213-236.  

[11] L.Bowen. Every countably infinite group is almost Ornstein. Contemp. Mathematics.567(2012), 67-78.

[12] V.Capraro. A survey on connes's embedding conjecture. arXiv: 1003.2076v1 [math.OA]. Preprint, 2010.

     [13] A. Connes. Classification of injective factors. Ann. Math.104 (1976), no. 1, 73-115.

     [14] E.Csoka, G. Lippner. Invariant random perfect matchings in Cayley graphs. arXiv:1211.2374v1 [math. CO].  Preprint, 2012.

     [15] R.G. Douglas, P. W. Nowak. Every finitely generated group is weakly exact. J.Funct. Analysis261 (12), (2011), 3723-3734.

     [16] G. Elek. On the limit of large girth graphsequences. Combinatorica.30 (2010), 553-563.

     [17] G. Elek, G. Lippner. Sofic equivalence relations. J. Funct. Anal.258 (2010), 1692-1708.

     [18] W.Gottschalk. Some general dynamical notions. Recentadvances in topological dynamics. Lect. Note. Math. 318, 120-125. Springer, 1973.  

     [19] M.Gromov. Endomorphisms of symbolic algebraic varieties. J. EMS.1(2) (1999),109-197.

     [20] O.Gurel-Gurevich, A. Nachmias. Recurrence of planar graph limits. Ann. Math.177 (2013), no. 2, 761-781.

     [21] J.F. Le Gall. The topological structure of scaling limits of large planar maps. Invent. Math.169(3) (2007), 621-670.

     [22] J.F. Le Gall. Geodesics in large planar maps and in the Brownian map. Acta. Math.205(2) (2010), 287-360.      

     [23]  J.F. Le Gall, G. Miermont. Scaling limits of random trees and planar maps. In: Probabilityand Statistical Physics in Two and More Dimensions,

             Clay Mathematics Proceedings, Vol.15, pp.155-211.AMS-CMI, 2012.

     [24] L. Lovasz. Largenetworks and graph limits. AMS, Providence, RI, 2012.

     [25] L.Lovasz. Very large graphs (dedicated tothe memory of Oded Schramm). Current developments in mathematics, 2008,67-

             128, Int. Press, Somerville, MA, 2009.

     [26] L.Lovasz, B. Szegedy. Limits of dense graph sequences. J. Comb. Th. Ser. B.96(2006), 933-957.

     [27] R. Lyons. Asymptotic enumeration of spanningtrees. Comb. Prob. Comput.14 (2005), 491-522.

     [28] G. Miermont. The Brownian map is the scaling limitof uniform random plane quadrangulations.Acta Math.

     210(2) (2013), 319-401.

[29]J.F. Marckert, A. Mokkadem. Limit of normalized random quadrangulations: theBrownian map. Ann. Probab.34(6) (2006),

     2144-2202.

[30] G. Pete. Probabilityand geometry on groups. Book, 2013.

[31] V.Pestov. Hyperlinear and sofic groups: a brief guide. Bull. Symbolic Logic.14(2008), no.4, 449-480.

[32] O.Riordan. Percolation on sequences of graphs. Proceedings. ICM2010.Vol.IV (2010), 2555-2578. Hindustan Book Agency, 2010.

[33] O.Schramm. Conformally invariant scaling limits: an overview and a collection ofproblems. Proceedings. ICM 2006. Vol. I,

      513- 543, European MathematicalSociety, 2007.

[34] S.Sheffield. Conformal weldings of random surfaces: SLE and the quantum gravityzipper. arXiv: 1012.4797v1 [math.PR]. Preprint, 2010.

    [35] B. Weiss. Sofic groups and dynamical systems. Sankhya Series A.62 (2000), no. 3, 350-359.