The Condensation Phase Transition in Random Graph Coloring
The Condensation Phase Transition in Random Graph Coloring
复制标题
随机图着色中的凝聚相变
DOI：
10.4230/lipicsapprox-random.2014.449
复制
发表时间：
2014
影响因子：
2.4
通讯作者：
Dan Vilenchik
中科院分区：
文献类型：
--
作者：
V. Bapst;A. Coja;S. Hetterich;Felicia Raßmann;Dan Vilenchik
基于一种称为“腔方法”的非严格形式主义，物理学家们对稀释平均场模型中的相变提出了有趣的预测，其中相互作用的几何形状由稀疏随机图或超图诱导。这种模型的一个例子是Erdens-Renyi随机图G（n，d/n）上的图着色问题，它可以被看作是Potts反铁磁体的零温度情况。腔方法预测，除了在组合学中深入研究的k-可着色性相变之外，还存在第二种相变，称为凝聚相变（Krzakala et al. Proc Natl Acad Sci 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 Erdős–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 k0.
默默地种植色彩
DOI：
10.1017/s0963548316000390
发表时间：
2017
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
V. Bapst;A. Coja-Oghlan;C. Efthymiou
通讯作者：
C. Efthymiou