DOI: 10.1007/s00220-009-0783-7. Reconstruction of Random Colourings

Reconstruction of Random Colourings

10.1007/s00220-009-0783-7

Crossref journal-article

Springer Science and Business Media LLC

Communications in Mathematical Physics (297)

Bibliography

Sly, A. (2009). Reconstruction of Random Colourings. Communications in Mathematical Physics, 288(3), 943â961.

Authors 1

Allan Sly (first)

References 21 Referenced 31

Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transition. http://front.math.ucdavis.edu/0803.2122 , 2008
Bhatnagar, N., Vera, J., Vigoda, E.: Reconstruction for colorings on trees. http://front.math.ucdavis.edu/0711.3664 , 2007
Bleher P.M., Ruiz J., Zagrebnov V.A.: On the purity of limiting Gibbs state for the Ising model on the Bethe lattice. J. Stat. Phys. 79, 473–482 (1995) (10.1007/BF02179399) / J. Stat. Phys. by P.M. Bleher (1995)
Borgs, C., Chayes, J.T., Mossel, E., Roch, S.: The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels. In: FOCS 2006, Los Alamitos, CA: IEEE Computer Society, 2006, pp. 518–530 (10.1109/FOCS.2006.76)
Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, 2006, pp. 159–168 (10.1145/1132516.1132540)
Dyer, M., Frieze, A., Hayes, T.P., Vigoda, E.: Randomly coloring constant degree graphs. In: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC: IEEE Computer Society, 2004, pp. 582–589 (10.1109/FOCS.2004.57)
Evans W., Kenyon C., Peres Y., Schulman L.J.: Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10(2), 410–433 (2000) (10.1214/aoap/1019487349) / Ann. Appl. Probab. by W. Evans (2000)
Janson S., Mossel E.: Robust reconstruction on trees is determined by the second eigenvalue. Ann. Probab. 32(3B), 2630–2649 (2004) (10.1214/009117904000000153) / Ann. Probab. by S. Janson (2004)
Jonasson J.: Uniqueness of uniform random colorings of regular trees. Stat. Prob. Lett. 57, 243–248 (2002) (10.1016/S0167-7152(02)00054-8) / Stat. Prob. Lett. by J. Jonasson (2002)
Kesten H., Stigum B.P.: Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Stat. 37, 1463–1481 (1966) (10.1214/aoms/1177699139) / Ann. Math. Stat. by H. Kesten (1966)
Krza̧kała F., Montanari A., Ricci-Tersenghi F., Semerjian G., Zdeborova L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Nat. Acad. Sci. 104, 10318–10323 (2007) (10.1073/pnas.0703685104) / Proc. Nat. Acad. Sci. by F. Krzza̧kała (2007)
Krza̧kała F., Pagnani A., Weigt M.: Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs. Phys. Rev. E 70(4), 046705 (2004) (10.1103/PhysRevE.70.046705) / Phys. Rev. E by F. Krza̧kała (2004)
Lange, K.: Applied probability. Springer Texts in Statistics. New York: Springer-Verlag, 2003
Mézard M., Montanari A.: Reconstruction on trees and spin glass transition. J. Stat. Phys. 124(6), 1317–1350 (2006) (10.1007/s10955-006-9162-3) / J. Stat. Phys. by M. Mézard (2006)
Mossel E.: Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Prob. 11(1), 285–300 (2001) (10.1214/aoap/998926994) / Ann. Appl. Prob. by E. Mossel (2001)
Mossel E.: Phase transitions in phylogeny. Trans. Amer. Math. Soc. 356(6), 2379–2404 (2004) (electronic) (10.1090/S0002-9947-03-03382-8) / Trans. Amer. Math. Soc. by E. Mossel (2004)
Mossel, E.: Survey: information flow on trees. In: Graphs, morphisms and statistical physics, Volume 63 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Providence, RI: Amer. Math. Soc., 2004, pp. 155–170
Mossel E., Peres Y.: Information flow on trees. Ann. Appl. Probab. 13, 817–844 (2003) (10.1214/aoap/1060202828) / Ann. Appl. Probab. by E. Mossel (2003)
Mossel, E., Sly, A.: Gibbs rapidly samples colorings of G(n,d/n). http://arxiv.org/abs/0707.3241V2[math.PR] , 2007
Semerjian G.: On the freezing of variables in random constraint satisfaction problems. J. Stat. Phys. 130, 251 (2008) (10.1007/s10955-007-9417-7) / J. Stat. Phys. by G. Semerjian (2008)
Zdeborová L., Krza̧kała F.: Phase transitions in the coloring of random graphs. Phys. Rev. E 76, 031131 (2007) (10.1103/PhysRevE.76.031131) / Phys. Rev. E by L. Zdeborová (2007)

Dates

Type	When
Created	16 years, 5 months ago (March 19, 2009, 5:06 a.m.)
Deposited	6 years, 4 months ago (April 6, 2019, 11:35 p.m.)
Indexed	3 months, 1 week ago (May 20, 2025, 5:17 a.m.)
Issued	16 years, 5 months ago (March 20, 2009)
Published	16 years, 5 months ago (March 20, 2009)
Published Online	16 years, 5 months ago (March 20, 2009)
Published Print	16 years, 2 months ago (June 1, 2009)

Funders 0

None

BibTeX

@article{Sly_2009, title={Reconstruction of Random Colourings}, volume={288}, ISSN={1432-0916}, url={http://dx.doi.org/10.1007/s00220-009-0783-7}, DOI={10.1007/s00220-009-0783-7}, number={3}, journal={Communications in Mathematical Physics}, publisher={Springer Science and Business Media LLC}, author={Sly, Allan}, year={2009}, month=mar, pages={943–961} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        5,
        20
      ]
    ],
    "date-time": "2025-05-20T09:17:10Z",
    "timestamp": 1747732630016
  },
  "reference-count": 21,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "3",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2009,
        6
      ]
    ]
  },
  "DOI": "10.1007/s00220-009-0783-7",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2009,
        3,
        19
      ]
    ],
    "date-time": "2009-03-19T09:06:33Z",
    "timestamp": 1237453593000
  },
  "page": "943-961",
  "source": "Crossref",
  "is-referenced-by-count": 31,
  "title": "Reconstruction of Random Colourings",
  "prefix": "10.1007",
  "volume": "288",
  "author": [
    {
      "given": "Allan",
      "family": "Sly",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2009,
        3,
        20
      ]
    ]
  },
  "reference": [
    {
      "key": "783_CR1",
      "unstructured": "Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transition. http://front.math.ucdavis.edu/0803.2122 , 2008"
    },
    {
      "key": "783_CR2",
      "unstructured": "Bhatnagar, N., Vera, J., Vigoda, E.: Reconstruction for colorings on trees. http://front.math.ucdavis.edu/0711.3664 , 2007"
    },
    {
      "key": "783_CR3",
      "doi-asserted-by": "crossref",
      "first-page": "473",
      "DOI": "10.1007/BF02179399",
      "volume": "79",
      "author": "P.M. Bleher",
      "year": "1995",
      "unstructured": "Bleher P.M., Ruiz J., Zagrebnov V.A.: On the purity of limiting Gibbs state for the Ising model on the Bethe lattice. J. Stat. Phys. 79, 473\u2013482 (1995)",
      "journal-title": "J. Stat. Phys."
    },
    {
      "key": "783_CR4",
      "doi-asserted-by": "crossref",
      "unstructured": "Borgs, C., Chayes, J.T., Mossel, E., Roch, S.: The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels. In: FOCS 2006, Los Alamitos, CA: IEEE Computer Society, 2006, pp. 518\u2013530",
      "DOI": "10.1109/FOCS.2006.76"
    },
    {
      "key": "783_CR5",
      "doi-asserted-by": "crossref",
      "unstructured": "Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, 2006, pp. 159\u2013168",
      "DOI": "10.1145/1132516.1132540"
    },
    {
      "key": "783_CR6",
      "doi-asserted-by": "crossref",
      "unstructured": "Dyer, M., Frieze, A., Hayes, T.P., Vigoda, E.: Randomly coloring constant degree graphs. In: FOCS \u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC: IEEE Computer Society, 2004, pp. 582\u2013589",
      "DOI": "10.1109/FOCS.2004.57"
    },
    {
      "issue": "2",
      "key": "783_CR7",
      "doi-asserted-by": "crossref",
      "first-page": "410",
      "DOI": "10.1214/aoap/1019487349",
      "volume": "10",
      "author": "W. Evans",
      "year": "2000",
      "unstructured": "Evans W., Kenyon C., Peres Y., Schulman L.J.: Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10(2), 410\u2013433 (2000)",
      "journal-title": "Ann. Appl. Probab."
    },
    {
      "issue": "3B",
      "key": "783_CR8",
      "doi-asserted-by": "crossref",
      "first-page": "2630",
      "DOI": "10.1214/009117904000000153",
      "volume": "32",
      "author": "S. Janson",
      "year": "2004",
      "unstructured": "Janson S., Mossel E.: Robust reconstruction on trees is determined by the second eigenvalue. Ann. Probab. 32(3B), 2630\u20132649 (2004)",
      "journal-title": "Ann. Probab."
    },
    {
      "key": "783_CR9",
      "doi-asserted-by": "crossref",
      "first-page": "243",
      "DOI": "10.1016/S0167-7152(02)00054-8",
      "volume": "57",
      "author": "J. Jonasson",
      "year": "2002",
      "unstructured": "Jonasson J.: Uniqueness of uniform random colorings of regular trees. Stat. Prob. Lett. 57, 243\u2013248 (2002)",
      "journal-title": "Stat. Prob. Lett."
    },
    {
      "key": "783_CR10",
      "doi-asserted-by": "crossref",
      "first-page": "1463",
      "DOI": "10.1214/aoms/1177699139",
      "volume": "37",
      "author": "H. Kesten",
      "year": "1966",
      "unstructured": "Kesten H., Stigum B.P.: Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Stat. 37, 1463\u20131481 (1966)",
      "journal-title": "Ann. Math. Stat."
    },
    {
      "key": "783_CR11",
      "doi-asserted-by": "crossref",
      "first-page": "10318",
      "DOI": "10.1073/pnas.0703685104",
      "volume": "104",
      "author": "F. Krzza\u0327ka\u0142a",
      "year": "2007",
      "unstructured": "Krza\u0327ka\u0142a F., Montanari A., Ricci-Tersenghi F., Semerjian G., Zdeborova L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Nat. Acad. Sci. 104, 10318\u201310323 (2007)",
      "journal-title": "Proc. Nat. Acad. Sci."
    },
    {
      "issue": "4",
      "key": "783_CR12",
      "doi-asserted-by": "crossref",
      "first-page": "046705",
      "DOI": "10.1103/PhysRevE.70.046705",
      "volume": "70",
      "author": "F. Krza\u0327ka\u0142a",
      "year": "2004",
      "unstructured": "Krza\u0327ka\u0142a F., Pagnani A., Weigt M.: Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs. Phys. Rev. E 70(4), 046705 (2004)",
      "journal-title": "Phys. Rev. E"
    },
    {
      "key": "783_CR13",
      "unstructured": "Lange, K.: Applied probability. Springer Texts in Statistics. New York: Springer-Verlag, 2003"
    },
    {
      "issue": "6",
      "key": "783_CR14",
      "doi-asserted-by": "crossref",
      "first-page": "1317",
      "DOI": "10.1007/s10955-006-9162-3",
      "volume": "124",
      "author": "M. M\u00e9zard",
      "year": "2006",
      "unstructured": "M\u00e9zard M., Montanari A.: Reconstruction on trees and spin glass transition. J. Stat. Phys. 124(6), 1317\u20131350 (2006)",
      "journal-title": "J. Stat. Phys."
    },
    {
      "issue": "1",
      "key": "783_CR15",
      "doi-asserted-by": "crossref",
      "first-page": "285",
      "DOI": "10.1214/aoap/998926994",
      "volume": "11",
      "author": "E. Mossel",
      "year": "2001",
      "unstructured": "Mossel E.: Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Prob. 11(1), 285\u2013300 (2001)",
      "journal-title": "Ann. Appl. Prob."
    },
    {
      "issue": "6",
      "key": "783_CR16",
      "doi-asserted-by": "crossref",
      "first-page": "2379",
      "DOI": "10.1090/S0002-9947-03-03382-8",
      "volume": "356",
      "author": "E. Mossel",
      "year": "2004",
      "unstructured": "Mossel E.: Phase transitions in phylogeny. Trans. Amer. Math. Soc. 356(6), 2379\u20132404 (2004) (electronic)",
      "journal-title": "Trans. Amer. Math. Soc."
    },
    {
      "key": "783_CR17",
      "unstructured": "Mossel, E.: Survey: information flow on trees. In: Graphs, morphisms and statistical physics, Volume 63 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Providence, RI: Amer. Math. Soc., 2004, pp. 155\u2013170"
    },
    {
      "key": "783_CR18",
      "doi-asserted-by": "crossref",
      "first-page": "817",
      "DOI": "10.1214/aoap/1060202828",
      "volume": "13",
      "author": "E. Mossel",
      "year": "2003",
      "unstructured": "Mossel E., Peres Y.: Information flow on trees. Ann. Appl. Probab. 13, 817\u2013844 (2003)",
      "journal-title": "Ann. Appl. Probab."
    },
    {
      "key": "783_CR19",
      "unstructured": "Mossel, E., Sly, A.: Gibbs rapidly samples colorings of G(n,d/n). http://arxiv.org/abs/0707.3241V2[math.PR] , 2007"
    },
    {
      "key": "783_CR20",
      "doi-asserted-by": "crossref",
      "first-page": "251",
      "DOI": "10.1007/s10955-007-9417-7",
      "volume": "130",
      "author": "G. Semerjian",
      "year": "2008",
      "unstructured": "Semerjian G.: On the freezing of variables in random constraint satisfaction problems. J. Stat. Phys. 130, 251 (2008)",
      "journal-title": "J. Stat. Phys."
    },
    {
      "key": "783_CR21",
      "doi-asserted-by": "crossref",
      "first-page": "031131",
      "DOI": "10.1103/PhysRevE.76.031131",
      "volume": "76",
      "author": "L. Zdeborov\u00e1",
      "year": "2007",
      "unstructured": "Zdeborov\u00e1 L., Krza\u0327ka\u0142a F.: Phase transitions in the coloring of random graphs. Phys. Rev. E 76, 031131 (2007)",
      "journal-title": "Phys. Rev. E"
    }
  ],
  "container-title": "Communications in Mathematical Physics",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/s00220-009-0783-7.pdf",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        4,
        7
      ]
    ],
    "date-time": "2019-04-07T03:35:58Z",
    "timestamp": 1554608158000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/s00220-009-0783-7"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2009,
        3,
        20
      ]
    ]
  },
  "references-count": 21,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          2009,
          6
        ]
      ]
    }
  },
  "alternative-id": [
    "783"
  ],
  "URL": "http://dx.doi.org/10.1007/s00220-009-0783-7",
  "relation": {},
  "ISSN": [
    "0010-3616",
    "1432-0916"
  ],
  "subject": [],
  "container-title-short": "Commun. Math. Phys.",
  "published": {
    "date-parts": [
      [
        2009,
        3,
        20
      ]
    ]
  }
}