COMBINATORIAL APPROACH TO THE INTERPOLATION METHOD AND SCALING LIMITS IN SPARSE RANDOM GRAPHS
COMBINATORIAL APPROACH TO THE INTERPOLATION METHOD AND SCALING LIMITS IN SPARSE RANDOM GRAPHS
复制标题
DOI：
10.1214/12-aop816
复制
发表时间：
2013-11-01
影响因子：
2.3
通讯作者：
Tetali, Prasad
中科院分区：
文献类型：
--
作者：
Bayati, Mohsen;Gamarnik, David;Tetali, Prasad
在Erdos-Renyi图G(N，[CN])和随机r-正则图G(N，r)上建立了几种组合模型的自由能极限的存在性。对于包括独立集、最大割、着色和K-SAT在内的各种模型，我们证明了当基础图的大小发散到无穷大时，正温度和零温度下的自由能在适当的重新标度下都收敛到一个极限。在零温度情况下，这被解释为相应的组合优化问题的标度极限的存在。例如，作为特例，我们证明了这些图中由节点数归一化的最大独立集的大小收敛到一个极限W.H.P.这解决了奥尔德斯提出的一个开放问题(一些开放问题)，作为他最喜欢的六个开放问题之一。它在其他几个地方也被作为一个公开问题提到：Wormard[在组合学调查中，1999(坎特伯雷)(1999)239-298剑桥大学]中的猜想2.20。书名/作者声明：Reach for[Random Structures][J][J]；可能吧。电脑。17(2008)259-264]和Aldous and Steele[in Probability on Display Structures(2004)1-72 Springer].我们的方法是基于扩展和简化Guera和Toninelli的插值法[Com.数学课。太棒了。230(2002)71-79]和弗朗茨和里昂[J.Stat.太棒了。111(2003)-564]。在其他应用中，该方法被用于证明Erdos-Renyi图上的Viana-Bray和K-SAT模型的自由能极限的存在性。在零温情况下，采用正温度模型的极限处理。相反，我们提供了一种更简单的组合方法，并在Erdos-Renyi图G(N，r)和随机正则图G(N，r)的情况下直接处理零温情况(优化)。此外，对于G(N，[CN])随机图模型，我们建立了约束满足问题K-SAT和NAE-K-SAT的可满足性的大偏差原理。
We establish the existence of free energy limits for several combinatorial models on Erdos-Renyi graph G(N, [cN]) and random r-regular graph G(N, r). For a variety of models, including independent sets, MAX-CUT, coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. This resolves an open problem which was proposed by Aldous (Some open problems) as one of his six favorite open problems. It was also mentioned as an open problem in several other places: Conjecture 2.20 in Wormald [In Surveys in Combinatorics, 1999 (Canterbury) (1999) 239-298 Cambridge Univ. Press]; Bollobas and Riordan [Random Structures Algorithms 39 (2011) 1-38]; Janson and Thomason [Combin. Probab. Comput. 17 (2008) 259-264] and Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].Our approach is based on extending and simplifying the interpolation method of Guerra and Toninelli [Comm. Math. Phys. 230 (2002) 71-79] and Franz and Leone [J. Stat. Phys. 111 (2003) 535-564]. Among other applications, this method was used to prove the existence of free energy limits for Viana-Bray and K-SAT models on Erdos-Renyi graphs. The case of zero temperature was treated by taking limits of positive temperature models. We provide instead a simpler combinatorial approach and work with the zero temperature case (optimization) directly both in the case of Erdos-Renyi graph G(N, r) and random regular graph G(N, r). In addition we establish the large deviations principle for the satisfiability property of the constraint satisfaction problems, coloring, K-SAT and NAE-K-SAT, for the G(N, [cN]) random graph model.