Correlation decay and the absence of zeros property of partition functions. Issue 1 (18th March 2022)

• Record Type: Journal Article
• Authors: Gamarnik, David
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 155
• Page End: 180
• Publication Date: 2022-03-18
• Subjects: algorithms -- complexity -- counting -- statistical physics; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21083
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok for designing deterministic approximation algorithms for various graph counting and related problems. An earlier method used for the same problem is one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply often coincide or nearly coincide. In this article we show that this is not a coincidence. We establish that if the interpolation method is valid for a family of graphs, then this family exhibits a form of the correlation decay property which is asymptotic strong spatial mixing at superlogarithmic distances. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs. Indeed this conjecture was recently confirmed by Regts. See the body of the article for details.