The Condensation Phase Transition in Random Graph Coloring
The Condensation Phase Transition in Random Graph Coloring
复制标题
DOI：
10.1007/s00220-015-2464-z
复制
发表时间：
2016-01-01
影响因子：
2.4
通讯作者：
Vilenchik, Dan
中科院分区：
文献类型：
--
作者：
Bapst, Victor;Coja-Oghlan, Amin;Vilenchik, Dan
基于一种非严格的形式论，物理学家们提出了关于稀释平均场模型中相变的有趣预测，其中相互作用的几何形状是由稀疏随机图或超图引起的。这种模型的一个例子是ERDAS-Renyi随机图G(n，d/n)上的图着色问题，它可以看作是Potts反铁磁体的零温度情况。腔方法预测，除了组合学中深入研究的k-可染性相变之外，还存在第二个相变，称为凝聚相变(Krzakala等人)。载于《自然学报》第104期：10318-10323页，2007年)。事实上，关于这种相变的精确位置存在着一个猜想，它是关于某个分布不动点问题的。本文证明了k超过某一常数k(0)时的这一猜想。
Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in diluted mean-field models, in which the geometry of interactions is induced by a sparse random graph or hypergraph. One example of such a model is the graph coloring problem on the ErdAs-Renyi random graph G(n, d/n), which can be viewed as the zero temperature case of the Potts antiferromagnet. The cavity method predicts that in addition to the k-colorability phase transition studied intensively in combinatorics, there exists a second phase transition called the condensation phase transition (Krzakala et al. in Proc Natl Acad Sci 104:10318-10323, 2007). In fact, there is a conjecture as to the precise location of this phase transition in terms of a certain distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k (0).