随机图着色中的相变

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
我们考虑了一个大型稀疏随机图的顶点在给定的颜色数下的着色问题，使得相邻的顶点没有相同的颜色。利用空腔方法，我们对真色（解）空间进行了详细而系统的分析研究。我们证明，对于固定的颜色数，随着平均顶点度（约束数）的增加，解集经历了几个相变，类似于玻璃平均场理论中观察到的相变。首先，在聚类转变时，相空间中的熵占优部分分解成指数数量的纯态，因此在此转变之后，解的均匀采样变得困难。随后，解的空间在有限个最大态上凝聚，结果解的总熵小于退火后的熵。另一个转变发生在所有的熵占优状态中，有限部分的节点冻结，使得这些节点中的每一个在状态内的所有解中都允许一种颜色。最终，超过着色阈值，没有更多的解决方案可用。我们计算了Erdos-Renyi图和正则随机图的所有临界连通性，并确定了它们在大量颜色下的渐近值。最后，我们讨论了我们的发现的算法后果。我们认为计算硬度的开始与聚类转变无关，相反，我们认为冻结转变可能是相关的现象。根据我们的结果，我们还讨论了一种简单的局部Walk-COL算法和信念传播算法的性能。
---
英文标题：
《Phase Transitions in the Coloring of Random Graphs》
---
作者：
Lenka Zdeborov\'a, Florent Krzakala
---
最新提交年份：
2007
---
分类信息：

一级分类：Physics        物理学
二级分类：Disordered Systems and Neural Networks        无序系统与神经网络
分类描述：Glasses and spin glasses; properties of random, aperiodic and quasiperiodic systems; transport in disordered media; localization; phenomena mediated by defects and disorder; neural networks
眼镜和旋转眼镜；随机、非周期和准周期系统的性质；无序介质中的传输；本地化；由缺陷和无序介导的现象；神经网络
--
一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--

---
英文摘要：
  We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions).   We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors.   Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
---
PDF链接：
https://arxiv.org/pdf/704.1269

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：随机图 Consequences localization Computation Transitions 分析 算法 number 相变 着色