The condensation transition in random hypergraph 2-coloring
The condensation transition in random hypergraph 2-coloring
复制标题
DOI：
10.1137/1.9781611973099.22
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
A. Coja-Oghlan;L. Zdeborová
中科院分区：
文献类型：
--
作者：
A. Coja-Oghlan;L. Zdeborová
对于许多随机约束满足问题，如随机可满足性或随机图或超图着色，目前最好的解存在阈值估计是基于一阶矩法和二阶矩法。然而，在大多数情况下，这些技术不会产生匹配的上界和下界。来自统计力学的复杂但不严谨的论点将这种差异归因于一种称为凝结的相变的存在，这种相变发生在解决方案存在的实际阈值之前不久，并影响了问题的组合性质（Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007）。本文首次证明了自然随机CSP，即随机超图2-着色中存在缩聚跃迁。也许令人惊讶的是，我们发现应用于2色数的二阶矩法在冷凝转变之前严格失效。我们的证明也略微改进了随机超图2-可色性的阈值界限。
For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability.