 

 

 

.15;

1.5.!

It: .3
.

.

9.:

Mn,

1 1
Ed

. 3‘13‘5.‘
I23. 1 P.1d. 13:
1....ll‘ Xv)...

‘. 1.8. x

3. xs¥vxxr.’..3:.4
)5}: 31.19: i ‘

‘ thunk.

 

343.
”13‘.“

la;
:1 \.
.313;

5“... v1.6“.
.ﬁwa. gum“ .

“art... 1
s. ‘

Ila:- 1‘»
A a. in ﬁgs...»
5:03"... 1. I! I
. .u .13.. 54.39..
fin. 3....

5‘3... u

i
2... a...
, up 31!».
9.2.
.. "iii!
, .

.53. a

.ﬁ...

. .A ..
.Igi‘u.‘ w
3.3.3.. .. I. . ...
..:i..qa;lz.4su.v..txiuz ! 3 k
. . I . .v ..
gDiatﬁur I 1“

baa...
:3.
.uNi a! {It 0

3.1.... ..|..v..

I! 1.: l3.- . O3!
:.I..l§:!. l)7...9aa§i..x‘01
(4...!lii‘111lltti

THE-SIS

4 007’

This is to certify that the

dissertation entitled

Exact Ground States
Of Disordered Systems

presented by

Jan Hermann Meinke

has been accepted towards fulﬁllment
of the requirements for

Ph . D. degree in Physics

WW

Major professor?

 

 

Date S] 3/002

MS U is an Afﬁrmative Action/Equal Opportunity Institution 0' 1 2771

 

 

LIBRARY
Michigan State
University

 

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/CIRC/DateDue.p65-p.15

 

 

 

EXACT GROUND STATES OF DISORDERED SYSTEMS

By

Jan Hermann Meinke

A DISSERTATION

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Physics and Astronomy

2002

Abstract
EXACT GROUND STATES OF DISORDERED SYSTEMS
By

Jan Hermann Meinke

Finding the ground state of disordered systems is in general a hard problem. Mappings
of disordered systems to problems from computer science for which efﬁcient, i.e., polyno-
mial algorithms are known allow the numerical study of large systems. I study the ground
state of the random-ﬁeld Ising model both analytically using mean ﬁeld approximations
and numerically in 3D. I ﬁnd that the behavior for the inﬁnite-range model is nonuniver-
sal in the sense that the critical exponent E can vary continuously. On the Cayley tree ,
however, the behavior is universal.

I develop a theory for the roughening of the minimum energy fracture surface in poly-
crystalline materials as a function of the relevant energy parameter c = 61/69. 69 is the
internal binding energy of the grain and e,- is the adhesion energy. Both local and global
effects contribute to the toughening and have to be taken into account. This leads to an
e-dependent critical length LC. For systems with L > LC and e < 1 the interface is always

rough.

Contents

List of Tables vi
List of Figures vii
1 Disorder and Complexity 1
2 Analytic Methods and Concepts 10
2.1 Critical exponents and scaling theory ..................... 11
2.1.1 The scaling hypothesis ........................ 13

2.2 Ising model .................................. 17
2.2.1 Mean ﬁeld theory ........................... 20

2.2.2 Inﬁnite range model ......................... 24

2.2.3 Cayley tree .............................. 25

2.2.4 Renormalization group and universality ............... 26

2.3 Landau theory ................................. 29

2.4 Percolation .................................. 32
2.4.1 Cayley tree .............................. 35

2.4.2 Giant clusters in random graphs ................... 38

3 Paths, Domain Walls, and Spin Clusters in Random Media 40
3.1 Domain walls and random bonds ....................... 41

iii

3.2 Spin clusters and random ﬁelds ........................ 42

Maximum F low/Minimum Cut 44
4.1 The maximum ﬂow/minimum cut theorem .................. 44
4.2 Mappings to the maximum ﬂow/minimum cut problem ........... 46

4.2.1 Finding the interface in a random-bond Ising model with ﬁxed
boundaries .............................. 46

4.2.2 The mapping of the random-ﬁeld Ising model to the maximum

ﬂow/minimum cut problem ...................... 48

4.3 Algorithms for solving the maximum ﬂow problem ............. 50
4.3.1 The augmenting path algorithm ................... 50

4.3.2 Push-relabel .............................. 52

4.4 Benchmarks .................................. 54
Random-Field Ising Model 56
5.1 Inﬁnite—range random-ﬁeld Ising model ................... 57
5.1.1 Bimodal distribution ......................... 60

5.1.2 Gaussian distribution ......................... 61

5.1.3 Polynomial distributions ....................... 62

5.1.4 Finite temperature .......................... 65

5.2 Cayley tree .................................. 66
5.3 Numerical ground state calculations of the RFIM .............. 69
Interfaces in Disordered Systems 76
6.1 Models and methods ............................. 77
6.2 Weak adhesion limit 6 ——> O .......................... 81
6.3 Strong adhesion limit . .. ........................... 84
6.4 Intermediate regime .............................. 87

iv

6.5 Summary ...................................

7 Outlook

A Taylor Expansion of P+ for the RF IM on the Cayley Tree

Bibliography

Index

96

97

99

104

110

List of Tables

2.1 The standard set of critical thermal exponents ................ 12
2.2 Scaling relations between the critical exponents ................ 17
5.1 Benchmark results for the random-ﬁeld Ising model ............. 70

vi

List of Figures

1.1
1.2
1.3
1.4

2.1
2.2
2.3
2.4
2.5

4.1
4.2
4.3

5.1
5.2
5.3
5.4
5.5
5.6

Computer network ..............................
Network graph for computer network in Fig. 1.1 ...............
Tunable random distribution .........................

Magnetization for different distributions of random ﬁelds ..........

Phase diagram of water ............................
Graphical solution of the magnetization in mean ﬁeld theory. ........
Cayley tree with 2:3 .............................
Kadanoff’s block spins for an Ising model ..................

Percolation on a square lattice ........................

The minimum cut in a random-bond Ising model ..............
Mapping of a 1D random-ﬁeld Ising model to the maximum ﬂow problem .

Push-relabel Benchmarks ...........................

Tunable random distribution .........................
Magnetization for different distributions of random ﬁelds ..........
Maximum execution time vs. L ........................
Maximum standard deviation of the magnetization .............
Finite size scaling of critical width ......................

Scaling plot for the magnitude of the magnetization for p4 with y=0.5

vii

7

10
22

27

63

71
72
73
74

5.7

6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9

Scaling plot for the magnitude of the magnetization for p4 with y=-O.5 . . . 74

2D Grain Structure .............................. 78
Grain structures with interface ........................ 80
Scaling in the weak adhesion limit ...................... 82
Fraction of grain boundary bonds of the interface vs. 6 ........... 85
Average interface energy vs. 6. ........................ 86
Average roughness vs. 6 ............................ 87
Average number of interface bond vs. 6 ................... 88
Interface through granular material. ..................... 89
Scaling of roughness ............................. 94

viii

Chapter 1

Disorder and Complexity

The white elephant of the king moved graceﬁtlly through the jungle. He brieﬂy paused to
take a drink of water from the pond near Ibn Assam ’s village and then moved on with steady
step.

A few days later the elephant was stricken with a terrible illness. None of the king’s
learned medics could ﬁnd a cure. Ibn Assam, a poor farmer; offered his services to the king.
The king was so desperate that he accepted and promised to grant him a wish if he healed
his elephant. Ibn Assam had seen the king’s elephant drink from the poisonous pond and
had brought some of the herbs he used to heal his goats. After a week’s time the animal
was on his way to recovery and the king asked Ibn Assam what he wanted as reward.

“Sire, just grant me a single grain of wheat for the ﬁrst square of this chessboard and
two for the second and double it for each following square,” answered Ibn Assam. The king
thought this a modest reward for the health of his elephant. He told his servant to bring a
bag of wheat. The servant put a grain of wheat on the ﬁrst ﬁeld, two on the second, four on
the third, eight on the fourth, sixteen on the ﬁfth, thirty-two on the sixth, and still the king
was smiling. The servant went on and soon another bag of grain had to be brought and

another and another. The king was not smiling anymore.

To ﬁll the chess board with the promised grain the king would need 265 — 1 grains or
over sixty-three million times the world’s production of wheat in 1999. This problem was
ﬁrst posed by Ibn Kallikan, a 13th century mathematician. It has since been used in many
tales like the one above. Exponential growth didn’t ruin only the king. It is also one of the
challenges for computational physics.

Many interesting problems are disordered and have a complicated energy landscape.
Imagine you want to ﬁnd the lowest valley in the Rocky Mountains by randomly wander-
ing through the valleys and mountains. It is much easier to stay in a valley than cross a
mountain so you will tend to spend a lot of time in one valley to make sure you didn’t miss
a spot before you’ll climb up the next mountain. Finding the ground state of a spin glass is
such a problem.

A spin glass is a system of spins that can be either up or down. The interaction between
two spins either wants to align or antialign them. Often a spin is frustrated. It wants to
be both up and down due to its neighbors. The time it takes to ﬁnd a solution increases
exponentially like the number of grains on the chessboard. If the solution for 4 spins can
be found in a few seconds, the solution for 16 spins might already take several hours.

The spin glass belongs to a group of problems that in computer science is known as
Nondeterministic Polynomial or NP. A solution for NP problems may be hard to ﬁnd but
is easy to test. Other problems in this class are the Traveling Salesman or the Vertex Cover
problem. Many of these problems are important in practice. Imagine, for example, you
want to protect a computer network from viruses by ﬁltering trafﬁc between computers
(Fig. 1.1). The virus protection program should be installed on the smallest number of
systems possible to minimize overhead. To be effective every connection between com-
puters has to be covered, i.e., at least one of the computers connected must have the virus
protection program. This problem is equivalent to ﬁnding the minimum vertex cover in

the network graph in Fig. 1.2. The computers are the vertices and the connections are the

 

 

 

 

 

 

 

Figure 1.1: Computer network

edges.

The complement of the minimum vertex cover is the maximal independent set. It con-
sists of those nodes that do not share any edges. In Fig. 1.2 the ﬁlled dots mark the vertex
cover. The unﬁlled nodes are the corresponding independent set, which is equivalent to a
lattice gas [57].

Recently the minimum vertex cover and other NP problems have attracted the interest
of physicists. Using methods from statistical physics they ﬁnd a phase transition. This
phase transition, indicated by a critical slowing down of the computation, separates easy
instances of the problem class from hard instances [21, 56, 57, 58].

Polynomial problems P can be solved efﬁciently. The time to ﬁnd a solution scales with
the system size, i.e., t ~ N1 where N is the system size. A subset of NP problems can
be mapped onto each other via polynomial algorithms. The subset is called NP-complete.
NP-complete problems are among the hardest problems in computer science. As more and
more problems are added to this class it is becoming increasingly unlikely that somebody

will ﬁnd an efﬁcient way of solving them. One hope is that quantum computing will provide

3

 

O

 

Figure 1.2: Network graph for computer network in Fig. 1.1. The ﬁlled dots mark a
possible vertex cover.

new and efﬁcient algorithms, but so far no polynomial quantum algorithm for N P-complete
problems has been published. But if we ﬁnd an efﬁcient solution to any NP-complete
problem, all NP-complete problems are polynomial. All polynomial problems are also
NP problems since their solution can be checked in polynomial time. The question if all
problems in NP are also in P is still open. The Clay Mathematics Institute named this
question one of the seven Millennium Prize Problems and allocated one million dollars to
the answer for each of the seven questions [12, 43].

Often there are sub-classes of NP problems that can be solved efﬁciently. For example,
the spin glass in 2D can be solved by matching [3]. Other problems may seem hard for
a long time until a new way of solving them is discovered. Among these is the random-
ﬁeld Ising model. In addition to the spin-spin interaction of the spin glass, it contains local
random ﬁelds at each site. The interactions, however, are all ferromagnetic and want to
align neighboring spins. The energy landscape of the random-ﬁeld Ising model is very
complex. At ﬁrst Monte Carlo simulations were used to ﬁnd the lowest energy state.

Monte Carlo simulations work like the traveler that wants to ﬁnd the lowest lying valley

in the Rockies. It wanders through the energy landscape by changing the orientation of a
spin at random and checking if the energy is lower. If the energy is lower, the change is
accepted; if it is higher, the change is accepted with some probability depending on the
temperature. The time the algorithm needs to ﬁnd the global minimum increases expo-
nentially with the system size and it gets harder and harder as the temperature approaches
zero. In 1986 Ogielski published a revolutionary paper [39] where be solved the T=0K
(z —273°C) random-ﬁeld Ising model using a polynomial algorithm: the maximum ﬂow
algorithm.

The maximum flow algorithm ﬁnds the maximum ﬂow from a source to a target in a
graph. This graph could represent the streets of a city, a network of water pipes, or the
Internet. Each edge in the graph has a capacity, e.g., the number of cars that can pass
through a street segment per minute.

As we have all experienced, it doesn’t matter how wide a freeway is if there is a road
construction that limits the trafﬁc to one lane. This bottleneck determines how many cars
can get through. In fact it can be proven that the maximum ﬂow is exactly equal to the
capacity of the bottleneck, the minimum cut. The geometry of the minimum cut can still
be complex but that does not slow the algorithm down.

I used the maximum ﬂow algorithm to study the ground state properties of the random-
ﬁeld Ising model as well as the minimum energy fracture surface in polycrystalline materi-
als. In both cases the minimum cut is the interface in the system.

The random-ﬁeld Ising model is an important model for the study of complex system.
It also models diluted antiferromagnets in a ﬁeld, which play an important role in modern
magnetic storage devices. The critical point of a phase transition is key to understanding
the transition. The behavior near the critical point is often independent of the details of the
system. Only the dimensionality and the symmetry of the order parameter matter. This is

called universality. For the random-ﬁeld Ising model the disorder critical point is the width

of the random distribution of random ﬁelds at which the magnetization goes to zero because
the system becomes disordered. Many expected the random-ﬁeld Ising model transition to
be universal, but the matter is still debated. Phil Duxbury and I showed that for an inﬁnite-
range random-ﬁeld Ising model the approach of the magnetization to zero is not universal.
In the inﬁnite-range model spins don’t just interact with their neighbors, but equally with
all other Spins. In computer science this is called a complete graph because all nodes and
edges in the graph are present. In an inﬁnite—range model all spins are equivalent. This
makes ﬁnding the ground state much easier.

The spins are trying to fulﬁll two conditions. They want to align with all the other spins
and they also want to align with their local ﬁeld. Usually this is not possible for all spins. In
the ordered phase some spins have to pay the price for not aligning with their local ﬁelds.
Since all spins have equivalent spin-spin interactions, these are the spins with the weakest
local ﬁeld. Based on this argument we can set up an equation for the magnetization m and
ﬁnd its behavior near the critical point where m goes to zero. For a universal system the
behavior does not depend on the distribution of random ﬁelds. We found a distribution,
however, (see Fig. 1.3) that allowed us to obtain any behavior near the critical point (see
Fig. 1.4). This nonuniversality does not extend to Cayley trees - another model that often
can be solved analytically - nor to 3 dimensions. In 3D I used the maximum ﬂow algorithm
to ﬁnd ground state conﬁgurations. The behavior of the magnetization near the critical
point is the same for different distributions. The correlation length, a measure of how many
spins have to act in concert, is, on the other hand, not universal. For distributions with
large ﬁelds that can ﬂip a spin by themselves, the correlation length is shorter than for
distributions where many local ﬁelds have to act together to ﬂip a small cluster.

We encounter polycrystalline materials all the time. Most metals are polycrystalline.
Polycrystalline diamond ﬁlms cover drill bits and the scanners in super markets. High—

temperature superconductors are ﬁnding more and more applications, e.g., in MRI (Mag-

2.5

1.5 ~-

1 g

l ' l

-l -0.5 0 0.5 l

 

\
CD

Figure 1.3: Tunable random distribution. P(h) = 221% (1 — (lg—IV) for y=l/20 (top), 1
(middle), and 20 (bottom).

 

A. A La 1 r H
0.5 l 1.5 2 2.5 3

 

 

Figure 1.4: Magnetization for different distributions of random ﬁelds. This shows the
y
magnetization for P(h) = ﬁ—l (1 — (LIZ—l) ) with y=2 (left), 1 (middle) and 1/2 (right)

2Hy

netic Resonance Image) scanners and in the Maglev trains developed in Japan. High tem-
perature superconductors are ceramics, which are by their very nature polycrystalline. We
wanted to know how easily a polycrystal breaks, how rough its fracture surfaces are, and
what the mechanism for roughening is. To study these properties we introduced two en-
ergy scales: the internal binding energy of the crystal grain and the adhesion energy. By
varying the ratio of these two parameters we studied the roughness, energy, and location of
the interface.

Roughening occurs on two length scales, locally and globally. The interface roughens
locally by following grain boundaries that only deviate marginally from the straight cleav-
age line. This effect becomes stronger as the adhesion becomes weaker until the interface
can follow any grain boundary at very weak adhesion.

To be in the lowest global energy state the interface must take advantage of ﬂuctuations
of the grain boundary angles. Some regions have a larger than average fraction of grain
boundaries that are close to the cleavage direction, others have a smaller than average
fraction of low angle grain boundaries. To take advantage of the low angle regions and
avoid the large angle ones, the interface has to wander. These mechanisms combine to give
an accurate description of our simulation data.

As we increase the average grain size the interface becomes increasingly rough. But it
doesn’t do it randomly. In 2 dimensions the roughness increases with the third root of the
average grain size. Physicists call this a power law behavior because it can be written as
roughness proportional to g to the one third power or 21) ~ 91/3. Many quantities follow
power laws. The energy necessary to form the interface, for example, increases with the
d-l power of the system size: E ~ Ld‘l. dis the dimensionality of the system.

The behavior with respect to the adhesion energy is not as simple. For weak adhe-
sion (adhesion/binding energy < 1/2) the interface stays rough. As the adhesion becomes

stronger and stronger the interface becomes ﬂatter. It becomes less favorable to go around

the grain. Recalling the mountain picture from before: once the hills become ﬂat enough
it’s not worth going around them anymore. The interface cleaves the grain rather than
taking the long way.

When the adhesion and grain binding energies are almost equal, the interface is ﬂat on
large length scales. This length scale is often called a critical length. The interface has to
be at least as long as the critical length before you can tell that it is not ﬂat.

The approach to ﬂatter and ﬂatter interfaces does not follow simple power laws. We
can, however, make approximations near the point where the two energies are equal that
give a good description of the behavior in terms of power laws. The energy, for example,
increases linearly as we approach this point. Other quantities depend on the distribution of

angles of grain boundaries within the sample.

Chapter 2

Analytic Methods and Concepts

Whenever physicists encounter a new problem they try to develop a model that is as simple
as possible but still captures the essential features of the system. Often these models are one
or two dimensional cases, or mean ﬁeld theory, which corresponds to inﬁnite dimensions.
For thermal phase transitions these cases often give insight into the qualitative behavior in
three dimensions. But sometimes they can be deceiving.

Best known - if not best understood - is the phase transition of water. At low temperature
(T < 0°C) water is a solid called ice. As temperature increases it melts and turns liquid.

At temperatures above 100°C it starts boiling and becomes a gas. The solid-liquid and

P11

Liquid
Solid

Triple point

 

Figure 2.1: Phase diagram of water (Cf. [48])

10

solid-gas transitions are example of ﬁrst order phase transitions. The liquid-gas transition
is second order above PC and Tc. The characteristic feature of ﬁrst order transitions is that
the phases can coexist. In a second order transition, on the other hand, the two phases are

indistinguishable at the transition point.

2.1 Critical exponents and scaling theory

To capture the nature of a phase transition we deﬁne an order parameter. This could, for
example, be the difference in volume between the liquid and the gas phase for a liquid-gas
transition or the magnetization for a ferro- to paramagnetic transition. The order parameter
is chosen in such a way as to be zero at the phase transition [53].

We characterize the phase transition by the behavior of the order parameter near the

critical point. More explicitly, one introduces a power law

f0+ *x‘Af, :1: > 0
M) = A,
f0_ * :1:— f a: < 0
where /\f is the critical exponent of the function f with respect to a: for a: > 0 and A’, is
the critical exponent for a: < 0. In practice there are often higher order corrections needed

to accurately describe f (1"). Therefore an alternate deﬁnition of the critical exponent is

frequently used:

 

A, = lim Inf”)

. 2.1
I—>0 ln(—f£) ( )
In this deﬁnition all correction terms vanish in the limit. It has, in addition, a very practical
interpretation. The critical exponent is the slope of f (:12) near the origin in a log-log plot.

In many cases the critical exponents do not depend on the details of the system under

study but only on the symmetry of the order parameter, the spatial dimension, and the range

11

 

 

 

 

 

 

 

[ Symbol ] Description 1 Deﬁniton Mean Field ]

- T—TQ ’0

or Specrﬁc heat exponent C ~ ( Tc ) 0

3 M ‘ ‘ T—T ’3 l

agnetrzatron exponent m ~ -—£TC -2-
‘7

c," Susceptibility exponent XT ~ (2%) 1

6 Critical isothermal exponent M ~ H i“ 3

1/ Correlation length exponent 6 ~ $27—33 %

 

 

 

 

 

 

 

Table 2.1: The standard set of critical thermal exponents

of the interactions. This is called universality.

Several exponents denoted by a set of Greek letters are commonly used . The most im-
portant for my thesis are the magnetization exponent ﬂ and the correlation length exponent
V. For a summary of exponents and their deﬁnitions see Table 2.1.

The critical exponents are not all independent of each other. Some of the relations
follow immediately from thermodynamics; others require additional assumptions about the
scaling behavior of thermodynamical functions. I will use the scaling hypothesis to derive
some of these relations.

An important function in statistical physics is the partition function (or “Zustandsfunk-
tion”, lit. function of state), which describes the system. A system is considered solved if

there exists a solution for the partition function. It is deﬁned as

Z: Z exp(—i37-l) (2.2)

{all states}

where 13 : l/(kT). k is the Boltzmann constant (1.38 * 10‘23J/K). T is the temperature
in Kelvin and H is the Hamiltonian.

From Z we can obtain the free energy

Free energy, F = —lenZ (2.3)

12

and the relevant derivatives:

R-Iagnetization, M : —§% (2.4)
Susceptibility, X = %% (2.5)
Internal energy, U = F — Tg—i (2.6)
Heat. capacity, C = T2g—Zf—2 (2.7)

2.1.1 The scaling hypothesis

There are two approaches to the scaling hypothesis. The ﬁrst one is motivated by the
physical argument that sufﬁciently close to the phase transition the correlation length, 5, is
the only relevant length scale. A simple dimensional analysis leads to the scaling laws (see,
e.g., [25]).

The second approach is more mathematical in nature and assumes that thermodynamic

functions are homogeneous functions. A function is homogeneous if

V?" f(/\7‘) = QWflt‘)

where g is limited to the form 9 : AP with p the degree of homogeneity. This expression can
be generalized to multiple independent variables, f (Ax, Ag) 2 A” f (3:, y) or even slightly

more general

fWI, A’y) = Af0»: 30- (2.8)

13

Note that this is the most general form of this equation. It cannot be further generalized by
adding an exponent on the right hand side.

Now assume that the free energy deﬁned in Eq. (2.3) is a homogeneous function

F(/\“‘e, W H) = Ara, H) (2.9)

where e = (T — TC) /TC. Following Stanley’s treatment [48], differentiate both sides of the

Eq. (2.9) with respect to H

xauarwe. A“"H)/0H = Aara, H) /aH.

Since 8F/8H : —M (cf. Eq. (2.4)) this is equivalent to

—A“’”M(A“e, /\“"H) = Ali’1(€, H). (2.10)

There are two exponents associated with the magnetization (see Table 2.1) , ,8 and 6. To

get 6 set H = 0 and let 6 —> 0, then Eq. (2.10) becomes

Map) : AaH-li’i”1()\a‘€,0). (2.11)

Since Eq. (2.11) holds true for all values of A it must be valid for A = (—1/e)1/°<.

Therefore

lif(e,0) = (—e)(1'“”)/“‘M(—-1,0)
and from the deﬁnition of the magnetization exponent we have

1 — an
[3 Z .

ac

 

l4

Similarly to obtain (5 set 6 :- 0 and let H —~> 0,

11(1), H) = A“”‘1.11(0,A“”H).

Choosing A = H‘l/aH this becomes

.11(0. H) = H“‘“”)/“” 11(0, 1)

and from the deﬁnition of (5 we have

 

6 — a” (2.12)

—1-—aH’

The remaining exponents can also be related to the unknown scaling parameters a(
and a”. For example differentiating Eq. (2.9) twice with respect to H we obtain, using
Eq. (2.5),

A20“X'(Aa‘e, AOHH) = Ax(c, H).

For H = 0 and A = (—c)‘1/“‘ this becomes
x = (-6)“2“”"’/“‘X(—1~0)

for 6 —> 0 using the deﬁnition of 7'

2. —1
,7: “H . (2.13)
a6

 

Now there are three different exponents deﬁned by two unknowns. Expressing a ,1 and

15

a. in terms of ,3 and 6 one can rewrite 2) as

yzsw—r) (2M)

This is known as the Widom equality. The Widom equality can be rigorously derived as an
inequality from thermodynamic relations. That it is satisﬁed as an equality is a prediction
of the scaling hypothesis.

Similarly differentiating Eq. (2.9) twice with respect to 6 leads to

Aga‘C(A”‘e, A"H H) = AC(6, H).

Again, since this equation is true for all A it has to hold for the particular choice of A =

(1/6)1/“‘. Setting H = 0,

From the deﬁnition of a,

2,—1
a: a . (25)
a.

 

Combining Eqns. (2.12), (2.13), and (2.15) one obtains

or + 213 + 7 = 2, (2.16)

which is known as the Rushbrooke equality.
As mentioned earlier, another way of deriving scaling relations is through dimensional

analysis. First note that F / [CT is dimensionless and F / kTV is therefore of dimension

16

 

 

 

 

 

7 — 13(6 —— 1) Widom equality
2 = a + 2.3 + 'y Rushbrooke equality
2 = a + 13(1 + (5) Grifﬁths equality
(11/ = 2 — a Josephson law

 

 

 

Table 2.2: Scaling relations between the critical exponents.
length—d. g is the only relevant length scale near the critical point, thus

F N g—ud.

kTV

Comparing this with the deﬁnition of a we see that
2 — a : I/d. (2.17)

Eq. (2.17) is called the Josephson law. Scaling relations that include dimension are often
called hyperscaling relations.
Other relations can be derived in similar ways. Table 2.2 lists some of the more impor-

tant 01168.

2.2 Ising model

The Ising model was introduced by W. Lenz in 1920 [36]. He suggested it to his student E.
Ising as his Ph.D. thesis topic. Ising solved the 1D Ising model as part of his thesis in 1924
[29] and the result was published in 1925 [30].

To their great disappointment they did not ﬁnd a phase transition except at T=0K. For
any ﬁnite temperature the 1D Ising model is a paramagnet. This was surprising since the
importance of dimensionality for phase transitions had not been discovered yet.

Although introduced by his adviser the name “Ising Model” stuck. The term seems to

have ﬁrst been coined by R. Peierls in 1936 [40] (see [35] and references therein).

17

The Ising model is a two state system with ferromagnetic interactions between sites,
i.e., neighboring sites prefer to be in the same state. Commonly it is viewed as a spin

system where each spin can take only two values, 3 = :tl. The Hamiltonian is
_ _:Jij5i3j (2.18)
0'

Finding the partition function for the 1 dimensional chain is beautifully simple. To ease

notation let J,,+1 —> J, . The partition function is then

Z = Z Z .2 exp(ﬁZJs,s,+1)

{$12i1}{52=:t1} {SN Zil}

N—2
: Z Z "' 2 9X1)” 2 Ji3i3i+1)COSh(,BJN_-1S,).
{S1=i1} {.SQZiI} {SN_1::i:1} i=1

Since cosh is an even function the Sign of sN_1 does not matter and one gets

N-—2
Z = Z Z --- Z exp(,3 Z J,s,s,+1)2 cosh(,3JN_1)
{$1=i1} {S2=i1} {8.v-r=i1} i=1

N—l
= 2: H 2cosh(,3J,-)

{slzil} i=1
where the last sum just contributes another factor of two. The partition function is thus
N—l
Z : 2N H cosh(gBJ,)
i=1
or for the case of uniform .1,

Z = 2N coshN—1(13J).

To ﬁnd the critical point for the magnetization without ﬁeld, it is useful to analyze the

18

spin-spin correlation function 11(7).

Pk”) = <5k5k+r>

where
1 N—l
(31'3k+r> :- E Z 3k19k+r €Xp(—)’3 Z J,s,s,+1). (2.19)
is} .=1

The sum over {5} stands for the sum over all states. The above formula takes advantage of

the fact that the average of any observable :r: can be calculated as

1 ,
(.13) : Z Z :rexp(—,d7-l).

all states

For r = 1 Eq. (2.19) becomes
1 N—l
<3k3k+1> = Z Z 3k3k+l €XP(—»3 Z Jr3r81+1)
{s} i=1

1 a ”’1
: 2 g 5:];- exp(—,B 12:; Ji3i31+1)

1 8
——Z.
ZBJ),

For r = 2 it is almost the same. Note that sksk+2 can be written as sksk+13k+13k+2,

 

 

thus
1 N—l
(81181”) = Z {2; 3k3k+13k+13k+2 (KM—2’3 Z; Jisr'si+1)

1 0 8 N—l

= — — ' ‘3 Ji-‘z' 1
Zgarjkaqjk+1ehp( 1 ; 58+1)

_ 1 a a

— 28.1), 0Jk+1 ’

19

This can be generalized for any r to

 

1 (9 ('9
r :__... z_
8“” 1 2 EU. map.
For the case .9 : i1 this is
(3,3,...) = H tanh ﬁJk+,_1. (2.20)
i=1

When does long range order set in? For long range order the following must hold true

lim (.sk.sk+,) > 0.
T—iOO

The hyperbolic tangent is less than one for any ﬁnite argument. The product in Eq. (2.20)
therefore goes to zero at any ﬁnite temperature. But, when T = 0 => )3 = 00 :> tanh 5.] =
1 so that at T = OK, the magnetization jumps from 0 to l.

The solution for the 1D Ising model chain in an external ﬁeld can be found using the
transfer matrix method, which also forms the basis for the solution of the 2D Ising model
without external ﬁeld. The 2D Ising model does have a ﬁnite temperature phase transition
at TC 2 2.269J/k [25].

For higher dimensions or for the 2D case with ﬁeld, no exact solution has been pre-
sented so far. There are, however, many approximations and numerical methods that can

provide insight into the nature of the phase transition.

2.2.1 Mean ﬁeld theory

In mean ﬁeld theory the interaction between spins is approximated by an effective ﬁeld

proportional to the average magnetization. It is therefore useful to ﬁrst solve the non-

20

interacting spin system in a ﬁeld. The Hamiltonian is

H: —HZS,'.

The partition function is

Z Z Z exp(,3HZs.-)

{Si—1:111}
= 2NcoshN/1’H.

The free energy is F = —kT 111 Z and the magnetization M = —(8F/8H)T,

a
A = —
I a H kT 1n Z

_ kT'BzNN coshN—1 EH sinh 13H
— ’ 2N coshN 6H
: N tanh ,BH

 

I I
A

2 MO

 

= tanh )BH

Til

In mean ﬁeld theory, the effective ﬁeld is H83 2 H + Am, where A is called the

molecular ﬁeld parameter. Replacing H by Heff we get

at = tanht3(H + Am). (2.21)

Eq. (2.21) is an implicit equation. For H = 0 it can easily be solved graphically (see
Fig. 2.2). The ﬁgure shows that m = 0 is always a solution and that there are non trivial

solutions only if the slope of tanh(,8Am) at m = 0 is greater than 1. To determine when

21

 

Figure 2.2: Graphical solution of the magnetization in mean ﬁeld theory. The solution of
Eq. (2.21) is the intersection of the two graphs. In the above plot A = 1.5. For A < 1 only
m = 0 remains a solution.

22

 

this is the case expand the right hand side of Eq. (2.21) to ﬁrst order around 0.

tanh(3Am) 2 t3Am+O((/3/\m)3)

A
:A3>1® —>1

k‘T
A
— T
<=> k >
A
TC : —. 2.22
k < )
To ﬁnd the critical exponent for the magnetization )3 introduce T = % = §T and expand

the right hand side of Eq. (2.21) around 0.

m 1771.3
m. 2 7:: + —~— +

1 ~
772.2 3 (1— :) T3
T

| 2

I2
OJ
ﬁler
”:12
I

 

12
DJ
A
ﬂit]
V
A

H
,5 1
1‘3
V

thus

 

so that )3 : 1/2.

23

2.2.2 Inﬁnite range model

In 1968 Kac showed [33] that mean ﬁeld theory can be interpreted as a system with inﬁnite

range interaction. For the Ising model the inﬁnite range Hamiltonian is

2
J
”H = ‘1? (Z 3,) + J. (2.23)

i
The partition function is

ZN : Zexp(,’3(J/N)(Zs,) +15’J)

{3,} i

: ef’JZexpmJ/N (23,) ).
{3,}

i

Using the identity

/00 exp(—(1.12 + 12.17) = (Mr/a, exp(b2/4a) (2.24)

00

with a. : N/4J1'3 and b2 = (Z, 3,)2 the partition function can now be written as

ZN 2 3J2/ exp( —4J,'3x 2+Zs,:r)dzr:

 

. 00 V . r
= :‘H/ exp(—411’}’11311.'2’)2’V coshA 2:012:

At large :1: the ﬁrst term of the integrand dominates. It is proportional to exp(:rQ)
whereas the second term only goes like exp(:r). This suggests the saddle-point method,

or method of steepest descent [48, 6]. In the saddle point method the integral is replaced

24

by the largest value of the integrand in the interval. The free energy is thus

F 2 —kT(1’3J +1n _£§§wexp(—%T2)2N coshN :r) (2.25)

Since the logarithm is monotonically increasing we can ﬁnd the maximum of the inte-

grand by ﬁnding the maximum of the logarithm of the integrand.

N 2
; I: —_ ’ N’Y ’ '
f( 1:) 4:3]:1 + 1 ln(2 cosh z) (2 26)

Nr+ 2sinh:1:
2,8] ’ 2cosha:

l

= _2,BJ +Ntanhr

 

 

’V
0 = —2’BIJ+Ntanh:1:

ZﬁJtanh :1:

 

a
I I

This is recognized as essentially the mean ﬁeld equation for the magnetization with H = 0

(cf. Eq. (2.21)).

2.2.3 Cayley tree

The Cayley tree, or Bethe lattice, is another solvable model that usually gives mean ﬁeld-
1ike behavior. To construct a Cayley tree start at a node 0 and add 2 neighbors. To each
neighbor add z-l neighbors and so on (see Fig. 2.3). Each interior node has 2 neighbors and

each leaf node has only 1 neighbor. Often instead of z the number of children a = z — 1 is

25

   

st Generation

Figure 2.3: Cayley tree with 2:3

used to describe the tree.

A Cayley tree with z = 3 and 3 generations, for example, consists of 10 nodes of which
6 are on the surface. For larger and larger Cayley trees the ratio between the number of
leaves, the nodes on the surface, and the total number of nodes goes to (a — 1) /a and not
to zero as it does for more conventional lattices for d < 00. In that respect the Cayley tree
acts like an inﬁnite dimensional lattice. For 2 ——> 00 it can be shown that the Cayley tree

usually gives the same results as mean ﬁeld theory.

2.2.4 Renormalization group and universality

In 1966 Kadanoff [34] presented an intuitive picture on how to rescale the Ising model. He
suggested to successively group the spins in blocks with a volume bd, where b is the length
of the block and d is the dimension. Each block of spins is then assigned a spin, e. g., the
average spin value with some spin chosen as tie breaker. Then the Hamiltonian is rewritten
in terms of these “block spins”. He considered only nearest neighbor interactions for the

spins as well as the block spins. This technique is based on the idea that for distances

26

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l, / / 21/

Figure 2.4: Kadanoff’s block spins for an Ising model. The shaded 3x3 block of spins on
the left becomes a single block spin on the right.

much smaller than the correlation length 6 the spins should act in concert. The method is
illustrated in Fig. 2.4.
Although this method provides a nice visualization, the restriction to nearest neighbor

interactions makes it all but useless for practical calculations. Thus it is necessary to include

all possible interactions and write the Hamiltonian in its most general form.

H(K,{8i},N) =K0+K128i+KQZSiSj+K3ZSiSj'i—K4 Z Si8j8k+...

r ”(1) 1312) ijk“)

where the (n) at the indices indicates summation only over the nth nearest neighbors. The

partition function is thus
Z(K, N) = :exp(—7-l(K, {3,}, N)).
{5.}
Now introduce blocks and sum over the spins inside the block 0,.

Z(K,N) = :exp(—H(K,{sl,01},N))

81,0!

= Z€XP(—H(KL3{81}2NL—d))-
{31}

27

Note that the partition function in terms of the block spins has the same form as the original

partition function. K and K L are related by the transformation

Since the Hamiltonian has the same form as before, the process can be repeated for larger
and larger blocks.

KnL : T(K(n—1)L) (227)

If the system is not at the critical point, the correlation length 6 will get smaller and
smaller with each successive rescaling. Therefore the system moves further and further
away from criticality. If the system is critical, however, 5 remains inﬁnite. The transforma-

tion T can no longer change K. For such values K‘,

K“ = T(K*). (2.28)

T is called the renormalization group although it is only physically relevant as a semi-
group since the inverse of T, the unblocking of block spins, has no physical interpretation.
K“ is called a ﬁxed point of the transformation.

To learn more about the behavior of the system near a ﬁxed point subtract (2.28) from
(2.27),

KnL - K’ = R(K(n—1)L) “‘ K’-

For 11 >1 one can make the linear approximation

R(KnL) : R(K*) + W(KnL _ K*)

where W is a matrix with the elements

6R0
8K3 KzK' ’

W05 2

 

The eigenvectors of W ua can be used to represent the coupling-constant vector KnL.

The new coordinates are

an : Z ua(KnL — K*)a-

The eigenvalues A0, determine the behavior of the associated coordinate under renormal-
ization group transformation. For A0 < 1 the coordinate moves towards the critical point.
For A0 > 1 the coordinate moves away from criticality. The critical surface in K space
is deﬁned by 1),, = 0 for all Aa > 1 with K" as the origin. All systems with K in the
critical plane will approach the same ﬁxed point under successive renormalization group
transformations and belong to the same universality class and have the same critical expo-
nents [42, 25]. Often the latter part of the previous statement is used to deﬁne a universality
class: Systems that show the same critical behavior and thus have the same critical expo-

nents belong to the same universality class.

2.3 Landau theory

Landau theory tries to express phenomenologically the behavior of a system near its critical
point. It only deals with macroscopic quantities and explicitly avoids microscopic details.
Nevertheless it has been very successful, and offers yet another insightful way to the mean
ﬁeld approximation. I will follow Huang’s introduction to the Landau approach [25].
Starting with a macroscopic system in (1 dimensions assume that there exists some
coarse grained order parameter density, m(:1:). Coarse graining could be done by averaging

over some volume 0.". Then there are no ﬂuctuations in m(:r) on length scales shorter than

29

a. Therefore there are no Fourier components with wave number greater than A ~ 1 / a.

The partition function can be written as
Z(H, T) : exp(—C(H, T)/kT) : N/exp(—E(m, H))(Dm) (2.29)
where G is the Gibbs free energy and E is

E(m,H) :fd.r1,:(m(1‘),H(;r)).

The integral in Eq. (2.29) is a functional integral over all possible forms of m(:r) that do
not vary over a.

1,1’.‘ (m(:r), H (13)) is called the Landau free energy. Near the critical point where m(;r) is
small it can be expanded in powers of m(:1:):

1 1
(.r)H(;r) + —r0m2(1‘)+ som3(;1:) + 11.07n4(.1:) + - ..

1
1,” (m(.r), H(;r)) : §|Vm(;1‘)|2 — Hm 2

where m, so, no are parameters that may depend on temperature and A. no is usually

considered independent of temperature while r0 is of the form
7‘0 2 (106

with (10 positive and c = (T — TC)/Tc.
The simplest approximation to the functional integral in Eq. (2.29) is the saddle point
approximation [6]. The integral is replaced by the maximum value of its integrand. This

approximation leads to mean ﬁeld theory. For constant H, 711(1) 2 771(H, T) with the

30

boundary conditions

 

am mzm
2.),
(9 t. (m, H) 2 0 (2.31)
(97712 mZm

maximizes the integrand. The Landau free energy in the mean ﬁeld approximation ex-

panded in powers of m is

, mH 1
1,2(111,H) = TrT + 3mm? + 80m3 + 110m" + - .-

From 21’) one can calculate the Gibbs free energy
1 , _ _
VGUJ’ T) = kTr,2(-m,0) — mH

and the magnetization M : ——BG/3H

M _
— = m.
"/7
Choose
1 . H
t,/.r(m, H) : ~2-r0m2 + 110m4 —— "IZ—T-
where uo > 0 and r0 = (1.06. From Eq. (2.30) we have
H
4: v-.3————=0. 2.32
T0771 + 110m kT ( )
For H = 0, ﬁr = 0 is always a solution and
(106 = ——4rr.0ﬁr2.

31

Additional real solutions exist only for 6 < 0. They are

171. = i (110/4110) |t|

which gives 3 = 1/2.
The magnetic susceptibility is obtained by differentiating m with respect to H. From

Eq. (2.32) we get
1
kT(r0 + 121101712)

 

X:

and 7 = 1. All the other exponents listed in Table 2.1 take on their mean ﬁeld values, too.

2.4 Percolation

So farI have used thermal phase transitions to introduce the concepts of critical phenomena.
This is, however, not the only situation where critical phenomena arise. Another class of
systems experiences criticality due to quenched randomness. Quenched here means that the
disorder changes - if at all - on a time scale much larger than that of thermal ﬂuctuations.
One such system is percolation. Percolation comes in two ﬂavors: bond percolation
and site percolation. In both cases we consider a regular lattice in (1 dimensions. In bond
percolation all sites in the lattice are present and we add one band at a time. The question
is then, at which concentration of bonds, p : 12,, does a path appear that connects opposite
sides of the lattice. In other words, when does a path percolate from one side of the lattice to
the opposite one. The concentration of bonds at that point gives the percolation threshold.
For small p only a few bonds (or edges) are present. Therefore only small clusters of nodes
connected by edges can form. As )1) increases, larger and larger clusters begin to form until,
ﬁnally, there is a percolating cluster (see Fig. 2.5). The percolating cluster is also called

the inﬁnite cluster since its size is of order the system size and becomes inﬁnite in the

32

 

(a) p=O.3 (b) p=0.65

Figure 2.5: Percolation on a square lattice. The left graph shows a square lattice with a bond
concentration p=O.3. There is no percolating path. The right graph has a concentration of
p=0.65 where most bonds are part of the percolating cluster.
thermodynamic limit, i.e., in the limit of inﬁnite system size.

For site percolation imagine a checker board. One square at a time is occupied and
the question becomes at which concentration, p = pc, of occupied squares does a path
containing only occupied squares appear that percolates.

The order parameter in percolation is the probability P of a node to be part of the
inﬁnite cluster. For p < 12,, P is 0 since there is no inﬁnite cluster. Above pc the probability
increases until it becomes 1 at p = 1. Two other quantities are of interest: the average
cluster size (3) and the ﬁnite cluster size distribution as [49, 4].

The average cluster size (3) is deﬁned as

where Pp(s) is the probability to have a cluster of size 3 at a concentration p. The cluster

size distribution, or normalized cluster number 71,, is deﬁned as the number of clusters of

33

size 3 per lattice site:

1
12, = —Pp(s).
s

I have not related percolation to disorder so far. To remedy this, let all bonds (sites)
have a randomly assigned value between 0 and 1. Usually the random numbers are drawn
from a uniform distribution. For a particular value of p all bonds (sites) with a value less
than p are present (occupied).

To get a better feel for the above quantities let us ﬁrst look at the one dimensional chain.
Any hole in the chain interrupts the percolating cluster thus pc 2 1. The probability to be
on the inﬁnite cluster P is 0 for p < pc and 1 for p = [30. Assume L is large so that we can
ignore the ends of the chain. To get a cluster of size 1 the site has to be occupied, which
it is with probability p, and its two neighbors have to be empty. The probability for a site
to be empty is 1 — p. Since we assume independent random variables the probability for
any two sites to be empty is just (1 — p)2. The probability of having a cluster of size 1 per
lattice site is thus a, : p(1 — p)2. For a cluster of size 2, 2 neighboring sites have to be

occupied and the ends have to empty. This gives n2 2 [22(1 — p)2. Or for a cluster of size 5

n, : p3(1 — 1))2.

Next let us look at the correlation function F (r). The correlation function gives the
probability of two sites at a distance r to belong to the same cluster. For T = 0, I‘(0) = 1.
For r > 0 all sites between the origin and the site at distance T have to be present, which
happens with probability 12’.

Hr) zpr.

For p < pc, F(r) goes to zero exponentially,

F(r) 2 84/5,

34

where g is the correlation length.

 

or near the critical point

 

(pa —p)’

which in analogy to the thermal case leads to a critical exponent z/ : 1 (see Table 2.1).

2.4.1 Cayley tree

For another exactly solvable example consider the Cayley tree. Just like described earlier
each site is assigned a value between 0 and l drawn from a uniform distribution. A site is
occupied if its value is less than p.

We consider percolation from the origin to the surface. For a percolating path to exist
at least one of the (z — 1) (or z for the origin) neighbors has to be present. Therefore

p(z — 1) 2 1 and the percolation threshold is

1
z—l’

 

pc : (233)

This time p > pc is accessible and we can study the behavior of P, the probability of a
site to be part of the inﬁnite cluster, in more detail.

Even above pC there is no guarantee that the origin or any other node is part of the
inﬁnite cluster. All neighboring Sites could be unoccupied. This happens with a probability
of (1 — p)? Even if all neighbors are present it is possible for none of the neighbors to
be connected to the surface. Let Q be the probability that a branch is not connected to the
surface. For simplicity consider 2 = 3. The probability that neither of the sub branches
lead to inﬁnity is Q2. The probability that the neighbor site is occupied but none of its

sub branches are connected to inﬁnity is pQ2. The probability that the neighbor is missing

35

already is 1 — p. Thus the total probability for a branch not to lead to inﬁnity because either

the neighbor is missing or neither of the sub branches lead to inﬁnity is
Q = <1 — p) + p122. (2.34)

Equation (2.34) has two solutions: Q1 2 1 and

1—10
(222—.
p

The probability that the origin is not part of the inﬁnite cluster is p — P = pQ3, which leads

to P = 0 for Q1 corresponding to p < p, and

P 1— 3
_:1_(__Pa)
P I?

for Q2 corresponding to p _>_ pc.
To make the recursive nature of the calculation more explicit I can write the probability
of a site at level I + 1 to be connected to the surface in terms of the probabilities at level l.

The level count starts from the surface.

P(l+1> = p2: 0’ Paw-9(1).
9:1 9

Just like in the previous calculation I ﬁnd the steady state solution by setting P (l ) = P (l +
1):P*:(1_Q‘)2

0‘ a
P‘ z p: P*9(1 — 19*)0-9. (2.35)
9:1 9

36

1f the sum started at zero Eq. (2.35) would be a binomial sum of the form

0

0

Z P*9(1—P*)“‘9 = (P‘+(1—P*))".

51:0 9

Thus we can rewrite Eq. (2.35) as

 

 

Pt
1) = (P’ +(1— P"‘))O — (1 — P‘)“.
Fora = 2this is
P!!!
= (P* + (1 — P"‘))2 — (1 — 1D")2
I)
= P’2 + 2P"(1— P’)
1
0 : (2 — —)P* — P”.
P

The ﬁrst solution is P" = O, which corresponds to p < 1 / 2. The second solution is

P" =(2—1).
P

For the central spin the probabilities of the z = a + 1 incoming branches have to be

combined. The probability for the central spin to be connected to the surface is

37

which for a = ‘2, z = a + 1 = 3 becomes

Po
1)

= 19*3 + 3P*2(1— P’) + 3P*(1— P‘)2

= <——>

The second way of ﬁnding P looks more complicated than the ﬁrst one but is easier to

extend as I’ll Show later.

2.4.2 Giant clusters in random graphs

The deﬁnition of percolation that I gave above contained a regular lattice in some dimension
where neighboring nodes are connected with edges. It may seem odd at ﬁrst to extend
percolation to a system where neighbors can be inﬁnitely far away and a percolating cluster
can consist of one edge and two nodes. Although the connectivity aspect is the intuitive
interpretation of percolation, I deﬁned all the quantities, including the order parameter, in
terms of clusters and cluster sizes. A cluster can exist in a random graph just as well as on
a regular lattice. Random graphs have ﬁrst been studied by Erdos and Rénya [16]. They
are interesting to both mathematicians and physicists [4, 31].

A graph consists of nodes and edges connecting the nodes. In a complete graph every
node is connected to every other node in the graph. Again assign a random number between
0 and 1 to each edge. A random graph with concentration p is a complete graph, where an
edge is present if its value is less than p. Erdos noticed that for each property of the graph
he investigated, for example, the emergence of trees of size 3 or the emergence of cycles,
there exists a threshold. For p below this threshold almost no graphs have this property and
for p above the threshold almost all graphs have this property. This included the emergence
of the giant cluster. The giant cluster includes a ﬁnite fraction of the nodes. It is equivalent

to the inﬁnite cluster in percolation.

38

In contrast to percolation theory where pC is independent of the system size the threshold
in a random graph, which is an inﬁnite dimensional system, depends on the system size and
goes to either 0 or 1 for N —> 00. Instead of using p directly, deﬁne an exponent z with
p(N) = N Z. The critical values of z are independent of N.

In random graph theory often the evolution of graphs is considered. Starting from a
graph with N nodes and no edges we slowly increase p(N) = N z, the concentration of
edges. 2 varies from —oo, p(N) = O, to 0, p(N) : 1. For 2: < —3/2 only isolated nodes
and edges are present. At 2 = —3 / 2 trees of order 3 appear. For z = —1 the structure of
the graph changes dramatically. The average connectivity < k >= 1, and a giant cluster
forms containing of the order of N 2/ 3 nodes.

We can study the growth of the giant cluster using invasion percolation and Cayley trees.
Pick a vertex v and label it as visited. All adjacent vertices are labeled active unless they
have been visited already. Now pick an active vertex and repeat. If we use a ﬁrst in-ﬁrst out
(FIFO) queue for the active vertices, this procedure grows a Cayley tree. The active vertices
are the leaves of the tree and form the growth surface. The critical connectivity for the giant
cluster is < k >2 1 as for the Cayley tree in Sec. 2.4. 1. The Cayley tree has, as I mentioned
in Sec. 2.2.3, properties that one usually only ﬁnds in an inﬁnite dimensional system. I can
therefore use it as a model for inﬁnite dimensional percolation. The appearance of the giant
cluster in a random graph and percolation in inﬁnite dimension are therefore in the same

universality class.

39

Chapter 3

Paths, Domain Walls, and Spin Clusters

in Random Media

Flux lines in super conductors, directed polymers in random media, domain walls in the 2D
random-bond Ising model, shortest paths in networks are all examples of directed paths in
physics. They ﬁnd their way through complex energy landscapes and often stick to pinning
sites or random pinning areas caused by ﬂuctuations. Pinning and the complex energy
landscape make it very hard to ﬁnd the global minimum for any of these paths. Simulated
annealing methods get stuck around the pinning sites, which are deep local minima, and
it takes a long time to overcome those large barriers to explore other parts of the energy
landscape.

The problem becomes even more difﬁcult as we move to higher dimensions. Domain
walls in the 3D random-bond Ising model are surfaces with additional degrees of freedom.
In the random-ﬁeld Ising model more than one domain can form so that there is a multitude
of possible conﬁgurations. Often we use the term manifolds instead of paths and surfaces.

Finding the global minimum for manifolds in random media is a hard problem due to

local minima that have almost the same energy as the global minimum but are often far

40

away in space. In 1986, however, Ogielski [39] presented results for the ground state of the
random-ﬁeld Ising Model at T=OK that he obtained using an algorithm from combinatorial
optimization. This opened the door to detailed, large scale investigations of disordered

Ising models.

3.1 Domain walls and random bonds

The random-bond Ising model (RBIM) is the most general form of the Ising model without

ﬁeld as introduced in 2.2. The Hamiltonian is given by Eq. (2.18),

H 2 — Z JijSiSj,
if

where, as the name implies, each bond can have a random bond strength J,j.

If we ﬁx the boundary spins to be up on one side and down on the opposite side, two
domains will form. For uniform J the interface between the two domains is ﬂat. A ﬂat
interface minirrrizes the number of neighbors with opposite spins and therefore the energy
cost of creating the boundary. There is no preferred location for this interface either. It is
degenerate. In a two dimensional system the interface is a path, in three it’s a surface.

In a random-bond model it may be favorable to break more but weaker bonds and thus
form a rough interface.

The roughness and energy are independent of the distribution, P(J) [26, 17]. The

roughness scales as

 

w=\/<h2>—<h>2=b1LC,

with C = 2 / 3 in two and Q 2 041(1) in three dimensions. The energy scales as

E = alLd‘l + (1.2L"

41

with 0 =1/31n 2D and 19 : 082(2) in 3D [38, 2].

3.2 Spin clusters and random ﬁelds

The random-ﬁeld Ising model (RFIM) is the most general form of an Ising model with
ferromagnetic interactions. A random ﬁeld is associated with each spin. The ﬁelds are
drawn from some distribution, P (h), where h can be positive or negative. In addition the
spin-spin interaction can be non-uniform and a uniform external ﬁeld can be present. The

full Hamiltonian for the RFIM is

”H = —ZJ,J-s,sj —Zs,(h,+B). (3.1)
r j i

The RFIM has an order-disorder transition depending on the width of the random dis-
tribution in d>2. For a long time this was a hotly debated topic. Imry and Ma [28] gave
a simple argument that identiﬁed d=2 as the critical dimension and predicted a phase tran-
sition in 3D. From renormalization group arguments, however, it was predicted that the
behavior of a disordered system should be the same as the ordered system in d-2. Thus
there should be no phase transition in 3D. In 1984 Imbrie showed rigorously [27] that there
is a phase transition in 3D but none in 2D.

Numerical simulations weren’t of much help either. The energy landscape of the RFIM
has many local minima. Monte Carlo simulations easily get stuck in these minima. The
transfer matrix method is another algorithm that was employed early in RFIM calculations.
Both Monte Carlo and the transfer matrix method are exponential algorithms. The max-
imum time needed by these algorithms to ﬁnd the solution increases exponentially with
the system size. But in 1986 Ogielski published numerical results using for the ﬁrst time
a mapping of the problem of ﬁnding the ground state in the RFIM to the maximum ﬂow

problem of combinatorial optimization [39]. The mapping provides exact ground states at

42

T=0K in polynomial time. This allowed Ogielski and others to study larger systems and get
better statistics. The two major questions that Ogielski addressed are, however, still under
debate: Is the phase transition ﬁrst or second order in 3D and is it universal, i.e., does the
phase transition depend on the random distribution.

The latter point is important for practical reasons. The closest experimental realization
of the RFIM is the diluted antiferromagnet in a ﬁeld (DAFF). It is supposed to be in the
same universality class as the random-ﬁeld Ising model. But if the phase transition of the
RFIM is not universal, which distribution has to be used to compare it with the experimental

results?

43

Chapter 4

Maximum Flow/Minimum Cut

All the problems treated in my thesis have some instances where ﬁnding the ground state
can be mapped to ﬁnding the minimum cut in a capacitated network.

Combinatorial optimization provides us with efﬁcient ways to ﬁnd the minimum cut
by using maximum ﬂow algorithms.The maximum ﬂow is equal to the capacity of the
minimum cut.

In this chapter, after presenting and proving the maximum ﬂow/minimum cut theorem,
1 detail various mappings to the relevant physics problems. Finally I explain two algorithms

that solve the maximum ﬂow problem.

4.1 The maximum ﬂow/minimum cut theorem

Let G(V,E) be a graph where V is a set of vertices (or nodes) and E g V x V a set of edges.
Each edge has a capacity a and a ﬂow f. The maximum ﬂow problem can then be phrased

as follows: Given a set of sources {9} and a set of sinks {t} ﬁnd the maximum amount of

44

ﬂow that can be transported from {s} to {t} subject to the constraints

W e V \ ({s} u {t}) : thuu v) = Z f(v. w) (4.1)

V6 6 E : fe 3 "tie. (4.2)

A ﬂow that obeys Eq. (4.1) and (4.2) is considered a feasible ﬂow. For the remainder of
this chapter I will consider only one source 3 and one sink t unless otherwise noted.
A cut is a set of edges separating V in two disjoint sets S and T, V = S U T. If s is in S

and t is in T the cut is called an s-t cut. The capacity of such a cut is given by

u(S,T)= Z u(v,w).

vES,-wET

The cut with the minimum capacity u(S, T) is the minimum cut. Its capacity gives an
upper bound for the ﬂow. Actually, it can be shown that the maximum ﬂow is exactly equal
to the minimum cut. This is known as the maximum ﬂow/minimum cut theorem [3, 32].

PROOF: Adding the balance constraint (Eq. (4.1)) for all nodes in S and doing the same

for all nodes in T we get

m = Emu—2mm)

(I-uw)€(S,T) (vrw)€(T.~S)

All ﬂows within S cancel and the same is true for all ﬂows within T. Only the ﬂow between

45

S and T remains. Since f, g u, and fe 2 0

m S 2 “'(va'w) = u.(S, T).

(v.w)E(S.T)

This means that any ﬂow f is at most equal to the capacity of any cut (S, T). Therefore if
we ﬁnd a ﬂow | f I that is equal to the capacity of a cut (S, T) we ﬁnd the maximum ﬂow

and the minimum cut. [:1

4.2 Mappings to the maximum ﬂow/minimum cut prob-
lem

Several interesting ground state problems in physics map to the maximum ﬂow/minimum

cut problem.

4.2.1 Finding the interface in a random-bond Ising model with ﬁxed

boundaries

Historically the mapping for the random-bond Ising (RBIM) problem was discovered sev-
eral years after the mapping of the ground-state random-ﬁeld Ising model problem de-
scribed in 4.2.2. But it is easier to visualize.

I want to ﬁnd the interface in a random-bond Ising model where the spins of two of
the boundaries are ﬁxed to +1 and -1 respectively. The boundary conditions force two spin

domains and therefore an interface. The Hamiltonian for the RBIM is (cf. 3.1)

’H = _ E JijSiSj,
ij

With Jij Z 0.

46

Let 1' be the set of all spins. Then any spin conﬁguration has a set of spins S = {i E
l'ls, : 1} and a set of spins S = {i E l'ls, = —1} = V \ S. The energy of such a system

can be written as

E = — Z lJul- 2 ”01+ X Vol (4-3)

 

(5,69,51,68) (3,633,163 (5,65,11,63)

= — E :iJijl+2 E iJijl (4'4)
ii (s,€S,sJ€S)
E01” Einterface

: Eopt +2Eintcrface. (4‘5)

In the ground state E is minimal and therefore Einterface must be minimal since Eop, is
always the same. The factor of 2 is needed since all bonds in the interface have already
been counted in the optimal energy and this has to be canceled.

Let G be a graph. To map the random-bond Ising model interface to a graph problem,
map each spin in V to a node in G. The interaction J,j between two spins is represented
by an edge between those spins. The capacity 11,]- of this edge is equal to the strength
of the interaction, 11,]- : J,j. To ﬁx the boundaries introduce two ghost nodes, 3 and t,
and connect all spins on one face to s using edges of inﬁnite capacity and all spins on the
opposite face to t again with edges of inﬁnite capacity. Now ﬁnd the maximum ﬂow from
s to t. The minimum cut will separate the system in two domains, one connected to s and
one connected to t. All spins connected to s have s,=1 and all spins connected to t have
s, = —1.

As I showed in 4.1 the maximum ﬂow is equal to the sum of capacities on the minimum

cut

ucut = E ”if

tesaes

Using the deﬁnition of S and S and the assignment of spins, this is exactly equal to

47

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 4.1: The minimum cut in a random-bond Ising model. The strength of the spin-spin
interaction is indicated by the thickness of the line. The thick line crossing the sample
shows the location of the minimum cut.

E interface -

4.2.2 The mapping of the random-ﬁeld Ising model to the maximum

ﬂow/minimum cut problem

The mapping of the random-ﬁeld Ising model (RFIM) is very similar to the one for the
RBIM. In fact the RFIM can be treated as a special case of the RBIM. Again introduce two
ghost nodes, 3 and t. Every site with a positive ﬁeld is connected to s, and every site with
a negative ﬁeld to t. The capacity of each of these edges is equal to the magnitude of the
ﬁeld, i.e., as, = h, , and 11,, = lh,|. In this way the spin-ﬁeld interaction is mapped into a

spin-spin interaction and the Hamiltonian can be written as

H : — Elli-78,81“,

it

48

 

 

 

 

.T

Figure 4.2: Mapping of a 1D random-ﬁeld Ising model to the maximum ﬂow problem. The
source S is connected to the spins that have a local ﬁeld pointing upwards. The sink T is
connected to the spins where the random ﬁeld is pointing downwards. The numbers give
the magnitude of the ﬁelds in terms of J. The thick line indicates the minimum cut. All
spins above the out are up in the ground state. All spins below the cut are down.

49

where i andj run over 1" U {s t}.

The minimum cut in this case is not limited to spin-spin bonds but can also include
broken ﬁeld bonds. The energy can be written exactly as in Eq. (4.5) with S —> S U s and
S —> S U t.

The geometry of the minimum cut in the RFIM, however, is completely different from
the one in the RBIM. Instead of two domains separated by a single interface, there is a

multitude of clusters with domain walls between them.

4.3 Algorithms for solving the maximum ﬂow problem

4.3.1 The augmenting path algorithm

To check if a ﬂow f is maximal it is sufﬁcient to verify that there is no path from s to t
along which the ﬂow could be increased [32]. Such paths are called augmenting paths.
Augmenting paths form the basis of our ﬁrst algorithm (see Alg. 1).

Find an augmenting path from s to t. Determine the minimum capacity am," on this
path and send um," units of ﬂow from s to t. Calculate the residual graph and repeat the
procedure until no more paths with 11mm > 0 can be found. The excess on t is the maximum
ﬂow. The residual capacity of an edge e,, is just a;- = 11,]- — f,, + f], where f,, is the ﬂow
from node i to node j.

How fast is the algorithm? The complexity of an algorithm is expressed in the “big 0”
notation. Instead of using benchmark times that change with faster computers, the order of
the number of operations is given in terms of the size of the system. Constant prefactors are
usually ignored. Finding a path with residual capacity greater than zero can be done using
a breadth ﬁrst search (bfs) and takes 0(IE I) operations where IE I is the number of edges.
Augmenting the ﬂow along the path takes O(|V|), the length of the path. Each time there

is at least one critical edge that will be saturated on this path. Therefore this procedure

50

 

main:
initialize
repeat
# ﬁnd augmenting path
choose ﬁrst unlabeled node v w/ pre(v)
forall outgoing edges e of v:
if NOT pre(wztail(e)) AND f (e) < 11(6):
pre(w) = v
(1177(11‘) = -l-
d(’w) = Inin(u(e) — f(e),d(v))

forall incoming edges e of v:
ifNOT pre(w = head(e)) AND f(e) > 0:
pre(w) = v
(11'1“(11') = —
(1(111) : min(f(e), (1(a))

label v
ifpre(t):
#augment ﬂow
w=t
d=d(w)
while 11) ¢ 3:
v = pre(w)
if dir(w) = +:
f (6) = f (6) + d
else:
He) = f(e) — d
w=v
forall v in V except 8:
delete pre(v) and dir(v)
d(v) = 00
clear label of v

until all nodes v with pre(v) are labeled

Algorithm 1: Augmenting path algorithm by Edmonds and Karp (1972)

 

51

needs to be repeated a maximum of IE 1 times and the total complexity of the algorithm is
(9(IVIIE l2). For the typically sparse graphs in physics problems this reduces to 0(IVI3).
The augmenting path algorithm is representative of a class of ﬂow algorithms that main—
tain a feasible ﬂow at every step and strive towards an optimal solution. A ﬂow is feasible
if f,, _<_ 11,]- and for every node i, E]. f,, — f], : 0, in other words the ﬂow is conserved at

each node and never larger than the maximum capacity of the edge.

4.3.2 Push-relabel

Another class of algorithms maintains a solution that is always optimal but not necessar-
ily feasible at each step of the algorithm. Among these is the push-relabel algorithm by
Goldberg and Tarjan [l9] . Instead of ﬁnding one path from s to t at a time, all edges
originating from s are ﬂooded up to capacity at once. The result is an excess ﬂow at the
connected nodes. The excess ﬂow is then pushed towards t or if that is not possible, back to
the source. This procedure is repeated until all excess ﬂow lies at either 8 ort (see Alg. 2).

The terms “towards t” and “back to the source” imply a direction and, thereby, a dis-
tance. In fact the push-relabel algorithm requires a valid distance label at each node. The
distance label can change over time. A node can be raised so that its neighbors become
accessible to push ﬂow into them. A valid labeling scheme obeys the following rules:
d(t) = 0, d(s) : N, (1(1) 3 d(j) + 1 for all i,j where 11:]. > 0. Setting the distance of all
nodes but 3 to zero is therefore a valid labeling. A reverse breadth ﬁrst search starting at t,
however, also gives a correct distance label and improves overall performance.

With the distance labels deﬁned, it is now possible to give the rules for the push and
relabel procedures. Given an active node 1, active meaning a node with an excess ﬂow
3:, > 0, a push can be performed if there is an edge with 111} > 0 and d(i) = d(j) + 1. This
ensures that ﬂow will be pushed towards the sink as long as possible. If a node i is active

and all its neighbors have d(z') S d(j) i gets relabeled d(z’) = min{d(j) + llufj > 0}. At

52

ﬁrst glance this might seem too restrictive. Due to the deﬁnition of u ,7], however, there is

always the possibility to push the ﬂow back to where it came from.

 

main:
determine distance label
forall outgoing edges 1 of s:

fsi = ”31'

f1. = —f..~.-

11;, = 0

a; = 11,, + 11.3,
331' : fsi.

while there is an active node i:
choose an active node i
apply an allowed operation to 1

push:
ifi is active AND 1",]- > 0 AND d(i) :2 d(j) +1:
6 = mi-n(:r,,r,j)

fij = fl)” +4
fj-i = fjr' — 0
'11sz 11:1 — (5
u’ — ”Ur-- +6

relabel:
ifi is active AND forall 11% > 0 AND 11(2) 3 d(j):
(1(1) 2 min(d(j)+1|ufj > 0)

Algorithm 2: Push-relabel algorithm by Goldberg and Tarjan

The order in which push and relabel operations are performed is important for the per—
formance of the algorithm. Using a ﬁrst-in-ﬁrst-out (FIFO) queue of active nodes and re-
peating the push operation until the node is either no longer active or a relabel is necessary,
it can be shown that the algorithm can be done in O(|V|3) time. Further improvements
using more complicated data structures are possible. The best bound for a push-relabel

algorithm is currently O(]V|]E|log(|V|2/|E|))[11,19].

53

4.4 Benchmarks

For most of my calculations I took advantage of LEDA [37], a library written in C++ that
provides many well implemented advanced data structures and algorithms. I also wrote
my own library of graph data structures and algorithms, SmaGL, in C++. In this section I
present some benchmark results for LEDA and SmaGL using Goldberg’s implementation
of his push-relabel algorithm in C as a reference. The benchmarks were performed on a
Dual PHI Xeon 550MHz PC with 2GB of memory.

SmaGL uses the FIFO implementation described in 4.3.2. Both LEDA and Goldberg
use a different ordering, the highest-label (HL) ordering. In the highest-label implemen-
tation the active node with the largest distance label is used next. Cherkassky and Gold-
berg [1 1] showed that the HL implementation is faster than FIFO for all tested problem
instances. FIFO, however, is easier to implement, performs well, and is much easier to
parallelize.

The benchmark consisted in calculating the interface in a random-bond Ising model (see
4.2.2) with opposing ﬁxed boundaries in one, and open boundaries in the other directions,
on a 3D cubic lattice. For each linear size L between 10 and 100 different samples were
solved.

Note that although LEDA (squares) and Goldberg (diamonds) perform better in abso-
lute times, SmaGL (circles) scales best (see Fig. 4.3).

In this chapter I proved the maximum ﬂow/minimum cut theorem. I showed how to
map the random-bond and the random-ﬁeld Ising to a maximum ﬂow problem. I presented
the augmenting path and the push-relabel algorithm to solve the maximum ﬂow problem.
Finally, I gave some benchmark results for three implementations of the push-relabel algo-

rithm.

54

700

600

500

400

[[5]

300

200

 

 

TTTTIITIT

 

— r~L3 7" (SmaGL)
1~L"'°" (LEDA)
1~L"'” (Goldberg)

 

 

TTTTTTTTTITTTTTTTTTITTTTTTTIIIITTTTTTTllTTTlTTTTTITTTTTTTTT

     
 

 

E

TTTTTI l

ITTTTT

100

T [1111"]

O

T T T TTTTT]

 

'l

I

I T TTTTI

   
  
 

1 L1 1111

l I 1 111111

 

1 J 1 111111

 

 

TTTTTIT‘ITTTTITTI[TTTTTTTTTITITITIITTITTTTTTTIIITTTITIITTI

 

0 20

 

40

   

L

’

+11‘IQI'I—I—lll11[Ill-1.11111111111111111111111

60

80 100 120

\
lllllllllllllllllllll1llllllllllllfilllllllllll11llllllllllllllllllI“

 

Figure 4.3: Push-relabel Benchmarks. The plot shows the time needed to solve the maxi-
mum ﬂow problem for a random-bond Ising model for different system sizes for 3 different
implementations (see text). The lines are best ﬁts of the form t = (1 =1: Lb. The values for b
are given in the legend. The inset shows the same data on a log-log plot.

55

 

Chapter 5

Random-Field Ising Model

The central issue in the equilibrium random-ﬁeld Ising model (RFIM) is the nature of the
phase transition from the ferromagnetic state at weak disorder to the frozen paramagnetic
state at high disorder. The existence and universality class of the RFIM transition is key, as
the best experimental tests of RFIM theory are diluted antiferromagnets in a ﬁeld (DAFF).
e.g., F e1_,Z nng, which are believed to be in the same universality class as the RFIM.
In 1979 Fishman and Aharony showed [18] that a uniform magnetic ﬁeld in a disordered
anisotropic antiferromagnet creates random ﬁelds proportional to the external ﬁeld. In
F e142 an2, Fe is replaced randomly by non-magnetic Z 72 atoms. This creates disorder
and anisotropy. The external ﬁeld is the control parameter that allows us to change the
strength of the random effective ﬁelds and thus drive the system from an ordered antiferro-
magnet at low ﬁeld to a paramagnet at high ﬁeld.

After some controversy it was rigorously demonstrated [27] that the RFIM transition
occurs at a ﬁnite threshold of the width of the distribution in three dimensions, and at an
inﬁnitesimal threshold in one and two dimensions. It seems natural to try to extend the
idea of universality discussed in 2.1 to systems with quenched disorder. In fact several sys-

tems like percolation and directed polymers in a random medium (DPRM) show universal

56

properties. But in more complex systems, like spin glasses, universality, though often as-
sumed, is unproven. Aharony showed [1] that already the mean ﬁeld RFIM can behave in
two distinct ways depending on the distribution of random ﬁelds. If the distribution has a
maximum at the origin, the transition is second order with exponent 1/2. For distributions
with a minimum at the origin he predicted a ﬁrst order transition. Numerical studies at
zero temperature suggest that in four dimensions the bimodal case is ﬁrst order, and the
Gaussian case is second order. The analysis in three dimensions is less conclusive [51].
The difference between the Gaussian and bimodal cases has been attributed to percolative
effects [52]. Numerical work in three dimensions has also suggested that the correlation
length exponent, as deduced from ﬁnite size scaling, is nonuniversal [13].

Another important concept for RFIM is the zero temperature ﬁxed point. Renormaliza-
tion group theory predicts that temperature is not a relevant parameter for phase transitions
in the RFIM. Thus phase transitions can be studied at T=0K and the results should be appli-
cable at ﬁnite temperature. This is of particular interest since there exists an exact mapping
of the ground state of the RFIM to the minimum s-t cut problem from combinatorial opti-

mization, which can be solved exactly in polynomial time (see Chapter 4).

5.1 Inﬁnite-range random-ﬁeld Ising model

Studying the inﬁnite range random-ﬁeld Ising Model (IRIM) at T=0K, Phil Duxbury and
I ﬁnd that the critical exponent for the magnetic phase transition can vary continuously
depending on the distribution of random ﬁelds. This means that the RFIM is nonuniversal
in the ground state. Furthermore, this behavior is not observed at any ﬁnite temperature

where the usual thermal order parameter 1/2 is restored.

57

The Hamiltonian for the inﬁnite-range random-ﬁeld Ising model is

H I —%ZS,SJ — Zine,
r] z

where the ﬁrst sum is over all spin pairs and the second is over all spins. To ﬁnd the ground
state it is only necessary to minimize the Hamiltonian since entropy does not contribute
to the free energy at T=0K. The minimum energy possible would be achieved with all
spins aligned and all local ﬁelds pointing along the same direction. If the distribution is
symmetric around zero, this is not feasible. There are additive terms due to broken spin-
spin interactions and rrrisaligned ﬁelds.

Given a particular magnetization m there is a number of spins 71+ = N (1 + m) / 2 point-
ing upwards and a number of down spins n- = N (1 —— m) / 2. Without loss of generality

let m > 0. The exchange energy per spin is

J —-J
E1; : —W(Tli + 723 — 271+n_) = 77712.

The ﬁeld energy has two terms. The ﬁrst represents the maximum possible ﬁeld energy

with all spins aligned with their ﬁelds

EM=—/ wmma.

DO

The second term is due to misaligned ﬁelds. For the inﬁnite range model all spins are
equivalent. In the ground state the local misaligned ﬁelds will therefore be those with the

smallest magnitude. The total ﬁeld energy is thus

00 hC
Ey=—/’|MPth+2/thMh
— 0

00

58

where he depends on the magnetization and the distribution. Taking advantage of the sym-

metry of the distribution, he is deﬁned by

'72

.3, 1 he
— — — = P h, dh.
A 2 f0 ( )

I can rewrite the left hand side of the above equation in terms of the magnetization m =
2(n+/1~7) — 1,
he
m = 2/ P(h)dh. (5.1)
0

To ﬁnd the ground state I need to minimize the total energy. This is done in the usual
way by setting the ﬁrst derivative of the energy with respect to the magnetization to zero

and then comparing the second derivative to zero.

8E 81.,
— _ —Jm + 2hCP(hC) am‘

Om (5.2)

 

By taking the derivative of Eq. (5.1) with respect to m we get 1 : 2P(hc)8hC/8m. Using
this to replace (MC/8m in Eq. (5.2) and setting Eq. (5.2) to zero we get

2th(hC)
0 —- -—-Jm + W
he 2 Jm
and Eq. (5.1) becomes
Jm
m = 2/ P(h.)dh. (5.3)
0

Eq. (5.3) is the ground state mean ﬁeld equation. Note that m = 0 is always a solution as
expected.
To determine if the solutions to Eq. (5.3) are minima or maxima one needs the second

derivative of the energy with respect to m. If the second derivative at m is greater than

59

zero, m is a minimum, if it is less, 111. is a maximum.

02(E, + Eh) _ 8h, _ 1
0112.2 — J + 8171 _ J + 2P(hc)

 

 

 

If J > 1/2P(hc), m. is a minimum and if J < 1/2P(hc), m is a maximum. In addition to
this comparison it is also necessary to compare the energy for the cases m = 0 and m = 1
to that of the non-trivial solution 711,.

Now let’s do the calculation for four particular distributions of random ﬁelds:

p111) = $61M) — H)

(see 5.1.1),
1 h?
0201) = WWW—717)
(see 5.1.2),
+1 h y
0301) = ygl‘fy- (1+ (LEI) ) (5-4)
and
+1 it y

(see 5.1.3). The ﬁrst two cases were considered by Aharony and the last two illustrate the

nonuniversality of the second order phase transition.

5.1.1 Bimodal distribution

A bimodal distribution is an extreme case in the sense that there is only one possible mag-

nitude of the random ﬁelds. Only the direction of the ﬁelds can differ between two neigh-

60

boring sites. For this distribution Eq. (5.3) becomes

Jm
1112/ d(|h| — H)dh,
0
which is only non-zero if J m > H. It therefore reduces to

1J>H

m = ,

0

which clearly marks it as a ﬁrst order transition with the critical point at H = J.

5.1.2 Gaussian distribution

A Gaussian distribution is quite different from the bimodal one. Most of its weight is near
the origin but there is also an exponentially small probability for very large ﬁelds. This
changes the behavior of the transition signiﬁcantly. A large ﬁeld, it > of where c is the
connectivity of the site, will always be able to force the local spin in alignment. On the
other hand the cooperation of many small ﬁelds is necessary to ﬂip a spin cluster of the
order of the system size.

The ground State mean ﬁeld equation is

Jm 1 h?
0 ﬁH em“?

 

m = 2 )dh, (5.6)

which can be rewritten in terms of the error function m : erf (Jm/ H) Unfortunately,
except for the solution m = 0, this equation can only be solved numerically. Nevertheless

this solution is important since it becomes the minimum solution when J > 1/2P(0) or

H/J> Q/ﬁ.

61

Next expand Eq. (5.6) for small m

2.115111 2.1361113

 

 

 

- _ 5 ,1
din — FIT/7:1— — W + 0((5171, ),
which again has the obvious solution of (5m 2 0.
1 __ 2.] 2J3m2
Hﬁ 3H3\/_7i
- 2 2.1 3H3ﬁ
0m. = — 1 .
Hﬁ 2J3

1/2 1/2
6111 = ———3\/7? E E- — E
2 J J C J

where (H/J),t = Q/ﬁ as expected and 111 ~ A(H/J)1/2.

5.1.3 Polynomial distributions

To test universality further, we use the distributions p3 and p4, that are deﬁned on the
interval -H g h g H. These distributions have an additional tunable parameter. The
exponent y determines the shape of the distribution. For small values of y, p3 is sharply
peaked at the origin, whereas for y >> 1 it approaches a uniform deviate (see Fig. 5.1).

The solution of Eq. (5.3) can be found for a general y

J’"y+1 |h| y
=2 1— — (ll.
f. 21111 (H1):

Since the upper and lower bound of the integral are positive it is not necessary to take the

 

62

 

 

 

Figure 5.1: Tunable random distribution. p3(h) = 32%; (1 — (Fly) for y=l/20 (top), 1
(middle), and 20 (bottom).

absolute value of h and it is easy to do the integration explicitly

, y+1
m 2 (1:12 h__H_ ﬂ.
Hy y+1 H 0

(y+1) Jm— H {2 WI

Hy y+1 H ’
Solving the above equation gives m = 0 and
(1:1) J__i__ J_m_ y

Hy y+1 H

y+1 H J 1 J ”+1 y

y J H y H n

1/1
= we) ——:—) 1%

Jm

 

 

p-r
||

63

 

 

11

 

0:5 1 1.5 2 2:5 3

Figure 5.2: Magnetization for different distributions of random ﬁelds. This shows the
y
magnetization for p3(h) = 1:1 (1 - ('7’?) ) with y=2 (left), 1 (middle) and 1/2 (right).

2lly

where (H/J), : (y + 1)/y. The magnetization decays like m ~ A(H/J)l/y near the
critical point.

This is quite remarkable since it shows that the exponent depends explicitly on the exact
shape of the distribution and is therefore not universal.

Now I brieﬂy consider the distribution p4(h) given in Eq. (5.5). For y > 0 this dis-
tribution is bimodal. In this case, it is easy to conﬁrm the conclusion of Aharony that the
transition is ﬁrst order. However the cases —1 < y < 0 are more interesting. In these
cases the disorder is dominated by small random ﬁelds, as the distribution is singular at the
origin (though it is integrable). It is easy to carry out the mean-ﬁeld calculation (5.3) with

the result,

7716,, = (7) H > J (5.7)

By comparing the energies ofE(m = 0), E(m = 1), and E(meq), I ﬁnd that for H < J the
ground state is fully magnetized, while for H > J the ground state has magnetization (5.7).
The interesting feature of the result (5.7) is that there is no phase transition at ﬁnite H in

this system, and the system always has a ﬁnite magnetization. The disorder distribution

64

(5.5) thus destroys the ground state phase transition, due to the large number of small

random ﬁelds.

5.1.4 Finite temperature

How does temperature influence the phase transition? If there is a zero-temperature ﬁxed
point the nonuniversal behavior described above should also be observable at ﬁnite tem-
perature. From 2.2.1 we know that the mean ﬁeld equation for the Ising model with an
external ﬁeld is m : tanh(m/T + H/T) (cf. Eq. (2.21)). For the RFIM the external ﬁeld
is not uniform. To take the distribution of random ﬁelds into account, multiply the right

hand side of Eq. (2.21) by p(h) and integrate over h. The mean ﬁeld equation becomes

m 2 /OO dhp(h) tanh(m/T + h/T).

00

Assuming p(lt) is symmetric this can be rewritten as

DC

tilt. W")

p=tal wT . 5.8
m m 1(m/ )/0 1 + cosh(2h/T)/ cosh(2m/T) ( )

 

There are two regimes m / T >> 1 and m / T << 1. At zero temperature only the ﬁrst regime
is applicable. But at any ﬁnite temperature the second regime is applicable close to the
critical point.

If m/T >> 1, tanh(m/T) —+ 1 and cosh(2h/T)/cosh(2m/T) —> exp(?(h — m)/T),

which yields,

 

, _ 0° p(h)dh
m. _ 2/0 1+ exp(2(h — m)/T) m/T —+ 00'

Note that this equation looks like a Sommerfeld integral for a free Fermi gas with the

Fermi Energy given by e, = m. The leading order term for the low temperature expansion

is thus the integral of p(h) from zero to m. This is the same as Eq. (5.3).

65

If m / T << 1, then cosh(‘2m / T) ——> 1 and Eq. (5.8) reduces to the mean ﬁeld equation
for the thermal transition, albeit with an additional factor of two in the argument and a

renormalized coefﬁcient in front.

m = 21(H, T) tanh(2m/T) m/T ——) 0

where

Ni)
1+ cosh(h/T)°

 

[(H, T) :/ dh
0

Therefore at any ﬁnite temperature, provided that m/ T << 1, an expansion to third
order shows that the magnetization approaches zero with exponent [3 = 1 / 2.

Thus for ﬁnite temperature the universal mean ﬁeld exponent ﬂ =2 1/2 is recovered.
This is surprising, since it was assumed previously that the RFIM is dominated by a zero

temperature ﬁxed point. At least for the inﬁnite range model this is not true.

5.2 Cayley tree

Motivated by the results from the previous sections, we have analyzed the zero temperature
RFIM on a Cayley tree, or Bethe lattice, for a variety of disorder distributions. We ﬁnd that
the Bethe lattice is universal, provided the transition is second order, even in the limit of
large coordination. This is surprising since in this limit the Bethe lattice usually approaches
the mean ﬁeld limit.

The Hamiltonian of the random-ﬁeld Ising model is

H = — Z JiJ‘SiSj — 2(3 + h,)S,-, (5.9)
1'J'

i

where the exchange is ferromagnetic (Jij > O) and the ﬁelds h,- are random and uncorre-

66

lated. The random ﬁelds are drawn from a speciﬁed distribution p(h).

We determine whether the nonuniversal results found above for the mean ﬁeld theory
extend to the ground state of the RFIM on a Cayley tree. The coordination number of a
tree is taken to be 2, while the probability that a spin is up is P+ and the probability that a
spin is down is P_. The probability that a spin is up at level 1 can be written in terms of
the probabilities of the level that is one lower down in the tree. This leads to a recurrence

relation similar to P for percolation discussed in 2.4. This yields [14, 10]

P+(l) = Z a P£(l—1)Pf_g(l—1)a+(a,g) (5.10)

9:0 9

where a+ (a, g) is the probability that the local effective ﬁeld is positive when g neighbors
are up. The local effective ﬁeld combines the local random ﬁeld with the spin-spin inter-
action of the neighbors. The idea is similar to the molecular ﬁeld in the mean ﬁeld Ising
model (cf. 2.2.1). If we know the distribution p(hi), we can compute a+(a, 9). Analyzing

the equilibrium behavior, we have

a:q(a',g) = /(00 p(h)dh. (5.11)

a—29)J—H
By direct iteration of the recurrence relation (5.10) we show that a stable steady state

solution, :1: = P; = 1 — PI, exists (cf. 2.4.1)

0 a
1: = Z :L'g(1 — :r)a_9a+(a,g) (5.12)
9:0 9

It is easy to solve equation (5.12) for small values of a. For a = 1, 2 Cayley trees have
no ordered state for any ﬁnite H, for the disorder distribution (5.4). But for a = 3 a

ferromagnetic state does exist for a range of disorder. As we see from Eq. (5.10), the oz 2 3

67

case leads to a polynomial of order 3,
J: = (1 — 1‘)3a+(3, O) + 3.1“(1 — 1')2a+(3,1) + 3190— I)CL+(3, 2) + x3a+(3, 3),
which can be simpliﬁed to,
$[7722(1—3b+a)—1+3a+3b] :0 (5.13)

were m : 2(P;—1/2),a: a:q(3,0) :1— a‘f(3, 3) and b : a:q(3, 1) = 1 — aT(3,2).

Eq. (5.13) has the following solutions:

_ 1/2
3a+3b 1) . (5.14)

m 0, and (3b—1—a

These solutions apply for any disorder distribution. For the distribution p3(h), performing

the integrals yields,

(5.15)

 

_ 1/2
m _ 4y —1‘2(y +1)J + 3(3y+1+1)7i"+1
3(1— 3y)?+1

We can now expand the magnetization around the critical point, .107 2 7C — e. We ﬁnd,

1/2

t +1
m~ (—1‘2(y+1)+3 J (1+3y+1)7”)e (5.16)

‘31
Thus m ~ 61/2 for any y, so that 13 = 1/2 is universal. Since the non-equilibrium behavior
on trees is related to that of the equilibrium behavior by a simple shift, this universality
extends to the hysteresis and avalanche exponents. It is easy to conﬁrm numerically that
the behavior extends to large values of the branch coordination number a. Moreover by

doing an expansion of (5.10) using P+ = 1 / 2 + m, it is possible to show analytically that

68

only the ﬁrst and third order terms in m exist (see Appendix A), regardless of the value of
y in the disorder distribution (5.4). This conﬁrms that for this distribution, the behavior is
universal for all coordination numbers.

For the distribution pg(h) and a- : 3 we get from Eq. (5.14)

 

1/2
4 — . ' y+l —y+1
m = l: 38 +1)J ] . (5.17)

3(3y — 1)?"+1

Just like we have done before we can expand m around the critical point, 7 2 JC - 6:

1/2

y +1
772 ~ (3y+1 +1))Tcy€

'9

Thus for pg, ,3 = 1 /‘2 is a universal exponent, too.

5.3 Numerical ground state calculations of the RFIM

To see which of the two models is closer to the RFIM in 3D I use the mapping of the RFIM
to the maximum ﬂow problem (see 4.2.2). I ﬁnd the ground states for cubic systems with
periodic boundary conditions. Gaussian and bimodal distribution have been previously
studied [13, 39, 46]. To test universality I use the distribution p4 with y=O.5 and y=—O.5.
The positive exponent leads to a bimodal distribution for p4 and in the mean ﬁeld limit
gives a ﬁrst order phase transition, whereas for y=O.5 the magnetization decays as 1 / H .
Determining the critical ﬁeld has been a challenge for RFIM studies from the beginning.
I will look at several quantities to extract both the critical ﬁeld as well as the exponents: a)
the differential of the magnetization, b) the standard deviation of the magnetization 0(m),
c) the execution time, and d) the critical ﬁeld. For a, b, and c I study the peak position and

peak height. For (1 I only look at the change in the value for different system sizes. All

69

 

[ Name 1 Description lRFIMBench ]

 

 

 

 

zufall Dual Xeon 550MHz, 2GB RAM 1
pannonia AMD Athlon lGHz, 512MB RAM 1.12
cojocaru, fay, musolffc Pentium 4 1.6GHz, 512MB RAM 1.56

 

 

 

 

 

Table 5.1: Benchmark results for the random-ﬁeld Ising model (see text).

quantities should show a power law behavior with respect to the system size of the form

max('r) ~ L—a/V (5.18)
0(1) ~ L’b/V (5.19)
H, ~ Hg“+aL-C/V (5.20)

where r/ is the correlation length exponent. In particular for 0(m),

0(m) ~ L43”.

To compare results from different computers I ran a 503 sample with H E [2,5] and
6 H 2: 0.125 using the same realization of random ﬁelds on all systems. I deﬁned the result
on zufall as 1. Higher benchmark values indicate a faster computer. For details see Table
5.1.

I ﬁnd the maximum time for each run and average over all realizations for a given
system size and distribution exponent. I plot both the average and the standard deviation
vs. L on a log-log scale (see Fig. 5.3).

The standard deviation of the magnetization 0(m) vs. L (see Fig. 5.4) is very ﬂat. This
leads to a value of 26/1/ z 0 and therefore 6 z 0. This agrees with previous results for both
Gaussian and bimodal distributions in 3D but not with the results from the inﬁnite-range
calculation.

1 used the locations of the maximum of the calculation time, the maximum of 0(m),

7O

 

l 000

I I IWIIYI

 
 

100 "E-

1 1 111111]

 
 

10

l [[111]

([s]

I I
11 l 1 1111111

I TTIIIIII
l llllll

0.1

l l l 1111]

T I IIIIIII

-1

 

 

 

Jr 1 1 i 1 r 1 r i 1
0.01 1V0 100

Figure 5.3: Maximum execution time vs. L. The circles and up-triangles are the maximum
times obtained for y = 0.5 and y = —0.5 respectively. The squares and the left-triangles
are the respective standard deviations. Each point has been averaged over all available
realizations. The solid lines are least squares ﬁts to power laws, y ~ 2:“ with a = 3.75 for
the upper curve and a = 3.37 for the bottom one.

71

 

0.5— 3

 

 

 

E
b O O 13
0.252.; t: c g g D O _
O
O
0.125 _ —
l 1 1 l 1 l 1 1 1
10 20 30 50 70 100
L

Figure 5.4: Maximum standard deviation of the magnetization. The circles are the data for
y = 0.5, the squares are for y = —0.5. Both are essentially ﬂat.

and the maximum of the differential of the magnetization to determine the critical ﬁeld H CL
The results are in good agreement with each other (see Fig. 5.5). The large number of small
ﬁelds in p4 with y = -—O.5 leads to a larger critical ﬁeld value than y = 0.5. The approach
to the inﬁnite volume limit leads to different values of u.

I also used the ﬁnite size scaling relation
M =111L3/"117((H — Hfo)L1/")

to determine :1 and 3. I achieved the best collapse for H50 2 330(5), 1/ 2 200(5), and
: 000(1) for y = 0.5 (see Fig. 5.6) and H50 2 500(5), z/ = 1.530(5), and 3 = 000(1)
for y = —0.5 (see Fig. 5.7). The errors in H5”, u, and ,3 are estimated from the quality of
the collapse.

The timing exponent is universal for the two distributions. As in previously published

72

 

.9
u:
I

 

 

 

 

 

1 1 1 1 1 1 L
10 20 30 40 50 70 100
L

 

Figure 5.5: Finite size scaling of the critical width of the distribution. The critical width
of the distribution H 6" is determined in three independent ways: The maximum of the
execution time (circles), the maximum magnetization jump (squares), and the maximum
of the standard deviation of the magnetization (diamonds). All three values are in good
agreement. The plot shows H CL — Hg”. The solid lines are ﬁts of the form (H CL — HEW;
with (5 = 1/1/. 6 = 0.5 for y = 0.5 and 6 = 0.66 for y = —0.5. The error bars are given for
the values determined by the maximum execution time.

73

 

 

0.8

l

I

0.6

 

 

 

 

20

(H-HC)L1N

Figure 5.6: Scaling plot for the magnitude of the magnetization for p4 with y=0.5 and
L = 20, 30, 40, 60, 80, 100. For this ﬁt I used Hf,” = 3.3, 1/ = 2.0, and 3 = 0.0.

 

MLB/v

    

H .
l
.|

‘ w.
“in: _

I.
\

 

 

 

0.2e :.
. We, .
—20 0 20 40 60
(H-HC)Ll/v

Figure 5.7: Scaling plot for the magnitude of the magnetization for p4 with y=-O.5 and
L = 10, 20, 30, 40, 60, 80, 100. For this ﬁtI used Hf.” = 5.0, V = 1.5, and ,3 = 0.0.

74

work [20] the scaling is consistent with 3 z: 0. This is in contradiction to the inﬁnite-range
model prediction. The correlation length exponent on the other hand is not universal nor
does it agree with the exponents previously obtained for Gaussian and bimodal distribution
where 1/ = 1.2 and 1/ = 1.67 respectively [13, 20].

In this chapter I presented the behavior of the RFIM with inﬁnite-range interactions.
I showed that the behavior of the magnetization near the critical point depends explicitly
on the distribution of random ﬁelds for T =OK. This nonuniversality does not extend to
ﬁnite temperature. The behavior of the inﬁnite-range random-ﬁeld model is therefore not
dominated by a zero-temperature ﬁxed point.

In summary, I ﬁnd that the stretched exponential disorder distribution leads to a nonuni-
versal order parameter exponent in the RFIM mean-ﬁeld theory at T = OK. In contrast the
Cayley tree does not show this nonuniversality. The order parameter exponent of the RFIM
in 3D with short range interactions is so small that the issue of universality in 3 seems a
moot point there. The behavior in dimensions higher than three, or for longer range in-
teractions in three dimensions, however, should be interesting. In addition, even for short
range interactions in three dimensions, I see nonuniversality in the ﬁnite size scaling be-
havior. This is compatible with previously published results for bimodal and Gaussian

distributions [13]. The physical origin of this nonuniversality is unclear at present.

75

Chapter 6

Interfaces in Disordered Systems

Damascus blades made in the l6th and 17th century are among the best blades known to
man. Their strength and beauty made them popular items in trade and warfare and more
recently as collectors and museum pieces. The art of making Damascus blades had been
lost for centuries and has only recently been rediscovered [55, 54]. Materials researchers
studying these blades ﬁnd themselves faced with other obstacles besides analyzing the
composition and structure of the metal. The valuable blade has to be destroyed to ana-
lyze it. But some blades have been donated for analysis. They have helped rediscover
the making of Damascus blades and furthered our understanding of what makes them so
tough. The steel used to forge a Damascus blade is imported from India and called wootz.
The composition and structure of the impurities in wootz steel are essential for forging as
well as the blade’s ﬁnal properties. During the cooling of the blade the iron freezes in the
shape of inverted pine trees. The impurities segregate out of the solid iron and form bands.
These impurity bands form the seeds for the growth of iron carbide (F 830 ) particles dur-
ing subsequent heating and cooling cycles. The iron carbide bands increase the average
internal grain binding energy within the blade, while embedding the bands in the softer

steel effectively increases the adhesion energy between grains. This combination leads to

76

a high minimum fracture energy and provides a plausible explanation for the strength and
toughness of Damascus blades.

Low energy surfaces play a critical role in growth, material processing, and controlling
material properties [59, 50]. The morphology and energy of crystal surfaces have been
heavily studied, as have misoriented interfaces between two single crystals. In this study,
Phil Duxbury and I consider the lowest energy surface through a polycrystalline aggregate.
This is a multiscale problem. Atomistic simulations can provide the grain boundary en—
ergies, while a higher level calculation is required to ﬁnd the energy of separation of the
polycrystal. We develop a graph representation of the polycrystal. Each bond in the graph
has an assigned energy that depends on whether it is in the interior of a grain or on a grain

boundary.

6.1 Models and methods

The favorite model of a solid in condensed matter physics is a regular, inﬁnite crystal. Many
metals and other materials form large crystals that can be described by a repeated unit cell.
Most real world materials, however, are not single crystalline but consist of crystal grains
of different sizes and orientations. Grain sizes play an important role for their properties
such as stress and strain resistance, critical currents in superconductors, or the roughness
of the fracture surface.

Using the Potts model of grain growth [24] I generated the model grain structures I
used to test the scaling predictions. The grain structures produced by this model have been
shown to reproduce the grains size statistics of metals and ceramics accurately [47, 5].

The Potts model is a generalization of the Ising model that allows q distinct spin states.

The Hamiltonian is

H 2 -JZ(S(81‘, SJ') (6.1)
U

77

Figure 6.1: 2D Grain Structure. The thick line through the grain structure indicates the
minimum energy surface for weak adhesion.

where the interaction is not necessarily limited to nearest neighbors. In fact I used a square
lattice with nearest and next-nearest neighbor interactions to produce the grain structures
in this work. (5 is the Kronecker (5. It is 1 if s,- and s,- are equal, and 0 otherwise.

The starting conﬁguration is created by assigning random numbers between 1 and q
to each site. Then the algorithm picks sites randomly, changes the spin and checks if the
overall energy is lower than before. If the total energy is lower, the change is accepted;
otherwise it is rejected. This is a T=OK Monte Carlo method. The actual program uses
an improved algorithm. Instead of picking a new random value for the spin between 1
and q it chooses among the values of the neighboring spins. Once the grains have grown
enough, the algorithm takes advantage of the fact that changes can only occur at the grain
boundaries [22] and not in the interior of a grain.

We have two energies in our model: 69 is the internal binding energy of the grain and

e, is the adhesion energy between grains. The relevant energy scale in our calculations is

78

e = e,/eg. To ﬁnd the minimum energy interface we map the grain structure to a graph.
The spins are the nodes and we assign a capacity to each edge. If an edge connects two
nodes with equal spins its capacity is eg, if the spins differ it is 61'. The resulting graph is
equivalent to a random-bond Ising model (see 3.1) and the minimum energy interface is the
minimum cut (see 4.2.1).

The connection between domain walls in Ising magnets and the minimum cut/maximum
ﬂow problem has led to improved precision in the calculation of the energy, energy ﬂuc-
tuations, and roughness of these interfaces [38, 2]. Here I extend the scaling theories for
domain walls in random Ising magnets and their supporting numerical analysis to graphs
that represent a polycrystalline microstructure. I show that the roughening transition of do-
main walls corresponds to the transition from cleavage to intergranular interfaces in poly-
crystalline materials. Fig. 6.1 and Fig. 6.2 give examples of minimum energy surfaces in
the 2D grain structures I used.

One application of the analysis is the study of fracture surfaces [8]. The experimental
evidence suggests that fracture surfaces have a roughness exponent in the range 0.5 S C _<_
0.85. It has been suggested that at short length scales, the “quasistatic” exponent should
apply [8, 41]. Raisanen et al. have shown that for mode III failure (or scalar quasistatic
failure) this exponent is close to 0.42 [41] in three dimensions. Many of the experiments,
however, are carried out in polycrystalline materials, so it is important to test the effect
of polycrystalline morphology on the quasistatic exponents. For the case of weak grain
boundaries in two dimensional systems, the intergranular interface problem was recently
simulated [23] and it was found that the ball and spring model [44, 7] produces surfaces
that have similar properties to the minimum energy surface. Allowing grain boundaries
to have a range of bonding strengths allows the possibility of a transition from cleavage
to intergranular interfaces. To describe the large length scale properties of these minima]

energy surfaces, I develop a scaling theory based on those for domain walls [26, 17] and

79

     
     

95. in , '
Reset»? " .
. :.¢-."‘

 

 
 
  
    
  
 

   

     
     

      
   
   
     

 

Q ~

° N - 0| . - _

' ‘.“" .‘.“’- ~ " 'o‘a-O
° e... . 6'! ~‘ smeaveeeeeaoea
.0’0B'.".v. '. My... 0‘. .,.|’.e‘ .3.” ~4.“.‘.’..
:Qs‘B‘...‘ . 9.!" ‘63!" ‘ .. Q‘s'oUe“ . $.i’ "ng‘, ‘
‘33.:..v.g0 .‘cég‘gg’ﬁ .O:.'v.¢.0 ‘65::59’9.
.' . ""‘ ‘ N 0' ' "s... . .0.
53396430322”? 22.3%. :e aware Mote.

   
    

  

            
   

      
    

 
    
  

    
       
     

         

     

   
            

        
   

    
 
  
  

 
  

 
   

       
     
     
 

        
  
   

  

(a)e=0.1 (b)6=06
.‘ lg. O I .‘O c. .\.D.‘Q . ‘ 0. O I .‘O I P .‘\'..‘\ .
«33'0”. . “ﬂies.
.eov”"« g: .aoega‘a-k‘
‘9. ‘33“‘306’09’9 4:699... ”100:3". .306'6‘89.0‘é920°5
'é'b’O-ﬂb‘”6'c~'¢‘ev~ca ‘- ‘é'b‘coﬂb‘"o’w~'0ev~cw
'369e03339.?.v:°3~°¢4‘9 '3‘ 36.91“?»aotkv'3’e‘t's9 r.
‘0. '. ." ‘Q . . c ‘r.'.\‘.‘. .":O‘. ‘\'.O ‘c..
’ x s‘ ”‘0‘.“ ‘36! ‘02" .‘ f“
'9 4 arts- tom's. « 945
. on? a :"‘.'¢'O-‘..O'O:‘.°’
"Y ‘3‘7li.“l.‘" ‘7" .\ .v‘wl..“" ‘eﬁ! 5“.
«Pegsszezz'ofﬁo‘ﬁkw -. .0. P. ' "'0 5.

      

0
1 ‘0 1.... If". 1.
' «an '0‘!“
'2? .o‘e‘ ":99.“
I: ”3.0;“ ‘ Wk
0 §

 
 
   

(c) e = 0.75 (d) e = 0.95

Figure 6.2: Image of a grain structure with g 2 16 and L = 500. The 4 frames show the
interface for different adhesion strength.

80

for periodic elastic media [9, 15, 45].

6.2 Weak adhesion limit 6 —> 0

In the limit of weak grain boundary adhesion (e ——> 0), the minimal energy surface through
the polycrystalline material follows the grain boundaries. The scaling laws for the interface
energy and the interface roughness are found by extending the theory for random manifolds.
An example of a random manifold is a minimal energy surface through a hypercubic Ising
magnet where the exchange constants are all ferromagnetic, but random. There is a well
developed theory for this problem [26, 17] and the scaling predictions are: The energy
of the minimum energy surface E scales as E = alLd—l + agLO, where 0 is a universal

exponent with 6 = 1 / 3 in two dimensions and 0 2 082(2) in three dimensions [38, 2].

 

The surface roughness is w = \/< h2 > — < h >2 = b1LC where C = 2/3 in two and
C = 041(1) in three dimensions. C and 6 are universal exponents that do not depend on
the details of the disorder or lattice structure. A quantity that is not usually treated, but that
is of interest in many problems, is the number of bonds on the minimal energy surface N,
which scales as N 2 QB“1 + c2L".

Let’s extend the above scaling laws for random manifolds to the case of interest here.
The average grain size acts like the lattice constant so that L/g is the effective system
size. The scaling laws for the energy of the minimal energy surface lying along the grain

boundaries is given by

11—1 0
E = 9‘“ [a1 (5) + a2 (5) J . (6.2)
g g

If we ignore the correction term and rescale by L"’1 the energy is

2'5 01 (6.3)

 

 

a n 0000009 :1 9 QOQJMQ “ho 333%036 ;" D

w/Lm E/(L""e)

 

 

9
01— o o _ w/L2/3~g0.35 ﬂ

 

 

 

 

 

 

l 1 l l 1 l l l l l
10 100
g

Figure 6.3: Plots of the scaled energy (E / L, squares) and roughness (w/L2/3, circles) as
a function of the average grain size of polycrystalline materials, in the limit of weak grain
boundaries 6 ——> 0 The system sizes are L=500, 1000, 1200, and 2000. Each point is a
single data point. The data are well described by the scaling prediction (6.3) of an interface
energy which is asymptotically independent of the grain size E = const and of a roughness,
which scales as to ~ 91/3 (see Eq. (6.5)).

as shown by the squares in Fig. 6.3.

The roughness scales as

L C to
u, : blg (E) or ‘17 Z blgl-C. (6.4)
In 2D - where C is 2 / 3 - this becomes
31— z 5191/3 (6.5)

In Figure 6.3, we see that both relations (6.3) and (6.5) are in good agreement with the

numerical data. The plot shows individual data points. The broad scatter of the roughness

82

is typical for quenched disordered systems, which self-average very slowly. The width of
the scatter decreases, however, with increasing system size.

The energy, in this limit, is proportional to the number of bonds N in the interface

E = egeN (6-6)

and N must therefore scale like the energy

1112111.

As we shall see in Section 6.3, the weak adhesion limit applies over quite a broad range
of grain boundary energies, with a mixed transgranular and intergranular failure regime
setting in at 6c z 1 / 2. This onset is nonuniversal and is expected to depend on the lattice
structure. In the simulations described here there is an underlying square lattice. The
critical boundary energy can be estimated by considering the conditions under which the
interface prefers to cleave a section of the grain containing two atoms. In this case the
energy to cleave the two atoms is 269, while the energy to follow the grain boundary is
45,-. Balancing these two energies leads to the critical value CC = 1 / 2. These sorts of
conﬁgurations do occur in the grain structure and are necessary to the evolution of the
grain morphology. In contrast a single atom “bump" is much less likely.

A surprising feature of the purely intergranular minimal energy surface is that the num-
ber of bonds on the interface is very close to N / L = 3/ 2. This means that for every
two steps along the cleavage direction the interface takes one step perpendicular to the
cleavage direction. It also means that the typical angle of the minimal energy surface

giypical : aI‘Ctan(1/2) : 26.60.

83

6.3 Strong adhesion limit

The strong adhesion limit applies only in the limit 6 —> 1. Nevertheless understanding this
limit sets the stage for the mixed regime, which exists for 1 g e S (C. For the particular
case of grain structures on a square lattice cc ~ 1 / 2.
In the limit 6 —> 1, cleavage occurs, i.e., the interface is ﬂat. The roughness and number
of bonds are 11.1 = 0 and N = L"‘1 respectively. The energy can be expressed as E z
69 ( fg + cf.) L“"1 where fg is the fraction of the interface within the grains, f,- is the fraction
of the interface along grain boundaries, and f9 + f. = 1. We can rewrite the energy in terms
0f ft.
Ezeg(1—f,:+ef,)Ld‘1. (6.7)

As can be seen from Eq. (6.7) the energy is proportional to e as long as f,- is a constant.
Note that f,- is in general not zero as even a ﬂat surface must cross some grain bound-
aries. For 5 —+ 0, f,- z 1, since the interface follows the grain boundaries to take advantage
of the cheap grain boundary bonds. For 6 = 1 a simple argument can also be made. The
interface has to cross on average Ld‘l /gd’1 grains. The area of the grain boundary of each
crossing is proportional to g"‘2 and the total area of the interface is Ld'l. The fraction of

the interface along grain boundaries is then

d—2 11—1
9 L

f.- = dt——Ld_,gd_, (6.8)
1

ft = 0315- (69)

where (11 is a constant that depends on the details of the grain boundary structure, but is

independent of the average grain size 9.

84

 

0.8

l

0.6 F

0.4

l

0.2 —

 

 

 

 

0 1 l 1 1. 1' 1 1 1"- 113;.
0 0.2 0.4 8 0.6 0.8 1

Figure 6.4: Fraction of grain boundary bonds of the interface f,- and its standard deviation
vs. 6. For this and the following ﬁgures each point was averaged over all available system
sizes, L=500, 1000, 1200, and 2000, and grain sizes, ranging from g 2 2 to g 2 350
depending on the system size. We did not produce grain structures with g / L < 1/ 3. The
top curve shows the average and the bottom curve the standard deviation.

85

 

 

 

 

1 t r 1 1 1 3

0.8— _

_ 0.6” ‘
'2
LL]

0.4” —

0.2— q

0 0.2 0.4 0.6 0.8 1

E

Figure 6.5: Average interface energy (top) and its standard deviation (bottom) vs. 6. The
plusses are the average energy calculated from Eq. (6.7) verifying the relation. The squares
give the ﬁt from Eq. (6.26) and agree well up to e 2 0.7 (cf. Fig. (6.7)). The bottom curve
is the standard deviation of the energy.

86

 

 

 

 

 

Figure 6.6: Average roughness and its standard deviation vs. 6. The circles are the average
(top) and standard deviation (bottom) of the data. The squares are the ﬁt using Eq. (6.21).

6.4 Intermediate regime

Numerical results found from analysis of interfaces in polycrystalline materials as a func-
tion of the grain boundary bond strength 6 are presented in Figs. 6.4-6.7. The weak adhesion
behavior persists up to energy ratios 6 ~ 1 / 2. At higher grain boundary adhesion we enter
the mixed regime, where the intragranular fraction of the interface is a sensitive function
of the adhesion energy 6. From the discussion in the previous section we know that the
energy becomes a non-linear function of 6 only in the intermediate 6 regime where f, is
varying (see Fig. 6.5). I now present an analytic argument to describe the way in which the
crossover from cleavage to intergranular interfaces occurs in the mixed phase.

Our theory for the onset of the mixed regime is based on theories for the roughening
of manifolds in periodic elastic media. The key idea originated with Imry and Ma who

constructed a theory for the stability of the ferromagnetic phase in the random-ﬁeld Ising

87

 

 

 

 

 

 

l

1.5% G o —
1.4~ —
S 1.3— 1

d
z .1
1.2— ~
, _
1.1T -
1 4 1 1 m
1o 0.2 0.4 0.6 0.8 ‘7“‘1

Figure 6.7: Average number of interface bonds and its standard deviation vs. 6. The circles
are the average of the data. The squares give the ﬁt using Eq. (6.25). The ﬁt agrees well up
to e 2 0.7. The standard deviation is of order 0.05.

88

 

 

111 1111
11111111111111111

1111 1

1111 ”[11111'1'11'111 11111111 ""11' 1111111111111

1111111111

. . "1111111'"'"""" 111111" 11111 111111 111“
11'1"

.1111.
“111 1‘1

 

Figure 6.8: Interface through granular material.

model.

We consider in detail faceted grains in two dimensions, as indicated in Fig. 6.8. When-
ever the fracture interface encounters a grain boundary it has two choices. It can either
go straight through the grain and cleave it or it can follow the grain boundary. The grain
boundary makes an angle 19 with the cleavage interface. The way along the grain boundary
is therefore longer than the cleavage path. The cleavage path has a length l . The length of
the facet is l + h due to the underlying square lattice.

The angle 9 = arctan(h/l). The energy necessary to cleave is E6 2 leg. The energy to

follow the facet is E f = 6,- (1+ h). The fracture interface can only follow the grain boundary

89

if E 3 E1 or equivalently

 

E!

— >1
EC —
c(l+h) >1
1 _

E > l_1
l _ 5

Substituting the last result in the equation for the angle gives us the critical angle for a given
6 9

1
QC 2 arctan(— — 1).
c

It is locally favorable for the failure surface to follow all facets with angles 6 smaller than
66.

The argument above gives the local picture of how the interface roughens. According
to this local picture, the local fraction f L of grain boundaries that lie on a minimal energy

surface is given by,

0c
fL = / P(6)d0 (6.10)

9c
where P (61) is the probability that a grain boundary is at angle 19 to the cleavage direction.

The average deviation from the cleavage surface is

0c
h = g/ 6tan(0)d0.
0

In three dimensions the arguments are more complex. For the arguments below, however,
we only need to deﬁne a local fraction f L. A reﬁnement that may be important in some
cases, is to include the curvature of the grain boundaries. If curvature is included, the grain
boundaries may partially fail. For the grain structures I use here, the grain boundaries are

quite faceted.

9O

The argument above describes the local variations in the surface morphology. We seek,
however, the global minimum energy surface. To ﬁnd the global minimum we need to
consider the energy ﬂuctuations on large length scales. On large length scales, there exist
statistically favorable regions where a number of small angle facets are close to each other.
It is energetically favorable to include these regions in the minimum energy interface. To
include these favorable regions, it is necessary for the interface to wander. The interplay
between the desire of the interface to accommodate favorable regions with many low angle
facets and the energy cost of the wandering, determines the interface roughness. I now
make this energy balance quantitative.

According to the local argument, culminating in Eq. (6.10), the typical number of facets

that occur due to local deviations from a cleavage surface is given by
N; = fL(L/g)“‘1. (6.11)

The central limit theorem states the typical variation in this quantity is 6Nf : N fl/ 2. Such
variations can be either positive (unfavorable ﬂuctuations) or negative (favorable ﬂuctua-
tions). In our case, the favorable case corresponds to a clustering of grain boundaries that
have low angles to the cleavage direction. There is another factor that must be considered:
There are many ways in which a favorable ﬂuctuation on an interface may be selected.
That is, the minimal energy ﬂuctuations may occur in many different places in the material.
This is an entropy-like factor. The typical number of ways that the set N f of facets may
be selected on a cleavage plane is of order (L / g). To include this factor in estimating the

typical largest energy gain, set
L 2
—exp(—6Nf/Nf) z 1 (6.12)
9

The typical size of the most favorable ﬂuctuation in the number of low angle facets in a

91

minimal energy surface is then

L (d—1>/2 ‘
6‘\fmar ~ ~f1/2 (g) 10g1/2 (15') (6-13)

The typical energy gain for each favorable facet is 69(1 — c) 9""1 / 2. Multiplying this by the

typical largest favorable ﬂuctuation in the number of facets (Eq. (6.13)) gives

L (d-IV2 L
Ugain~ ~ — 69(1 _ {Md—1 [V2 (E) 10g1/2 (E) ' (614)

To take advantage of this energy gain, the interface must make excursions from the cleavage

plane of order the grain size. This leads to an energy cost of order
Umst z 696 ng—2.

Setting Ugain + Um, : 0 we get

 

 

e =2 f1/210g1/2(% ). (6.15)

Where B is an undetermined constant that depends on the details of the grain structure,

lattice structure, etc. In two dimensions Eq. (6. 15) becomes

2 , (6.16)

 

 

and in three dimensions

 

——€—— 2 f1/210g1/2 (% ). (6.17)

From Eqns. (6. 16) and (6.17) we can conclude that for large enough systems the cleavage

92

state is unstable to ﬂuctuations for any 6 < 1 in both two and three dimensions. Often this is
expressed as a critical length. In two dimensions, the logarithmic term is usually negligible.
Omitting the logarithmic term in Eq. (6.16) we ﬁnd that the critical length depends on grain

size and grain boundary adhesion in the following way,

—' = — , = (6.18)

 

 

where f (e) = 62 / (1 — a)? In three dimensions, the logarithm is important and it leads
to a critical length that is an exponential function of the grain boundary adhesion. From

Eq. (6.17) we have

 

E = exp (317(6)) . (6.19)
9 fL

For sample sizes L < LC the lowest energy interfaces have constant roughness, while for
sample sizes L > LC the interface roughens. LC is also the linear size of the cleavage
regions on the interface. These cleavage regions are terminated by steps which are of order
the grain size. Thus the minimal energy surfaces are expected to be quite ﬂat on length
scales less than LC and algebraically rough on larger length scales. The critical length
decreases continuously with increasing 6. At the transition point to the weak adhesion limit
(which occurs at 6 ~ I / 2) it becomes a constant and LC 2 g. The formulae (6.18) and
(6.19) are valid well above the transition to the weak adhesion limit.

In order to test the scaling theory, rewrite the roughness in terms of LC
. L C
”‘1 2 b1 (—) . (6.20)

Using Eq. (6.20) and all of my data on a range of sample sizes and for a range of values
of e > 1 / 2, I ﬁnd the data of Fig. 6.9. The data follow the predictions of Eqns. (6.20)

and (6.18) nicely, conﬁrming the basic physics of roughening in these polycrystalline mi-

93

 

    

 

 

 

 

 

 

 

 

,. I I IIIIIII I I I IIIIIII I 1 I I IIIIII J I I I IIIu.
.- o -4
I 4 I
r 0.65 a
_ - w/g ~ (L/L ) ° _
C
l - _
E =
E .‘ {'94. .‘1 :
00 r ' :
\ .- .1
3 ~ .
0.01 - _
O
E o o E
: ° ct: :
I- .-
0 0(6) 1 1 1111111 1 1 #111111; 1 1 1 1 111111 1 1 1 11111
. l 0.01 1 100

-2
LfL/g(£/( 1-8))
Figure 6.9: Scaling of roughness. The roughness w is plotted vs. L / Lc on a log-log scale.

All data for 0.6 S e g 0.95 and w 76 0 is included. The roughness exponent C c: 2/3.

crostructures.

From the theory developed above, it is straightforward to estimate the dependence on
the adhesion energy of the roughness w, interface fraction fi, energy E, and number of
bonds N in the limit 6 ——> 1.

Firstly, using Eqns. (6. 18) and (6.20), the roughness as a function of e behaves as

2
w _ fL 3 ~ 4 3 2/3
—L2/3g1/3 - Bl (7(5) ~ 3‘66 / h ‘6'“)

where 66 = 1 — e, and the last expression is the limiting behavior at small 66. The fraction

94

of minimum energy surface bonds which lie on grain boundaries is approximated by

g +(1+ h_)fLLc +(1— fL)Lc
: 1+(1+13)B2f(6) (6.23)
1+ (71L- +h.)B2f(e)

f L (6.24)

 

 

22

The total number of bonds on the minimal energy interface is approximated by

g + (1+ l—i)fLLc +(1— fL)Lc
LC

=1+i+EfL

Le
1+ FfL '1‘ 323(6)

— 662
g 1+hfL+§§fL

 

N
L

 

Finally, the energy of the minimum energy surface is given by

 

 

E N
279— : (I‘m—0ft)?
: 1_(1_€)1+(1-+-H)f(e)
+(ﬁ+ﬁ)f(e)
(1+EfL+ ngﬁd)
% (1"(1_€)fL)(1+EfL+éBf—2fL)
662 663

R5 1+EfL—66fL—EééfZ+-é§fL f2.

_ 35
For the grain structures I used, 7; is not important. I therefore use the approximations

g+Lc:1+ fL

L. B2f(c) (6'25)

 

 

N~
L~

95

and

 

E ~ fr.
Z6—g~(1—(1—6)fL)(1+Bf(E)). (6.26)

The ﬁts using the data from fL z f, are shown in Fig. 6.5 and Fig. 6.7.
The results of this section provide estimates of the behavior in the regime 1 > c > cc,

where (C ~ I / 2 for the grain structures used here in two dimensions.

6.5 Summary

There are three distinct fracture regimes. For 6 < 1 / 2 the minimum energy fracture surface
follows the grain boundaries. For 1 / 2 < c < 1 the interface includes both intragranular
bonds and grain boundary bonds and is instable against roughening. For 6 = 1 the interface
is a ﬂat cleavage interface. In the weak adhesion regime the minimal energy surfaces follow
the grain boundaries and are described by scaling theories that have been developed for the
roughness of domain walls in Ising magnets, but with a renormalized length scale L / g. The
ideal cleavage state at e = 1 is unstable to ﬂuctuations, so that any small reduction of the
grain boundary bonding from c = 1 leads to a mixed interface mode on long length scales.

We have developed a scaling theory to describe the behavior of the energy and interface
morphology in the mixed interface phase. In the mixed phase, in both two and three dimen-
sions, the minimum energy interface is ﬂat on length scales L < LC but it is rough on length
scales L >> LC. The dependence of LC on the grain size and the grain boundary adhesion
is a power law in two dimensions (see Eq. (6.18)), while this dependence is exponential in
three dimensions (see Eq. (6.19)). The scaling laws in two dimensions are conﬁrmed by

large scale simulations (see Fig. 6.9).

96

Chapter 7

Outlook

In both physics and computer science disordered systems serve as models for complexity.
Each discipline has developed methods for the study of disordered systems. Computer Sci-
ence studies are traditionally case studies concentrating on instances rather than averages.
Statistical physics, on the other hand, deals with the average properties and ﬂuctuations of
ensembles. Erdos’ study of randomly diluted graphs, for example, complements percola-
tion and is really a study of phase transitions. The methods of the study of phase transitions
allow a better classiﬁcation of NP-hard problems.

Although the random-ﬁeld Isin g Model has been studied for over three decades there are
still many fundamental questions open. The magnetization exponent 6 for the RFIM in 3D
is approximately 0. Neither numerical analysis nor experiment will be able to distinguish
between a ﬁrst and second order phase transition based on the magnetization. A better way
to decide the order of the transition might be to analyze the percolation behavior of the
majority and minority spin clusters. Other open question are: why does the inﬁnite-range
model fail to predict a phase transition for certain distributions of random ﬁelds, and why
do the results obtained on the Cayley tree differ from those of the inﬁnite-range model even

in the z —+ 00 limit?

97

My numerical analysis of the interface roughness in Chapter 6 is limited to 2D. The
natural next step is to do the numerics in 3D and test the scaling prediction. In 3D other
mechanisms, e.g., partial facet fracture, may play a role. In addition to the scaling of
minimal surfaces the scaling of shortest paths in polycrystalline materials is important.

Further improvements to the model should include an angle dependent adhesion energy.

98

Appendix A

Taylor Expansion of 13+ for the RFIM on
the Cayley Tree

I want to show that the second order term in the Taylor expansion of the steady state solution
of P1, disappears for general a.

The steady state equation for the RFIM on the Cayley tree is

O
a
1: 2 Z (L‘g(1-— I)a‘9a+(a, g)

9:0 9

Expand this in a Taylor series around 1: = 1 / 2.

W) = M) + from + $f”(0)x2 + . ..

The zeroth order term in the series is

99

The ﬁrst order term, f’(0), is

m, : 32C) (;+.)9(;-.)°‘9a.ra,gr

 

 

 

 

101

The second order term is

WW)

0 , ‘

if (1)

O I 9—2 a—g
; : (1+(asg) 9(9-1)(%+1‘) (é—I)

 

 

g—l a—g—l
—g(a—g) (3+1) ($— —1:) J

1., (0 a-+(a«g)[g(g-1)-9(a-g)+(a-g)(a-9-1)-9(a-9)l

1:20

 

 

 

 

 

 

 

 

.(l

102

Where the sum up to cr/‘Z for 0 odd means the sum up to (a— 1)/2. For even a a+ (a, 01/2) 2

a
1 /'2 does not disappear from the sum. It contributes 1 / 2 to the total sum, which
a / 2
. (1
gives 235) = 2"“.
9

103

Bibliography

[1] Amnon Aharony. Tricritical points in systems with random ﬁelds. Phys. Rev. B,
l8(7):3318—3327, October 1978. Mean ﬁeld approach and renormalization group
theory applied to the RFIM.

[2] M. J. Alava and P. M. Duxbury. Disorder-induced roughening in the three-
dimensional ising model. Physical Review B, 54(21): 14990—14993, December 1996.

[3] M. J. Alava, P. M. Duxbury, C. F. Moukarzel, and H. Rieger. Exact Combinatorial
Algorithms: Ground States of Disordered Systems, volume 18 of Phase Transitions
and Critical Phenomena. Academic Press, 2001.

[4] Réka Albert and Albert-Laszlo Barabassi. Statistical mechanics of complex networks.
arXiv:cond-mat/0106096, 6 June 2001.

[5] M. P. Anderson, D. J. Srolovitz, G.S. Grest, and RS. Shani. Computer simulation of
grain growth .1. kinetics. Acta Metallurgica, 32:783-791, 1984.

[6] George B. Arfken and Hans J. Weber. Mathematical Methods for Physicists. Aca-
demic Press, 4th edition, 1995.

[7] P. D. Beale and D. J. Srolovitz. Elastic fracture in random materials. Physical Review
B, 37(10):5500 — 5507, APR 1 1988.

[8] E. Bouchaud. Scaling properties of cracks. Journal of Physics-Condensed Matter,
9(21):43l9 — 4344, MAY 26 1997.

[9] J. P. Bouchaud and A. Georges. Competition between lattice pinning and impu-
rity pinning - variational theory and physical realizations. Physical Review Letters,
68(26):3908 — 3911, JUN 29 1992.

[10] R. Bruinsma. Random-ﬁeld Ising model on a Bethe lattice. Physical Review B,
30(1):289—299, July 1984.

[1 l] B. V. Cherkassky and A. V. Goldberg. On implementing the push-relabel method for
the maximum ﬂow problem. Algorithmica, 19(4):390—410, Dec 1997.

[12] Clay Mathematics Institute. The P versus NP problem. Clay Mathematics Institute.

104

[l3] J.-C. Anglés D’Auriac and N. Sourlas. The 3d random ﬁeld ising model at zero
temperature. Europhys. Lett., 39(5):473-478, 1997.

[14] Deepak Dhar, Prabodh Shukla, and James P. Sethna. Zero-temperature hysteresis in
the random-ﬁeld Ising model on a Bethe lattice. J. Phys. A: Math Gen., 30:5259—
5267, 1997.

[15] T. Emi g and T. Nattermann. Disorder driven roughening transitions of elastic mani-
folds and periodic elastic media. European Physical Journal B, 8(4):525 — 546, APR
1999.

[16] P. Erdos and A. Rényi. On random graphs 1. Publ. Math. Debrecen, 6:290—297, 1959.

[17] Daniel S. Fisher. Interface ﬂuctuations in disordered systems: 5- epsilon expansion
and failure of dimensional reduction. Physical Review Letters, 5611964, 1986.

[18] Shmuel Fishman and Amnon Aharony. Random ﬁeld effects in disordered anisotropic
antiferromagnets. J. of Phys. C: Solid State Phys, 122L729—L733, 1979.

[19] A.V. Goldberg and RE. Tarjan. A new approach to the maximum—ﬂow problem.
Journal of the Association for Computing Machinery, 35(4):921—940, October 1988.

[20] Alexander K. Hartmann and U. Nowak. Universality in three-dimensional random
ﬁeld ground states. cond-mat/9807131, 1998.

[21] Alexander K. Hartmann and Martin Weigt. Statistical mechanics perspective on
the phase transition in vertex covering of ﬁnite-connectivity random graphs. cond-
mat/0006316, June 2000.

[22] Gregory N. Hassold and Elizabeth A. Holm. A fast serial algorithm for the ﬁnite
temperature quenched Potts model. Computers in Physics, 7(1):97—107, 1993.

[23] E. A. Holm. Surface formation energy for intergranular fracture in two-dimensional
polycrystals. Journal of the American Ceramic Society, 81(3):455 — 459, MAR 1998.

[24] Elizabeth A. Holm and Corbette C. Battaile. The computer simulation of microstruc-
tural evolution. Joumal of The Minerals, Metals & Materials Society, 53(9):20—23,
2001.

[25] Kerson Huang. Statistical mechanics. John Wiley & Sons, Inc, 2 edition, 1987.

[26] David A. Huse and Christopher L. Henley. Pinning and roughening of domain walls
in Ising systems due to random impurities. Physical Review E, 542708, 1985.

[27] John Z. Imbrie. Lower critical dimension of the random-ﬁeld Ising model. Physical
Review Letters, 53(18): 1747—1750, 29 August 1984.

105

[28] Yoseph Imry and Shang keng Ma. Random-ﬁeld instability of the ordered state of
continuous symmetry. Physical Review Letters, 35(21):1399—1401, 1975.

[29] Ernst Ising. Beitrag zur Theorie des F erro- und Paramagnetismus. PhD thesis, Uni-
versit'at Hamburg, 1924.

[30] Ernst Ising. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift ﬁir Physik,
31:253—258, 1925.

[31] Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random Graph. John Wiley
& Sons, Inc., 2000.

[32] Dieter Jungnickel. Graphen, Netzwerke und Algorithmen. BI Wissenschaftsverlag, 3
edition, 1994.

[33] Mark Kac. Statistical Physics, phase transitions, and superﬂuidity, volume 1, chapter
Mathematical mechanisms of phase transitions, page 241. Gordon and Breach, New
York, 1968.

[34] L. P. Kadanoff. Physics, 2:263, 1966.

[35] Sigismund Kobe. Ernst Ising - Physicist and teacher. Journal of Statistical Physics,
88(3-4):99l—995, August 1997.

[36] Wilhelm Lenz. Phys. ZS., 21:613, 1920.

[37] Kurt Mehlhom, Stefan Naeher, et a]. LEDA, the Library of Efﬁcient Data types and
Algorithms. LEDA is now published by Algorithmic Solutions and is available at
www.algorithmic-solutions.com.

[38] A. Alan Middleton. Numerical results for the ground-state interface in a random
medium. Physical Review E, 52:R3337—R3340, October 1995.

[39] Andrew T. Ogielski. Integer optimization and zero-temperature ﬁxed point in Ising
random-ﬁeld systems. Physical Review Letters, 57(10): 1251—1254, September 1986.
First paper using maxﬂow to determine magnetization in groundstate.

[40] R Peierls. On Ising’s model of ferromagnetism. P. Cambridge Philos. S., 32:477,
1936.

[41] V. I. Raisanen, E. T. Sepp'al'a, M. J. Alava, and P. M. Duxbury. Quasistatic cracks and
minimal energy surfaces. Physical Review Letters, 80(2):329 - 332, JAN 12 1998.

[42] L. E. Reich]. A Modern Course in Statistical Physics. University of Texas Press,
1980.

[43] Steffen Reith and Heribert Vollmer. Wer wird Million'zir? Komplexit'atstheorie:
Konzepte und Herausforderungen. c’t, (07):240—251, 2001.

106

[44] M. Sahimi and J. D. Goddard. Elastic percolation models for cohesive mechanical
failure in seterogeneous systems. Physical Review B, 33(11):7848 — 7851, JUN 1
1986.

[45] E. T. Seppal‘a, M. J. Alava, and P. M. Duxbury. Intermittence and roughening of
periodic elastic media - art. no. 036126. Physical Review E, 6303(3):6126 — +, MAR
2001.

[46] Nicolas Sourlas. Universality in random systems: The case of the 3-d random—ﬁeld
Ising model. unpublished, 1998.

[47] D. J. Srolovitz, M. P. Anderson, P. S. Sahni, and G. S. Grest. Computer simulation of
grain growth .2. grain-size distribution, topology and local dynamics. Acta Metallur-
gica, 32:793—802, 1984.

[48] H. Eugene Stanley. Introduction to Phase Transitions and Critical Phenomena. Ox-
ford University Press, 1971.

[49] Dietrich Stauffer and Amnon Aharony. Introduction to Percolation Theory. Taylor &
Francis, revised 2nd edition, 1994.

[50] AP. Sutton and R.W. Balufﬁ. Interfaces in Crystalline Materials. Oxford University
Press, 1995.

[51] Michael R. Swift, A. J. Bray, Amos Maritan, Marek Cieplak, and Jayanth R. Ba-
navar. Scaling of the random-ﬁeld Ising model at zero temperature. Europhys. Lett.,
38(4):273-278, 1 May 1997.

[52] Michael R. Swift, Amos Maritan, Marek Cieplak, and Jayanth R. Banavar. Phase
diagrams of random-ﬁeld Ising systems. Journal of Physics A: Math. Gen., 27:1525—
1532, 1994.

[53] D. I. Uzunov. Introduction to the Theory of Critical Phenomena. World Scientiﬁc,
1993.

[54] J. D. Verhoeven, A. H. Pendray, and W. E. Dauksch. The key role of impurities in
ancient Damascus steel blades. Journal of The Minerals, Metals & Materials Society,
50(9):58—64, 1998.

[55] John D. Verhoeven. The mystery of Damascus blades. Scientific American,
284(1):74—79, January 2001.

[56] Martin Wei gt and Alexander K. Hartmann. Number of guards needed by a museum:
A phase transition in vertex covering of random graphs. Physical Review Letters,

84(26):6l 18—6121, June 2000.

107

[57] Martin Weigt and Alexander K. Hartmann. Minimal vertex covers on ﬁnite-
connectivity random graphs - a hard-sphere lattice picture. Physical Review E,
63:056127, 2001.

[58] Martin Weigt and Alexander K. Hartmann. Typical solution time for a vertex-
covering algorithm on ﬁnite-connectivity random graphs. Physical Review Letters,
86(8):1658—1661, February 2001.

[59] A. Zangwill. Physics at Surfaces. Cambridge University Press, 1988.

108

Glossary

Manifold A topological space that is locally ﬂat, or Euclidian. More formally, for every
point in a manifold there exists a neighborhood and a continuous transformation of
that neighborhood into an open unit ball of the same dimension.

NP Nondeterrninistic Polynomial. A class of problems in computer science where a known
solution can be veriﬁed in polynomial time.

NP-complete A class of problems in computer science that has no known polynomial
algorithm for all problem instances but a solution can be veriﬁed in polynomial time.
Each problem of the class can be mapped into any other NP complete problem by a
polynomial algorithm.

109

Index

Cayley tree, 25—26
percolation, 35—38
RFIM, 66—69

complete graph, 38

critical exponent, 11

cut, 45

edges, 38

ﬂow
feasible, 45

giant cluster, 38
graph, 38

homogeneous functions, 13
hyperscaling, 17

Josephson law, 17

Landau theory, 29—32
lattice gas, 3

manifold, 40, 109
maximal independent set, 3
maximum ﬂow algorithm
augmenting path, 50
push relabel, 52
maximum ﬂow/minimum cut theorem, 45

nodes, 38

nondeterrninistic polynomial, 2, 109
NP, see nondeterrninistic polynomial
NP-complete, 3, 109

partition function, 12
percolation, 32—39
bond percolation, 32
site percolation, 33

quenched disorder, 32

random graph, 38

random-bond Ising model, 41
random-ﬁeld Ising model, 42

RBIM, see random-bond Ising model
renormalization group, 28

residual graph, 50

RFIM, see random-ﬁeld Ising model
Rushbrooke equality, 16

scaling hypothesis, 12
traveling salesman, 2
universality class, 29
vertex cover, 2
Widom equality, 16

Zustandsfunktion, 12

110

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

[Ill[Illlﬂlqlll'ﬂﬂllalllllsllyylll