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 with vertex set
. Each vertex of the graph coincides with a discrete variable
. Thus,
is the number of possible states of the variables
.
Two vertices are connected by an edge if they interact in the Potts model.
Moreover, to each edge
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.
).
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
summands. The constant
is determined by the temperature
and the Boltzmann constant
.
Now we want to reformulate the partition function (2) by using the equation , which is valid for
, 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
. Let
denote the number of connected components of the graph
. Then there are
possible choices to assign values
to the connected components of the graph
which implies
Suppose , then we get
because of definition (3), and we are able to define variables
as follows:
By fitting these variables into formula (4) we get
where is a function with
for all
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 
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 for all
, it holds
Furthermore the lower bound holds as equality if and only if for all subsets
. Applying the logarithm to formula (10) we get
For the sum
is converging to zero. Thus, for large numbers
it holds
For almost all possible values of (and
, respectively) there exists an unique optimum solution, i.e.
. Then
.
Furthermore, small variations in the values can cause only small changes of
but large changes of
. This means that small variations of the values
can have large influence to the partition function of the physical system.
Optimum solutions for the partition function for 
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)])