Local Convergence of Random Graph Colorings
Local Convergence of Random Graph Colorings
复制标题
随机图着色的局部收敛
DOI：
10.1007/s00493-016-3394-x
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
N. Jafaari
中科院分区：
文献类型：
--
作者：
A. Coja-Oghlan;C. Efthymiou;N. Jafaari
设G =G（n，m）是一个平均度为2 m/n的随机图，它的k-可着色性阈值小于G（n，m）。如果我们对G的ak-着色σ进行均匀随机抽样，那么我们可以对分配给相距很远的顶点的颜色之间的相关性说些什么呢？根据统计物理学的预测，对于低于所谓的凝聚阈值dk，cond的平均度，分配给远处顶点的颜色是渐近独立的[Krzakala等人：美国国家科学院院刊2007]。我们证明了这个猜想不超过某个常数k 0。更一般地说，我们研究的联合分布的k-染色，σ诱导局部上的有界深度邻域的任何固定数量的顶点。此外，本文还指出了对重建问题的一个启示。
LetG=G(n,m) be a random graph whose average degreed= 2m/nis below thek-colorability threshold. If we sample ak-coloringσofGuniformly at random, what can we say about the correlations between the colors assigned to vertices that are far apart? According to a prediction from statistical physics, for average degrees below the so-calledcondensation threshold dk,cond, the colors assigned to far away vertices are asymptotically independent [Krzakala et al.: Proc. National Academy of Sciences 2007]. We prove this conjecture forkexceeding a certain constantk0. More generally, we investigate the joint distribution of thek-colorings thatσinduces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on thereconstruction problem.
登录
查看更多内容
DOI：
--
发表时间：
1987
期刊：
Comb.
影响因子：
--
作者：
D. Matula
通讯作者：
D. Matula
影响因子：
1
作者：
C. McDiarmid;B. Reed
通讯作者：
B. Reed
一般高尔顿-沃森树着色的重建/非重建阈值
DOI：
--
发表时间：
2014
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Charilaos Efthymiou
通讯作者：
Charilaos Efthymiou
影响因子：
8.6
作者：
M. Mézard;M. Palassini;O. Rivoire
通讯作者：
O. Rivoire
影响因子：
2.4
作者：
V. Bapst;A. Coja;S. Hetterich;Felicia Raßmann;Dan Vilenchik
通讯作者：
Dan Vilenchik