Mem. Fac. Sci. Eng. Shimane Univ.
Series B: Mathematical Science
32 (1999), pp. 41–47

COMBINATORIAL PROBLEMS ARISING FROM THE
STATISTICAL MECHANICS MODEL OF SPIN GLASSES
Makoto Idzumi(Received: December 25, 1998)

Abstract. A problem of calculating the free energy of the Ising spin glassmodel on a graph is reformulated into certain combinatorial enumeration problems.

1. Introduction
Spin glasses are magnetic systems in which the interactions between the magnetic moments are “in conﬂict” with each other due to some frozen-in structuraldisorder ([1]). The Ising spin glass model, which is the subject of this paper,
is a statistical mechanics model for such magnetic systems. To take account of
the disordered nature, interactions are assumed to be random variables and theaveraging over these variables is taken for the free energy. The computation of
the averaged free energy is the aim of statistical mechanics of spin glasses.
We consider the Ising spin glass model on a general graph G (see Section 2).
We shall give two diﬀernt reformulations for the free energy of the model: oneof which is based on the high-temperature expansion (Section 3), and the otherbased on the low-temperature expansion (Section 4). The both formulations
rely on the replica trick ([4],[2]) and convert the original problem into certain
combinatorial enumeration problems. To demonstrate how they work, we shallgive explicit computations for the model on the cyclic chain (Section 5).
In condensed matter physics the graph G (the base space of the model) is(almost) always assumed to have some symmetry, such as translational one.
From such a physics viewpoint the simplest but nontrivial one is the model on
the two-dimensional square lattice with cyclic boundary conditions, for which
the exact solution has not yet been obtained; this is an open problem.
2. The Ising spin glass model
Let G be a graph, consisting of a ﬁnite set V of points (or vertices), #V = N ,and a ﬁnite set B of edges (or bonds), #B = M . We assume that G is simple;
1991 Mathematics Subject Classiﬁcation. 82B44, 82B20, 05A15.
Key words and phrases. Random Ising model, Spin glasses, Combinatorial enumeration.
41

42

MAKOTO IDZUMIthat is, G has no loops or parallel edges. Then each edge can be speciﬁed as(α, β) by its distinct endpoints. To each point α ∈ V attach the set {−1, 1}, andcall a cross-section σ : V → {−1, 1}N a spin conﬁguration. Let C be the set of
all spin conﬁgrations. For a given σ ∈ C and α ∈ V we call σα = σ(α) the (valueof) spin on the point α. To each (α, β) ∈ B let us attach a real parameter Kαβwhich speciﬁes the interaction between adjacent spins on α and β. The partition
function of the Ising model on G for the interactions K = (Kαβ |(α, β) ∈ B) is,by deﬁnition,X¡ X¢
Z(K) =exp(1)Kαβ σα σβ .
σ∈C(α,β)∈B

One of the goals in statistical mechanics is to compute the free energy per point
Tf (K) = − log Z(K).
N
This is the deﬁnition of the Ising model for given interactions K on the graph
G. (Cf. such general models were considered in [3] by the author).
Now let us introduce randomness in the interactions K. We assume that eachKαβ takes values ±K with equal probability independently, where K > 0 is aparameter whose physical meaning is K = J/T where J is the coupling constantand T the temperature. Observed (physical) free energy in the spin glass system
is supposed to be the average
1 XThf (K)iK = M
f (K) = − hlog Z(K)iK(2)2 K∈KN
where K is the set of all K : B → {−K, K}M . In statistical mechanics thisaverage is called an quenched average. (For more physics background we referto a review [1].) Thus our task is the computation of hlog Z(K)iK .
In the next two sections we will give two diﬀerent reformulations of hlog Z(K)iK :either of which converts the problem to that of calculation of a generating function of a certain enumeration problem on the graph G (or its dual). In bothcases, to compute the average of log Z, we will use the replica trick ([4],[2]): thatis, we will use the exact relation¢1¡∂hlog Zi = lim hZ n i − 1 = lim
hZ n i.
n→0 n
n→0 ∂n3. Reformulation based on the high-temperature expansion
The ﬁrst reformulation of (2) is based on the so-called high-temperature expansion. Substitutingexp(Kαβ σα σβ ) = (cosh Kαβ )(1 + σα σβ tanh Kαβ )(since σα σβ = ±1) we can rewrite (1) as¢¡ Y¢X Y ¡(3)
Z(K) =
1 + σα σβ tanh Kαβ .
cosh Kαβ(α,β)∈B

σ∈C (α,β)∈B

STATISTICAL MECHANICS MODEL OF SPIN GLASSES

43

P
Expanding the summand, taking the summation σ∈C , and noting that½
X
2
for k even,kσα =0for k odd,
σα =±1

we have an expression in terms of polygons (deﬁned below)¡ Y¢X Y(4)
Z(K) = 2N
cosh Kαβtanh Kαβ .
(α,β)∈B

P ∈P (α,β)∈P

Here, P is the set of all polygons on the graph G; a set of edges P in G is calleda polygon on G if each point in G is incident to an even number of edges inP . A few remarks are in order: (i) the empty set is a polygon; (ii) a subgraph
G(P ) generated by a polygon P is not necesarily connected; (iii) every connectedcomponent of G(P ) has a closed Euler trail (i.e., can be drawn with one strokealong a closed path) for any polygon P . For example

is a polygon (thick lines) on a graph (dashed lines; this graph is called a squarelattice). We can interpret the summation in eq. (4) as a weighted summation
over all polygons on G with weight tanh Kαβ on each edge (α, β).
Now consider the averageD¢E¡X Yhlog Z(K)iK = N log 2 + M log cosh K + log
tanh Kαβ.
P ∈P (α,β)∈PKTo evaluate the last term we employ the replica trick. Thus we are to calculate
D³ X Y´n Etanh Kαβ(5)P ∈P (α,β)∈PKfor positive integers n. Expand (· · · )n in (5); then each term represents a productof weights for n species (or n copies; n replicas) of polygons, each of which camefrom each factor in (· · · )n . We shall call such a ﬁgure, corresponding to eachterm, consisting of polygons of n species an n-ply polygon. Finally we mustaverage this series. Since½(tanh K)kif k is even,kh(tanh Kαβ ) iK =0
if k is odd
only terms that have an even number of edges of polygons of n species on eachedge of G remain non-zero, and the weight of each term is averaged to (tanh K)kwhere k is the number of edges of polygons of the term. For example, if G is asquare lattice, the term corresponding to the diagram

44

MAKOTO IDZUMI

consisting of three polygons of diﬀerent species contributes to (5) with weight(tanh K)18 since a total of 18 edges of the polygons are there; on the other hand
the term corresponding toβαvanishes in (5) since, say, the edge (α, β) is occupied by a single polygon.
Thus, we can rewrite (5) asX(6)³´#P̃tanh K

allowed P̃ ∈P̃n

where P̃n is the set of all n-ply polygons, an allowed n-ply polygon means thatevery edge in G is occupied by an even number of edges of the n-ply polygon,
and #P̃ means the number of edges of the n-ply polygon P̃ .
4. Reformulation based on the low-temperature expansion
Our second reformulation of (2) is based on the so-called low-temperatureexpansion. Let us rewrite (1) asP(α,β)∈B KαβZ(K) = eX Y1−σα σβxαβ 2σ∈C (α,β)∈B

where xαβ = e−2Kαβ . If we decompose the set of all spin conﬁgurations as C =C+ ∪ C− (disjoint union) where C+ = {1} × {−1, 1}N −1 , then(7)PZ(K) = 2e(α,β)∈B KαβX

Y

1−σα σβxαβ 2.

σ∈C+ (α,β)∈B

This expression can be interpreted graphically. In the rest of this section weassume that the graph G is embeddable into a 2-surface. Thus, 2-cells (cell forshort) of G surrounded by edges are well-deﬁned, and we can consider the dualof G. The dual graph G∗ of G is deﬁned as follows: place a point on each cellof G, and let V ∗ be the set of all such points; for each edge e ∈ B connect twopoints in V ∗ placed on cells adjacent to this edge e by an edge e∗ which goesacross e, and let B ∗ be the set of all such edges; then G∗ is the pair of V ∗ andB ∗ . Note that a point, an edge, and a cell in G∗ correspond to a cell, an edge,
and a point in G, respectively; and especially that an edge in G∗ can be speciﬁed
uniquely by the corresponding edge in G. Now consider a polygon on the dual

STATISTICAL MECHANICS MODEL OF SPIN GLASSESgraph G∗ and look at (7). Since½1 − σα σβ1=0245

if (σα , σβ ) = (−1, 1), (1, −1),
if (σα , σβ ) = (−1, −1), (1, 1),

we notice that there exists a one-to-one correspondence between C+ and the setP∗ of all polygons on G∗ . Thus we get
X YP(8)xαβ .
Z(K) = 2e (α,β)∈B KαβP ∗ ∈P∗ (α,β)∈P ∗To calculate the average of log of (8), we again use the replica trick. So ourtask is to evaluate
D¡ X Y¢n E(9)xαβKP ∗ ∈P∗ (α,β)∈P ∗for positive integers n. Since
hxkαβ iK = cosh(2kK)

for k = 0, 1, 2, . . .

we can rewrite (9) asX(10)Y¡¢cosh 2ναβ (P̃ ∗ )KP̃ ∗ ∈P̃∗n (α,β)∈B ∗where P̃∗n is the set of all n-ply polygons on G∗ , and ναβ (P̃ ∗ ) is the number ofedges in the n-ply polygon P̃ ∗ occupying the edge (α, β) ∈ B ∗ .
5. Example
To demonstrate how our reformulations work, we give explicit calculations forthe cyclic chain G of N points. Note that in this¢¡ computation
P caseQthe direct(without using the replica trick) is possible: since σ∈C (α,β)∈B 1+σα σβ zαβ =¢¡Q
2N 1 + (α,β)∈B zαβ , where zαβ = tanh Kαβ , andD

¡log 1 +Y(α,β)∈Bzαβ¢EK∞DX¢n E1¡ Y(−1)n−1=zαβnKn=1(α,β)∈B= −∞X¢¡
1 2mN1z= log 1 − z 2N2m2m=1

where z = tanh K, we have from eq.(3)(11)

hlog Z(K)iK = N log 2 + N log cosh K +¢¡1log 1 − z 2N .
2

46

MAKOTO IDZUMI

PQ
5.1. The high-temperature expansion. Let us denotetanh Kαβ in (5)by S, and h· · · iK by h· · · i. Since there are only two polygons (the empty and theall edges) on the cyclic chain, the computaion is straightforward. GraphicallyhS 2m i = 1 + r r r r r r+ r r r r r r+ · · · + r r r r r r
2m-ply¡2m¢ 2mN©
¡2m¢ 2N ¡2m¢ 4N
1z=z+···+z+(1 + z N )2m +It gives hS 2mi=
1+2m
422ªN 2m
2m+1(1©− z ). Similar expression
is obtained for hSi, and we get hS n i =ª1(1 + z N )n + (1 − z N )n for all n. Hence2ª 1∂
1©
log(1 + z N ) + log(1 − z N ) = log(1 − z 2N )hS n i =n→0 ∂n22
which gives eq.(11) as expected.
lim

5.2. The low-temperature expansion. The dual graph ¡G∗¢ consists¢¡ two¡ ¢ ofpoints and N edges. Since the number of polygons on G∗ is N0 + N2 + N4 +¡ N ¢= 2N −1 the computation should become more elaborate. We could. . . + 2[N/2]
not succeed in reproducing eq.(11); but we show the temporary computaions
PQ
P[N/2] ¡N ¢(cosh 2K)2ihere. Let us denotexαβ in (9) by S. Then, hSi = i=02i
and, inductively, if
X

[N/2]

hS

n−1i=X[N/2]···

k1 =0(n−1)

kn−1· · · ck11
Akn−1 ,... ,k1 cn−1

kn−1 =0

where cm = cosh(2mK), then
X

[N/2]

hS i =nX

[N/2]

···

k1 =0X X
i=0 |kkn−1 =0[N/2]·(n−1)n−1· · · ck11
Akn−1 ,... ,k1 cn−1···{zX µkn−1 ¶µkn−2 ¶}pnpn−1¶µ ¶µN − k1 − . . . − kn−1
k1···
p1p20≤p1 ,... ,pn ≤2i
p1 +...+pn =2i¡ cn ¢pn ¡ cn−1 ¢pn−1¡ c2 ¢p2 ¡ c1 ¢p1····.
cn−1cn−2c1c0©
ªFor n = 1, 2, explicit expressions can be obtained: hSi = 12 (1+c1 )N +(1−c1 )Nand¶µXXX
N
2(c2 )k1 (c1 )k2 +k3hS i =k1 , k2 , k3 , N − k1 − k2 − k3
| {z }
0≤k1 ,k2 ,k3 ≤N,k1 +k2 +k3 ≤N
k1 ,k2 ,k3 have the same parityª1©
(1 + 2c1 + c2 )N + (1 − 2c1 + c2 )N + 2(1 − c2 )N .
4
For larger n we have not succeeded in ﬁnding such explicit forms.
=STATISTICAL MECHANICS MODEL OF SPIN GLASSES

47

References[1] K. Binder and A. P. Young, Spin glasses: Experimental facts, theoretical concepts, andopen questions, Rev. Mod. Phys. 58 (1986), 801–976.
[2] S. F. Edwards and P. W. Anderson, Theory of spin glasses, J. Phys. F: Metal Phys. 5(1975), 965–974.
[3] M. Idzumi, On the partition function of the Ising model in a magnetic ﬁeld on an arbitrarylattice, J. Phys. A: Math. Gen. 26 (1993), L919–L922.
[4] M. Kac, On certain Toeplitz-like matrices and their relation to the problem of lattice
vibrations, Arkiv for det Fysiske Seminar i. Trondheim 11 (1968), 1–22.
Department of Mathematics, Faculty of Education, Shimane University, Matsue 690-8504 JAPANE-mail address: idzumi@edu.shimane-u.ac.jp