# Potts model

## Contents |

### 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 . Thus, is the number of possible states of the variables σ_{i}.
Two vertices are connected by an edge if they interact in the Potts model.
Moreover, to each edge (*i*,*j*) ∈ *E*(*G*) of the graph some real number is assigned, representing the interaction energy.

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

with δ(⋅) denoting the Kronecker function (i.e. δ(0) = 1 *a**n**d* δ(*x*) = 0 *f**o**r* *a**l**l* *x* ≠ 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

where goes over all possible vectors leading to *q*^{N} summands. The constant β = 1 / (*k*_{0}*T*) 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*δ) = 1 + (exp(*a*) − 1)δ, which is valid for δ ∈ {0;1}, and variables

Then we get

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

Obviously, the product is nonzero if and only if the same value σ 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 to the connected components of the graph *G*(*F*) which implies

Suppose ∀(*i*,*j*) ∈ *E*(*G*):*T* > 0 *a**n**d* *J*_{ij} > 0, then we get *v*_{ij} > 0 *f**o**r* *a**l**l* (*i*,*j*) ∈ *E*(*G*) because of definition (3), and we are able to define variables *w*_{ij} as follows:

By fitting these variables into formula (4) we get

where is a function with

for all *F* ⊆ *E*(*G*).
The function 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*→∞

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

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* ⊆ *E*(*G*)\Ψ_{G}^{ * }, it holds

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

For *q* → ∞ the sum is converging to zero. Thus, for large numbers *q* it holds

For almost all possible values of *J*_{ij} (and *w*_{ij}, respectively) there exists an unique optimum solution, i.e. | Ψ_{G}^{ * } | = 1. Then .

Furthermore, small variations in the values *w*_{ij} can cause only small changes of *f*^{ * } but large changes of | Ψ_{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*→∞

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)])