A Computational Method for Bounding the Probability of Reconstruction on Trees

DOI10.1137/090751244zbMath1236.60092arXiv0903.4812OpenAlexW1502923329MaRDI QIDQ3094947

Nayantara Bhatnagar, Elitza Maneva

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/0903.4812

zbMATH Keywords

graph coloringgraphsGibbs measuretreescorrelationsreconstructionPotts modelGalton-Watson treeMarkov random fieldsreplica symmetry breakingextremality

Mathematics Subject Classification ID

Trees (05C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Phase transitions (general) in equilibrium statistical mechanics (82B26) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Markov processes (60J99) General topics in the theory of algorithms (68W01)

Related Items

Reconstruction for the Potts model