Name
Abstract | ||
|---|---|---|
Let G = G(n, m) be a random graph whose average degree d = 2m/n is below the k-colorability threshold. If we sample a k-coloring σ of G uniformly 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-called condensation 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 for k exceeding a certain constant k0. More generally, we investigate the joint distribution of the k-colorings that σ induces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on the reconstruction problem. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00493-016-3394-x | Combinatorica |
Field | DocType | Volume |
Discrete mathematics,Random regular graph,Wheel graph,Combinatorics,Graph power,Bound graph,Fractional coloring,Cycle graph,Degree (graph theory),Mathematics,Path graph | Journal | 38 |
Issue | ISSN | Citations |
2 | 0209-9683 | 0 |
PageRank | References | Authors |
0.34 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Charilaos Efthymiou | 2 | 209 | 15.44 |
| Nor Jaafari | 3 | 0 | 1.01 |