{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:13Z","timestamp":1787323153606,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1761603"],"award-info":[{"award-number":["DMS-1761603"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In this paper, we analyze the tree reconstruction problem, which is to determine whether symbols at the $n$th level of the tree provide information on the root as $n\\rightarrow \\infty$. This problem has wide applications in various fields such as biology, information theory, and statistical physics, and its close connections to the clustering problem in the setting of the stochastic block model (SBM) have been well established. For SBM, an \u201cinformation-theoretically-solvable-but-computationally-hard\" region, or say \u201chybrid-hard\" phase, appears whenever the reconstruction bound of the corresponding reconstruction on the tree problem is not tight. Inspired by the recently proposed $q_1+q_2$ SBM [F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborov\u00e1, Phys. Rev. E, 99 (2019), 042109], we extend the classical works on the Ising model [C. Borgs et al., Proceedings of the 47 th Annual IEEE Symposium on Foundation of Computer Science, 2006, pp. 518--530] and the Potts model [A. Sly, Ann. Probab., 39 (2011), pp. 1365--1406] by studying a general model which incorporates the characteristics of both Ising and Potts through different in-community and out-community transition probabilities and rigorously give the conditions for the nontightness of the reconstruction threshold.<\/jats:p>","DOI":"10.1137\/20m1322674","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T13:38:16Z","timestamp":1623937096000},"page":"1381-1417","source":"Crossref","is-referenced-by-count":0,"title":["Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree"],"prefix":"10.1137","volume":"35","author":[{"given":"Wenjian","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8950-1279","authenticated-orcid":true,"given":"Ning","family":"Ning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"atypb1","unstructured":"J. Banks, C. Moore, J. Neeman, and P. Netrapalli (2016),\n                      Information-theoretic thresholds for community detection in sparse networks\n                      , in Proceedings of the Conference on Learning Theory, pp. 383-416."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0369-4"},{"key":"atypb3","unstructured":"J. Bernussou and J.L. Abatut (1977),\n                      Point Mapping Stability\n                      , Pergamon, London."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20305"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"N. Bhatnagar, A. Sly, and P. Tetali (2010),\n                      Reconstruction threshold for the hardcore model\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, New York, pp. 434-447.","DOI":"10.1007\/978-3-642-15369-3_33"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"N. Bhatnagar, A. Sly, and P. Tetali (2016),\n                      Decay of correlations for the hardcore model on the $d$-regular random graph\n                      , Electron. J. Probab., 21.","DOI":"10.1214\/16-EJP3552"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02179399"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"C. Borgs, J. Chayes, E. Mossel, and S. Roch (2006),\n                      The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 518-530.","DOI":"10.1109\/FOCS.2006.76"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01210926"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, E. Mossel, and S. Roch (2006),\n                      Optimal phylogenetic reconstruction\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 159-168.","DOI":"10.1145\/1132516.1132540"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.107.065701"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1019487349"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/09075514X"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"H.O. Georgii (2011),\n                      Gibbs Measures and Phase Transitions\n                      , Stud. Math. 9, Walter de Gruyter, Berlin.","DOI":"10.1515\/9783110250329"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699139"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(67)90155-2"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01731581"},{"key":"atypb20","first-page":"1","author":"Liu W.","year":"2019","journal-title":"J. Statist. Phys."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-019-02228-0"},{"key":"atypb22","unstructured":"W. Liu and N. Ning (2019c),\n                      The Non-Tightness of the Reconstruction Threshold of a 4 States Symmetric Model with Different In-Block and Out-Block Mutations\n                      , preprint,https:\/\/arxiv.org\/abs\/1906.09479."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-017-1937-1"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20132"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-006-9162-3"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/998926994"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-03-03382-8"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/12"},{"key":"atypb29","first-page":"1","volume":"38","author":"Mossel E.","year":"2013","journal-title":"Combinatorica"},{"key":"atypb30","unstructured":"E. Mossel, J. Neeman, and A. Sly (2014),\n                      Belief propagation, robust reconstruction and optimal recovery of block models\n                      , in Proceedings of the Conference on Learning Theory, pp. 356-370."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.042109"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP584"},{"key":"atypb33","first-page":"512","volume":"10","author":"Tamura K.","year":"1993","journal-title":"Molecular Biol. Evolution"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP833"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1322674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:57Z","timestamp":1787319897000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1322674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1322674"],"URL":"https:\/\/doi.org\/10.1137\/20m1322674","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}