Reconstruction for Colorings on Trees
From MaRDI portal
Publication:3094945
DOI10.1137/090755783zbMath1298.05060arXiv0711.3664OpenAlexW2963060561MaRDI QIDQ3094945
Eric Vigoda, Nayantara Bhatnagar, Dror Weitz, Juan Carlos Vera
Publication date: 27 October 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0711.3664
Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)
Related Items (8)
Reconstruction of random colourings ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Global alignment of molecular sequences via ancestral state reconstruction ⋮ Gibbs measures and phase transitions on sparse random graphs ⋮ Local convergence of random graph colorings
This page was built for publication: Reconstruction for Colorings on Trees