The Library
Local convergence of random graph colorings
Tools
Tools
Tools
Coja-Oghlan, Amin, Efthymiou, Charilaos and Jaafari, Nor (2018) Local convergence of random graph colorings. Combinatorica, 38 (2). pp. 341-380. doi:10.1007/s00493-016-3394-x
|
PDF
WRAP-Local-convergence-random-graph-colorings-Efthymiou-2018.pdf - Accepted Version - Requires a PDF viewer. Download (900Kb) | Preview |
Official URL: https://doi.org/10.1007/s00493-016-3394-x
Abstract
Let 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 \SIGMA of G(n,m) 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 {\em condensation threshold} \dc, 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 k_0. More generally, we investigate the joint distribution of the k-colorings that \SIGMA induces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on the reconstruction problem.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph coloring, Random graphs | ||||||||
| Journal or Publication Title: | Combinatorica | ||||||||
| Publisher: | Springer Berlin Heidelberg | ||||||||
| ISSN: | 0209-9683 | ||||||||
| Official Date: | April 2018 | ||||||||
| Dates: |
|
||||||||
| Volume: | 38 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 341-380 | ||||||||
| DOI: | 10.1007/s00493-016-3394-x | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
