Reconstruction for the Potts model

ABSTRACT

The reconstruction problem on the tree plays a key role in several important computational problems. Deep conjectures in statistical physics link the reconstruction problem to properties of random constraint satisfaction problems including random k-SAT and random colourings of random graphs. At this precise threshold the space of solutions is conjectured to undergo a phase transition from a single collected mass to exponentially many small clusters at which point local search algorithm must fail. In computational biology the reconstruction problem is central in phylogenetics. It has been shown [Mossel 04] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model.

Rigorous reconstruction thresholds, however, have only been established in a small number of models. We confirm conjectures made by Mezard and Montanari for the Potts models proving the first exact reconstruction threshold in a non-binary model establishing the so-called Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the $q$-state Potts model when q ≥ 5. Moreover, we determine asymptotics for these reconstruction thresholds.

REFERENCES

• 1: Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transition. http://front.math.ucdavis.edu/0803.2122, 2008.
• 2: Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Related Fields, 131:311--340, 2005.
• 3: P. M. Bleher, J. Ruiz, and 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.
• 4: Christian Borgs , Jennifer Chayes , Elchanan Mossel , Sebastien Roch, The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.518-530, October 21-24, 2006 [doi>10.1109/FOCS.2006.76]
• 5: J. T. Chayes, L. Chayes, James P. Sethna, and D. J. Thouless. A mean field spin glass with short-range interactions. Comm. Math. Phys., 106(1):41--89, 1986.
• 6: Constantinos Daskalakis , Elchanan Mossel , Sébastien Roch, Optimal phylogenetic reconstruction, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132540]
• 7: Martin Dyer , Alan Frieze , Thomas P. Hayes , Eric Vigoda, Randomly Coloring Constant Degree Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.582-589, October 17-19, 2004 [doi>10.1109/FOCS.2004.57]
• 8: William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman. Broadcasting on trees and the Ising model. Ann. Appl. Probab., 10(2):410--433, 2000.
• 9: M. Formentin and C Kuelske. On the purity of the free boundary condition potts measure on random trees. http://arxiv.org/abs/0810.0677, 2008.
• 10: Antoine Gerschenfeld , Andrea Montanari, Reconstruction for Models on Random Graphs, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.194-204, October 21-23, 2007 [doi>10.1109/FOCS.2007.58]
• 11: H. Kesten and B. P. Stigum. Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Statist., 37, 1966.
• 12: Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborova. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104:10318--10323, 2007.
• 13: Fabio Martinelli , Alistair Sinclair , Dror Weitz, Fast mixing for independent sets, colorings, and other models on trees, Random Structures & Algorithms, v.31 n.2, p.134-172, September 2007 [doi>10.1002/rsa.v31:2]
• 14: Marc Mézard and Andrea Montanari. Reconstruction on trees and spin glass transition. J. Stat. Phys., 124(6):1317--1350, 2006.
• 15: A. Montanari, R. Restrepo, and P. Tetali. Reconstruction and clustering in random constraint satisfaction problems. 2009.
• 16: Elchanan Mossel. Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Probab., 11(1):285--300, 2001.
• 17: Elchanan Mossel. Phase transitions in phylogeny. Trans. Amer. Math. Soc., 356(6):2379--2404 (electronic), 2004.
• 18: Elchanan Mossel. Survey: information flow on trees. In Graphs, morphisms and statistical physics, volume 63 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 155--170. Amer. Math. Soc., Providence, RI, 2004.
• 19: Elchanan Mossel and Yuval Peres. Information flow on trees. Ann. Appl. Probab., 13:817--844, 2003.
• 20: Elchanan Mossel and Allan Sly. Gibbs rapidly samples colorings of g(n,d/n). http://arxiv.org/abs/0707.3241, 2007.
• 21: Guilhem Semerjian. On the freezing of variables in random constraint satisfaction problems. J.STAT.PHYS., 130:251, 2008.
• 22: Allan Sly. Reconstruction of random colourings. http://front.math.ucdavis.edu/0802.3487, 2008.
• 23: Lenka. Zdeborová and Florent. Krzakała. Phase transitions in the coloring of random graphs. Phys. Rev. E, 76:031131, 2007.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Theory

Keywords:
Potts model, reconstruction