{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T09:19:24Z","timestamp":1784107164056,"version":"3.55.0"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T00:00:00Z","timestamp":1738627200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called\n                    <jats:italic>occupation problems<\/jats:italic>\n                    , and in particular on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline1.png\"\/>\n                        <jats:tex-math>$r$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -in-\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline2.png\"\/>\n                        <jats:tex-math>$k$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    occupation problems. By now, out of these CSPs only the satisfiability threshold \u2013 the largest degree for which the problem admits asymptotically a solution \u2013 for the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline3.png\"\/>\n                        <jats:tex-math>$1$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -in-\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline4.png\"\/>\n                        <jats:tex-math>$k$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    occupation problem has been rigorously established. Here we determine the satisfiability threshold of the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline5.png\"\/>\n                        <jats:tex-math>$2$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -in-\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline6.png\"\/>\n                        <jats:tex-math>$k$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    occupation problem for all\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000440_inline7.png\"\/>\n                        <jats:tex-math>$k$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignments to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.\n                  <\/jats:p>","DOI":"10.1017\/s0963548324000440","type":"journal-article","created":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T01:32:51Z","timestamp":1738632771000},"page":"491-527","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Satisfiability thresholds for regular occupation problems"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0572-7252","authenticated-orcid":false,"given":"Konstantinos","family":"Panagiotou","sequence":"first","affiliation":[{"name":"LMU M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2389-6586","authenticated-orcid":false,"given":"Matija","family":"Pasch","sequence":"additional","affiliation":[{"name":"LMU M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2025,2,4]]},"reference":[{"key":"S0963548324000440_ref6","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/36\/43\/026"},{"key":"S0963548324000440_ref43","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/12\/P12004"},{"key":"S0963548324000440_ref42","doi-asserted-by":"publisher","DOI":"10.1137\/090750755"},{"key":"S0963548324000440_ref34","doi-asserted-by":"publisher","DOI":"10.4171\/aihpd\/31"},{"key":"S0963548324000440_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20057"},{"key":"S0963548324000440_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001796"},{"key":"S0963548324000440_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255445"},{"key":"S0963548324000440_ref12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.77.031118"},{"key":"S0963548324000440_ref33","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#"},{"key":"S0963548324000440_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591878"},{"key":"S0963548324000440_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746619"},{"key":"S0963548324000440_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-017-0145-9"},{"key":"S0963548324000440_ref36","unstructured":"[36] Panagiotou, K. and Pasch, M. (2019) Satisfiability Thresholds for Regular Occupation Problems. In 46th Int. Col. on Automata, Languages, and Programming (ICALP \u201919), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), 90:1\u201390:14."},{"key":"S0963548324000440_ref38","first-page":"26","article-title":"A remark on Stirling\u2019s formula","volume":"62","author":"Robbins","year":"1955","journal-title":"Amer. Math. Monthly"},{"key":"S0963548324000440_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548324000440_ref41","unstructured":"[41] Yedidia, J. S. , Freeman, W. T. and Weiss, Y. (2001) Bethe free energy, kikuchi approximations, and belief propagation algorithms, Technical Report TR2001-16, MERL - Mitsubishi Electric Research Laboratories, Cambridge, MA 02139, May 2001."},{"key":"S0963548324000440_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2492-8"},{"key":"S0963548324000440_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.08.006"},{"key":"S0963548324000440_ref32","volume-title":"World Scientific Lecture Notes in Physics","volume":"9","author":"M\u00e9zard","year":"1987"},{"key":"S0963548324000440_ref39","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2016\/08\/083303"},{"key":"S0963548324000440_ref16","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"S0963548324000440_ref7","first-page":"231","volume-title":"Statistical physics, optimization, inference, and message-passing algorithms","author":"Coja-Oghlan","year":"2016"},{"key":"S0963548324000440_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548324000440_ref37","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199611)23:3<215::AID-JGT1>3.0.CO;2-V"},{"key":"S0963548324000440_ref1","first-page":"1","article-title":"Community detection and stochastic block models: recent developments","volume":"18","author":"Abbe","year":"2018","journal-title":"J Mach Learn Res"},{"key":"S0963548324000440_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"S0963548324000440_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2280915"},{"key":"S0963548324000440_ref22","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/233\/1\/012003"},{"key":"S0963548324000440_ref2","doi-asserted-by":"publisher","DOI":"10.37236\/6361"},{"key":"S0963548324000440_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"S0963548324000440_ref20","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/aa9529"},{"key":"S0963548324000440_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"S0963548324000440_ref40","volume-title":"Spin glasses: a challenge for mathematicians","volume":"46","author":"Talagrand","year":"2003"},{"key":"S0963548324000440_ref35","volume-title":"Geometry and Inference in Optimization and in Information Theory","author":"Mora","year":"2007"},{"key":"S0963548324000440_ref28","volume-title":"Statistical physics, optimization, inference, and message-passing algorithms","author":"Krzakala","year":"2016"},{"key":"S0963548324000440_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548324000440_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000390"},{"key":"S0963548324000440_ref31","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548324000440_ref19","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0042"},{"key":"S0963548324000440_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.11.007"},{"key":"S0963548324000440_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"S0963548324000440_ref26","first-page":"9","article-title":"The phase transition in exact cover","volume":"5","author":"Kalapala","year":"2008","journal-title":"Chic. J. Theoret. Comput. Sci."},{"key":"S0963548324000440_ref25","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8508"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:49:37Z","timestamp":1775796577000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000440\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,4]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0963548324000440"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000440","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,4]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}