Correlation decay and the absence of zeros property of partition functions

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.

Automated summary

The absence of (complex) zeros property is the core of Barvinok's interpolation method, which is used to design deterministic approximation algorithms for graph counting and related problems. The author establishes the relationship between this property and the correlation decay property, and proves it using a certain graph polynomial representation. The conjecture that this result holds for all graphs has recently been confirmed by Regts.