Potts model

The Model

A relevant model in statistical physics is the so-called Potts model which was introduced as a generalization of the Ising model describing some physical systems (cf. the article about spin glasses).

The Potts model is defined on a graph $G = (V,E)$ with vertex set $V(G) = \{1,2,...,N\}$. Each vertex of the graph coincides with a discrete variable $\sigma_i\ \in\ \mathbb{Z}_q\ (\mathbb{Z}_q = \{0,1,...,q-1\})$. Thus, $q\ \in\ \mathbb{N}$ is the number of possible states of the variables $\sigma_i$. Two vertices are connected by an edge if they interact in the Potts model. Moreover, to each edge $(i,j)\ \in\ E(G)$ of the graph some real number $J_{ij}\ \in\ \mathbb{R}$ is assigned, representing the interaction energy.

The so-called Hamiltonian, i.e., the energy function for the Potts model is defined as

$H(\sigma) = - \sum\limits_{(i,j)\ \in\ E(G)} J_{ij}\delta(\sigma_i - \sigma_j),\qquad (1)$

with $\delta(\cdot)$ denoting the Kronecker function (i.e. $\delta(0) = 1\ and\ \delta(x) = 0\ for\ all\ x\ \ne\ 0$).

Determining exact ground states for Potts glasses

We determine exact ground states of Potts spin glasses using branch-and-cut based on positive semidefinite optimization (cf. [Ghaddar et al. (2007)]).

The partition function

In the following we summerize the work by Juhasz et al. (2001) investigating the so-called partition function

$Z = \sum\limits_{\sigma} \exp(-\beta H(\sigma))\qquad (2)$

where $\sigma\ \in\ \mathbb{Z}_q^N$ goes over all possible vectors leading to $q^N$ summands. The constant $\beta = 1/(k_0T)$ is determined by the temperature $T$ and the Boltzmann constant $k_0$.

Now we want to reformulate the partition function (2) by using the equation $\exp(a\delta) = 1 + (\exp(a) - 1)\delta$, which is valid for $\delta\ \in\ \{0;1\}$, and variables

$v_{ij} = \exp(\beta J_{ij}) - 1\ for\ all\ (i,j)\ \in\ E(G).\qquad (3)\,\!$

Then we get

$\scriptstyle \begin{matrix} Z & = \sum\limits_{\sigma} \exp(\sum\limits_{(i,j)\ \in\ E(G)} \beta J_{ij}\delta(\sigma_i - \sigma_j)) \\ & = \sum\limits_{\sigma} \prod\limits_{(i,j)\ \in\ E(G)} \exp(\beta J_{ij}\delta(\sigma_i - \sigma_j)) \\ & = \sum\limits_{\sigma} \prod\limits_{(i,j)\ \in\ E(G)} (1 + v_{ij}\delta(\sigma_i - \sigma_j)) \\ & = \sum\limits_{\sigma} \sum\limits_{F\ \subseteq\ E(G)} \prod\limits_{(i,j)\ \in\ F} v_{ij}\delta(\sigma_i - \sigma_j) \\ & = \sum\limits_{F\ \subseteq\ E(G)} \sum\limits_{\sigma} \prod\limits_{(i,j)\ \in\ F} v_{ij}\delta(\sigma_i - \sigma_j). \end{matrix}$

The product over the empty set is supposed to be equal to one.

Obviously, the product $\prod\limits_{(i,j)\ \in\ F} v_{ij}\delta(\sigma_i - \sigma_j)$ is nonzero if and only if the same value $\sigma$ is assigned to the vertices of each connected component of the induced subgraph $G(F) = (V,F)$. Let $c(F)$ denote the number of connected components of the graph $G(F)$. Then there are $q^{c(F)}$ possible choices to assign values $\sigma_i\ \in\ \mathbb{Z}_q$ to the connected components of the graph $G(F)$ which implies

$Z = \sum\limits_{F\ \subseteq\ E(G)} q^{c(F)} \prod\limits_{(i,j)\ \in\ F} v_{ij}.\qquad (4)$

Suppose $\forall(i,j)\ \in\ E(G): T\ >\ 0\ and\ J_{ij}\ >\ 0$, then we get $v_{ij}\ >\ 0\ for\ all\ (i,j)\ \in\ E(G)$ because of definition (3), and we are able to define variables $w_{ij}$ as follows:

$w_{ij} = \log_{q} v_{ij}\ for\ all\ (i,j)\ \in\ E(G).\qquad (5)\,\!$

By fitting these variables into formula (4) we get

$Z = \sum\limits_{F\ \subseteq\ E(G)} q^{c(F) + \sum\limits_{(i,j)\ \in\ F} w_{ij}} = \sum\limits_{F\ \subseteq\ E(G)} q^{f(F)}\qquad (6)$

where $f:\ 2^{E(G)}\ \rightarrow\ \mathbb{R}$ is a function with

$f(F) = c(F) + \sum\limits_{(i,j)\ \in\ F} w_{ij}\ \qquad (7)$

for all $F\ \subseteq\ E(G).$ The function $f:\ 2^{E(G)}\ \rightarrow\ \mathbb{R}$ is called Potts function.

Computing the partition function is (in general) a difficult task. However, it can be approximated in reasonable time.

Approximation of the partition function for $q\rightarrow\infty$

The approximation of the partition function can be determined using the Potts function. Thus, let

$\scriptstyle \begin{matrix} f^* & = & \max\limits_{F\ \subseteq\ E(G)} f(F)\qquad \qquad \ and\qquad (8) \\ \Psi^*_G & = & \{F\ \subseteq\ E(G):\ f(F) = f^*\}\qquad (9) \end{matrix}$

be the maximum function value and the set of optimum solutions to the maximization problem, respectively.
Then, because of $0\ <\ f(F)\ <\ f^*$ for all $F\ \subseteq\ E(G)\setminus \Psi^*_G$, it holds

$q^{f^*}|\Psi^*_G|\ \le \ Z = q^{f^*}(|\Psi^*_G| + \sum\limits_{F\ \subseteq\ E(G)\setminus \Psi^*_G} q^{f(F) - f^*}).\qquad (10)$

Furthermore the lower bound holds as equality if and only if $f(F) = f^*$ for all subsets $F\ \subseteq\ E(G)$. Applying the logarithm to formula (10) we get

$f^*\ln q + \ln |\Psi^*_G|\ \le\ \ln Z\ \le\ f^*\ln q + \ln(|\Psi^*_G| + \sum\limits_{F\ \subseteq\ E(G)\setminus \Psi^*_G} q^{f(F) - f^*}).\qquad (11)$

For $q\ \rightarrow\ \infty$ the sum $\sum\limits_{F\ \subseteq\ E(G)\setminus \Psi^*_G} q^{f(F) - f^*}$ is converging to zero. Thus, for large numbers $q$ it holds

$\ln Z\ \approx\ f^*\ln q + \ln |\Psi^*_G|.\qquad (12)$

For almost all possible values of $J_{ij}$ (and $w_{ij}$, respectively) there exists an unique optimum solution, i.e. $|\Psi^*_G| = 1$. Then $\ln Z\ \approx\ f^*\ln q\ for\ large\ q$.

Furthermore, small variations in the values $w_{ij}$ can cause only small changes of $f^*$ but large changes of $|\Psi^*_G|$. This means that small variations of the values $w_{ij}$ can have large influence to the partition function of the physical system.

Optimum solutions for the partition function for $q\rightarrow\infty$

The above function is submodular and therefore polynomially solvable. Furthermore, we could use any algorithm for submodular function minimization for its solution. However for this special submodular function it is possible to design an algorithm with better worst-case running time. The latter is based on iteratively computing minimum cuts (cf. [Auriac et al. (2002)]).

Using graph theory, we show that many of these mimimum cut calls are not necessary in practice, leading to a considerably faster implementation (cf. [Fanghänel and Liers (2008)])