Reconstruction of random colourings

Allan Sly

doi:10.1007/s00220-009-0783-7

Reconstruction of random colourings

Allan Sly

Research output: Contribution to journal › Article › peer-review

45 Scopus citations

Abstract

Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. Bhatnagar et al. [2] showed non-reconstruction when log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].

Original language	English (US)
Pages (from-to)	943-961
Number of pages	19
Journal	Communications In Mathematical Physics
Volume	288
Issue number	3
DOIs	https://doi.org/10.1007/s00220-009-0783-7
State	Published - Jun 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Statistical and Nonlinear Physics
Mathematical Physics

Access to Document

10.1007/s00220-009-0783-7

Cite this

@article{4b3cc9afd0ef41519974c94e8ab605be,

title = "Reconstruction of random colourings",

abstract = "Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. Bhatnagar et al. [2] showed non-reconstruction when log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].",

author = "Allan Sly",

note = "Funding Information: Supported by NSF grants DMS-0528488 and DMS-0548249. Acknowledgments Open Access ",

year = "2009",

month = jun,

doi = "10.1007/s00220-009-0783-7",

language = "English (US)",

volume = "288",

pages = "943--961",

journal = "Communications In Mathematical Physics",

issn = "0010-3616",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Reconstruction of random colourings

AU - Sly, Allan

N1 - Funding Information: Supported by NSF grants DMS-0528488 and DMS-0548249. Acknowledgments Open Access

PY - 2009/6

Y1 - 2009/6

N2 - Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. Bhatnagar et al. [2] showed non-reconstruction when log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].

AB - Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. Bhatnagar et al. [2] showed non-reconstruction when log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].

UR - https://www.scopus.com/pages/publications/67349106422

UR - https://www.scopus.com/inward/citedby.url?scp=67349106422&partnerID=8YFLogxK

U2 - 10.1007/s00220-009-0783-7

DO - 10.1007/s00220-009-0783-7

M3 - Article

AN - SCOPUS:67349106422

SN - 0010-3616

VL - 288

SP - 943

EP - 961

JO - Communications In Mathematical Physics

JF - Communications In Mathematical Physics

IS - 3

ER -

Reconstruction of random colourings

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this