Reconstruction of random colourings

DOI10.1007/s00220-009-0783-7zbMath1274.60163arXiv0802.3487MaRDI QIDQ842496

Allan Sly

Publication date: 25 September 2009

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0802.3487

Mathematics Subject Classification ID

60G60: Random fields

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

05C15: Coloring of graphs and hypergraphs

Related Items

Phase transitions in theq-coloring of random hypergraphs, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, Combinatorial statistics and the sciences, Global alignment of molecular sequences via ancestral state reconstruction, Reconstruction for the Potts model, Local convergence of random graph colorings, Gibbs measures and phase transitions on sparse random graphs, Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees, The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, The asymptotics of the clustering transition for random constraint satisfaction problems, The large deviations of the whitening process in random constraint satisfaction problems, The Glauber dynamics for edge‐colorings of trees, Randomly coloring planar graphs with fewer colors than the maximum degree

Cites Work

• Unnamed Item
• Reconstruction on trees and spin glass transition
• Information flow on trees
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Uniqueness of uniform random colorings of regular trees
• Reconstruction on trees: Beating the second eigenvalue
• Broadcasting on trees and the Ising model.
• Robust reconstruction on trees is determined by the second eigenvalue.
• On the freezing of variables in random constraint satisfaction problems
• Randomly coloring constant degree graphs
• Optimal phylogenetic reconstruction
• Reconstruction for Colorings on Trees
• Phase transitions in phylogeny
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Gibbs rapidly samples colorings of \(G(n, d/n)\)