Approximate Counting and Expansion

Abstract

Spin models are mathematical frameworks used to study the collective behavior of interacting particles in various systems. A model assigns a discrete spin to each vertex of an underlying graph and assigns a value to each spin assignment. This produces a natural counting problem, summing the value of all spin assignments. In this thesis we study the approximate counting problems of two specific spin models.

First, we consider a variant of the ferromagnetic Ising model. The approximate counting problem of the ferromagnetic Ising model is tractable on all graphs (Jerrum and Sinclair 1993) but here we show that hidden inside this model are hard computational problems. Namely, we present computational thresholds for the approximate counting problem at fixed magnetization (that is, fixing the number of specific spins in each assignment).

Next, we consider the ferromagnetic Potts model on graphs with expansion grantees. We give algorithms for the approximate counting problems on d-regular expanding graphs and small-set expander graphs. The approximate counting problem on bounded-degree graphs is as hard as counting independent sets in bipartite graphs (#BIS-hard), so our algorithms can be seen as evidence that hard instances of #BIS are rare.