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