The Ising Antiferromagnet and Max Cut on Random Regular Graphs

Autor:	Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
Rok vydání:	2022
Předmět:	FOS: Computer and information sciences Discrete Mathematics (cs.DM) General Mathematics Probability (math.PR) 05C80 FOS: Mathematics Mathematics - Combinatorics QA Mathematics Combinatorics (math.CO) Mathematics - Probability Computer Science - Discrete Mathematics
Zdroj:	SIAM Journal on Discrete Mathematics. 36:1306-1342
ISSN:	1095-7146 0895-4801
DOI:	10.1137/20m137999x
Popis:	The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {\sc Max Cut} of random regular graphs predicted by Zdeborov\'a and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1335076b7e66654def5b5b0bf155a92d https://doi.org/10.1137/20m137999x Zobrazit plný text záznamu