v
kg
can. .i
. a... n.
as?

q
.E... ~
u 2c

3.

r.- .
2:...

15:259....
.14 .3..4.C..I
t! 1.21..
a.

3ft.

 

 

 

 

'13:: 5m "

 

 

2 LIBRARY
2002? Michigan State
University

 

 

This is to certify that the
dissertation entitled

Statistical Mechanics of Vertex Cover

presented by

Charles W Fay IV

has been accepted towards fulfillment
of the requirements for the

Doctoral degree in Physics and Astronomy

 

 

(Wm

Major Profe'ssor’s Signature
lot/W o 7

Date

MSU is an affirmative-action, equal-opportunity employer

 

 

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.

 

DAIEDUE

DAIEDUE

DAIEDUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:/ClRC/DateDue.indd-p.1

STATISTICAL MECHANICS OF VERTEX COVER

By
Charles W Pay IV

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Physics and Astronomy

2007

ABSTRACT
STATISTICAL MECHANICS OF VERTEX COVER

By
Charles W Pay IV

Vertex cover is a member of a class of problems that is known to be computa-
tionally hard, and includes the spin-glass and the hard-core lattice gas problems. In
computer science this class of problems is known as NP-complete. NP-complete
problems display a phase transition between easy and difficult instances. In the
worst instances these problems can require a number of operations that scales ex-
ponentially in relation to the size of the input. The class of NP-complete problems
provides one of the main motivations for quantum computing, and they impinge
on nearly every area of physics.

This dissertation presents an investigation of computational techniques to sim-
ulate and analyze the behaviour of vertex cover in two and three dimensions. First,
the method of reducing a graph by removing small cliques, known as core perco-
lation, is presented. Core percolation by leaf removal is analyzed on the Bethe
lattice. The percolative behaviour of the ErdOs-Réyni random graph, the triangu-
lar lattice, the square lattice and the FCC and simple cubic lattices are examined
after leaf removal and after triangle removal. The scaling is found to be in the
same universality class as standard percolation. Then a novel approach to finding
a near ground state at zero temperature is found for vertex cover, by the analysis of
local structure. The behaviour of this algorithm is compared to the replica method
and some exact methods. The data generated compares favorably to methods for

finding exact covers

© Copyright December 13, 2007 by

Charles W Fay IV
All Rights Reserved

ACKNOWLEDGMENTS

I would like to thank my wife Angela, and my family for all of their encourage-
ment.

iv

TABLE OF CONTENTS

LIST OF TABLES viii
LIST OF FIGURES ix
1 Introduction 1
2 Physics of Hard Computational Problems 4
2.1 Spin glasses ................................... 4
2.1.1 Frustration ................................... 13
2.2 Hard core lattice gas .............................. 14
2.2.1 A physical example .............................. 16
2.3 Diluted anti-ferromagnet and the hard-core lattice gas ........... 18
2.4 Spin glass applications ............................. 19
2.4.1 Neural networks ............................... 19
2.4.2 Protein folding ................................ 21
2.4.3 Combinatorial optimization ......................... 21
3 Computational Complexity 22
3.1 NP-completeness ................................ 23
3.1.1 P to NP transition ............................... 24
3.1.2 The traveling salesman ............................ 27
3.1.3 3-SAT and K-SAT ............................... 28
3.1.4 Vertex cover .................................. 29
3.1.5 Maximum independent set ......................... 31
3.1.6 NP-complete games ............................. 32
3.2 Mappings .................................... 33
3.2.1 Mapping K-SAT to vertex cover ....................... 33
3.2.2 Mapping vertex cover to the hard core lattice gas ............ 34
3.3 Analytic results for VC: vertex cover on trees ................ 35
4 Algorithms 38
4.1 Exact algorithms ................................. 39
4.1.1 Divide and conquer ............................. 40
4.1.2 Branch and bound .............................. 42
4.1.3 An algorithm by Tarjan and Trojanowski ................. 44
4.2 Reduction of diluted graphs .......................... 45
4.2.1 Core percolation by leaf removal ...................... 45
4.2.2 Leaf removal on the Bethe lattice ...................... 50
4.2.3 Core percolation by triangle (and leaf) removal .............. 52
4.3 Heuristic algorithms .............................. 54
4.3.1 Greedy algorithms .............................. 55
4.3.2 Random selection algorithm ......................... 55

4.3.3 Vertex-Local Probability Recursion (vLoPR) ................ 56

4.3.4 Analytic solution of vLoPR ......................... 59
4.3.5 The vertex-LOPR algorithm ......................... 60
4.3.6 DIG ....................................... 62
4.3.7 Bond-LOPR (bLoPR) ............................. 63
4.3.8 Analytic solution of bLoPR ......................... 65
4.3.9 The bond-LOPR algorithm .......................... 67
4.3.10 Convergence of vertex and bond LOPR .................. 69
5 Core Percolation 76
5.1 Core percolation by leaf removal on random graphs ............ 77
5.1.1 Generation of random graphs ........................ 77
5.1.2 Random graph results ............................ 78
5.2 Core percolation by leaf removal on regular lattices ............ 84
5.2.1 Graph generation ............................... 90
5.2.2 Leaf removal on 2-d lattices ......................... 90
5.2.3 Leaf removal on 3-d lattices ......................... 98
5.3 Summary of core percolation by leaf removal ................ 100
5.4 Core percolation by triangle removal ..................... 104
5.4.1 Triangle removal on a random graph .................... 115
5.4.2 Summary of triangle removal ........................ 115
6 Local Probability Recursion 121
6.1 LOPR on the triangular lattice ......................... 123
6.2 LOPR on the square lattice ........................... 127
6.3 LOPR on the FCC lattice ............................ 134
6.4 LoPR on the simple cubic lattice ........................ 135
6.5 LOPR on the random graph .......................... 138
6.6 Summary ..................................... 141
7 Conclusion 143
7.1 Conclusion .................................... 143
7.2 Further Work .................................. 144
APPENDICES 146
A Percolation 147
A] Introduction ................................... 147
A2 The infinite cluster on the Bethe lattice .................... 148
A3 Mean cluster size ................................ 150
AA Finite-size scaling in percolation ....................... 150
A5 Bond percolation on regular lattices with free boundary conditions . . . 151
B Replica Symmetric Calculations 159
B] Replica Method on the Ising Spin Glass [83] ................. 159
B2 Replica solution to the lattice gas [94] ..................... 165

vi

BIBLIOGRAPHY 172

vii

LIST OF TABLES

4.1 Solution frequency for LoPR algorithms ................... 75
5.1 Critical exponents for core percolation on random graphs ......... 84
5.2 Percolation thresholds for bond, and core percolation ........... 85
5.3 Core percolation exponents for 2-d lattices .................. 97
5.4 Comparison of exponents for 3-d lattices after leaf removal ........ 99
5.5 Comparison of exponents after triangle removal .............. 114
A.1 Standard percolation exponents ........................ 151

A2 Comparison of percolation exponents .................... 152

viii

LIST OF FIGURES

2.1 AC susceptibility of dilute magnetic alloys ................. 5
2.2 Order parameter distribution for a spin-glass ................ 10
2.3 RSB and its ultrametric structure ....................... 11
2.4 Frustration .................................... 13
3.1 A solution for VC and M18 on two clusters ................. 31
3.2 Mapping K-SAT to vertex cover ........................ 33
3.3 Representation of a Bethe lattice ........................ 35
4.1 Core percolation by leaf removal ....................... 46
4.2 Percolation Thresholds of bond, core and triangle percolation ...... 47
4.3 Percolation Thresholds of bond, core on the random graph ........ 48
4.4 I n ......................................... 50
4.5 Xn ......................................... 51
4.6 [C ......................................... 51
4.7 XC ......................................... 52
4.8 Visualization of LOPR and DIG solutions .................. 58
4.9 Convergence of LOPR .............................. 69
4.10 Convergence of vertex-LOPR .......................... 70
4.11 Convergence of bond-LOPR .......................... 71
4.12 Convergence of LOPR using a single randomized node list ........ 72
4.13 Convergence of vertex-LOPR using a single randomized node list . . . . 73
4.14 Convergence of bond-LOPR using a single randomized node list ..... 74
5.1 Giant cluster probability for a random graph ................ 79
5.2 Number of edges in giant cluster for random graph ............ 80

ix

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10
5.11
5.12
5.13
5.14
5.15
5.16
5.17
5.18
5.19
5.20
5.21
5.22
5.23
5.24
5.25
5.26
5.27
5.28
5.29

Connectivity of the core of a random graph versus connectivity. ..... 81

Finite size effects of core percolation on random graphs ........... 82
Finite size scaling of giant cluster in a random graph ............ 83
P5 and P00 vs connectivity for core percolation on a triangular lattices. . 86
P5 and Poo vs connectivity for core percolation on square lattices. . . . . 87
P3 and P00 vs connectivity for core percolation on FCC lattices ....... 88
P5 and Poo vs connectivity for core percolation on a simple cubic lattices. 89

Log-log plot of the width of P5 transition vs L on 2-d lattices ........ 91
Plot of p l as a function of tip, for 2-d lattices ................. 92
Higher order finite size scaling for 2—d lattices ................ 93
Scaling of Poo on 2-d lattices .......................... 94
Average cluster size on approach to p l for 2-d lattices ........... 95
Cluster size distributions for 2-d lattices ................... 96
Log-log plot of the width of P3 transition vs L on 3-d lattices ........ 100
Plot of p I as a function of 5p, for 2-d lattices ................. 101
Higher order finite size scaling of 3-d lattices ................ 102
Scaling of P00 for 3—d lattices .......................... 103
Average cluster size on approach to PI for 3-d lattices ........... 104
Cluster size distribution for 3-d lattices ................... 105
P3 and Poo vs connectivity on a FCC lattice after triangle removal . . . . 106
P5 and P00 vs connectivity on a FCC lattice after triangle removal . . . . 107
5m as function of L after triangle removal on triangular and FCC lattices 108
pt versus (5;); after triangle removal on triangular and FCC lattices . . . . 109
Higher order finite size scaling after triangle removal ........... 110
Scaling of Poo after triangle removal on the triangular and FCC lattices . 111

Average cluster size after triangle removal on triangular and FCC lattices 112

Cluster size distribution for the triangular lattice after triangle removal . 113

5.30 Giant cluster probability for a random graph after triangle removal . . . 116

5.31 Number of edges in giant cluster for random graph ...... ~ ...... 117
5.32 Connectivity of the core after triangle removal of a random graph. . . . . 118
5.33 Finite size effects of core percolation on random graphs ........... 119
5.34 Finite Size Scaling of core after triangle removal on a random graph. . . 120
6.1 Histogram of vertex probabilities in LOPR on triangular lattice ...... 124
6.2 Size of MIS and frozen fraction on a triangular lattice ........... 125
6.3 Histogram of vertex probabilities in LOPR on a square lattice ....... 128
6.4 Size of MIS and frozen fraction on a square lattice ............. 129
6.5 Histogram of vertex probabilities in LOPR on an FCC lattice ....... 132
6.6 Size of MIS and frozen fraction on an FCC lattice .............. 133
6.7 Histogram of vertex probabilities in LOPR on a simple cubic lattice . . . 136
6.8 Size of MIS and frozen fraction on a simple cubic lattice .......... 137
6.9 Histogram of vertex probabilities in LOPR on a random graph ...... 139
6.10 Size of MIS and frozen fraction on a random graph ............. 140
A.1 Log-log plot of the width of PS transition vs L for bond percolation. . . . 154
A2 Plot of Pb as a function of (Spb for bond percolation ............. 155
A3 Average cluster size on approach to Pb for bond percolation ....... 156
A.4 Cluster size distribution for bond percolation on 2-d lattices ....... 157
A5 Cluster size distribution for bond percolation on 3-d lattices ....... 158

IMAGES IN THIS DISSERTATION ARE PRESENTED IN COLOR

xi

Chapter 1

Introduction

In recent years we have seen an explosion in the crossover of scientific disciplines.
One area that has seen a large amount of interest is the area of computational op-
timization. As computer simulation becomes increasingly important for a wide
variety of disciplines, it becomes necessary to do simulations as quickly and ef-
ficiently as possible. A large number of common problems have been found to
map to known computationally difficult problems. Among these problems are the
ground state of the spin-glass, protein folding, neural networks, time table design,

and games like Tetris and Sudoku.

In physics, much work has been done on the ground state of spin-glasses. It is
known that finding the ground state of a spin-glass is computationally hard. In the
second chapter of my thesis I will review the basics of the spin-glass problem, out-
lining the replica method, replica symmetry breaking and the rough free-energy
landscape this implies. I will outline similar problems known to physicists, that
can be mapped to a spin-glass, such as the hard-core lattice gas, protein folding
and neural networks. These systems can be modeled with statistical mechanics
and display glassy behaviour. These problems also map to the computationally

hard class of problems known in Computer Science as nondeterministic polyno-

mial complete (NP-complete).

In the third chapter, I will review the concept of computational complexity in
NP-complete problems, outlining some basic NP-complete problems. I will map
the hard-core lattice gas to the NP-complete problems Of vertex cover, and maxi-
mum independent set. NP-complete problems display a phase transition, between
regimes where is it commonly easy to find a solution and regimes where it is dif-
ficult to find a solution. As physicists we can apply what we know about phase
transitions to study and classify the transition region. I will review the replica sym-
metric solution to the hard-core lattice gas to find a solution to vertex cover, and

compare this to our analysis of the solution on the Bethe lattice [37].

Chapter 4 will examine algorithms I used in generating my numerical results.
First, I will present some basic algorithms used to find exact solutions on vertex
cover. I will also present the leaf-removal and triangle procedures which are a
subset of the minimum vertex cover algorithm by Tarjan and Trojanowski [87].
Leaf removal was previously utilized by Karp [46] in a study of matching, and
Bauer and Golinelli [4] for calculating the maximum independent set on a random
graph. Leaf removal has also been used by Correale et. al. to study core percola-
tion in Boolean networks [15]. I will analyze leaf-removal on the Bethe lattice [38].
Since exact solutions of NP-complete problems can handle no more than a few
hundred sites, we often have to resort to heuristics to find near optimal solutions.
A good heuristic will give some insight into the actual solutions and the nature of
the ground state. Two common heuristics for vertex cover are greedy and random
selection, I will outline these two before presenting and analyzing a new heuris-
tic for vertex cover, that we have termed LOPR, which relies upon local cluster

geometries [40] [37].

Chapter 5 is devoted to analyzing the percolative results of leaf removal on the

random graph, and the triangular, square, simple cubic and FCC lattices. Here

we Show that leaf removal is in the same universality class as standard percola-
tion. The results for the triangular lattice have been published [40], while a paper
detailing the results on the other regular lattices is in preparation [37]. Chapter 5
also contains the results of triangle removal on the FCC and triangular lattices [38].
Triangle removal is also in the same universality class as standard percolation.
The sixth chapter presents the approximate solution of maximum independent
set problems using our LOPR procedures, on the triangle, square, FCC, simple cu-
bic lattices and the random graph. LOPR shows good results on finding the car-
dinality of the maximum independent set, but fails to fully represent the frozen
fraction. Results for LOPR on the triangle lattice have been published [40], a paper

detailing the results on the other lattices is in preparation [39].

Chapter 2

Physics of Hard Computational

Problems

2.1 Spin glasses

A spin glass is a collection of spins that in its low-temperature state has a back-
bone of frozen and disordered sites [22], the Sites not residing on the backbone
are allowed to fluctuate. In order to construct such a phase two ingredients are

necessary, disorder and frustration (see section 2.1.1).

In the nineteen-fifties and early nineteen-sixties, measurements were made on
alloys such as AuFe and CuMn that exhibited unusual properties in the AC mag-
netic susceptibilities. The experimental properties as listed by Chowdhury [13] are:
(i) the ac susceptibility Xac(T) exhibits a cusp at temperature T3 at low-frequency
and in low magnetic fields see Fig. 2.1, (ii) no sharp anomaly appears in the specific
heat (iii) below T3 the magnetic response is dependent upon previous magnetiza-
tions, (iv) below T3 the remnant magnetic field decays very slowly over time, (v)
below T3 a hysteresis curve, laterally shifted from the origin appears in the mag-

netization, (vi) below T3 no magnetic Bragg scattering is observed, demonstrating

an absence of periodic long range order, (vii) the susceptibility begins to deviate

from the Curie law at temperature T > > T8 [13].

Physical systems that have been associated with spin glasses include, dilute
magnetic alloys (such as AuFe and CuMn mentioned earlier) and amorphous mag-
netic systems (such as FeMn, CoMn and CrSnTe4). Chowdhury, [13] contains a

description of many physical SG systems.

 

 

sob 9",;
'o.4{\Ag:-:10% Mn
4.0% ” ' . 9 o.
: : «f ’9
L. ’3: O O“‘ .0
o I
Pl ‘. \a. Au-0.2°/o Cr
go 30L .' ', \‘f’ (xm)
E o. 0
no b / O . .
é ',Au-0.S% Mn a .
32 2.0L- '..
0..
L / .‘o.
Ag-0.5%Mn "0.,
I 0 / h
° F Cu-0.1% Mn
)-
0 IL.I.ILI.4LIJ_IJLL1.J
l 2 3 4 S 6 7 8 9 10

70‘)

Figure 2.1: Cusp in the AC susceptibility of dilute magnetic alloys [22]

Progress toward a mean field solution for spin glasses began in 1975, with the

Edwards-Anderson model (EA), [19] ;
1 a _.
H = —-2- E11751” Sj (2.1)
(11)

where lij is the magnetic coupling between sites i and j, if Iij > 0 the coupling
is ferromagnetic and if Iij < 0 the coupling is anti-ferromagnetic. The spins are
classical dipoles free to point in any direction. Edwards and Anderson introduced

the spin-glass order parameter defined by,

(IE/l“) = l5i(t)’5i(0)lave, (2.2)

where the square brackets ( Have), denote the time average. The EA model’s order-
parameter is a measure of the long-time auto-correlation [13]. In the long time limit

as t —> 00, we expect Eq. (2.2) to be equal to the static EA order parameter,

qEA = [[silzlave, (2.3)

(2.4)

the brackets ([]) denote the thermal average. In the spin glass phase, because of a

lack of long range ferromagnetic order, the magnetization is
m = [81'] : 0, (2.5)

while the spin-glass order-parameter is non-zero. The random spin interactions

are given by a Gaussian distribution of,

P<I.-,-> o< exp(—I?,-/212po). (2.6)

where I2 2 iii [12]. and p0 is the density of bond occupation [19].

Sherrington and Kirkpatrick [83] solved an Edward-Anderson type system
with Ising-spins, having N infinite range interactions. Moreover, in terms of the
free energy, it has been shown that as the dimension, D, of the EA model in-

creases [78],

lim EA(D) = SK. (2.7)

D—>oo
The SK model is important because it was the first spin-glass system solved, giving
mean-field values for the spin-glass. The disorder and frustration is supplied by
the parameter Iij which can vary randomly between positive and negative values.

The Hamiltonian of the SK model is Similar to the EA model, containing Ising

spins in place of the vector spins,
1
H : —E Z Iijsisj (2.8)
(11)
with a Gaussian distribution of Iij given as,

(Iij - I0)2)

PUij) = [Ti—fie”) (- le (2-9)

with IO and I scaled, to meet the requirement that the free energy is extensive, by,

10:70/N and [=f/N1/2 (2.10)

where 70 and I are intensive and N is the number of spins in the system. The
relative magnitudes of [0 and f determine if spin-glass ordering or ferromagnetism

occur at low temperatures [50]. The partition function of the SK model is,

z = gem-g- }: Iijsisj), (2.11)
Si (17')

from which the physical properties may be calculated for example the free energy,

P = —kBTan. (2.12)

In systems that are highly disordered like spin-glasses, it is often difficult to
calculate quantities like the free energy that are dependent upon the averaged log-
arithm of the partition function. The replica method allows us to determine the
logarithm of the partition function by the expansion of a replicated partition func-
tion,

(2.13)

 

(an) = < lim Z" —1>,

n—rO Tl
the brackets (()) signify an average over the disorder. Eq. (2.13) is derived from
the expansion [53],

z" = 1+n1nZ+O(n2). (2.14)

For a more detailed derivation of the replica method on the SK model see Ap-
pendix B. In the replica method, the partition function is copied n times. To av-
erage over the quenched couplings, one takes the thermodynamic limit N —) co,
and then uses the mathematically dubious process of doing analytic continuation
on integers, to take the limit as n —-+ 0. The order parameter is now a matrix with

elements,

40,5 = (sf .315), (2.15)

a and B are replica indices. If all overlaps between replicas are assumed to collapse

into a steady state value,

q 2 (MB-1 if“ 71" fl (2.16)

This is known as the replica symmetric solution. After a bit of work we arrive at

the order parameter and the magnetization from the SK model (see Appendix B),

_ _ _1_ —22/2 2 I 1/2Z +_I_0m

q — 1 m fdze sech (k—Tq +kTm (2.17)
_ _1_ ~22/2 I 1/2Z +_I_om

m — _Zn/dze tanh (k—Tq +ka (2.18)

m = 0 and q 75 0 indicates the spin-glass phase.

Almeida and Thouless showed that the SK model was correct above the critical
temperature Tg. At low temperatures, the entropy calculated from the symmetric
SK method becomes negative and the solution becomes unstable. The entropy

calculated from the symmetric SK model is [16] [50],

S ‘2 H
K, ——— —[’—g'.f,i +<4,{T-—2)<1—q)<1+3q>——;"-
+k(27r)—1/2fdzexp(—%)ln(2coshZ). (2.19)

This entropy is negative and nonphysical when T —+ 0, H = 0, m = 0. In finite
fields, H > 0, the onset of replica symmetry breaking (RSB) defines the Almeida-
Thouless line [16].

In 1977, Thouless, Anderson and Palmer (TAP) generated mean-field equations
for the SK model [88]. The TAP equations describe a ”many valley” picture of the
rough free-energy surface defining the solution space. The lowest valleys corre-
spond to stable thermodynamic states, the vast majority of valleys are meta-stable
states [9]. The number of solutions (stable and meta-stable) is exponential in N
(exp(aN)). We can imagine the surface as a series of valleys separated by barriers
that become infinitely tall in the limit N becomes large. In these valleys, we may
have local minima that are separated by finite barriers, any valleys not correspond-

ing to global minima would be meta-stable states [22].

Replica symmetry breaking is evident in the order-parameter, in the RS solution

 

2.5

 

 

 

Err.
Wm“

 

 

 

 

 

 

 

0.5 ..-.....

-1 -0.5 0 - 0.5 1

 

Figure 2.2: The order parameter distribution, P(q) = (P](q)) for a Spin-glass [78].

there is one spin-glass order parameter, while in the RSB solution there exists an
infinite number of order parameters [74] [75] [76] forming the matrix in Eq. 2.15.
The Parisi method of symmetry breaking proceeds by starting with the replica
symmetric matrix and dividing it into (n x ml) x (n x ml) blocks, see Fig. 2.3. The
off-diagonal blocks are left unmodified with a value of ‘70 and the diagonal blocks
are assigned a value of 41- The diagonal blocks are further subdivided iteratively
[58]. Breaking the symmetry of the order-parameter into an infinite number of
matrix elements makes the determination of a solution Significantly more difficult
[62]. This matrix is associated with a function q(x) describing the order parameter

[75]. This function exists on the interval [0 —- 1] and is defined by,
q(x) = ql- if m,- < x < mi+1 (220)

The sum is done over all n(n — 1)/ 2 pairs of replica indices, the normalization

insures (1(0) 2 1 [74] [62]. Parisi lists some interesting qualities of the function

10

q(x); (i) q(x) is piecewise constant under K-step symmetry breaking taking on
K+1 values, (ii) x(q) the inverse function is discontinuous, and gives the order
parameter distribution,

PM) = 5' (2.21)

(iii) q(x) is continuous in the K —> oo limit, leading to continuous replica symmetry
breaking [78]. The function P(q) has the form of two delta functions at ten; A
with a flat region in between in zero magnetic field [78]. Figure 2.2 shows the
order parameter distribution for a spin glass. The quantity P] (q) is the ”probability
distribution of the overlap among two equilibrium states” [78]. When we average
P](q) over the disorder, we arrive at the mean field approximation of the order

parameter distribution,

P(q) = <P](q))- (2-22)

 

 

 

 

'1

Figure 2.3: Diagram of Parisi’s replica symmetry breaking procedure and the tree-
like structure of its solutions. From Mezard et. a1. [57] [58].

The Parisi method of symmetry breaking the solution implies a multiplicity of
states, organized in a ultrametric structure [57]. The structure of the space, implies

that the order parameter is not self-averaging, but depends on the realization of

11

the couplings [60]. Fig. 2.3(b) shows the tree like structure of an ultrametric space,
stable states are the lowest points in the trees. The distance between two states is
the number of steps one needs to make on the ultrametric tree to get to another
state. The representation becomes a genealogical tree such as in Fig. 2.3. The
states of the systems are the extremities of the trees, while the overlap between
states ”depends only on their closest ancestor” [60]. These states are believed to
correspond to the global minimums from the TAP equations [22]. For a stable state
a there is an ultrametric distance Da (i, j) between the N sites. There is a minimum
distance d such that for two states with an overlap qafi, the distances Da and D fl
are equal and D“ (i, j) 2 d [60]. This means for any three states forming a triangle,
the triangle will be either equilateral or isosceles. For a ultrametric space we have
the inequality,

dafi g max(da7,dfi,y). (2.23)

”In an ultrametric space after any number of fixed length steps one discovers one-
self at the same initial distance from the starting point" [62]. All points then lie
in one cluster. The equilibrium states are divided by energy barriers that become
infinitely high in the thermodynamic limit. These states are believed to correspond

to the global minimums from the TAP equations [22].

Questions have been raised about the interpretation of the existence of an infi-
nite number of ground states on real finite size spin-glasses by Newman and Stein,
where they have shown that there are a small number of ground states with the

metastable states sitting on the boundaries of the real solutions [68] [67].

Glass phases have been shown to exist in p-spin glasses that are not frustrated

[25], and have also been demonstrated in spin systems without disorder [7].

12

 

Figure 2.4: Frustration as shown on two plaquettes, the first plaquette is not frus-
trated. The second is unable to fully satisfy all bonds.

2.1.1 Frustration

Frustration is the term that is applied to the competing interactions that form an
important ingredient in any spin-glass [89]. To examine frustration, lets consider
for a moment a 2-d square lattice with an Edwards-Anderson Ising model, Fig. 2.4.
For the purposes of illustration, the interactions here are i], a ”+ I ” interaction is
ferromagnetic, causing the spins to want to be aligned, while a ”— I ” interaction
is anti-ferromagnetic causing the spins to be in opposite directions. If we place
two ferromagnetic bonds randomly and two anti-ferromagnetic bonds randomly
on the square plaquette, Fig. 2.4(a), we can see that it is easy to satisfy the plaque-
tte regardless of the placement of the bonds illustrating a case of disorder but no
frustration. However, if we place an odd number of ”— I" bonds on the plaquette,
then there will be one bond that cannot be satisfied. If all the bonds have the same
value for | I I then there is a degeneracy in the ground state of 4. If different values
of | lij I are placed into the frustrated plaquette, the degeneracy is broken, and
there exists the possibility of metastable configurations [22]. If we place the two
smallest values of | Iij | on opposite sides of the plaquette, there is a metastable
state if the second weakest bond is broken, separated by a barrier from the true

ground state (weakest bond) [22]. Glassy behaviour is expected in diluted geomet-

13

rically frustrated systems, such as the hard-core lattice gas [92], and the diluted

anti-ferromagnet in a field [79].

2.2 Hard core lattice gas

The hard-core lattice gas, like the Ising model, is a fundamental model for physi-

cists in condensed matter. Its Hamiltonian,
H = E Iijnl-nl- -- It 2711', (2.24)
{ii}

describes a lattice with nearest neighbor repulsion (I > O), and chemical potential
It. "i represents the occupancy variable, "i = 1 indicates an atom at site i, and a
value of "i = 0 means the site is vacant. By adjusting the chemical potential we can
control the number of atoms. At low temperatures for y > 0, I —> co and y/ I —> 0
the lowest energy state corresponds to the maximum density of atoms on the lat-
tice, with the constraint that no two atoms occupy nearest neighbor sites. The max-
imum density is equivalent to the NP-complete problem of maximum independent
set and is related to the vertex cover problem. I will define N P-completeness and
discuss it in more detail in Chapter 3.

The Hamiltonian for the hard-core lattice gas can be transformed to the Ising

 

model by the substitution of,
n1, : Si 5‘ 1, (2.25)
which yields the diluted anti-ferromagnetic in a field,
H = )2 Iijsisj — Ehini. (2.26)
if

The lattice gas often differs from the Ising model by placing a constraint upon the

14

number of atoms in the lattice. The equivalence breaks down for random systems
when the chemical potential and the magnetic field involve the quenched coupling
[82]. However by using the replica method on the hard-core lattice gas a glass state
can be shown [82] [81] [69](see appendix B).

Disorder in this model may be introduced through the turning off or on of the
interactions Iij- Frustration is introduced by the geometry of the lattice, provid-
ing the elements of possible glassy behaviour. The hard-core lattice gas has been
studied in relation to glasses [82] [92] [77] and vertex cover [94] [34] [2] [93].

Once we have a description of the system we need a set of observables; physi-

cally, we analyze the following quantities;
0 Density, p
o Degeneracy, entropy
0 Frozen fraction

We will be doing our work with the Helmholtz free energy, F,
F = E — T5 = —kT1nZ. (2.27)

The thermal average of the density is defined as,

p = [£032.01 = @371,- Zniexm—fiHn. (2.28)

"i
Which we can see is,

1 a exp(—BH) _ _I_dan

zgfigfi z _ ,BN—ry . (2.29)

At T = 0 the density corresponds to the normalized cardinality of the maximum

independent set, and 1 — p gives the density of the vertex cover. The disorder

15

average of the free energy, F , (F), is equal to
(F) = —kBT(ln Z), (2.30)

and we may use the replica method to solve for (In Z), in systems where a standard

formalism is very difficult.

2.2.1 A physical example

A physical example of a lattice gas arises in the modeling of a nano-structure made
up of 2 types of atoms, A and B. Because of the relative sizes of A, and B, there are

favorable combinations, so we define (observe) occupancy rules.

0 A-B=Good
o B-B=GOOd
o A-A=Bad

This would be the case if A were too large to occupy adjacent sites without distort-
ing the lattice. This can then be modeled by the hard-core lattice gas where atoms
of type A are the particles and B are vacancies.

This is the case with Xenon on Graphite. Xenon takes the role of the atom of
type A, and the vacancies are analogous to the atoms of type B. Graphite forms a
hexagonal lattice, the minimums of the potential energy fall in the centers of the
hexagonal lattice (forming a triangular lattice). The noble gas prefers to sit in the
energy wells, the difficulty arises because the size of the deposited atoms is larger
than the cell spacing, making it impossible to occupy nearest neighbor sites. We
know that the maximum independent set corresponds to the densest packing in

the first layer.

16

In the Xenon and graphite system experimentally several things happen. At
low temperature and pressure Xenon has a incommensurate configuration. As
pressure is increased the system under goes a transition into a commensurate
phase [41] [43] [65] [70] [42] [36] [72]. This results from the \/3 x \/3 spacing 4.26
A, being slightly smaller than the spacing for the lowest Xe-Xe energy, 4.40 A [41].

loos et al. calculated the maximum allowable compression, by minimizing the
enthalpy per atom of a double layer. The potential for a Xe atom above a graphite

layer can be given as,

V(r =V0(z) 2V8 (z) exp(i§ . 7’). (2.31)
f?
The 57' are the reciprocal lattice vectors for the two dimensional graphite surface.
Vg decreases rapidly with increasing height.
Periodic lattice structures were relaxed to strain-free configurations. The sur-
face coverage of n for a compressed configuration of hexagonal symmetry on the

J3 x \/§ plane can be given by,

nHC _ 912—9l+3
no 912—151+7'

 

 

(2.32)

where l is the number of atoms per side of the hexagon. For expanded configura-

tion of hexagonal symmetry,

nHE _ 912—9l+3

 

_ . 2.33
no 912 — 31+ 1 ( )
For striped compressed and expanded.
n SC 3i
—— = —— . 4
no 31 - 2I (2 3 )
"s_E __ 3’
n0 _— 31 + 2' (2°35)

The coverage is obviously just an expression of the density.

loos et al. then calculated the energies per atom of striped and hexagonal con-
figurations. These show curves that give an energy minimum for a particular frac-
tional coverage, with the minimum energy corresponding to the maximum cover-
age. This idea can also be extended to the formation of a second layer providing a

threshold coverage of the first layer before the second layer begins to form.

2.3 Diluted anti-ferromagnet and the hard-core lattice
gas

A direct mapping exists between the hard core lattice gas and diluted antiferro-

magnets in a field (DAFF’S). The Hamiltonian of the DAFF is,
H = I E €i€ijSj — Bzé‘isi, (2.36)
(if) i

where, B is the applied magnetic field, 51’ are Ising spins, and 6i represents the
dilution. Sites are present, 61- = 1, with probability p and absent, 51’ = 0, with
probability 1 — p.

DAFF’S were originally studied as the experimental mapping of the random
field Ising model, a fundamental model of disordered materials. This mapping
applies for DAFF’S on bipartite lattices as occurs for the system PexZn1_xP2 [71]
[48] [30] [3], and hence the hard core lattice gas on diluted square and cubic lattices
map to the random field ising model.

In the DAFF a domain state (DS) that is similar to a spin glass has been
shown, this state is characterized by ”domains, metastability and slow dynam-
ics" [71]. In the H, T plane, the DS region occurs between the long range ordered

anti-ferromagenetic phase and the paramagnetic phase [71], above a critical field.

18

Glaser et. al. examined the phase diagram in the B, x plane [30], showing the onset
of glassy behavior at a critical concentration, and field. In the B, x plane the low
concentration, low field state is the paramagentic phase and followed by the onset

of the DS state and the long range anti-ferromagnetic state [30].

More recently the issue Of geometrical frustration has gained attention [79].
The hard core lattice gas on triangular, face-centered cubic and random graphs is
geometrically frustrated due to odd loops in the graph. Frustration due to odd

loops is common to the hard core lattice gas and Ising antiferromagnets.

2.4 Spin glass applications

2.4.1 Neural networks

Spin glass theory has also found applications in biological systems such as neural
networks, and protein folding. The Hopfield method of modeling neural networks
can be described by the Hamiltonian [62] [35],

H = E IijSl'Sj. (2.37)

i<j

Under a sequential model the neurons are updated by the equation,
si(t + (St) = sign( EIiI-sz- + hi), (2.38)
i

19

where we define,

5i 2 state of the ith neuron
Ii]- 2 synapse from jth neuron to the ith neuron, assumed to be symmetric
h,- 2 threshold of ith neuron

(2.39)

t and (5t define the intervals between the learning events [62]. 5i = 1 if the neuron
is firing and 3i = —1 if it is not firing. Learning can be introduced by the Hebb’s
rule [1] [62]

Iii = %}::1§f§;f,i 79 I. (2.40)

The sets of {55‘ } are determined by the learning process, assuming a value of 3:1
with equal probability [1]. Amit, Gutfreund and Sompolinsky solved the sym-
metric case, showing the onset of metastable states of the associative memories in
the low temperature regime [1]. Another learning model has been presented by
Toulouse et. al. [90]. Parga and Virasoro examined the ultrametric structure of
memories, generated by a Markovian process of categorizing words as they are
stored [73]. Mezard applied the replica method to several different types of learn-
ing patterns modeling short term memory [55]. Gardner calculated the maximum
storage capacity of such networks [27] [28]. A more mathematical treatment of
neural networks is given in the book ”Mathematical Aspects of Spin Glasses and

Neural Networks” [8].

20

2.4.2 Protein folding

Protein folding has been modeled as a spin glass, by Rao and Bhattacarjee, using

the Hamiltonian [80],

Iij
1I
here (7 is a measure of the correlation. While Bryngelson and Wolynes used the
form [11],
H = — germ) - Eii,i+1(“ilai+1) — 219709 “i+1' r,» ’1')! (242)
z 1 z]

5i is a measure of the energy associated with an amino acid state, (xi, I i,i +1 is related
to the interactions along the chain taken as nearest neighbor interactions, Kij are
long-range interactions, caused when acids far apart on the chain are brought to-
gether by bends in the chain, rl- is a position vector to the ith element [80]. Frankel
showed that the protein folding problem, like the spin glass, is a member to the
computer science classification of problems known as NP-complete [24]. Spin glass

theory has also provided a method of optimizing code for protein folding [31]

2.4.3 Combinatorial optimization

The spin glass problem has been shown to be NP-complete, this allows one to ap-
ply statistical physics to other NP-complete problems. In this thesis we will con-
centrate on the problems of vertex cover and maximum independent set. Compu-
tational complexity will be studied further in chapter 3. A large amount of work
has been done in the area of combinatorial optimization, in relation to the spin

glass [60] [26] [62].

21

Chapter 3

Computational Complexity

The difficulty or complexity of a problem in computer science is measured in terms
of the time it takes to solve the problem. Time, T, is a measure of the number of
operations needed to find a solution. A theoretical computer such as a Turing
machine is used to define a standard number of operations an algorithm uses. A
problem is considered hard if it takes an exponential number of steps to solve the
problem, in this case T scales as T ~ exp(aN). If a problem has an input of size N
and it takes 0(N“) operations to solve it, in the worse case scenario, that problem
is known as polynomial. In practice if a is very large, it can still be very difficult
to find a solution. But, a polynomial time algorithm is, in general, better than
an exponential time algorithm. If a problem can be shown to be solvable using a
polynomial algorithm the problem is said to be tractable. For many problems it is

difficult to determine tractability or intractability.

It is possible to make some distinctions about the time needed to solve some
problems in the worst case. Already we have defined those problems which are
soluble in polynomial time as tractable, these problems are said to be in the class
P. The problems that are said to be soluble by a ”nondeterministic” algorithm are

in the class NP. Primarily the concept of a nondeterministic algorithm is a ”defini-

22

tional device for capturing the notion of polynomial time verifiability” [29]. Poly-
nomial time verifiability means that if a possible solution is available, it can be
determined in polynomial time if it is a viable solution. A nondeterministic algo-
rithm may be defined, informally, as an algorithm which finds a ”solution” to a
given instance, by guessing and checking [29]. It is still an open question if NP is
also a member of P (NP 2 P), however, the widely held belief is that they are not
equivalent.

There are two ways to pose computational problems; as a decision problem
or as an optimization problem. The decision problem is considered easier, and is
usually used to prove NP-completeness. A decision problem poses the question
such that there are two possible solutions, yes or no. An optimization problem is
a problem where the object is find the best possible solution, for example, mini-
mizing the energy of the ground state of a spin-glass. We will be concentrating on

solutions of optimization problems.

3.1 N P-completeness

The first classification of NP-complete (NPC) problems was by Stephen Cook in
1971 [14]. Later, Karp added to that number [44] [45]. Currently there are hundreds
of problems that have been classified as NP-Complete [29]. There are two major

characteristics of NPC problems;
1. all NPC problems are soluble in polynomial time by a ”nondeterministic"
algorithm,
2. any problem in the class NPC may be transformed to another problem in

NPC by the application of a polynomial time reduction.

The first characteristic simply means that a possible solution is verifiable in poly-

nomial time, while the last characteristic means that if any NPC problem were

23

solvable in polynomial time all NPC problems would be, or conversely if it were
proven that any problem in NPC were proven to be intractable all problems in
NPC would be intractable. Proof of NPC generally consists of showing a polyno-
mial transformation into a known N PC problem.

There are Six basic NP-Complete problems; the traveling salesman, 3-SAT, 3-
dimensional matching, minimum vertex cover, Hamiltonian circuit and number
partitioning [29].

In all NPC problems there are instances that are easy to solve, and instances
that are difficult to solve. It can be shown that there is a phase transition that
exists between easy and hard instances [94] [33]. It is particularly hard to find a
solution near the critical value in NP-complete problems, since near the critical
point complexity problems display critical slowing down. One way to determine
the critical point for an NPC problem is to measure the time required to find a
solution in respect to a variational parameter [34], such as the connectivity in a

graph theory problem such as vertex cover.

3.1.1 P to NP transition

When finding a vertex cover, or a ground state, in the hard-core lattice gas, there
are 2 possible states for every vertex, so that if there are N vertexes that means
there are 2N configurations, that may be a possible solution. If each configuration
has to be tested, it is not hard to see that even with a small number of nodes, (ie
N =100 then 2N = 1.27 x 1030) it becomes prohibitively difficult to find a solution
in any reasonable time. Fortunately, the typical case is often easier than the worst
case scenario, however, no exact algorithm exists to solve NP-complete problems
in less than exponential time in the worse case scenario. We will discuss specific
algorithms more in chapter 4.

When solving NPC problems on graphs, such as vertex cover, It has been ob-

24

served that there is a phase transition in computational complexity, as the connec-
tivity of the graph is increased. This can be understood in relation to percolation
(see Appendix A) [64]. We know the probability, P(s), of a node being on a cluster

of size S in a random graph below the critical point is,

P(s) ~ exp(—as), (3.1)

where a depends on the concentration of present sites. With N clusters,

N8Xp(—a5max) N 1, (3.2)
so that,
lnN
Smax N T- (3-3)

The largest cluster, sma x is proportional to In N. The time/r, to find a solution for

the largest cluster is,
T ~ smax ~ exp (Ea—Ii) ~ NU“. (3.4)
With N clusters the time to find a solution for the graph is,
I ~ Nl/“H. (3.5)

Thus the time to find a solution below the critical point is polynomial. Above the
critical point, the largest cluster is on the order of O(N) and not O(ln N) as it is
below the threshold. This means the time to find a solution of the largest cluster at

worst is,

T «2 exp (712,—), (3.6)

which is clearly exponential in time. This case illustrates a phase transition that is

25

observed in the computational complexity as average coordination number of the
vertexes, c, is increased.

Some relevant questions, we then ask from a computer science perspective are;
0 How do we speed up our calculations (algorithmically)?

o Are there easy instances or sub-graphs that can be dealt with in a way that speeds up

the calculations?

0 In NPC problems not all instances are hard, what are the characteristics of easy

instances?

While as a physicist, one might ask, do the physical examples of these problems give us
insight in how to solve them? What insight can the study of phase transitions in physics
provide to computational problems.

Mézard et al. in their book ”Spin Glass Theory and Beyond”, provide a basic
mapping of a computation optimization problem to statistical physics [62]. The

partition function is,

Z = 2: exp(—8 x cost(configuration)) (3.7)

configurations

The mapping is then [62],

OPTIMIZATION STATISTICAL PHYSICS

instance sample
cost function energy
optimal configuration ground state
minimal cost ground state energy

26

3.1.2 The traveling salesman

One of the first problems to be identified as computationally complex is commonly
known as the Traveling Salesman Problem (TSP). It may be posed as: given a fixed
number of cities and various roads connecting them, with difi‘ering speed limits, what is
the fastest round trip where the traveling salesman visits every city once? The decision
problem could be posed as: given a fixed number of cities and various roads connecting
them, with difi‘ering speed limits, does there exist a round trip with a time less than some
maximum, ttrip S tmax? A partition function for the traveling salesman problem

can be written as,

ZTSP = 2 exp ( — :BNUH-1Ltour) (3-8)

tours

Mezard and Parisi did a statistical mechanical analysis based upon this partition
function, and derived its replica symmetric solution [56]. To make the entropy
extensive, at low temperatures, we reduce the relevant number of tours by con-

necting a node to two other nodes with probability,
P(d) N r_ (3.9)
where d is the typical distance between neighbors,
d ~ N—l/ 0+1). (3.10)

This makes the free energy,

1 1

Z. (3.11)

27

We can write a generalized partition function, if at each site we introduce an m-

component spin 5,- of fixed length 51.2 = m,

1
Z=jna 5- ex ex ————- d~S~-S- , (3.12)
...( .> 11(7):]. p( WW...) 2.. .)
where,
dp E Cmdmsé(32 — m). (3.13)

The partition function in Eq. (3.12) is the same as ZTSP in the limit,

. 1 . 2
2m, = ’jlglofivlgnoo’r—N. (3.14)

3.1.3 3-SAT and K-SAT

Satisfiability (SAT) is a logical problem that asks if a set of N Boolean variables

organized into M clauses, can be satisfied simultaneously [59]. A clause is a set of

K literals that may be a variable (1;, = 1') or a negated variable (1;, = '1'). Variables
. . . . . . . _ 1 2 3

form a clause by bemg In dISjunctlon (loglcal OR), Cp — lp V II) V l p [34]. The

Boolean formula can be expressed in conjunctive normal form as,
F = (x1 v :53 v 364) /\(x'1 v x2 v :64), (3.15)

/\ is a logical AND. The example given in Eq. (3.15) is 3-SAT with M = 2 clauses
and N = 4 Boolean variables. 3-SAT was shown to be NP-complete by Cook in
1971 [14], with a transition near a 2 4.2 [49], where a = M / N. When K = 1,
or 2 the problem can be solved with a polynomial time algorithm. The general
case, K-SAT, where the number of variables in each clause is allowed to vary, is
NP-complete if K 2 3 [29]. Monasson et al. [64] studied the onset of the transition

from P to NP using a mixture of 2 variable and 3 variable clauses. They showed

28

for this (2 + p)-SAT model the transition between polynomial / exponential occurs
near the critical value of p > p0 ~ 0.4, where the formula contains M clauses,

(1 — p)M two variable clauses and pM three variable clauses [64] [51].

K-SAT is important because it is very general and many other problems have
been transformed into K-SAT to prove N P-completeness. A Hamiltonian for K-
SAT may be written such that the energy is a measure of the unsatisfied clauses,
and solved with the replica method. Then E = 0 signifies a satisfied instance
[63]. Recently, K-SAT has been the subject of interest in statistical physics [61]
[54]. Kirkpatrick and Selman showed that the transition in K-SAT is similar to the
spin glass transition, they applied finite size scaling to find scaling exponents for

2§K26H%

3.1.4 Vertex cover

The vertex cover (VC) problem is a graph theory problem that was identified by
Karp as NP-complete [44]. Before we formulate vertex cover, I should define some
basic concepts in graph theory. A graph is a set of vertexes V and a set of edges
E. For the purpose of this thesis each edge is defined by a pair of vertices (i, j)
which are connected by an edge, we might also think of this as a bond. We define
the cardinality of a set as the size of a set, for example, the cardinality of the set of
vertexes V is the number of vertexes, N. The average number of edges incident on
a vertex can be found by,

2 | E

c:—

N , am)

where I E | is the cardinality of the edge set. There is are critcial coordinations,
c*, changes in the lattice occur. For example, we might talk about the coordination

where percolation of the lattice occurs, see appendix A. The probability a bond

29

exists is,
c
P = ‘1 (3.17)
z
where z is the maximum coordination of the lattice. Thus the corresponding critical

probability occurs at,

(3*

In general, covering can be formulated as: given any graph G = (V, E), what is
the minimum number of vertexes that need to be covered such that a particular fraction of
edges are covered? An edge (i, j) is said to be covered if at least one if its end points
is in We, the set of covered nodes. ch C V and is a full vertex cover if and only if
all edges in G have at least one endpoint in ch.

The minimal vertex cover problem consists of finding a full vertex cover We
with the smallest cardinality, | We |. In the remainder of this dissertation, we will
assume that the fraction of covered edges is set to one. The fraction of covered

nodes is,

l l’vc I
—_ —. .1
xc N (3 9)

The decision variant of the problems asks; can a full vertex cover be constructed with
a fixed fraction, x, of covered nodes?

For those unfamiliar with graph theory, vertex cover can be visualized by the
analogy of a museum, with a series of hallway and the junctures where the hall-
ways meet. The museum has a number of guards that stand in the junctures and
protect any hallway they can see down. Then we can pose vertex cover, by asking
how many guards does the museum need, such that there is at least one guard
looking down all hallways.

Vertex cover can be shown to be equivalent to the ground state of the hard core
lattice gas [94], and shows a second order phase transition in a random graph [34].

Using the equivalence to a hard-core lattice gas and the replica method Weigt and

30

Hartmann showed that the replica symmetric solution was accurate to c* = e on
a random graph [94] [33], here c* is the replica symmetry breaking critical point.
Hartmann and Weigt also calculated a typical time to find a solution for vertex

cover using a backtracking algorithm [91].

W

Figure 3.1: A solution for VC and MIS on two clusters. The solid vertexes are in
the minimum vertex cover, while the open circles are in the maximum independent
set.

Figure 3.3 shows two clusters with a calculated minimum vertex cover. In the
left cluster, all the edges can be covered by selecting the three solid vertexes. This
cover is denegerate however as several of the covered vertexes may be swapped
for the uncovered (open) vertexes. The addition of a new edge in the right cluster,
requires that one more edge must be covered, increasing the cardinality of the VC

by one.

3.1.5 Maximum independent set

The Maximum Independent Set(MIS) problem is closely related to VC. We define
and independent set (IS) by; given a graph G = (V, E), a set of vertexes V15, where
V15 C V, is independent if no vertex in V15 is connected to another vertex in V15 by
an edge. The maximum independent set involves finding the independent set with
the largest cardinality (known as the independence number), the fractional MIS is
given by

PMIS = LKAfiII-IS—I. (3.20)

31

The MIS and the minimum VC are related by,

1 = xc+pM15, (3.21)

so that,

VMIS + We = V. (3.22)

Physically, we find that the maximum independent set is the same as the maximum
density of the hard core lattice gas, at T = 0.

Again we may pose a decision problem: Given graph G is there an independent
set of size p greater than or equal to some maximum, p 2 pmax; or an optimization
problem, what is the maximum size for an independent set in Graph G? Throughout the
course of the work done for this thesis we concentrated on the optimization form
of the VC and MIS problems.

Figure 3.3 shows two clusters with a calculated maximum independent set, the
Open vertexes. In the left cluster, three vertexes is the maximum number of ver-
texes that may be found without a connecting egde. This MIS is denegerate how-
ever as the location of some open vertexes may be moved. The addition of a new
edge in the right cluster, requires that one more edge must be covered, decreasing

the cardinality of the MIS by one.

3.1.6 NP—complete games

To illustrate the commonness of N P-Complete problems, here is a small list of com-
mon NPC problems, for a more extensive list please see the book by Garey and

Johnson [29].
0 Tetris [17] [10]
o Minesweeper [47]

32

o Sudoku (Latin Squares) [96]
o Mastermind [86]
o Timetable design [21]

o Multiprocessor scheduling [29]

3.2 Mappings

3.2.1 Mapping K-SAT to vertex cover

One can map a K-sat instance to vertex cover by placing a pair of nodes in the
graph for each variable. An edge is placed in the graph connecting the node rep-
resenting variable, xi, and the node representing the negated variable, xi. For each
literal in a clause we place a node into the graph (K nodes for each clause, a} to dig),
with edges connecting each of these nodes. Then the clause nodes are connected to
the nodes representing the variables that occur in the clause. Thus for a 3-SAT in-
stance involving N variables and M clauses, there will be a total of 2N + 3M nodes

in the graph, and 6M + N edges. The resulting graph for eq. 3.15 is displayed in
Figure 3.2.1

x16 6 Q Q 6 Q *3

GI 63
Gy a3 82 Q9

Figure 3.2: This is the mapping of Eq. 3.15 to a graph for vertex cover. Figure and
example taken from Hartmann and Weigt [34].

 

 

 

 

33

3.2.2 Mapping vertex cover to the hard core lattice gas

Having defined both the hard-core lattice gas and the vertex cover problem, we
would like to show how vertex cover may be encoded as a hard-core lattice gas.
We will be using Weigt and Hartmann’s notation [94]. First we need to define the

site occupancy variables,

0 if i is covered
yi = . (3.23)

1 if i is uncovered

The constraint that no two adjacent sites may be occupied is enforced by the indi-

cator function,

X0?) = 1'I(1 — I/fljl (3.24)
(if)
When the indicator function is one, the set x’ = (x1, . . ., x N) corresponds to a ver-

tex cover. This allows us the write the grand partition function,

E = Z eXP(rZyz-)x(f)- (3.25)

yi=0,1 i
Weigt and Hartmann found the replica symmetric solution for this expression [94].
Here I will state the solution, see Appendix B for the full treatment. The density of

the vertex cover is,
2w + w2

2c (3.26)

xc=1

Note: W(c) is the Lambert function and is given by the solution to WeW = c. The

fraction which is always covered (frozen covered),

xfC -_- W/c (3.27)

34

The fraction which is sometimes covered (degenerate),
xd = WZ/c. (3.28)
The fraction which is never covered (frozen uncovered),

xfu = 1 — (w + W2)/c. (3.29)

3.3 Analytic results for VC: vertex cover on trees

As an approximation to this problem, we consider Bethe lattices. A Bethe lattice or
a Cayley tree is a lattice, where a node at each level, I + 1, is connected to at most
a nodes at the next lower level, 1. Each node then has a maximum connectivity of
z = or + 1. The structure looks like a tree branching out toward the lower levels.

The center node connects 2 tree structures.

Figure 3.3: The center node and first 2 levels of a Bethe lattice where z = 3.

35

The limiting probability that a site is part of the maximal independent set, Px,
is given by the equation,

Pj‘ = (1 — ppf)“ (3.30)

where p is the probability a bond exists. A site is independent if none of its con-

nected neighbors are part of the MIS. In the random graph limit, this yields,

 

Pf = exp(—ch‘) = WEC). (3.31)

The probability that a site is degenerate, Pd, meaning that it is sometimes part of

the cover and sometimes not is given by,

2
Pd = 0.pr (1 — pr)“_1 = cpj‘ exp(—cpf) = C(Pj‘)2 = [Vic—)- (3.32)
A site is degenerate if it is singly connected. The degenerate sites have probability
1 / 2 of being on the minimal vertex cover, so on average, the probability that a site

is on the minimal vertex cover is,

 

 

 

_ W(c) W(c)2
PU — 1 c ——2—C—— (3.33)
and the probability a site is in the MIS is,
P —W(C)+W(C)2 (up
MIS — C 2C '

Note: PC = W(c) / c. Since the maximum independent set, or the repulsive lattice
gas, on random graphs is highly degenerate, we may define three types of sites:

the fraction that is always covered x fc, the fraction that is always uncovered, x fur

36

and the fraction that is sometimes covered xd as,

xfC : W/c (3.35)
xfu = l—pb—pezl—(W+W2)/C (3.36)
xd = Wz/c (3.37)

For a given random graph, all of the degeneracy occurs due to rearrangements of
the atoms on the sites with volume fraction (xd). One can also define the probabil-

ity that a site is frozen Pf
szxfc+xfu =1—W2/c (3.38)

The results for xd, x fc and x fu on trees reproduce those found by Hartmann and
Weigt using the replica symmetric theory Eqs. (3.27)-(3.29) (see Appendix B) [33]
[94]. However, the Bethe lattice approach generalizes their analysis to random

graphs with maximum coordination, z = a + 1.

37

Chapter 4

Algorithms

One principle difficulty in examining NP-complete problems is the inability and
perhaps impossibility of constructing algorithms that are efficient for large sam-
ples. In physics, typically we prefer to work at or near the thermodynamic limit,
which is nowhere near the sizes that can be efficiently examined with exact algo-
rithms. The best exact algorithms typically top out around a few hundred sites.
This has channeled research for efficient solvers in several directions. One avenue,
the development of exact algorithms is slowly becoming more efficient. The con-
jecture in computer science is that no algorithm capable of solving the worst case in
less than exponential time will be found. Another avenue, centers around heuristic
algorithms of polynomial complexity that provide near optimal solutions, for large
lattices. Often, it is sufficient to get near the ground state, though in physics the
structure of the ground state and subsequent excitations are the meat of our meal.
Heuristics can illuminate behaviour that might be exploited in exact algorithms,
and give a rough idea to the energy landscape. The push for new solvers has also
generated interest in quantum computers where the multiplicity of states might be

exploited.

Another important question is the difference between the worst case scenario

38

and the average behaviour of the problem. Often the typical time to find a solution

is less than the exponential time of the worst case scenario.

In this chapter, we will examine some exact algorithms provided by Alexan-
der Hartmann, and an exact algorithm of complexity O(2N/3) by Tarjan and Tro-
janowski [87]. The algorithm of Tarjan and Trojanowski leads to the graph re-
ductions by leaf and triangle removal (the two simplest cases in their algorithm).
Linear reduction of graphs has long been understood as a way to reduce the size
of a problem by removing easy elements from a more complex graph. Karp ap-
plied leaf removal to matching [46]. Bauer and Golinelli applied the first case of
Tarjan’s algorithm, as core percolation by leaf removal, to the problem of VC on
random graphs and found a phase transition at c* = e where a core of nodes that
could not be resolved by leaf removal emerged [4]. This is of interest as c* = e is
the replica symmetry breaking point on a random graph [4]. This phase transition
will be examined in more detail in chapter 5. Recently, Correale et. al. applied
leaf removal to simple Boolean networks [15]. We applied leaf removal to some
regular lattices and have begun to examine triangle removal on the FCC lattices,
triangular lattices and random graphs [38] [39]. After examining the exact algo-
rithms, we will examine several heuristic algorithms. The two simplest heuristic
algorithms, greedy and random selection will be examined briefly, followed our by

local probability methods centered on node probabilities and edge probabilities.

4.1 Exact algorithms

Exact algorithms for NP-complete problems are an area of intense study. The
most naive algorithms resort to exhaustive search, which is very inefficient. It
is widely conjectured that no exact polynomial time algorithm exists, so there has

been interest in super-polynomial time algorithms [95]. One important aspect of

39

the search for faster exact algorithms is proving performance bounds of particular
algorithms. We are not going to go into a lot of detail here on the fastest algorithms
currently being used. There is a good review of exact algorithms for a variety of
NPC problems by Gerhard Woeginger from 2003 [95]. We will discuss two ba-
sic method, branch_and_bound and divide_and_conquer, then the exact algorithm by
Tarjan and Trojanowski, which has a complexity of O(l.2599N ), and leads to some
polynomial time graph reductions.

Alexander Hartmann kindly provided us with a program that finds exact
ground states using a combination of branch_and-bound and divide_and-conquer
methods [94]. Both algorithms yield a solution tree where every vertex is either
covered or uncovered, this tree has 2N possible leaves. This type of tree is called a
binary backtracking tree, at each step there are two branches; one where the rele-
vant node is covered and one branch where it is uncovered, vertexes that have not

been reached in the solution tree are left free.

4.1.1 Divide and conquer

A divide and conquer algorithm is based on the concept that a vertex cover can be
constructed from the covers of sub-graphs of graph G [94]. The goal then is to split
G into sub-graphs and solve them individually. If the graph has a low connectivity,
this works well, allowing it to be easily divided. At each step as edges are covered,
they are removed allowing for more subdivision of the graph. As the graph moves
toward higher connectivities, the graph becomes difficult to subdivide and the al-

gorithm is less effective [94]. A pseudo-code for divide and conquer is given below.

DIVIDE-AND_CONQUER (G)
1 get a free vertex i of largest current degree d,-

2 marki as covered

40

\0m\]O\U1rl>UJ

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

numcoverl +— 1
remove all edges { i, j} from E
calculate all connected components{Ci} of graph built by free vertexes
for all components C,-
do
numcoverl <— numcoverl + divide.and_conquer(Cl-)

insert all edges{i, j} which have been removed

mark i uncovered, £2 <— xl- +— 0
numcoverz +— 0
cover all nodes 1' adjacent to i and remove incident edges { j, k}
calculate all connected components {Ci};
for all components C,-
do
numcoverz = numcoverz + divide_and.conquer(Ci)
for neighbors j of i
do
mark j as free

insert all edges { j, k} which have been removed

mark i as free
if numcoverz > numcoverl
then
return (numcoverl)
else

return (numcoverz)

41

The divide and conquer algorithm initially will find a greedy cover (see section
4.3.1) based upon covering the highest connected nodes (at each call of the func-

tion). This function searches every possible branch, returning the best solution.

4.1.2 Branch and bound

For graphs with higher connectivities, branch and bound methods are better. In the
branch and bound algorithm sub-trees of the binary backtracking tree are trimmed
when they cannot lead to a better solution. The bounding is controlled by keeping
the size of the smallest found vertex cover, we will call this ”current-min”. The
current-min is initialized to the number of nodes in the lattice. Nodes are covered
(as we descend in tree) and the number of currently covered nodes is kept in X. At
each step we choose the highest current degree node to cover, this means that the
first descent through the solution tree is a greedy cover (see section 4.3.1).

At any step, if we want to improve on or match the current_min, we need
to cover P S current-min — X nodes further down in the tree. The boundary is
enforced if the number of free (uncovered) edges is greater than the sum of the
degrees of the F highest degree free nodes, then a cover smaller than curreanin
cannot be constructed. This sub-tree is trimmed and the algorithm backtracks to
find the next possible sub-tree [94]. The advantage to such an algorithm is that
it can clearly provide the cardinality of minimum vertex cover and all associated

ground states. A pseudo code for branch and bound is provided below.

BRANCH_AND_BOUND (G, current-mi n, X)

1 if all edges are covered

2 then
3 if X < best
4 then

42

\oooucnm

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

current_min +— X

return

calculate P +— current_min — X, D <— 2:11: d,-
if D < number of uncovered edges

then return I> Bound

take one free node i with largest degree d(i)
cover i

X +- X + 1

remove all (i, j) from E
branch_and_bound(G, current_min, X)
insert all (i, j)

X <— X —- 1

if X > number of current neighbors
then
uncover i
for for all neighbors j of i
do mark j as covered
X <— X + 1
remove all incident edges { j, k} from E
branch_and_bound(G, current-mi n, X)
for for all neighbors j of i
do mark I as free

X4—X—1

43

32 insert all( j, k) that have been removed
33
34 mark i as free

35 return

Hartmann implemented this algorithm to analyze vertex cover for con-
nectivities in the regime 4 < c < 10, and N S 140 nodes. The
DIVIDE_AND_CONQUER and BRANCH-AND_BOUND pseudo codes are

taken from Hartmann and Weight [94].

4.1.3 An algorithm by Tarj an and Trojanowski

Tarjan’s and Trojanowski’s [87] algorithm for finding a MIS is a branch and bound
style algorithm for finding a maximum independent set on a N —vertex graph with
complexity O(2N/3) [87].

Tarjan’s algorithm identifies the degree of a vertex, up to d S 6, makes a de-
termination of the structure around the vertex, from this one can determine the
possible independent sets. The algorithm is recursive, often there exists a choice
of independent sets, which need be evaluated as the algorithm progresses. From
these independent sets the MIS can be determined.

One subset of cases is Simple to analyze; this subset is comprised of complete
sub-graphs that subtend on the boundary. This is far simpler to state than to imple-
ment as finding complete sub-graphs of a graph is in itself an NP-complete problem
known as clique [29]. A complete graph is a graph where every node is connected
to all other nodes, sometimes in graphs, there may be a sub-graph that is com-
pletely connected, this is known as a clique. Finding cliques in a graph is a difficult
problem. However, small cliques remain accessible, such as leaves and triangles.

On lattices though this may be made simpler as the possible cliques are limited

44

by the geometry, such as the absence of triangles in cubic or square lattices. Once
a clique that subtends the boundary is identified, the boundary node is placed in
the independent set and all other nodes in the clique are covered. This procedure
is exact for the cardinality of the VC but may not take into account all degenerate

states, ie. a vertex cover is found but not all vertex covers are found.

4.2 Reduction of diluted graphs

Often when working with slow algorithms, a certain amount of preconditioning
can speed up the calculations. Preconditioning sometimes known as reduction, has
long been a way of attacking difficult problems. Sometimes preconditioning may
simply involve sorting the list and gathering information that will be necessary for
the exact algorithm. An example would be finding the connectivities and sorting
them. The sorting of data may lead to an exponentially large gain in the running
time [95]. Other times preconditioning may involve a reduction in the complexity
of the instance, as in the case of the leaf and triangle removal algorithms featured
below. The reduction removes the easy parts of the problem so that the exact solver
may concentrate on the difficult problem, but one that is smaller than the original

instance.

4.2.1 Core percolation by leaf removal

A leaf is defined as a node with connectivity one, leaf removal is the removal of
the node with connectivity one, its adjacent node and all edges connected to the
two nodes. We will refer to the node of connectivity one as the”leaf node”, its
adjacent node as the ”root node” and nodes adjacent to the root, excepting the
leaf, we will simply call the ”adjacent nodes”. When a leaf is covered the root

node is placed in We, or equivalently we place the leaf node in the VM I 5. When a

45

 

 

Figure 4.1: Illustration of leaf removal. The dashed edges were originally present,
but were removed during the leaf removal process. (a) shows a small graph with 2
leaves when one is detected the root is covered and the dashed edges are removed.
(b)-(d) are 100 node planar triangular graphs before and after core percolation. (b)
Initial bond concentration of c=1.0, leaf removal removes all bonds from the graph.
(c) Initial concentration of c=3.0, after leaf removal a percolating core remains; thus
p > pc (d) Initial concentration of c=4.5, there are no singly connected bonds; thus
leaf removal is ineffective in reducing the graph. Note that c 2 pz, where p is the
bond probability and c is the average connectivity of nodes in the graph.

46

 

lllllllllllllllll I '77“:- I I I

a) ' I

0.8
0.6
0.4

0.2

I
1 1 ._ 1 =1141

DJ 0.2 0.3 0.4

 

IIIIIIIIIIIIIIIIIIIIIIII
llllllllllllllllllllllll

 

 

 

Illllllllllllllllll

0.6 0.7 0.8 0.9

 

O
O
L

é== _
0.5

 

0.4

0.2

 

l l l l I l l l I I l I I I I I I l l I I l l I

P
Illlllllllllllllllllllll

 

 

 

0.] 0.2 0.3 0.4

C
.9
Ln

Figure 4.2: The spanning cluster probability of the triangular lattice (a) and FCC
lattice (b) for N=1,000,000 node graphs. The black line corresponds to bond perco-
lation, the red to core percolation, and the blue to triangle percolation.

47

 

I I I I I I I I I I l I I I I I I I I j l I I T T

0.8

erjIII

0.6

lJJilIIlLIJJII

I I I I

0.4

l

0.2 —

 

I l l I I l l l l I

l I l 1 I J

 

O
N
w—
b
(J!

C

Figure 4.3: The largest cluster probability of the random graph. The black line
corresponds to bond percolation, the red to core percolation, and the blue to tri-
angle percolation, for N=1,000,000. Triangle removal and leaf removal coincide on
random graphs as N —> oo.

leaf is removed, the connectivity of the adjacent nodes are reduced. The algorithm
in its most basic terms is then identify a leaf, cover the leaf, remove the leaf, and
examine the adjacent nodes for newly generated leaves. Below is a pseudo-code

for leaf removal.

LEAF REMOVAL(G,5c’)

1 Make list L of leaves

2 while L > 0

3 do

4 Choose leaf i from list L

5 Find j the root of i (j = A(i))
6 x,- <~— 1,x]- <— O

7 for all neighbors k of j

48

8 do

9 Remove edge { j, k}
10 Adjust Ck the connectivity of k
11 remove i from L
12 if ck = 1
13 then
14 L <— k
15 return

When the algorithm is finished the number of nodes covered is | x | and the
remaining part of the graph is called the core in G. In Figure 4.1(a) we see the
results of leaf removal on a small graph with two leaves. When one leaf is chosen

(say i or j) then k is covered and the dotted edges are removed, leaving a core.

As we show in chapter 5, below the percolation threshold for the core, the core
clusters are logarithmic in size and VC on the core can be solved by an exponential
algorithm in polynomial time. The core percolation threshold corresponds to the
onset of replica symmetry breaking which sheds some light on the issue of where
graphs become difficult to solve. The core has a minimum connectivity of two
showing it is the onset of loops (leading to frustration) that creates the computa-
tional difficulty of MIS. Figure 4.2 shows the position of the transitions of standard
bond percolation, pb, core percolation by leaf removal, p1, and core percolation by

triangle removal, pt, on the FCC and triangular lattices.

The evolution of the core occurs in three regimes. In the first regime, the con-
nectivity is very small and so there is no core. In Figure4.1(b) we see the com-
plete removal of the edges of a triangular lattice with initial bond concentration of
p = 1 / 6. As the connectivity is increased, small clusters begin to form in the core.

We see the emergence of a giant percolating cluster, as in Figure4.1(c). Finally, the

49

graph has no leaves on a triangular lattice with connectivity p = 3/ 4, Figure4.1(d).

The algorithm runs in polynomial in time, which means that it is efficient on
low connectivity graphs and we gain some advantage on intermediate connectiv-
ity graphs. This implies that one should construct exact solvers that begin with

leaf removal before fully exploring the more highly connected nodes.

4.2.2 Leaf removal on the Bethe lattice

We would like to determine the concentration where
the core percolates after leaf removal. To do this we will
define four probabilities; In 2 A site is part of the MIS

and is not the core, Xn = A site is not part of the MIS

 

and is not on the core, IC 2A site is part of the MIS and
is on the core, X5 2A site is not part of the MIS and is Figure 4-41 In

on the core. These probabilities need to have the following properties;

In + X11 + IC + Xc 2‘ 1, (4.1)

and

[C + IN = PI (4.2)
Where PI is the probability a site is part of the MIS as found Eq. (3.30) from section
3.3. The probability a site is on the core is,

PC = Xc + Ic. (4.3)

For each of the four probabilities we can construct what may occur in lower
levels of the tree. To make this easier to visualize, we provide 2 levels of the tree:

the top level node in question and the types of connections to lower level nodes,

50

including the possibility of an absent bond (dotted). Bonds will be crossed out
when they are explicitly forbidden, and red when they are explicitly needed.
In: For a node to be independent and not on the core (see Figure 4.4);

1. it must not be connected to a node on the core,
2. it cannot be connected to another independent site.

This means the node can only be connected to another site that is not indepen-

dent and not on the core. We write this probability as,

In = (1 — r + Mn)“. (4.4)

Xn: In order for a node to be covered and not on
the core it must be connected to a minimum of one site
that is independent and not on the core (see Figure 4.5).

Thus we write the probability, Xn as,

X f(“)(1)’(1—I>“" (45)
n [=1 l Pn Pn I -

1 — (1 — pIn)“". (4.6)

Here we notice that In and Xn form a closed set of
equations. In may now be solved for analytically. Let
us continue, however to the probabilities for Xc and lg.

lg: All adjacent sites must be unconnected or con-

 

nected and covered (see Figure 4.6).

Figure 4.6: [C
(X
19 = )2 (007x010 ~ PXc — PIn — plc)“”’, (4.7)
1:1
a a l a—l
= E (,)(ch) (1—p—an) . (4.8)

~
H
H

51

Ic = (1 — p + an + ch)“ — (1 — p + an)"(.4.9)

 

Xc: at least one site must sit on the core and be in the
MIS, all other s1tes must be dlsconnected or connected Figure 4.7: Xc

and covered (see Figure 4.7) .

IX
Xe = 2 (0011010 — PIn — Weld—Ir (4-10)
1:1
(I
= 2 (0011010 - r + P(Xn + Xc))“", (4.11)
l=1
= (1 - pIn)“ - (1 — PIC — p1n)“- (4.12)

Eqs. 4.4, 4.6, 4.9, 4.12 satisfy Eq. 4.1 as required. These equations may now be

solved numerically.

4.2.3 Core percolation by triangle (and leaf) removal

After leaves, triangles are the next clique. Triangles are identified by finding
boundary nodes of degree two, the adjacent nodes are then tested for a connecting
edge. If a triangle exists, the boundary node is placed in the IS, all other nodes in
the triangle are covered and all edges contained in and incident to the triangle are
removed. Figure 4.2 shows the position of the transitions of triangle removal, leaf
removal and bond percolation on the FCC and triangular lattices.

Triangle removal is slower than leaf removal due to the step taken in testing
for a connection between the adjacent nodes. As stated previously any clique
sub-tending on the boundary may be removed with a similar procedure, however

as the cliques become larger the number of nodes that need to be tested grows.

52

On regular lattices however, simple geometry determines the cliques that might
be present. For example, on a bipartite lattice such as a square lattice a triangle
cannot exist. While, on a lattice such as the triangular or FCC lattice all cliques are

size 3 or smaller, so we need not search for anything larger than a triangle

TRIANGLE(AND LEAF) REMOVAL(G, Newer, 51’)

1 Make list L of singly connected and doubly connected nodes

2 while L > 0
3 do
4 Choose node i from list L
5 if Ci = 1
6 then
7 Find j the root of i (j=A(i))
8 xi 4— O,x]- +— 1
9 for all neighbors k of j
10 do
11 Remove edge { j, k}
12 Adjust connectivity of k, Ck
13 ifck=1||ck=2
14 then
15 add k to L
16 else Ci 2 2
17 if i part of a triangle
18 then
19 Findj the roots of i (j = A(i))
20 xi +— O,x]- +— 1
21 for all neighbors k of j

53

22 do

23 Remove edge 0', k)

24 Adjust connectivity of k
25 ifck=1||ck=2

26 then

27 add k to L

28 else remove i from L

29 return

4.3 Heuristic algorithms

For larger samples where it becomes impractical to use exact solvers, it is often
sufficient to find a near optimal solution. In this case, we can employ a heuristic
algorithm [93]. Ideally a heuristic will run in polynomially bounded time. From a
physics stand point it should demonstrate some flavor of the actual ground state. I
will outline the simple heuristics of greedy cover and random selection, then I will

discuss the local probability methods we have developed.

4.3.1 Greedy algorithms

The simplest heuristic is a greedy algorithm [33]. In this case, the algorithm is
predicated on the fact that highly connected nodes are more likely to be covered.
At each step the highest connected node is covered, when a node is covered the
connectivity of adjacent nodes is adjusted. Lovasz [52] showed the greedy algo-

rithm gives an upper bound on hypergraphs of

xN g (1 + 1nd) | v... |, (4.13)

54

x is the fractional cover, N is the number of nodes in the lattice, d is the maximum

degree and | We | is the cardinality of the minimum vertex cover.

GREEDY COVER(G,1?)
1 56' <— 0

2 while Edges are uncovered

3 do

4 choose node i with largest connectivity

5 cover i; x,- <— 1

6 update connectivity of i and neighbors of i
7

8 return

4.3.2 Random selection algorithm

Another simple heuristic is the random choice algorithm, here the algorithm
chooses one edge randomly at a time and covers each end, because of this property

the algorithm has an upper bound of,
xN S 2 | We |, (4.14)

RANDOM SELECTION ALGORITHM (G, 56)
1 J? <— 0

2 while Edges are uncovered
3 do
4 choose edge E = {i,j}
5

cover i,j; x,- +— 1,xj <— 1

55

6 deletes edges incident to i and j

8 return

4.3.3 Vertex-Local Probability Recursion (vLoPR)

By examining a local area on a graph, we can see that the probability a vertex is
covered is dependent on the probabilities of the surrounding vertexes. If there
is a vertex i with v,- neighbors, and every neighbor j is covered then every edge
(i, j) is covered and i need not be covered. If, however, any one (or more) of the
neighboring nodes is uncovered, then i must be covered.

The probability a vertex i is covered, xi, exists on the interval [0, 1]. When
xi = 1, the vertex is covered and when x,- = 0 the vertex is uncovered (in the MIS).
We can assume that a vertex i may not be covered (or uncovered) in all possible so-
lutions, this node would then be degenerate and its probability would lie between
1 and 0.

Imagine a barbell graph (two nodes with one connecting edge), by inspection
we can see that each vertex would be covered exactly one half of the time, so each
x,- = 1/ 2, with a degeneracy of 2. Another simple case is chain of three nodes,
with two bonds. Here the degeneracy is 1, both outside nodes have x,- = 0 and the
central node is xi = 1.

This algorithm can be expressed mathematically in a very simple formula;
vi
x,- = 1 — H xj. (4.15)
i=1

This equation can be used to solve for x,- recursively. The average probability

(x) = flxi/N appears to be at worst an upper bound for the minimum frac-

56

tion of vertexes covered (xc). We call this type of procedure Local Probability
Recursion(LoPR).

In the cases, of the barbell, or the 3 node chain, it can be shown that if one begins
with the correct probabilities for all the vertexes except one, the correct probability
can be calculated for that node. The second case can be generalized to any chain
consisting of an odd number of nodes. The algorithm also finds the correct value
for the cover probability for a 4-node chain and a square, (x4—chain) = 0.5, (xsq) =
0.5. If we were to use a triangle, three vertexes and three edges, then by inspection
the cover probability of each x should be 2/ 3. However, if we place values of
x = 2 / 3 on two of the vertexes and calculate x,- on the third vertex we find that
x,- = 5 / 9 after the first iteration and it does not converge to the correct value. In
fact, the limiting probability for a triangle is (xtri) = 0.61803. This probability
is a function of the algorithm and not the precision of the machine, as the same
result was obtained on a 32-bit Pentium chip running Linux and a 64-bit Turion

chip running Linux.

4.3.4 Analytic solution of vLoPR

Now if we want to find an analytic solution for the vLoPR algorithm, we make
the probability x,- a constraint on the probability P of a vertex having a particular

cover probability, x. For a vertex with v neighbors this will be written as;
U
Pv(x) = j dxl . . . j dva(x1)...P(xv)6(x — 1 + 11:11 xj). (4.16)

57

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A‘ A A 5‘

 

Figure 4.8: The minimum vertex cover on a 100 node diluted triangular lattice. a)
The probabilistic solution found using the vertex-LOPR algorithm. The solid circles
are nodes where a guard is necessary, the hatched nodes are ones, where the node
is degenerate, and the open nodes are where a guard is not necessary. b) A specific
minimum vertex cover generated from the vertex-LoPR probabilities using DIG.
(c) The probabilistic solution found using the bond-LOPR algorithm. (d) A specific
instance generated from (c) using DIG. The minimum cover for this graph is 54 as
was confirmed by finding the exact cover using an exact solver, and found by both
bond and site algorithms.

58

Using the identities,

 

P(x) = go" of P600 (4.17)
(x) = /()1xP(x)dx, (4.18)

We can now write,

00 1 e—ccv oo 1 e—ccv
A xvg U! Pv(X) = A xvgo U! fdxl...

0

 

 

/dx0P(x1)... P(xv)6(x — 1 + f1) xj , (4.19)

 

i=1
and
co e—C
(x) = / xdxvé;0 v /dx1
fdva(x1)...P(xv)6(x — 1 + 121 xj), (4.20)

i=1

Now, performing the integration over x on the right hand side to get,

 

c v
e c
v! /dx1 C I I

/dx0P(x1)...P((1xv) -j]:[1xl‘). (4.21)

(X)

00—

The integrals can now be separated, and since each integral is identical they can be

written as a product,

 

 

(x) = 1— E0 3:: CU 11:1[fdxjjx ~(xP (4.22)
= 1_ foe—1:606)”. (4.23)
v:

So what we finally get is,
(x) = 1 — e_C+C<x). (4.24)

And the probability I = 1 — x of a vertex being in the independent set is,
(1) = e—CW, (4.25)

which is the same result that was derived in Eq. (3.31), for the maximum indepen-

dent set on a Bethe lattice.

4.3.5 The vertex-LOPR algorithm

vLoPR is an iterative method, where each vertex is given a starting probability
drawn from a uniform random sampling between [0, 1]; there is no bias in selecting
vertexes. It would be possible to choose some initial probabilities based on local
structure such as leaves. Once the probabilities have been assigned, the node list
is randomized, a vertex i is selected from the list and a new cover probability x,- is
calculated, using vLoPR(G, x).

All vertexes are updated, and after each full sweep the averaged difference of

the site probabilities,

(6x) = (x,- — xf’evim), (4.26)

is calculated and iterations are stopped if (6x) < BOUND. Typically a
BOUND = 5 x 108 was used.

FUNCTION vLoPR(G, 51’)
1 while (6x1) 2 BOUND
2 do

3 Randomize node list

60

econome-

10
11
12
13
14
15
16
17
18

19 return

before it, with good results (See section 4.3.10). While the algorithm was being
tested, the node list was randomized before the while loop. Surprisingly, the re-
sults of these tests compare favorably to the results for the algorithm as stated

above. In section 4.3.10, I analyze the effect of the location in the algorithm of the

SU M <— 0
fori +— 1 to N from Randomized list

do

lprevzous (__ 1
PRODUCT +— 1
for all neighbors I ofi
do

PRODUCT <— PRODUCT x x]-

xi +— 1 — PRODUCT
xlprevious

SUM .— SUM + 531,.

éxi +— x,- —

(axi) .— SUM/N

Step 3 of randomizing the node list may be placed inside the while loop or

randomization procedure.

4.3.6 DIG

Once a graph has been ”solved” using the vLoPR method, the graph has still not

been resolved into a particular instance. The vertexes have been classified as cov-

61

ered, uncovered or degenerate. The next step is to generate a specific instance. We
call the procedure we use the Discrete Instance Generator(DIG).

The DIG procedure is simple. We choose a vertex i from a degenerate cluster
and uncover that vertex. The vertex list is now re-randomized and vLoPR is run
again. In general, this procedure reduces the number of degenerate sites by at
least 2. The choosing of degenerate nodes continues until there are no degenerate
vertexes left in the graph.

The DIG procedure always ends after a vLoPR run, such that the final gener-
ated instance is always a true cover of the graph. We believe that if, the original
vLoPR run resulted in a fractional cover, xc, less than the true minimum fractional
cover, then a true minimum fractional cover with be generated from the DIG
procedure. Fractional covers with different cardinality fall into discrete instances

with a small range of cardinality.

FUNCTION DIG(G,5r')
while there are degenerate nodes
do

choose a node i from list of degenerate nodes

FUNCTION VERTEX-LOPR(G, 5?)

1

2

3

4 x,- <— 0

5

6 count degenerated nodes
7

return

4.3.7 Bond-LOPR (bLoPR)

In the previous section we dealt with vertex probabilities irrespective of bonds.

Now, we want to create a similar procedure where the probability that a bond is

62

covered is forced to one. If we examine a bond (i, j), with vertex i at one end and
j on the other, the vertexes have v,- and vi neighbors respectively. Now in general
there are 4 possible states for the bond to be in, one vertex covered X1110 or X31, two
vertexes covered le1 or degenerate Kg. Just a comment here on the notation. The
superscript identifies the edge and the subscript indicated the state of each vertex,
1 if covered, 0 if not covered, D if naturally degenerate, so X110 means node i is
covered and node j is not. These bond probabilities are determined by the vi — 1

and v j — 1 neighbors outside of the bond.

To calculate X11]O we ignore the bond (i, j), if one, or more, of the v,- neighbors
are not covered then i must be covered, we also need to ensure that no neighbors
of j are uncovered. These two terms can be combined so that the probability that
vertex i is covered and j is not becomes,

1.- vi ”1'
X] — (I - n xk)( H XI). (4.27)
kEn(i)\j IEn(j)\i

This can be then extended to the other 3 probabilities to get,

.. vi v]-
zj = _ I .
. v-
le1 = 1— 131 xk) (1— 1’1 x,), (4.29)
k€n(i)\j l€n(j)\i
.. v,- vi
Xg = ( n xk)( H x1). (4.30)

kEn(i)\j lEn(j)\i

If a simple definition of,

Yij = H .xk, (4.31)

is made these can rewritten these as,

XI.) = (I- my.»

X31 = Yij(1——in),

XIII = (l—Yz‘j)(1_in)r
X1111 = Yiini

(4.32)
(4.33)
(4.34)

(4.35)

One can find the probability a vertex i is covered from summing the edge proba-

bilities,

We can also write this as the complementary probability,

if

211‘:( X’1j1+§ill).

vi 1]

1 ii XD
E121 (1 " X01 ‘ TI'
1 vi Yl—jyli
1_v—ij§1(yij(1—Yfi)+ 2 —)r
1 vi Yi_j_.in
1 _ 171. g (Yii 2 _l'
1 vi 1 vi vi
l—v—£( I_I xk—§( H xk)( H 3‘0)-
lj=1 kEn(i)\j k6n(i)\j lEn(j)\i

(4.36)

(4.37)

(4.38)

(4.39)

(4.40)

Similarly to the vertex-LOPR algorithm, the bond-LOPR algorithm performs

well on the barbell, and the 3-node chain. However, on the 4-node chain and the

square it over estimates the cover probability, (x4—chain) = 0.514719, (151)) =

0.583433 While the limiting probability for a triangle is underestimated, (x
0.585786.

64

tril :

4.3.8 Analytic solution of bLoPR

Similarly to the analysis of the vLoPR algorithm, we can then write our analytic

representation of bLoPR as,

Pv(x) = /dx1.../dva(x1)...P(xv)(5(x—1+-1—g[ 1211 xk

”5 1=1 ken(i)\1‘

1 vi 0]:
—1( 1‘1 x101 1‘1 241) (441)

k€1’l(l’)\1’ l€n(1)\i

For a moment we will just look at the delta function and work on simplifying that,

1 vi 01 1 vi z’1'
5(x—1+;E[ H xk—§( II xk)( H 9611])-
lj=1 k€n(i)\j k€n(i)j l€n(j)\i

To begin we make the approximation that all vertexes converge to a steady state

probability related to the average connectivity v,
01 ”1'
H xk = n x]. (4.42)

kenmv Ien(1)\z'
We rewrite the delta function as,
1 v v 1 v 2 v—1 1 v—1 2
5(x—1+5;[H.x "El-kal) — 6(x—1+I:ka—§I:1xk)4.43)
j—l k7é] kyé] k—l k—l

65

The analytic equation can be written as,

Pv(x) = fdx1.. .fdva(x1)...

 

P(xv (x—1+ka——nxk) (4.44)
00 eC-C
P(x) = Ugoe v!6)/dx1.../dva(x1)...
—1 —1
P(xv)6(x — 1 + 01—1 xk — 1v11 xi). (4.45)
k=1 2k=1

Multiply both sides by f xdx and integrate over dx to get,

         

(x) ..fdva(x1)...
v—11v—1
P(:,)(1 -— 1'1 xk +— 2 111 xk), (4.46)
which can be reduced to,
(x) = 1 — (17>exp(—c+c(x)) + fiexp(—c+c(x2)). (4.47)

Equation (4.47) involves the higher moment (x2), so it is useful to examine other

moments. The higher moments can be calculated by multiplying Eq. (4.45) by

66

h

f x“ dx and integrating to get the at moment,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 _ _ 2exp(——c+c(x)) 2exp(—c+c(x2))
(x ) — 1 (x) + (x2)
9X — 3 8X — 4
_ P( (ago D P( 42:1;(96 >) (4.48)
3 _ _ exp(—c(1 + (20)) 9exp(—c(1 + (x2>))
(x ) — 1 3 (x) + 2<x2>
_4exp(—c(1 + (x3))) 9exp(—c(1 + (x4)))
(x3) 4(x4)
_3exp<—c<1 + <x5>>> exp<—c(1 + 1x6)»
4(x5> 8 (x6) (4.49)
<x4> = 1 _ 4eXP(-C(1 + (10)) + 88XP(-C(1 + (362») _ 106XP(-C(1 + (X30)
(96> (x2) (x3)
+17exp(—c(1 + (x4))) _ 5exp(—c(1 + (x5))) + 2exp(—c(1 + (x6)))
206“) (x5) 806)
exP(-C(1 + (x7>)) exP(-C(1 + (968»)
_ 2(x7) 16(x8) ' (4'50)

These as yet have resisted our attempts to write them in a general form.

4.3.9 The bond-LoPR algorithm

BOND LoPR(G, 51')
1 Randomize node list

2 while (15x1) 2 BOUND

3 do 1

4 fori +— 1 to N from Randomized list
5 do

6 xlprevzous (_ xi

7 S <— 1

8 S) <— 5k +- 1

67

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

for all neighbors j ofi
do
for all neighbors k ofi
do
if k 7E j
then S, <— 8, x xk

for all neighbors k of j
do
if k 7E i
then Sk +— 5k x xk

S<—S+Sl—O.5XSIXSk

x,- <— 1 — S
revious
(5xl- +— x1- — x1?

SLIM <— SUM + 5x,-

(5xi) = SUM/N

return

4.3.10 Convergence of vertex and bond LoPR

In order to examine the convergence and performance of the LoPR algorithms we

tracked three quantities; The first quantity is the fraction of covered nodes (x),

the second is the difference between the average fraction of covered nodes and its

value for the previous run 5(x) = (x) — (xprevious> , the third quantity is the aver-

68

 

 

 

 

 

 

 

0.55 . l I I I I I I I I I I I f I I I I I I I I I I I I I I l I I T I I I I I l-
0.54 - —
A -
X a
V :
0.53 T
0.52 - l l l 1 l l l l 1 l l l l J l l l l l I l l l l l l l I l I I l l l I l [A
0 200 400 600 800 1000 1200 1400

iteration

Figure 4.9: The minimum vertex cover as a function of iteration for a specific 10000
node triangular lattice, using the site (thin line) and bond (thick line) LOPR algo-
rithms, while randomizing the ordering of nodes every iteration.

age of the differences between the site probability xi and its value in the previous
run (5x) = (x _ xpreviousy

As a measure of the stability of the algorithm, I also tested running the algo-
rithms with the node list randomized before the while loop, and samples where

the node list was re-randomized before each pass through the lattice.

Figs. 4.9-4.14 show the convergence of the site-LOPR and bond-LOPR algo-
rithms on an arbitrary N = 10, 000 node triangular lattice with connectivity,
c = 3.0. All simulations were started with the same initial conditions, and run
on the same lattice. In Figs. 49- 4.11, we see the convergence profiles for the al-
gorithm when the node list is randomized on each pass through the lattice. Figs.

4.12— 4.14 shows the convergence profile when the node list is randomized once.

Figs. 4.9 and 4.12, show that the algorithm converges very quickly to the neigh-

69

 

0
10 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIW—IFTITITII—rIII

8<x>,<6x>

 

._. v—-
C O
00 \l
“ -(
IIIIIJ IIIIIJ IIII lllll‘ IIIIIJ IlllI‘ lllll‘ IIIIIJ lllll‘ IIIIIJ Illll‘ III

 

 

10‘ . W W w
10'9 1 1 l ‘l 1 ll 11
10-10 ;
10-11
10'12 I I I I I l l I I I I I I I I I I l I I I 1 I l I I l I I l I 1 I l I I l I I l J
0 200 400 600 800 1000 1200 1400
1terat10n

Figure 4.10: 6(x) (orange) and (5x) (blue) as a function of iteration for the same
10000 node triangular lattice and initial conditions, as the previous figure, using
the vertex-LOPR algorithms, while randomizing the ordering of nodes every itera-
tion.

borhood of the correct value. We can see that as (x) converges it often does in a
stepwise fashion, the value of (x) changes quickly. This indicates an avalanche
where the probabilities over a significant portion of the graph change dramati-
cally. The algorithm mathematically need not be stepwise since x is continuous.
Convergences for these tests were run to a BOUND = 5 x 10-9. For all samples
we studied, in chapter 6, convergences were done to a BOUND = 5 x 10‘8, where
the frozen fraction is largely set. The value of (x) over the whole graph converges
much faster than the values at individual vertexes. This can be understood by re-
membering the barbell graph. If one end is covered the other is uncovered (x) = 1,
but if we flip the values of the nodes then (x), (6(x) = 0) remains unchanged but
(6x) = 1.

The convergence profiles for vLoPR, as shown in Figure 4.10 and Figure 4.13,

70

 

I—l H
o. o .
o 1'). J:- LL:
o IIIIII‘ [III-'1‘ IIIW In"! I'll-l1 [”1”qu IIIIIl‘ IA!”

5<x>,<6x>

 

_.
-_n

 

llllld IIIILIJ Illll‘ IlllllJ IIIIIIJ lllll‘ Illll‘ llllllJ Illl|d llllllJ Illll.‘ llLl

 

l I

l I I I l I l I AI—l l I
209 _ 400
1terat10n

 

Figure 4.11: 6 (x) (orange) and (6x) (blue) as a function of iteration for the same
10000 node triangular lattice and initial conditions, as the previous figure, using
the bond—LOPR algorithms, while randomizing the ordering of nodes every itera-
tion.

illustrate that in this instance the algorithm proceeds through cycles of relaxation
followed by reorganization. This continues until the system is unable to drop into
a new lower state. This does not mean, however that the final state found is nec-
essarily the global minimum energy state, it is possible that we have found a local
minimum. The single list case, is similar to the re-randomized case, but there is a
complete lack of noise on the quantities 6 (x) and ((5 x). Both variants seem to be ro-
bust enough to pass over several energy barriers. The noise in the standard version
of the algorithm does not have a large effect on the overall covered fraction.

In the bond algorithm, Figs 4.11,4.14, The convergence is comparatively fast
taking roughly one third of the iterations of the site algorithm. We see the same
ability to pass over some energy barriers that was exhibited by the site algorithm

though the effect on the measured values was less drastic, this is due to the fact,

71

 

0.55 x

 

 

 

 

 

 

 

I I I I I I I I I I ‘I I I I I I I I I I
.1
0.54 —
A _

><

V ..
0.53 ~- —
I _

0' 2 I I I I J L I I I I I I l I I I I I I I I

5 0 200 400 600 800 1000
iteration

Figure 4.12: The minimum vertex cover as a function of iteration for a specific
10000 node triangular lattice using the site (thin line) and bond (thick line) LOPR
algorithms generating one node list used for every iteration.

that in the bond algorithm significantly larger numbers of nodes are ”degenerate”.

All four convergence tests were run on the same lattices with the same initial
node probabilities. The final values converged to in Fig 4.9 are (x) = 0.52424 for
the site algorithm, and (x) = 0.530982 for the bond algorithm, in Fig 4.12 the sim-
ulations run with one node list converged to (x) = 0.524401 for the site algorithm
and (x) = 0.530678. Neither algorithm correctly counts the degeneracy, this im-
plies that neither algorithm fully explores the whole energy landscape, as such we
cannot say they converge to global minima. The practice of repeated reordering
of the node list, makes it easier for the algorithms to avoid local minima making
the final value of (x) much less affected by the initial conditions. It however, does
increase the running time, and also makes it less likely to converge to a 6 (x) value

of much less than 5 x 10‘9 on a N = 10,000 node graph. In general, good per-

72

 

0 I IIII I I I II IIIII IIIII I I ITT rl
10 = F I I I I
10' ?

 
   

8<x>,<8x>
_A
O
llIlIJ IIIII‘ Illfld lIlIIJ IIIIIJ Illll‘ IIIIH llll

I'
!

 

 

lllld IIIIIJ LLLIIJ ll

I I I I I I I I I I I L I l 1 l l I l l I I I I l l l I I I l l

200 400 . 900 800 1000
1teration

 

o IIII‘ Inn” III-"‘7 III-I" FIN“ III“! III"! III] I

Figure 4.13: (5 (x) (orange) and (5x) (blue) as a function of iteration for the same
10,000 node triangular lattice and initial conditions, as the previous figure, using
the vertex-LOPR algorithms generating one node list used for every iteration.

forrnance was found with both algorithms and with both methods of ordering the
node list. In order to more fully compare the effect of ordering the node list, the
algorithm was run over 105 configurations for the N = 100 node triangular lattice
displayed in Fig 4.8. Table 4.1 shows a histogram of the results comparing the sin-
gle ordered nodes list algorithms and the re—randomized node list algorithms for
a lattice with a known exact solution, we can clearly see there was no apprecia-
ble difference between the methods of ordering the node list. Using the single list
LoPR a slightly higher percentage of solutions, about one percent higher, found

the correct ground state.

73

8<x>,<6x>

Figure 4.14: (S (x) (blue) and (6x) (orange) as a function of iteration for the same
10000 node triangular lattice and initial conditions, as the previous figure, using

 

I I

l
209 .
iteratlon

L

I

 

I I

I
400

the bond-LOPR algorithms generating one node list used for every iteration.

Table 4.1: Percent of occurrence of solutions for the LoPR algorithms on the 100
node triangular lattice shown in Figure (4.8). The results are averaged over 10,000

runs. The exact solution for the lattice (x) = 0.54.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Standard LOPR Single List LoPR

(x) vLoPR DIG bLoPR DIG vLoPR DIG bLoPR DIG
0.53 0 0 0 0 0 0 0 0
0.54 55.975 56.66 0 68.505 56.7 57.65 0 69.17
0.55 39.555 40.965 0 31.495 39.02 39.985 0 30.88
0.56 4.365 2.275 100 0 4.2 2.28 100 0
0.57 0.1 0.1 0 0 0.085 0.085 0 0
0.58 0.005 0 0 0 0 0 0 0
0.59 0 0 0 0 0 0 0 0

 

74

 

Chapter 5

Core Percolation

Preconditioning of graphs is a time-honored method of simplifying an instance.
This chapter deals with reductions of a graph brought about by the removal of
leaves, and triangles. The subsequent remaining graph is known as the core, it
is this part of the graph that contains the higher connectivity nodes, and remains

computationally hard.

In this chapter, we will discuss the results of leaf removal and triangle removal.
First, we will discuss the results of core percolation by leaf removal on an Erdos-
Rényi style random graph, the 2-dimensional triangle and square lattices and the
3—dimensional FCC and simple cubic lattices. Then we will discuss the results of
core percolation by triangle removal on the random, triangular and FCC lattices.
The results of leaf removal on the triangle lattice has been published [40]. The
results for leaf removal on the other lattices are in preparation [37] as are the results

of triangle removal [38].

75

5.1 Core percolation by leaf removal on random
graphs

As stated previously, leaf removal is a partial application of Tarjan and Tro-
janowski’s algorithm for finding an MIS. It was first applied by Karp and Sipser
to matching in 1981 [46]. Subsequently, Bauer and Golinelli [5], analyzed the be-
haviour of leaf removal on a random graph. Leaf removal has also been applied
to simple Boolean networks [15]. Bauer and Golinelli found that above a critical
concentration of bonds, there remained a core of nodes and edges that could not
be removed by leaf removal. They observed that the core percolation threshold for
leaf removal on a random graph occurs at the same critical concentration as replica
symmetry breaking. In their paper, they analyzed behaviour at the critical point
and drew the conclusion that core percolation is in a different universality class to
that of standard percolation [5]. This section will draw an alternative conclusion,
namely that core percolation by leaf removal on a random lattice is in the same

universality class as standard percolation.

5.1.1 Generation of random graphs

All calculations on random graphs were made using the Erdos-Rényi model. In the

Erdos-Rényi model edges are placed at random into the graph with the probability,
p = c/ N. (5.1)

Where, N is the number nodes, and the connectivity, c = 2E/N, is the average
number of edges per node.

Simulations were done with sample sizes of N = 100, N = 1000, N = 104,
N = 105, N = 106 all samples N _<_ 104 were averaged over 104 configurations,

76

graphs of N = 105 were averaged over 1000 configurations and graphs of N = 106

were averaged over 100 configurations.

5.1.2 Random graph results

Figs. 5.1-5.3 show the results for the giant cluster after leaf removal. Figure 5.1 is
the probability of a node in the graph being on the giant cluster, and Figure 5.2 is
the number of edges in the giant cluster as a fraction of the number of nodes. The

probability a site is on the largest cluster,

and at percolation the number of edges in the largest cluster, EC, scales in standard
percolation as,

EC w—l
PC N N , (5.3)

where in standard percolation w takes a value of 2 / 3 [6]. Figure 5.3 shows the
connectivity of the core as a function of the original connectivity of the graph. The

connectivity of the core scales as [20],
cc — 2 ~ N—‘P (5.4)

The graphs of PC, EC and cc are in agreement with the results of Bauer and Golinelli
[5]-

In Figure 5.4, we apply the scaling relations to find w, 42. Here we make the ob-
servation that the widths of the mean scale as the mean, thus we find w = 066(2)
and 4) = 022(1), which are very similar to the values obtained by Bauer and Go-
linelli [5] (see table 5.1).

Figure 5.5 shows finite size scaling collapse in the critical regime of the giant

77

 

 

 

 

0.8 I I T I I I I I I I I I I I I I I I I 1%
’ 3
. i -
0.6 ~ _ ' -
I. . ..
I a .
I - :
Q
~ A 1
0.2 — —
l- ..
A? A A ‘
O . . l l l l_ I l l L l
2 3.5 4

 

Figure 5.1: Plot of the probability of being on the core versus connectivity for
random graphs. Sample sizes and number of realizations, starting from the
top trace: N=100(10,000), N=1,000(10,000), N=10,000(10,000), N=100,000(1,000),
N=1,000,000(100).

78

 

 

I S I I I I I I W I T I r I I I I I I I a
_ i
_ i
I- . -I
h- . c-I
I — i A
_ i .1
E I- I
0 :5.
LL] I I ‘
.
-I
-I
0 ‘ . ._ :: 3 § .. 1 1 1 I I I I 1
2 2.5 3.5 4

 

 

 

3
C

Figure 5.2: Plot of edges in the core cluster versus connectivity. Sample sizes (num-
ber of realizations), starting from the top trace: N=100(10,000), N=1,000(10,000),
N=10,000(10,000), N=100,000(1,000), N =1,000,000(100).

79

 

 

 

 

4 I r l' T r I I I I I I T I I I I T
b +
r- - -1

b I
3 S F I -
.. l q
- H -
L g a
l- . -‘
o

O 3 " g "
. i a
~ i
P -
2.5 -- —
A: A a ‘

26—8—3—a—a—8 I l 1 . .
2 . 3.5 4

 

Figure 5.3: Plot of connectivity of the core versus connectivity of original graph.
Sample sizes (number of realizations), starting from the top trace: N=100(10,000),
N =1,000(10,000), N =10,000(10,000), N=100,000(1,000), N=1,000,000(100).

80

 

I fTW TTII

~

‘-
.~..
‘-.
‘-
\‘.
\“

'-
‘0.
‘0
.‘.-
\
.....
‘l
s‘.
h‘.
s‘.
§‘.
\‘.

 

llllLLJ

I

..‘l
.‘.'
.....

l

3

10

I TIITIII

11111111

104

N

T

J

I rTIIIIl

1 1111111

105

I

I

 

I IIIIII

-I

d

i

 

Figure 5.4: Finite size effects of connectivity (+), Edges in core (V), PC (a), the vari-
ance the connectivity (x), variance in the number of edges in the core (V), vari-
ance of the probability of being on the core (I) at the transition, c = e. Sample
size (number of realizations), N=100(10,000), N=1,000(10,000), N=3,000(10,000),
N=10,000(10,000), N=300,000(10,000), N =100,000(1,000), N=1,000,000(200).

81

 

 

 

 

L- I I I I I I I I I I I I I I I f Ij fI T +I I _
0 a
no -
6 ’- Can _
+
000 O
a u
on“ °
0
r- on o -1
a
N 4 l— _
G 00
Z t ° ° L "
0:0 ~ A
U >- -
Du gap 1 ° _
2 l—. L" _
up
+ c: -
P #9??? -
t . .... 9 / -
ofi 1 39 [$5 ‘3 I 131“: 11551 0 1 I 1 I I 1 1 I 1 1 I 1 1
-8 -6 -4 -2 0 2 4 6 8

9
(p-pc) N '
Figure 5.5: Finite size collapse fit with 91 2 035(2), 62 = 033(3). Sample

sizes (number of realizations): N = 100(10,000)(A), N = 1,000(10,000)(<>),
N = 10, 000(10, OOO)(D), N = 100, 000(1, 000)(o), N = 1, 000, 000(100)(+).

CILISIIEI' using the scaling ansatz,
P N 61 N p — p N 2 5 5
C ( C) - ( ' )

Traditionally, 01 = 02. Here, 91 and 62 were allowed to vary independently to give
a check in relation to the standard scaling ansatz, and to allow more freedom to
find a good collapse. The collapse we found is good for values of N > 105, and
adequate for N = 104. It is hard to fit smaller samples because of increased finite
size effects. Upon collapse we have 91 2 035(2) and 92 2 033(3), verifying the

scaling ansatz. In standard percolation,
6 = 1 — w (5.6)

The exponents we measured are listed in table 5.1. We see that our value of (p =

82

0.22 is close to Bauer and Golinelli’s which they believe to be 1 /5 and given their

relation of,

(021—24),

(5.7)

convinces them that w is closer to 3/ 5, placing core percolation by leaf removal in

a new universality class rather than that of standard percolation. It is not simple to

say that core percolation is not a new universality class, it is easy to say that what

we have observed is consistent with leaf removal on a random graph being in the

same universality class as standard percolation. It is likely that higher accuracy

experiments in the future will deal with this question in more detail.

ohs

 

 

Table 5.1: Critical Exponents for core percolation on random gra]
exp. standard Bauer and Golinelli Fay
9 1 / 3 2/5 033(4) Figure 5.5
w 2 / 3 3 /5 066(2) Figure 5.4
4) 1 /5 022(1) Figure 5.4

 

 

 

 

 

 

5.2 Core percolation by leaf removal on regular lat-

tices

In this section we study the percolative properties of core percolation on regular

lattices, specifically, the triangular, square, simple cubic and FCC lattices. First we

will examine the properties of 2-d lattices and then the properties of 3-d lattices.

We focused on three percolative properties: (i) the spanning probability, PS,

the probability that a core cluster spans the sample, (ii) The probability a node is

O

on that spanning cluster Poo, (iii) the core cluster number 115(3, p) and the aver-

age cluster size (s). The scaling behavior of these quantities near a second order

transition is given by [84],

P509) N fswPLl/V)

83

(5.8)

I78

 

 

 

 

 

 

 

 

 

SSIA'Z z a 99152: x a 001 01de wopuei
’9 ’31 99 ’zn ‘10 ’ds
— (1)9690 881720 3mm
(z)8zz0 (UZOZ‘O 6110 33:1
— (928890 000090 3112an
(2)0890 (9269170 sumo Jalnfiuem
‘d ’zu. 1d ’211 4d as 3311491

 

 

'(Hl) [mower 313mm pue (3'1) [mower 5931 Kq uouqoo
dad 3103 pure ((5) uogqoolad puoq piepueis Jo; spmqsanp uopemmad :zg aneL

'uoue[o3iad
[euopuaAuo3 ueq; sagIApoauuoo 19148111 q3nLu ie .In33o spquanp uopqooiad 3.103
3111 mm 339 um 3M 'saomeI IBInBaJ uQ '9'17 pue z}; 'SBH pue 6'9 ’8'9 ’[9 ’9'9
315 ur paiuasaid 312 93311121 mo; am 10; amp MPH '39 3mm in 1811 are spmqsanp
uope[o3.tad 3111 '[179] 339321 :3qu adults e no ggpz'o = 4d pue ’a3p421 33:1 am no
6110 = ‘Id ’a3m21 3.19an am no so = 4d ’aomeI mmBuem am no 621.1790 = qd
in Burnmoo pmqsann uoue[o3iad puoq piepueis am 1mm ’99 ane; u; 9 = p 10;

pue 9'9 ane; u; paisn are 3 = p 10; siuauodxa [123141.13 uope[o3iad piepueis aqL

z—lg
I—ld

(zrs) v—z=np’z=k+dz+v’ —

’Aq
pomp; are A3111 pue ’iuapuadapur are siuauodxa 3111 Jo 0M4 A1110 aouIs pauuoyad
aq Aeux suopeIn3193 sq; uo >paqa V 'hi :9 mun 3313.421 anugu; am 11; .1. iuauodxa
am auruuaiap 0; sn smone (01:9) 'b3 '4, pure g ’n ’siuauodxa aqi aunmaiap 0; sn
M0119 091:; pure ’sonAeqaq Suneos azrs 31mg sq; uieiuo3 v] ’14] ’00] ’Sf ’suou3un;

81111939 aql '[PAOUIBJ 3931 .10} iqud [2311113 am 51 1d pue ’| 1d — d |= d9 aJaqM

(II'S) (11 NW) ”1 119 ~ <9)
(01's) 00 <— 7(d9fl9) “f 1_9 ~ (609“
(69) (a/ 17"?) “ya/91-7 N (d)°°d

 

0 . v>> ‘9

_ a) 5%, a _
0.8 - > up I —
.— ’1’» :- ‘

.. I 9b ’
s ‘
. I. a
0.6 - -1
- ‘ .4

‘4 *9

an face: I
_ ++ 5 -
0.4 — I ; ‘8? —

 

 

 

 

 

 

 

 

Figure 5.6: Plots of leaf removal on bond diluted triangular lattices. a) Span-
ning probability P5 as a function of the bond concentration p. b) The infinite
cluster probability as a function of p. Sample sizes and number of configura-
tions, N = 1,000,000(100), N = 500,000(2,000), N = 250,000(1,000), N =
100, 000(10, 000), N = 50, 000(10, 000), N = 40, 000(10, 000), N = 10, 000(20, 000),
N = 5, 000(20, 000), N = 3, 025(10, 000), N = 1,000(20, 000).

 

 

 

 

 

 

 

    
 

 

 

 

1 I I I I I I I I I I I I
_ I I fiffi‘mlfi‘ ‘
: ) :<:>>D 5’ _
_ a 3.; p _
0.8 — a» f -
_ 5, . _
' .5 ++ '
_ 4. -
_ a» _
0.6 — -‘
_ 3 _
v: - , -
Q4 _ J6 -
— w —
—_ +fl _-
0.4 _ 3"? _
_ + > _
_ ++ b ..a‘ _
.. 1 _
+ p A __
0.2 I— :1 D» ‘ 4 :1 _
I- 3" DD A 4:: ‘
_ + by; AA 4! -
_ ++ _
I W”? “MI E q . I 1 1 1 1 I 1 1 1 1
(I) 5 0.55 0.6 0 0 75
I- I I I I l I I I I I I I I I I I T f I I I I I I _
.. I
0.8 - b) —
I. ..
I _
0.6 "‘ "‘
m8 I I
0.4 - —
0.2 '_ +++ _‘
I. ............... 'v """"" .. ”H". I 1 I 1 1 1 I I I 1 1 1 -
%.5 0.55 0.6 0.65 0.7 0.75

Figure 5.7: Plots of leaf removal on bond diluted square lattices. a) Spanning prob-
ability P5 as a function of the bond concentration p. b) The infinite cluster prob—
ability as a function of p. Both graphs were done over a range of graph sizes,
N, and averaged over a number of configurations. Sample sizes and number of
configurations, N = 1,000, 000(100), N = 250, 000(1,000), N = 102,400(1,000),
N = 40, 000(10, 00), N = 10, 000(10, 000), N = 3, 025(10, 000), N = 1, 024(10, 000).

86

 

   

 

 

 

 

 

 

 

I - I I I I I I I I I I , 2. _'
i a) I e 2
6:8 I‘ ‘9‘
0.8 — 5° .4 :- —
: g3 fl I
0 6 ; °Il f —_
. 8‘ I; _
(h - ..
a. - g a _
_ I _
0.4 — 5f ——
_ £5 _
_ $§ "
_ {‘3’ _.
0.2 '- 1; cm": _
_ 3!: , :
4 I 1 L I 1 l l 1 I 1 1 J_ 1
0 l 0.15 0.2 0.25 0.3 0 35
0.8 l
L .
_ J
I- -1
0.6 —
. i
F -
8 L _
0.4 -- —
n. . _
T ..
L _
0.2 — _
0"“
0.1 015 02 0.25 03 035

 

 

Figure 5.8: Plots of leaf removal on bond diluted FCC lattices. a) Spanning prob-
ability P5 as a function of the bond concentration p. b) The infinite cluster, Poo,
probability as a function of p. Both graphs over sizes N = L3(and number of con-
figurations) of L 2 5(10, 000), L = 10(10,000), L 2 15(10, 000), L 2 20(10, 000),
L 2 30(10, 000), L = 50(1,000), L = 70(1, 000), L : 100(100).

87

 

   

 

 

 

I I I I I r ——_ I fiwé #A A
l I I I W ‘7' Iv
: Z): 3’ ,"I W“ _
_ a) 21.1: X _
_ .M: a" f _
0.8 — ..f: f —
L “a: 9 :
9,; j _
0 6 L 9‘: I a; -
' . a? .. .
(I) I- ." '3 _
9-. _ oi‘ : _
- I." 4
0.4 -— g; —
_ :2- .4
- 3‘0 -1
0.2 — i :38 —
I
_ i _ 5.0 _
I I” .2; :
_ 5g .
1 I I l I l I I 1 1 4 1
(I) 2 0.3 0 4 0 5

 

 
 

lJllIllllIllllIllllIll-

 

 

NIIIIIl‘l’TfiITIIfirIIIIIIIIIII

 

Figure 5.9: Plots of leaf removal on bond diluted simple cubic lattices. a) Span-
ning probability P5 as a function of the bond concentration p. b) The infinite
cluster, Poo, probability as a function of p. Both graphs over sizes N = L3(and
number of configurations) of L = 5(10000), L = 10(10000), L = 15(10000),
L = 20(10000),L = 30(10000), L = 50(1000), L = 70(1000), L = 100(100).

88

5.2.1 Graph generation

All lattices were generated with free boundary conditions. The two-dimensional
lattices were generated on an L x L substrate, where L = \/N. If \/N was not an
integer then L was rounded up (ie. \/1_000 = 31.6 => L = 32). The final row in the
sample is missing the number of nodes necessary to give the desired N. Thus an
N that is a natural square such as 10, 000 is an 100 x 100 lattice, while a 1000 node
lattice is 32 x 32 with 24 nodes missing in the final row. There was no difference in
the results calculated on lattices constructed in this manner and lattices constructed
from perfect squares. The FCC lattices and the cubic lattices were constructed in
an L x L x Lbox, such thatN = L3.

On all lattices edges were placed by the random insertion of bonds, each bond

has a probability of,
cN

= 5.13
” zemax ( )

 

of being present. Ema x is the total number of edges that would be present in the
lattice if there were no dilution, this number is dependent on the geometry of the
lattice. Each bond is assigned a random probability, which if less than p, the edge
is inserted into the graph. The FCC lattice is generated along the 1,1,1 direction
by stacking triangular lattices. The average connectivity of a site for the lattices is
c = zp, where z is the coordination number, 2 = 6, for triangular and cubic lattices,

z = 4 for the square lattice and z = 12 for the FCC lattice.

5.2.2 Leaf removal on 2-d lattices

In Fig 5.10, an unbiased estimate of the exponent v is found by using, (5 p12 = (p12) -
(pl)2 ~ L’Z/V, where (p1) is the average value of PI found by (P1) = f pddes /dp
and its second moment(p12) = f pzddes /dp. Fig 5.10 is a log-log plot of (5p, vs
L from which we find that v 2 134(3) for the triangular lattice, and v = 139(3)

89

 

 

 

 

I I f I I I I r I I I I I l T j I
E\. "l
\\
\0“.
.- ‘t- I _.
‘0
\\\'\
s"\
.. ss
‘i l
.t'
x
x
t;\
\‘.
‘ C
it.
x
10'2_ -
\ \
)- “'\ at
L- ‘\“* J
x
F d
s
N l'\.
and '- ‘s‘. q
s
w )- ‘. -I
\‘x.
\
x .
— ‘\‘ d
0‘.
\‘o
- “ " d
‘0-
x
“i
>- 4
10'3 L 1 1 1 1 1 1 I 1 1 l 1 1 1 1 1 I

Figure 5.10: Plots of (51212 2 (p2) — (p)2 as a function of lattice size L on a double
logarithmic graph. The triangles are data from the triangular lattice, the dashed
line is a best fit from which we extract the estimate 11 = 137(3). The boxes are data
from the square lattice from which we extract the estimate 1/ 2 139(3).

for the square lattice. The values for v are similar to each other, though the square
lattice value is slightly higher than the conventional value for percolation. A sum-

mary of the exponents found can be seen in Table 5.3.

Determination of the critical threshold is presented in Fig 5.11. As the sam-
ple size increases, the value of PI( L) approaches the infinite lattice value and the
width of the spanning probability (5p, approaches 0 [85] [32]. By plotting Pl (L) as
a function of 5p, (L), we can make an estimate of p I (00). To determine a value for
the intercept, the triangular lattice data was fit with a line, and the square lattice
data was fit with a quadratic. From this fit we find the threshold for the triangular
lattice at P1 2 0.4690(4), and the threshold for the square lattice at p, 2 0.6384(4).

In Fig 5.12, we analyze the finite size scaling behavior of the infinite cluster us-
ing higher-order finite size corrections. In correlated percolation problems, [3 can

be sensitive to these corrections [66]. We now analyze the infinite cluster probabil-

90

0.470
0.469
0.468
0.467

0 0.466
>
N

9" 0.465
0.464
0.463
0.462

0.461

0.639
0.638
0.637

0.636

3V6

0.635

0.634

0.633

0.632

 

 

 

 

 

 

 

 

L7. _
r- ‘Q‘é‘é -
. “4. _
— kk\‘ -—
r- —-
1 “‘~ -
)— “‘s“ _—
. ‘ ‘
_ ~~4 I
— “““‘ _‘
1 I 1 I 1 I 1 I 1 I 1 \“~
0 0.005 0.01 0.015 0.02 0.025 0.03
5p,
I I I I I I I I I I T
I“ -
_ ‘49 ._
I- ‘+. —
._ 2k _.
__ "‘11" -
_ . +‘ 's, _-
_ ................ 4.-.?
1 1 l l 1 1 1 l l l 1
0 0.005 0.01 0.015 0.02 0.025 0.03
p1

Figure 5.11: Plots of the average value of PI as a function of 6p], for each sample
size we find pl(L) and (5p1(L). 5p, goes to 0 as L goes to co. This allows us to
extract the infinite lattice critical point. (a) Corresponds to the triangular lattice
from which we extract p I = 0.4690(4). (b) Corresponds to the square lattice from
which we extract P1 = 0.6385(2).

91

 

_
_
q
—1
_1
.1
l

llllllllIlI“

0.25 r-

0.2

ln(P)/ln(L)

0.15 F-

I l l J l I I

 

 

0.1

l l l l I L l l I l l 1

0 0.1 I 0.2
l/ln(L)

 

Figure 5.12: Analysis of the infinite cluster probability using a next to leading or-
der finite size correction, as given by equation 5.14. The triangles are the data
for the triangular lattice at P1 = 0.4692. The + are data for the square lattice at
P1 = 0.63825, and in both cases a fit can easily be made for the standard perco-
lation exponent B/v = 0.104. The triangular lattice has a correction to scaling
exponent of w 2 035(5). The square lattice has a correction to scaling exponent of
w = 042(5). Sample sizes and number of realizations for the triangle lattice, N =
1,000(20, 000), N = 1,600(20, 000) N = 3, 000(20, 000), N = 4, 900(20, 000), N =
10, 000(20, 000), N = 16, 900(20, 000), N = 30, 000(40, 000), N = 62, 500(20, 000),
N = 100, 000(10, 000), N = 160, 000(10, 000), N = 300, 000(5, 000), N =
1,000, 000(1,000), N = 2,560, 000(1,000), N = 10, 240, 000(100). Sample sizes
and number of realizations for the square lattice, N = 1,024(10, 000), N =
3,024(10, 000), N = 10, 000(10, 000), N = 40, 000(10,000), N = 102, 400(10, 000),
N = 250, 000(1,000), N = 1,000, 000(1, 000), N = 10, 240, 000(100).

92

 

 

 

 

 

 

 

 

0
IN

L 5p,

Figure 5.13: A scaling plot for the infinite cluster probability. (a) The best collapse
for the triangular lattice was found with P1 = 0.4692, B/v = 0.163, v = 1.35. (b)
The best collapse for the square lattice is found with Pl = 0.3825, B/v = 0.146,
v = 1.37.

93

 

 

 

 

I I I I I I II I I I I I I II I If
5 _ _
10 ‘x
: ‘+\‘;\_‘ i
Z .3944 .
4 _ £2». _
10 E 10:. E
E ‘Ii. 5
: '1’ ‘
A 3 _ ‘tfik

Kl) 10 ‘tfl 1::
3 I51- 1
I. \;“-‘_ '1

2 A
1 E" 31“ g
0 E ‘3}. E
i it I
1 " _
1°? “4%
L- l l l l I [II J l l l I l I II I H1 2

-2 -1
10 10

lp-pll

Figure 5.14: Plots of the average cluster size on approach to p1 from below for
lattices of size N = 10240000 sites, from this plot we extract the exponent 'y. The
triangles correspond to the triangular lattice at P1 = 0.4692 yielding 7 = 216(3).
The circles correspond tot he square lattice at P1 = 0.63825 yielding 'y 2 219(3).

ity using the form [18],
P... = aL—fi/Vu + bL—w). (5.14)

Afitofthe data is then madeusing —lnPoo/lnL = B/v — lna/ lnL — bL‘w/lnL.
It is difficult however to find the ”best fit” for our samples, as any number of
y-intercepts yielded reasonable fits. We proceeded on the assumption that core
percolation was in the same universality class as conventional percolation. With
that assumption, both the square and the triangular lattice can be fit [with the stan-
dard percolation exponents ,6/1/ = 0.104, the correction to scaling exponents are
then, w 2 035(5) for the triangular lattice, and w 2 042(5) for the square lattice.
However, both lattices can be easily fit for a range of B/v, implying that while
this is consistent with the universality class of standard percolation, it is not suf-

ficient to rule out a new universality class. In order to get more exact results, it

94

 

I
111

I TnII
,v
I I llllI

p—d
C,
III I
I
V
11111111I

I— I-d
0_ ON
I I I ITI l I
43"
D
I l

l I I‘ll]!

 

 

 

 

A
A“
0 -— A
10 l [I 1 I l l I 1 I LI 1 I
1 2 3
10 10 10
S
:K‘ I I I I I I I I I I I I
4 ~\
10 E— b) ‘4‘
: u.
C \‘1‘.
3 \
10 I“...
N ‘4"
:w 4.

 

 

 

M
l: “#11:.-
10"? . , *
101 102 103
S

Figure 5.15: Double logarithmic plots of the cluster size distribution for lattices
of N = 10240000 sites. (a) For a triangular lattice the dashed line has a slope of
—2.09(5). (b) For a square lattice the dashed line has a slope of —2.07(2).

95

Table 5.3: Comparison of Core percolation exponents and Standard Percolation
exponents for 2-d lattices. * values measured without the use of corrections to
scaling.

 

 

 

 

 

 

 

exp. (i=2 triangular square comments
11 4/ 3 ~ 1.33 1.37(2) 1.39(1) Figure 5.10
v 4 / 3 135(4) 137(4) Figure 5.13
[3 5/36~ 0.139 *0.20(2) *0.20(2) Figure 5.13
7 43/18 ~ 2.39 *2.16(3) *2.19(3) Figure 5.14
T 187/91 ~ 2.05 209(5) 207(2) Figure 5.15

 

will be necessary to run larger sample sizes, but that becomes difficult as sizes
of N = 10,240, 000 with 100 realizations takes several days to run on our com-
puters, and getting results for sizes even an order of magnitude larger becomes
prohibitively difficult.

The scaling behavior of Poo may also be determined by the collapse of data
in Fig 5.13. A very good collapse for the triangular lattice of sizes N 2 40000
(L 2 200) sites, may be found with pc 2 0.4692(2), [3 = 020(2), and v = 135(4),
And for the square lattices over the same range of sizes for pc 2 0.3825(2),
,8 2 020(2), and v 2 137(4). The [5 found from the finite size collapse is higher
than expected, and is explained by the difficultly in determining [3 in correlated

percolation problems.

The cluster statistics are presented in Figs 5.14 and 5.15. The value of '7 we find
is smaller than the conventional percolation value of 'y = 216(3) for the triangular
lattice and, 'y 2 219(3) for the square lattice (see table 5.3). To find T, one sample
of L = 3200(N = 10, 240, 000) was run as near to P1 was possible. The quantity n5

is defined as,
number of clusters of size 5

 

 

And the average cluster size (S) is defined as,
"552
(5) = Z (5.16)

From Fig 5.15 we find that r 2 209(5) for the triangular lattice and T = 207(2)
for the square lattice, which are consistent with the conventional value.

Core percolation on the 2-dimensional lattice is shown to be consistent with
the universality class of standard percolation. The largest deviation from standard
percolation is in the value found for '7 (see Figure 5.14), which is significantly lower
than the standard value. 8 is also a difficult prospect but the higher-order scaling
corrections show that our results are consistent with the conventional value, simi-

lar finite size corrections occur in standard percolation (see appendix A).

5.2.3 Leaf removal on 3-d lattices

Leaf removal on 3-dimensional lattices shows behaviour similar to the 2-d lattices.
On the 3-d lattices most exponents are close to the standard percolation values,
however, 1! for both lattices and B for the cubic lattice show deviations from the
standard values. Fig 5.16 gives an estimate of v 2 100(5) for the simple cubic
lattice and v = 0.982(5) for the FCC lattice. These values are higher than the
conventional 3-d value of 0.88. Appendix A presents the bond percolation results
for the FCC and cubic lattices with free boundary conditions. The bond percolation
results give v = 093(4) for the cubic lattice and 1/ = 092(2) for the FCC lattice
(see table A2). A comparison of exponents can be seen in table 5.5. The critical
threshold for the FCC and cubic lattices is shown in Fig 5.17, giving a value of
P1 = 0.202(2) for the FCC lattice and P1 = 0.393(1) for the simple cubic after
quadratic fits.

The higher-order finite size scaling plots of the FCC lattice and the cubic lattice
appear in Fig 5.18, again with a fit constrained to intercept at the conventional
value of 8/1/ = 0.4659, they both show fits that appear reasonable, with the FCC
lattice needing no corrections to scaling. From a linear fit we find 8/1/ = 0.471 (6)

for the FCC lattice. The simple cubic lattice has a correction to scaling exponent of

97

w = 0.4(3).

The scaling plots for the collapse of the infinite cluster probability appear in
Fig 5.19. For both lattice types we were able to find a reasonable collapse. Fig
5.19(a) shows the collapse of the FCC lattice at p I = 0.2023, and the conventional
percolation values of 8 = 0.41(2), v = 0.88(4) this collapse is for the 5 largest
samples L 2 20. Fig 5.19(b) shows the collapse for the same sample sizes of the
cubic lattice at P1 = 0.3921. In this case, we see that the value for 8 2 061(2)
is higher than the standard value, while u = 088(4) is equal to the conventional

value.

When the results obtained here for the leaf removal and the results for standard
bond percolation are compared, on 3-d lattices with free boundary conditions, sim-
ilar values are obtained implying that the deviation seen in v is related to finite size

effects and the boundary conditions.

The cluster statistics are presented in Figs 5.20 and 5.21. In the 3-d case, the
value of 'y we find is much closer to the conventional percolation value of 'y = 1.80,
than we saw in the 2-d cases. We find '7 = 1.74(2) for the FCC lattice and, '7 =
1.7(2) for the cubic lattice. Likewise, we find that T = 2.17(8) for the FCC lattice
and T = 223(6) for the cubic lattice, which are consistent with the conventional
values. A summary of the exponents on the 3 dimensional lattices can be found in

table 5.5.

Table 5.4: Comparison of core percolation exponents and standard percolation ex-
ponents for 3-d lattices
exp. d=3 FCC cubic comments
1! 0.88 0.982(5) 100(5) Figure 5.16
0.88 088(4) 088(4) Figure 5.19
0.41 041(2) 061(2) Figure 5.19
1.8 1.74(2) 1.7(2) Figure 5.20
2.18 2.17(8) 223(6) Figure 5.21

 

 

 

'1th

 

 

 

 

 

98

 

 

 

 

10- __ I I T I I I I fii I I I I I I I _
>- l‘.‘x,‘_‘ a
tax _
I- “~‘ _
."*I“
r K.
"'~x
U s \_
Q 2 _ I _
to 10 : ““ x :
I- ‘v‘\ x .
.. ‘~‘\ Xs. ..
\“ "x
p "“ H
\‘v“
'3 I I I I L l I I I l I I I I I
10 1 2
10 10

Figure 5.16: Plots of 61912 = (p2) — (p)2 as a function of lattice size L on a double
logarithmic graph. The down facing triangles are the data from the FCC lattice
with give an estimate of v = 0.982(5). The cubic lattice data is the crosses which
give an estimate of v 2 100(5).

5.3 Summary of core percolation by leaf removal

On all lattices studied core percolation by leaf removal appears to be in the same
universality class as standard percolation. The exponent 8 was difficult to obtain
because of finite size effects, but higher-order scaling corrections showed it to be
consistent with the standard percolation value. The value for 11 found is close to
standard percolation. On the 2-d lattices 1! was measured as slightly higher than
the standard value. On the 3-d lattices the value of 11 measured in Figure 5.16 was
significantly higher than the standard percolation value. However, the value of v
extracted from the finite size collapse was equal to the standard percolation value.
The discrepancy is believed to be a product of edge effects from the free bound-
ary conditions and finite size effects, as shown by similar results in Appendix A.

The exponent ”r as calculated for the triangular and square lattices was low, but it

99

 

 

 

 

 

 

 

 

I I I f I I I I I I I I , I I I I I
I
0.21 — ’1’ v _‘
a) .
,I
I— II ‘
I
I
I
I
I- I -‘
I
I
I
I -I
" I
I
’I
0.205 — ,' —
Q) "
> I
m“ _ I, q
r. ‘
' ‘v. x" l
0.2 — “‘v\ ’1” —‘
I- “‘\\ ' It’ll '4
"‘~~~¥ ..... ” i
F
I I I I I I l I I I I I I I I I I
0 0 01 0.02 0.03
p1
0.405 I I I I I I I I I I I I I I I I I I I I I
I l I . l x
I
I- ’ -1
I
b) "
_ II -I
III
III
_ [I -I
I
I
0.4 — ,’ d
[’1
F I,
II —I
o " ,’
> 1'
CU " 1' .
o. -
x’
0.395 — _
I _
IR ’1” -
l- ‘93 x
x ‘
x--. ”,“x
0.39 ‘2" -
L I l I I I I I I I J_ L L I I A I I I I I I I I
O 0 01 0.02 0.03 0 O4 0 05
pl

Figure 5.17: Plots of the average value of PI as a function of 5p], for each sample
size we find pl(L) and 6p, (L). (a) Corresponds to the FCC lattice from which we
extract Pl = 0.202(1). (b) Corresponds to the cubic lattice from which we extract

p, = 0.3925(5).

100

 

 

 

 

In] - I I I I I I I I I I T I T T I I I I I I I I I I I I I I I I I I "(T d
I ,Jr’ 2
— ’ -l
I I— -‘.’-‘:I
t .-X'” I
0.9 — ”,3 rrrr .3
A >- .r',”' _.
d : «*5? ' 1
c: 0.3 r— ,x/V’ j
< I: "xx 1” -1
A8 : ’x-fi.x I ' :
m 0 7 _ xi ’ —
v L: ,x '1 ..
I: ' y" ‘
~ I- ” -4
0.6 — J
I _
P d
0.5 —.£"’ —‘
3’ I
0.4 _ I L I I I l I I I I I I I I I l I I I I l l I I I I I I I I l I I I -

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7

l/ln(L)

Figure 5.18: Analysis of the infinite cluster probability using a next to leading order
finite size correction, as given by equation(5.14). The triangles are the data for the
FCC lattice at Pl 2 0.2023. The crosses are data for the cubic lattice at P1 = 0.3928,
and in both cases a fit can easily be made for the standard percolation exponent
8/1/ = 0.4659. A linear fit for the FCC lattice gives 8/1/ = 0.471(6). The correction
to scaling exponent for the simple cubic lattice is w = 0.4(3). Sample sizes and
number of realizations. L = 5(10, 000), L 2 10(10, 000), L = 15(10, 000), L =
20(10,000),L 2 30(10, 000), L 2 50(10, 000), L 2 70(10, 000), L = 10(1,000),L =
200(100). .

101

 

 

 

 

 

 

 

 

I o Duo '
‘ v 000 " ..
a) A ' DD 0"
A a q-
. A . no -
DO.
I’m?)
A 'no '
“Om' "
‘8.
3%.? .
8 "a
n. .39
'5‘- .3
.—l _ i _
'0
+ f «
M?
“M
o I I I I I I I I I I I I I l I I I I l
1 05 0 05 1
UV
L 5p,
3 I I I I I T I I I I I I I I I I I I. '0.
- . '5 _
«- .00
l- b) ‘ .‘9
_ .39
‘A.Dd
2" .‘bo. —l
Al)
9.8 b If I
2 " (3'
n4 - ‘5
t 3
a!"
- g? _
39
. $33.83
prfifl J I I I I I I I L I I I I I I I
-2 -1 0 1 2
UV
L 5pI

Figure 5.19: A scaling plot for the infinite cluster probability. (a) A good collapse
for the five largest FCC lattices was found with P1 = 0.2023, 8 2 041(2), 11 =
088(4). (b) A good collapse for the five largest cubic lattices is found with P1 =
0.3921, 8 2 061(2), 1/ = 088(4).

102

 

 

 

 

: . up I I I I I I I I I l fl T I rI I I I I :
: 'V. i
v\._\. ......I. x _1
"XX
)- v X .x- _
3 — ‘3‘ . _
10 : '1 fig 5
E V. 'x. :
F IV.‘ ”Io; :
A . ‘v‘ ”‘8‘. -
Kl) 2 ‘._
10 E" "a
I 2
E \‘ '.. x x E
F '7‘ xxx,“ “ll :
’- l l I I I I l I I 4 1 I I I I I‘I" I I ‘
-3 -2 -l
10 10 10

Ip-p 1'

Figure 5.20: Plots of the average cluster size on approach to P1 from below for

lattices of size N = 8 x 106 sites. Plots for the FCC lattice (v) yield 7 = 1.74(2).
(b) Plots for the square lattice (x) yield '7 = 1.7(2).

was very close for the FCC and cubic lattices. T was found to be consistent with

standard percolation values on all graphs.

5.4 Core percolation by triangle removal

Core percolation by triangle removal appears to be in the same universality class
as standard percolation. Figure 5.22 and Figure 5.23, show a typical second or-
der phase transition in Poo. The transition on the triangular lattice occurs at
pt = 0.580(2) and at pt = 0.228(2) on the FCC lattice (see Table 5.2). Figure 5.25
shows the approach to pt(oo) as a function of ((5pt(L))2 = (pt(L))2 — (pt(L)2),
from which an estimate of the critical point, pt is extracted.

Critical exponents were determined using the same procedure as for bond per-
colation and core percolation by leaf removal. Figure 5.24 shows the plot to extract

the exponent 11 which gives a value of v = 133(6) for the triangular lattice, which

103

 

 

 

 

 

 

 

 

E‘ II I I I I I I I II T I l I I I I II E
5‘ V I
.. \ _
\\
:— a) E
E V\ E
\
r- \ -
‘\
E— ‘yt —E
E ‘1' E
: "V i
I \ I
r:— -=
E v E
P V W“ V V ‘
_ v ”('7 IN V
F V WV
:1 I l l l l l I I [I I l I l I I 1 II :
1 2 3
10 10 10
S
_‘\II I l I I I I I II I I I I I I I II
8‘ i
_— \ -:
E \ E
_ b) .\ _
l- \ .-
\
I
E- \X ‘5
I Xx 2
- "x _
E— ‘Q‘ "5‘
: ”not 1
: \l“ 3
_ x _
:— ‘X _:
: “06‘ :
3 xx} x I x a: 3
- xfi‘xnoot :- -
- Intuit): 3:00: —
E xxx \
l l I l l l I [I l I I l l l 11“
l 2 3
10 10 10
S

Figure 5.21: Double logarithmic plots of the cluster size distribution for lattices of
N = 8 x 106 sites. (a) For a FCC lattice we find a T 2 220(7) at pa. = 0.2023 (b) T
on a simple cubic lattice is 223(6) at pc 2 0.3928.

104

 

 

 

 

 

 

 

 

l r I I if I I I I ’ P
: “dd » W :
_ d4 “4"” _‘
- a 1.134 A‘ +5” _
o 8 — :54 f 9 w“ -
' :4 A pp» 3"; '
- A + —
.. ‘ p: ++++ —I
- ’ ‘ p f q
o 6 — a ‘ > x ~
. g ‘ b +
In - I: ’4' 1
_ ++ .
Dd — £9. :+ -I
04' 3““ ‘
- E: }
" I o
.. ++ ‘ D
0.2 — a?“ “a - «
_ ##9‘: a o‘ _
+ .X
: +,»“” a; A“ j 0.. :
_ ”fig-I f ff." _
01 I I I 1 I I I I I I I I
0.5 0.55 0.6 0.65 0.7
0-8 I I I I I I I I I I I I I I I I I I I I
.. ”#d-i
. b) 4+” _
,_ #4» -
_ #43”? -
4+“
0.6 '-- “a —
L J" -1
93'” J
_ +++¢
— + 4
8 .. _
a“ 0.4 — -
I. 0* _
,_ + 43+" -
_ “:1” 9"" -
o_2 — »*’+# f 4 _
- IMM 4 ' -
W” <1 _
.. W ,(
W M if ..
0 I L l IQ; I I J I I P I l
0.5 0.55 0.6 0.65 0.7

Figure 5.22: Plots of the core after triangle removal on a bond diluted triangular lat-
tice. a) P3 as a function of bond concentration. b) Poo vs connectivity. Sample sizes
and number of configurations, N = 1,000, 000(100), N = 250, 000(1,000), N =
102,400(1,000), N = 40, 000(10, 00), N = 10, 000(10, 000), N = 3, 025(10, 000),
N = 1,024(10, 000).

105

 

  
   

 

I - I I I I I I I jiT I Ifi -

E a) 3
0.8 — _

: a j

_ .3! , _

.. I‘o ‘ f _

0.6 — I: i f _
m I £3 j
9-: L 1 I; r
- e? «I 4
0.4— f j
I f _

_ a» _

0.2 _— _-
0('- I I I I l I I I I I I I I I I l J -

 

 

 

 

53
a.

0.1 0.15 0.2 0.25 0.3 0.35

 

0.8 l I I I I I I I I I I I I I I l I l l I I I I

b)

  

0.6

0.2

I I I I I I I I I I I I—I I I I I I I

I I I I I j I I I I l l I l I I I l

 

 

0‘ 1 I I I 1 1 1 1491 I l I I I l L

0.1 0.15 0.2 0.25 0.3 0.35 0.4

Figure 5.23: Plots of the core after triangle removal on a bond diluted triangular lat-
tice. a) R; as a function of bond concentration. b) Poo vs connectivity. Sample sizes
and number of configurations, L 2 5(10, 000), L = 10(10,000), L = 15(10, 000),
L = 20(10,00), L = 30(10, 000), L = 50(1,000), N = 70(1,000), N = 100(100).

106

 

 

 

 

- I I I I T I l I I I I I I I I I I I I I—r
10 I; I ‘\ I I-I
\
L. \s
K \\\
.. x
P- V\'\ ‘*\
'\ ‘\\
\‘\ \*\
‘K ‘\\
\. 1‘
a '\ \‘x‘
Ga ‘2 _ \V ‘; _.
0° 10 "x \“k
\ -4
‘\ ‘s‘ "
‘. L ‘
\ \‘
1‘ ~\ ‘
.‘v \~
\-
\. ..
V.
\
.\
\
1‘3 IIIII l I llIlllI \'x1 I IllIllI
0 1 2 3
10 10 10

Figure 5.24: log-log plots of (5 p t as function of L on after triangle removal on the tri-
angular and FCC lattices. A value of v 2 133(6) was measured for the triangular
lattice, and 1/ 2 092(2) was measured for the FCC lattice.

matches exactly the standard value for II. On the FCC lattice we got a value of
v = 092(2), which is higher than the standard value of 1/ = 0.88, but equal to the
value measured for standard percolation in Appendix A.

Figure 5.26 shows the correction to scaling analysis of the infinite cluster. The
triangular lattice may be fit with values consistent with those of standard perco-
lation, as with leaf removal there is a great deal of freedom in the fit. Lattices up
to the size of N = 106 nodes were run, which is an order of magnitude smaller
than those run for leaf removal (for leaf removal N z 107). This is due to the time
required for triangle removal on lattices near N z 107, with one realization taking
several days.

Finite size scale collapses are shown in Figure 5.27, which show that for the FCC
and triangular lattices, the value of I! obtained for the best collapse is equivalent
to the standard percolation value. As in the collapse for core percolation by leaf

removal, it is observed that the value for ,8 is higher than the standard value. The

107

 

 

 

 

0.595 I I I I l I I I I I I T I l I I I I fl I I ” r
I- ‘ q
I- a) ’1’, -I
0.59 - ,I’ -
2 . -
cu
Q. ’ ‘
0.585 — —
I- A ,” -I
0.58 ~.-‘ ‘ ’’’’’ _
_ ““A-"t ---- A .
I l I I I I I l I I I I I I I l I I J I I I I I
0 0.01 0.02 0.03 0.04 0.05

 

 

 

 

0.238 I I I I I I I I I I I I I I I I I I I I .F I I I
E b) ,1"! v 3
0.236 — _
0.234 - _‘
: .1" 1
g t .1". j
a 0.232 — _
Q: ' ."’ 1
I j
- ‘1' ..
0.23 '— .1" _
0.228 :- v _
.. "K." I, . "l ..
t- Y‘ ............. ’"r .4

0.226 I k I I I I I I I 4] I I I I l I I I I I I I I

0 0 005 0 01 0.015 0.02 0.025

Figure 5.25: Plots of pt as a function of 5m after triangle removal on the triangular
and FCC lattices From (a) we extract a value p t = 0.580(2) for the triangular lattice
and on the FCC lattice (b) a value of pt = 0.228(2) is obtained.

108

 

 

 

 

 

 

 

 

I T I I I I I I I I I I I I T I I I I I I I I I j 1 1 I 1
_ ‘5‘
.. a) x. .J
u- """" -1
0.3 — x," _
P ”a" -I
t ,A .
’l"’ -
A " ‘," ‘
,4 0.25 — ._
v - ,1 a
A _ I," _
D48 0.2 — _
v : x” 1
.s. - .
— I, .1
0.15 "- I!” —‘
.- I a:
I
I- I, c
’I
I- I a-
I
5’ ‘
7
0.1 — —
'- I I I I I I l l I I I I I I I I I I I I I I I I I I I I I q
0 0 05 0 l 0.15 0 2 0.25
1.4 I f I I I I I I I I I f I u
L- -.
r V -
l- b) -
1.2 —- -*
h "=
3 ' """" -
v I- V. -
= l- "’ d
Q ' ,y’” 3
A u- '7’ —4
m _ "1 I1
: 0.8 — ’,.v _
—0 F ”,7 "
F- "a' '1
0.6 _ I”” —
I- ’I” n:
I— ’I d
I,
V -4
— -+
I I I I I I I J I i I I I I
0.4
0 0.5 l 1.5

1/ln(L)

Figure 5.26: Higher order finite size scaling after triangle removal. a) Results for
the triangular lattice. b) Results of the FCC lattice.

109

 

 

 

 

 

 

.4
q
—1
‘l
—
d
'1
‘
.1
—4
q
.4
_
A
_
.1
u-
-

O.-
v

IIIIIIIIIIfIIIIIIIjII’I

 

 

 

 

N
L.
o
...
m

Figure 5.27: Finite size collapse of Poo on the FCC and the triangular lattice after
triangle removal. (a) The collapse for the triangular lattice was obtained for values
of pt = 0.579, )3 = 0.27, v = 1.33. (b) The collapse for the FCC lattice was obtained
for values of pt = 0.228, ,8 = 0.61, 1/ = 0.88.

110

 

 

 

 

10 i: ‘k‘ I I I I I l l I 1 f I I I I I I I fl T a
I A I
104 :— 1 A . 'i
I ‘ A 2‘
l- ‘ -t
-. at: I
h.‘-‘.‘ ‘ q
3 __ .‘.“s_ K _
A 10 E "v.‘.'\' E
m I ‘V 3
V “ "W ‘
2 x
10 ;- . xx 3
: ‘V- i ‘1
- *y“ ‘L‘ j
.. '0” ‘ -
101 E— m?
t x:
0 4 1 1 1 1 1 1 l 1 1 1 1 1 I 1 1 l I.""\ 1 1
10 -2 -1
10 10
p pt

Figure 5.28: The Average cluster size on approach to p t after triangle removal. For

both lattices each point represents one realization of lattices of size N = 106 nodes.
(a) Shows the triangular lattice with pt = 0.580 giving a value of 'y 2 213(4). (b)
Shows the FCC lattice with pt = 0.228 giving a value of 7 2 161(3).

111

 

 

 

 

 

 

 

 

I I I I I I I II I I I T I I I I
1‘ «
3 \\A
10 T \ 3
_ s :
: a) ‘
\\ "
h- \ q
A
P- \\ '1
2__ ‘x _
10 5 \\ E
”.4 E “‘6 5
:m r- ‘\ ‘ -1
T \\\Q -.
1 “s
10 E’ ‘QA A A —
r -
; *3AAA‘ 3
.. A‘« A .
. ‘\‘ AA AA 4
\
0 “
“WAA
10 r 1 1 41 1 1 1 1 1l 1 1 1 1‘4 1 1 1
l 2 3
10 10 10
S
+II I I I I I I rII l I I I I r I I
\ .
\
103 ~ Y“ “
u- \ "
: b “ I
: ) x 2
r- “ -4
. ‘ a
\
_ \ 3
‘v
102:— '5
m : 9\ :
r- \ "
A”) : '\\‘ :
1:: pr
.- V‘Y ‘
1_ 3. _
10 5 O" E
. V V I
,_ y ' "
i- Y -4
p VJ w v .
0'- \
10 : I I I I I I I I II IVWI~\\I I I I ‘
I 2 3
10 10 10
S

Figure 5.29: Cluster size distribution for the triangular lattice after triangle re-

moval. (a) Gives the value of T 2 198(8) for the triangular lattice of size N = 106
at pt = 0.580. (b) Shows the cluster size distribution for an FCC lattice of size

N = 106 at pt = 0.230 giving a value of T 2 207(8).

112

values found from triangle removal are higher than those found by leaf removal.
The triangular lattice sees an increase in 8 of roughly 40% and increase of 50% on
the FCC lattice, over the leaf removal values. The value of 8 for triangle removal
on the FCC lattice compares favorably to the values of 8 on the cubic lattice for
leaf removal, this of course is only a valid comparison if as for standard percola-
tion, only the dimensionality of the lattice matters in the universality of the critical
exponents. As stated previously it is difficult to obtain 8 in correlated percolation

problems.

The value of 'y is obtained from Figure 5.28. On the triangle lattice a value of
7 = 2.13(4) is observed, which, while lower than the standard percolation value,
compares favorably to the value of '7 for the triangular lattice from leaf removal.
The value of 'y = 1.61 (3) on the FCC lattice which is slightly lower than the values
obtained for leaf removal and for standard percolation. This exponent is sensitive
to the critical point, pt, used in its calculation, which may account for the discrep-
ancy. Finally, T obtained for the triangular lattice and FCC is consistent with the
values for bond percolation and leaf removal. On the triangular lattice it was nec-
essary to increase the box size of the histogram, in order to reduce the noise enough

to generate a fit.

Table 5.5: Comparison of Core percolation exponents and Standard Percolation

 

 

exponents after triangle removal
exp. d=2 d=3 triangular FCC
v 1.33 0.88 133(6) 092(2) Fig 5.24
1! 133(4) 088(4) Fig 5.27
8 0.139 0.41 027(2) 0.66 (2) Fig 5.27
’7 2.39 1.8 2.13(4) 161(3) Fig 5.28
T 2.05 2.18 198(8) 207(8) Fig 5.29

 

 

 

 

 

 

 

 

 

113

 

5.4.1 Triangle removal on a random graph

Triangle removal on a random graph resulted in an extremely small shift of the
critical point. This is due to the very small number of triangles present in a random
graph. Figs. 5.30-5.32 show the results for the giant cluster after leaf removal. From
Fig 4.2 we can see that the difference between triangle removal on a random graph
and leaf removal is minimal at best, as expected. In Figure 5.34, we see the collapse
of triangle removal data is similar to the collapse obtained for the leaf removal
data, Figure 5.5. Figure 5.33(a) shows the finite size effect of the connectivity just
as we had in the leaf removal case, with similar fits. Figure 5.33(b) shows the
deviation between the leaf removal and triangle removal at small sample sizes,
indicating an increase in the finite size effects This supports our claim that as the
dimensionality increases the difference between the transitions for leaf removal

and triangle removal disappears.

5.4.2 Summary of triangle removal

Core percolation by triangle removal appears to be in the same universality class
as core percolation by leaf removal and standard percolation. For all types of core
percolation it is difficult to obtain values of 8 consistent with standard percolation,
this is believed to be due to a lack of larger samples and the difficulty in determin-
ing 8 in correlated percolation problems. At lower dimensions, there is a sizeable
difference between the leaf removal critical point and the triangle removal critical
point, as the dimensionality of the graph increases the difference between the two

goes to zero.

114

 

   

 

 

 

0 8 I I I T I I r I I #
I
"' I A
U A
'- a A
0.6 — '3 —
>- 0 A '1
_ B x .
U
Q‘ 0.4 :- 8 p j
>- A
b-
0.2 - _
“ . _: 3 .. 3' “‘- 1 1 1 1 l 1 1 1 1
2 2.5 3 3.5 4
C

Figure 5.30: Plot of the probability of being on the core verses connectivity af-
ter triangle removal for random graphs. Samples sizes and number of real-
izations. N=100(10,000), N=1,000(10,000), N=10,000(10,000), N=100,000(1,000),
N=1,000,000(100).

115

 

 

 

 

Is I I I I I I I I I
a t
a 1:.
p—
a .5
U .«3
1... U a .—
0 a
m” 9
0 [1
A
9
{:1 —1
-I
I I I I 1 4L I
3.5 4

 

Figure 5.31: Plot of edges in the core cluster verses connectivity after triangle re-
moval. Samples sizes (number of realizations), N=100(10,000), N=1,000(10,000),

N=10,000(10,000), N=100,000(1,000), N=1,000,000(100).

116

 

 

 

 

4 I I I I I I I I T $
. 3‘11
0 A *
r- -1
3 S A
.~ I- o A -I
U Q -
l" 11‘; -‘
0.. ... a 9: _
Q ..
q
.4
I J I I I I
3.5 4

 

Figure 5.32: Plot of connectivity of core verses connectivity of original graph
after triangle removal. Samples sizes (number of realizations), N=100(10,000),
N=1,000(10,000), N=10,000(10,000), N=100,000(1,000), N=1,000,000(100).

117

 

I ITIIIIII I I IIIIIII I I IIIIIII r I IIIIIII
‘

l

u
5
.....

‘.
--.
-5,

\~'
“-
“.
§~.
\~.
‘\

  

‘5.
‘Q

 
  

 

 

 

 

 

 

 

10 _- ...............
U '- """"""
g. _
+-
1027 a)
l“I I I IIIIIII I I IIIIIII I
2 3 4 5 6
10 10 10 10 10
_I T I IIIIIII I I IIIIIII I I IIfiIII I I IIIrII‘
;.\.‘.‘ d
o "M‘.
-1 K“. _
10 E r... .
r- \_ _
o I ‘N I
m _ ~.\ .
p "I’ .4
.- -\.‘.‘.. _
102: b) “i
I I IIIIIII I l I4I_I_III I I IIIIIIL I I Illlllfi
2 3 4 5 6
10 10 10 10 10

Figure 5.33: a) Finite size effects of connectivity (+), Edges in core (V), PC (a), the
variance the connectivity (x), variance in the number of edges in the core (7),
variance of the probability of being on the core (I) at the transition, c = e. b)
shows the finite size effects of the probability of being on the core after both tri-
angle removal (black) and the leaf removal (green). Samples sizes (number of
realizations), N=100(10,000), N=1,000(10,000), N=3,000(10,000), N=10,000(10,000),
N=300,000(10,000), N=100,000(1,000), N =1,000,000(200).

118

 

 

 

7 I I I I I I I I j I I I I I r I I I I I I I I I I I I I I I I I I I I I I T I
: 0 -
t O ‘
6 — a —
- 0 an 0'1
'_ u 0 _‘
5 _ b a _
U
.— a O _
n- o D 1-
— D -
CIDz * °° ‘
'- ‘b I. Q'-
0 t :0 o z. ‘ 3
m 3 ‘— A A A —"
I- f‘. .4 q
~ ~ 3
h- d
2 — —
1 _ _
. a
of
-a -6 -4 4 6 8

 

9
(p-p.) N ‘

Figure 5.34: Finite size collapse of the core after triangle removal on the random
graph, fit with 61 2 035(2), 92 = 033(3).

119

Chapter 6

Local Probability Recursion

Hard computational problems, like the hard-core lattice gas, display glassy be-
haviour. The aspects of the hard computational problems that are important phys-
ically include the onset of glassy behaviour, and degeneracy of ground states. The
issue of degeneracy brings forth the ideas of fluctuations, the frozen fraction, and
clusters. We know that in spin glasses and frustrated lattice gases there are a large
number of ground states. The frozen fraction is defined by the overlap of the states,
the nodes in the frozen fraction, are nodes that are in the same state (covered or un-
covered) for all ground states. (P), which measures the density of the MIS, is the
coarsest measure of the lattice gas, corresponding to its density. The Hamiltonian

of the lattice gas is,

H: {giijn-nj —y2ni. (6.1)
{1]

The density of the lattice gas within the replica symmetric assumption is,

_e___><p(h)
p= f—OOdh oo h)1+exp(h) (62)

For more on the origin of this function see Eq. (8.43) in Appendix B. I want to

make a note here about the meaning of the function g(h). Weigt and Hartmann

120

describe its physical interpretation as, ”take a site i, then its average local occu-
pation number (xi-h, in the presence of the chemical potential y can be written
as exp [hi] / (1 + exp [hiD using an effective chemical potential h,- accounting for all
interactions on i. g(h) can now be constructed as the histogram of these effective
chemical potentials.” This is similar to the probability distribution of the order pa-

rameter, typical of spin glasses.

To study these problems, in the absence of suitable exact algorithms, we use
heuristics that capture or give an insight into the physics of the problem. In this
chapter, we present the results for the local probability algorithms presented in
chapter 4. These algorithms capture some of the physics, namely good results
for the order-parameter distribution, or the site probabilities. However, they fail
to correctly find the frozen fraction. This chapter contains the results for a site
based heuristic, and a bond based heuristic. The site based heuristic which we
have termed vertex-LOPR is based on iterating Eq.(4.15) until a steady state value
of the average site probability is found. The edge algorithm known as bond-LOPR
iterates equations Eqs. (4.27)-(4.40), which ensure that each bond is covered. These

are used to generate the site probabilities in Eq. (4.36).

The lattices used in these calculations were constructed using the same method
as in Chapter 5. The MIS site probabilities, Pi, were calculated using double preci-

sion on 32-bit Linux PCs, and converged to an accuracy of 5 x 10‘8.

Figs 6.1, 6.3, 6.5, 6.7, 6.9 show histograms of the site probabilities for various
large lattices. For the histograms, average connectivities, of c = 1.0, 2.0, 4.0 were
chosen to give graphs of the same size a similar number of bonds. The graphs illus-
trate the variability in the site probabilities typical of hard computational problems
and that there is a nontrivial order parameter distribution. There are pronounced
peaks at the binary values P = 1 and P = O. The strong peaks at O and 1 show
that the vLoPR algorithm finds a greater number of integer probability or ”frozen”

121

sites as compared to bLoPR. On all bond algorithm frozen fraction graphs we see
probability spikes at roughly P ~ 0.35, 0.5, 0.7 which correspond to those seen by
Weigt and Hartmann and attributed to ”dangling ends of the infinite cluster” [94].

6.1 LoPR on the triangular lattice

The calculations for the histogram of site probabilities were performed on N =
40,000 node triangular lattices with free boundary conditions, with one sample
for each value of the average coordination number. In figure 6.1(a), we observe
that as the average coordination of the graph increases the degenerate continuum
decreases for vLoPR. As the average coordination increases, the individual site
probabilities become less random, and more confined to specific values. This is
shown by the strong peak at slightly below P = 0.4, and the less prominent peaks
near P = 0.08, 0.23, 0.42, 0.48. When finding the MIS on a triangle we would
expect each node to appear in the MIS 1 / 3 of the time, so we would expect a peak
at P = 1 / 3, the peak is slightly higher than this value near P = 0.4. As stated in
chapter 4 this value is a result of the algorithm (note: The limiting cover probability
on a triangle, (x) = 0.61803 means that (P) = 1 — 0.61803 = 0.38197.)

For the bond algorithm the degeneracy increases with increasing c. In the re-
sults of bLoPR, there exist peaks in the Prequency(P) at P = 0.35,0.5,0.7. The
behaviour of the number of nodes in the degenerate state, (the degenerate contin-
uum), can be understood from the frozen fraction, (F), as plotted in Figure 6.2(b),
for as (F) decreases the number of nodes in the degenerate state must increase.
From both vLoPR and bLoPR it is observed that as the number of nodes in the
degenerate continuum increases the roughness of Frequency(P) decreases.

The average value of the MIS found from the site and bond algorithms are pre-

sented in Figure6.2(a) along with the average MIS found from the transfer matrix

122

 

3)

'l "‘ LlllllLL
W"

A
‘w..|— V I lllllll

)L

 

Frequency(P)

 

 

 

 

Frequency(P)

 

 

 

Figure 6.1: Distribution of the MIS probabilities Frequency(P) for triangular lattices
with N = 40, 000 sites and with free boundaries at c = 1.0(x), c = 2.0(El), c =
4.0(0) (a) vertex LOPR and (b) bond LOPR.

123

 

 

 

 

 

Efir I I I l I T fiIT I I [I l l I I I I I I I T T—I I q

. .‘ :

A .
0.9} £1. 1
I a“. I

. .\\ .

0.8 f u -
- 0 I

_ 6° \\ _.

0.7 L— ‘a “r
a - -. 2
. 9 “~\ -

V 0.6 - $95 r
_. .666 ““““ ..

: 65. ~~~~~~~~ 1

0.5 g 663% .............. -.
: °ée “““““““

0 4 ; a) 963 g _‘
' b y 6 1

. vegea x 4

" 1:

0.3 l— L 1 1 1 l 1 1 1 l 1 l 1 In 1 1 l l 1 1 1 1 l 51 996%
0 0.2 Pb 0.4 P] Pt0.6 0.8 1

It I ' I I I [I l I I r r f l4 T

31“ AAA...

. 0‘ AA 4

~. A
o — “X AAAAAA

O 8 b 0‘ AAAAAAAAAAAAA AA? ‘
AAAA -1

0.6

<F>
[Iij'lil
o
a
1—0-1
0
*—’-H3
I—o—lE
|-——o—{';
1. .01 pi

0.4 on

I Ir I I I I T T I

 

 

 

0.2 1)) ion :
DD 00 i a :
O 1 1 1 1 l 1 1 1 I1 I 1 I. 1 11] 10°
0 0-2 P1304 91 9.0.6 ‘ 5.58““ ‘1
P

Figure 6.2: (a) The average MIS per site (P) and (b) the frozen fraction of sites
(P) for N=10,000 triangular lattices averaged over 100 configurations. The data
are for site LoPR(A), bond LoPR (El), transfer matrix in (a) (x), the symmetric
Bethe approximation for z=6 (dotted line) and exact results on 64 node lattices (0)
averaged over 10 configurations, vertex LoPR on 64 node lattices (O) and bond
LoPR on 64 node lattices (V) . In this figure, Pb is the connectivity percolation
threshold while PI is the leaf removal threshold, and pt is the triangle removal
threshold.
124

method as prepared by Ji—Wu Liu, another student working with Dr. Duxbury. The
figures contain the results of the symmetric Bethe lattice (z=6) result of Eqs (3.35)-
(3.37), and the exact and LoPR results for N = 64 nodes lattices. The average value
of the MIS was calculated for N = 105 with the MIS averaged over 100 instances.
The exact values on the 64 node lattice, and their corresponding LoPR values, were
carried out with free boundary conditions, and the results were averaged over 10
realizations. We can clearly see that when p < 0.3 the vLoPR and the transfer ma-
trix results are very close, while the bond algorithm is slightly lower than either
vLoPR or the transfer matrix for nearly all values of p. When one compares the
LoPR algorithms on the same lattices as the exact solver (64 node lattices) (solid
circle, solid diamond, solid triangle) we see a similar result, with the LoPR algo-
rithms only at most a few percent different. LOPR is also a significant improvement

over the symmetric Bethe approximation.

The average fraction of frozen sites as calculated on triangular lattices is pre-
sented in Figure6.2(b). Again we have the results of the site, bond, Bethe lattice
and exact results on small lattices along with results for LoPR on N = 10, 000 node
triangular lattices. We can see that as the connectivity increases the frozen fraction
for the site algorithm decreases to a minimum near the bond percolation thresh-
old, then increases over the rest of the connectivity range. This increase mirrors
the decrease in degeneracy that was observed in the histogram of site probabili—
ties for the site algorithm. For the bond algorithm the frozen fraction decreases,
corresponding to the increase in the degeneracy on Figure 6.1(b). In the frozen
fraction, as calculated by the bond algorithm, there are two inflection points. The
first appears near the bond percolation critical point and the second near the core
percolation critical point. It is interesting to observe that while the value of the MIS
found from the LoPR algorithms is quite close, the frozen fraction is not close to

the correct value. This implies that the LoPR algorithms do not fully explore the

125

solution space, yet the algorithms are able to find near optimal states.

6.2 LoPR on the square lattice

The histogram of site probabilities of the square lattice were calculated on N =
40, 000 node lattices with free boundary conditions, with one realization for each
value of average coordination number. In Fig 6.3(a) behaviour similar to the tri-
angular lattice is observed, namely a decrease in the degenerate continuum and
an increase in roughness with an increase in average coordination. The primary
differences are the absence of a peak near P = 0.4, and that Frequency(P) appears
symmetric around P = 0.5. The first of these differences speaks to the lack of tri-
angles and odd numbered loops, and the latter to the bipartite nature of the lattice.

The main structure that is apparent is a slight arch centered around P = 0.5.

In the bond algorithm, Fig 6.3(b) the degenerate continuum increases as the
connectivity increases from c = 1.0 to c = 2.0 and then decreases as the connectiv-
ity increases to c = 4.0, This can be understood by examining the frozen fraction
(F) in Fig 6.4(b). At c = 1.0 there is a high level of roughness that is likely due to
the small number of edges relative to the number of nodes. When there are small
clusters the bLoPR algorithm is able to resolve the small clusters, leading to spikes
in the Frequency(P) related to recurring structures. We can see that as the number
of edges increases the roughness tends to decrease.

Fig 6.4 shows the value of the M15 and the frozen fraction on a square lattice as
calculated by the two LOPR procedures. Results for N = 105 node square lattices
averaged over 100 realizations at each connectivity are presented. The exact and
vLoPR and bLoPR results from N = 64 node square lattices averaged over 10
configurations are also shown, along with the Bethe lattice calculation for z =

4. For most values of p the probability of a site being in the MIS calculated by

126

 

a)

"'l n.- 1111]“
w‘

y—.
u A
vvlll I—lvl I III”

 

Frequency(P)

 

 

 

 

)—
O

b) :3

.—
O
pfn
run-'- w l lvnll

u

 

Frequency(P)

 

 

 

Figure 6.3: Distribution of the MIS probabilities Frequency(P) for square lattices of
N : 40, 000 sites with free boundaries at c=1.0(><), c=2.0(El), c=4.0(o): (a) vertex
LOPR and (b) bond LOPR

127

      
 

 

I I I I I I I I I I I III I I I rI IIITI I

IILIILIIJ_LI

.9
o
I

s
\
\
s
\
s
5
~
§
‘
‘\
~
~
“
‘~
~
‘s
~
~
‘
~
‘
‘-
‘s
‘s
‘s
-
‘s
~~

ITrIIIII

 

 

 

 

 

 

 

0.5 99 ‘12
3) “222322.31
O4 1 1 1 l 1 1 l 111 1 I I l 1 1 1 1 -
'0 02 O4 Pb 061’] 08 l
P

lffiI Ifi I I I I I I I I I I I I I I I I I
:‘h\ i AiAAAAKq

. a A A“ a
0.8” ‘h. EAAAE 00000:
C b} AAAA ODD :

_ Ibfigé‘EAAAAAAAAAf i noun _

_ D ............ a -4
A06: .Douaiua-fi-fii'fi'afl ‘9' """"""""""""""""""" 1
If; C o o o 1
0.4; 5
C i

r- .
0.2? 1
t b) 3
O’- I I I I I I I I J I I III I I I I I L L1+L J -
O 0.2 0.4 Pb 0.6131 0.8 1

P

Figure 6.4: (a) The average MIS per site (P) and (b) the frozen fraction of sites (P)
for N=10,000 square lattices averaged over 100 configurations. The data are for
site LoPR(A), bond LoPR (Cl), transfer matrix in (a) (x), the symmetric Bethe ap-
proximation (dotted line) and exact results on 64 node lattices (a) averaged over 10
configurations, vertex LoPR on 64 node lattices (O) and bond LoPR on 64 node lat-
tices (V). The solid line is the lower bound MIS found through leaf removal. In this
figure, Pb is the connectivity percolation threshold while p, is the core percolation
threshold.
128

both LoPR algorithms are close to the exact values, with the bond algorithm being
slightly lower for smaller values of p and being better at higher values. bLoPR
performs better than vLoPR when p > Mr The Bethe lattice with z = 4 deviates
significantly from the LOPR values.

From the geometry of the problem, we know that once the graph has its full
complement of edges the fraction of independent sites is P = 0.5 exactly, and
the frozen fraction is P = 0. The lattice is bipartite, without disorder and with
sub-lattices of identical cardinality. In this case a maximum independent set may
be constructed from one of the two identical sub-lattices. Each sub-lattice has a
cardinality of N / 2. As such, there are no intersecting solutions and P = 0. We
expect that as p increases the cardinality of the MIS should tend to P = 0.5 and
the frozen fraction should go to 0. We see that the bond algorithm trends toward
the correct answer for the MIS at high connectivity, just as it did on the triangular
lattice.

To find the size of the MIS using core percolation on a bipartite lattice two
things need to be known. The first is that when leaf removal is applied the cor-
rect value for the MIS of the removed parts of the lattice is known. The second
issue is how one finds the lower bound on the core. As such we make the follow-

ing conjectures, about the cardinality of a dilute hypercubic lattice.

1. The MIS of hypercubic lattices without leaves is unfrustrated and equal to

the cardinality of the largest sub-lattice of the graph.

2. The MIS on site or bond diluted hypercubic lattices is frustrated, and this
frustration is due only to the leaves. Leaf removal reduces the graph to those

treatable using conjecture 1.

3. conjectures 1 and 2 imply that asymptotically the exact MIS of a diluted hy-

percubic lattice is equal to the number of leaves removed, plus 1 / 2 the num-

129

ber of vertices in the core.

The MIS should be a monotonically decreasing function for all connectivities, one
cannot add edges and increase the number of independent nodes. Also, on a bi-
partite graph, (P) should never be below (P) = 0.5. The max independent set
is bounded below by the larger of the two sub-lattices. To be fully accurate we
need to consider that the graph is constructed such that it is a loose connection of
bipartite clusters; the MIS on each cluster being the largest sub-lattice of that clus-
ter. Then the MIS is the sum of the IS for each cluster. Using this information we
can construct a lower bound by adding the number of independent nodes found
through leaf removal to one-half the number of nodes in the core. This gives a
lower bound without measuring the size of the sub-lattices, and is expected to be

a good approximation as illustrated by the solid line in Figure 6.4(a).

The frozen fraction as calculated by vLoPR does not go to 0 as p —> 1. (F) for
the site algorithm displays similar behaviour as on the triangular lattice. However,
unlike the triangular lattice the minimum in (F) does not occur near the bond
percolation threshold. The frozen fraction of bLoPR, in contrast to its behaviour
on the triangular lattice, decreases to a minimum near the bond percolation critical
point before increasing. The shape of the frozen fraction as calculated by bLoPR is
similar to that calculated by vLoPR, though with a broader peak. The exact results
for (P) on the N = 64 node lattices is significantly lower than either of the LOPR
results on the same lattices. At the highest value of p on the 64 node exact lattice
we see the frozen fraction go to 0, while large sections of the lattice in the LoPR
algorithms remain frozen. At the maximum connectivity all bonds are present in

the 64 node lattice.

130

 

5
10 ‘1 fl fi‘r 1 l rij 1

a) a
1)

HA
In vllllll

JD-
"'1
I

...
O

 

b.)

Frequency(P)
S

 

 

 

N llllll
O"
v

Frequency(P)

 

 

 

Figure 6.5: Distribution of the MIS probabilities Frequency(P) for FCC lattices of
N=64,000 sites with free boundaries at c=1.0( x ), c=2.0(D), c=4.0(o): (a) vertex LOPR
and (b) bond LOPR.

131

 

1.
i
1

0.8 -

0.4

I I I I

 

 

 

 

l 1 I 1 I II I l I I l l l l I I I I l I I l I l
0'20 9b pipt 0.4 0.6 0.8 1

 

<F>

 

 

1’) ii 1..!“

0411 I III I 141—L1-L111 14_1_1

Pb PlPt 0.4 0.6 0.8 l

 

 

Figure 6.6: (a) The average MIS per site (P) and (b) the frozen fraction of sites (F)
for N=8,000(L=20) FCC lattices averaged over 100 configurations. The data are for
vertex LoPR(A), bond LOPR (El), the symmetric Bethe approximation (dotted line)
and exact results on 64 node lattices (o) averaged over 10 configurations, vertex
LOPR on 64 node lattices (O) and bond LOPR on 64 node lattices (V). In this figure,
Pb is the connectivity percolation threshold while pl is the leaf removal threshold,
and pt is the threshold for triangle removal.

132

6.3 LoPR on the FCC lattice

Not surprisingly, the behaviour of the degenerate continuum on FCC lattices is
similar to its behaviour on the triangular lattice. In Fig 6.5(a) we see that the degen-
erate continuum decreases with increasing connectivity when using vLoPR. This is
also accompanied by an increase in the roughness of the Frequency(P). There also
exists a peak near P = 0.4 that appears only for the FCC and triangular lattices.
The other smaller peaks seen in the triangular lattice are not observed. An exami-
nation of the distribution of site probabilities from the bond algorithm, For bLoPR,
Fig 6.5(b) shows the three peaks related to dangling ends. An increase in the de-
generacy in the Frequency(P), as the connectivity increases, is also observed. On
the FCC lattice the degenerate continuum appears to increase as we traverse the
connectivity from c = 1.0 to c = 2.0, then it appears to level out for c = 4.0. These
calculations were performed on N = 64, 000 node FCC lattices with free boundary
conditions, over one configuration at each value of p.

Fig 6.6(a) shows the fraction of nodes in the MIS for all values of p. Here, the
LoPR results are close to the exact values, the bond LoPR algorithm being slightly
lower. The first deviation of LoPR from the exact solutions appears to be near the
bond percolation critical point, Pb' At higher connectivities the bond based proce-
dure improves its performance, giving the correct answer on fully filled lattices.

(P) for the FCC lattice behaves as it does on the triangular lattice, like the tri-
angular lattice the FCC lattice shows a minimum in (F) for vLoPR near the bond
percolation threshold, 1912- At p z Pb / 2 the frozen fraction from the LoPR algo-
rithms begins to diverge from the frozen fraction on the Bethe lattice. The frozen
fraction calculated by bLoPR shows the first inflection point near Pb- Unlike the
triangular lattice, the second inflection point of the bLoPR frozen fraction point not
appear to be near the leaf removal threshold, p I- These calculations were carried

out on N = 8000 node FCC lattices with free boundary conditions averaged over

133

100 configurations. The exact results are for N = 64 node lattices averaged over 10

configurations.

6.4 LoPR on the simple cubic lattice

On the cubic lattice the degenerate continuum decreases as a function of connec-
tivity for the vLoPR algorithm. There is also a small increase in the roughness of
Frequency(P), as can be seen in Figure 6.7(a). The cubic lattice shows the same
apparent symmetry and slight arch about P = 0.5 that the square lattice shows,
though the arch is narrower on the cubic lattice. In Figure 6.7(b) we see that as the
connectivity increases the degenerate continuum of bLoPR increases for c = 2.0,
then decreases again for c = 4.0. This is mirrored as we expect in the (F), in Figure
6.8(b), since the degenerate continuum is related to the number of frozen nodes.
The calculations were carried out on one configuration of a N = 64, 000 node sim-

ple cubic lattice, with free boundary conditions.

The results for (P) and (F) as shown in Fig 6.8, were calculated for N = 8000
node lattices averaged over 100 realizations, exact, vLoPR and bLoPR calculations
from averages of 10 realizations on N = 64 node lattices and the replica symmetric
solution for z = 6. Examining the results (P) in Fig 6.8(a) one sees the diver-
gence between vLoPR and bLoPR begins near the leaf removal threshold, m. (P)
on the cubic lattice like the square lattice also deviates below the correct value of
(P) = 0.5, and the deviation from the exact value occurs at some point after the leaf
removal threshold. Like the square lattice, the geometry of the lattice tells us that
at high connectivities the covered fraction P1 = 0.5 and the frozen fraction (F) = 0.
The simple cubic lattice also displays the same behaviour in the MIS as compared
to the lower bound on the MIS from leaf removal, deviating significantly at higher

connectivities. The frozen fraction from the bond algorithm on the cubic lattice

134

 

1m; Illll
w"

a)

fin
uvlli

..n—l
I

p—n
O

 

Frequency(P)

 

 

 

 

v
lulu! 11111
“A

1—1

0
I
I

 

 

Frequency(P)

 

 

Figure 6.7: Distribution of the MIS probabilities Frequency(P) for simple cubic lat-
tices of N = 64,000 sites with free boundaries at c=1.0(x), c=2.0(El), c=4.0(o): (a)
vertex LOPR and (b) bond LOPR.

135

 

I I I I I

j.—
=

IILJI

~~~
~~

 

V 7 ~. is---‘ D
a) Raggggfinuuuoaumufiuanqgf? :
A “AAA “MAMAAAIN;

l L L I l 1 L

11 . . 1 . .
P1 0.6 0.8 1
P

 

 

 

"....11111.
0'40 0.21)b

 

find
1
_(
_.
q
l

1l|11

0.9 ‘. i ”Awta‘au‘éfiéé
an

0.8:

0 7 :— EM"33:23“ Ml
' : n “~~~- n
0.6 ' uni ---- °

IIIII
up
D
PD
9
P
H'FH
D
"it
“‘3'
a
D

D
1l|111l111

LL. 0.5;— —_
0.4:— —:
0.3:— —:
0.2 :— —f
0.1 :— b)

0‘111 ll111ll1111l111g1l1111

0 I 0.21%, pI 0.6 0.8 1
P

Figure 6.8: (a) The average MIS per site (P) and (b) the frozen fraction of sites (P)
for N=8,000 (L=20) for the simple cubic lattice averaged over 100 configurations.
The data are for site LoPR(A), bond LoPR (Cl), the symmetric Bethe approximation
(dotted line) and exact results on 64 node lattices (0) averaged over 10 configura-
tions, vertex LOPR on 64 node lattices (O) and bond LOPR on 64 node lattices (V).
The solid line is the lower bound MIS as calculated by leaf removal. In this fig-
ure, Pb is the connectivity percolation threshold while PI is the core percolation
threshold.

 

 

 

136

demonstrates a similar increase near the leaf removal threshold, p 1, although with
a more pronounced cusp. At high connectivities, the bond and vertex algorithm
approach the same value for the frozen fraction. LoPR nearly freezes the entire
lattice at the highest connectivity N = 64 node lattice, where the exact solver gives
a (F) = 0. This implies that with the greater number of solutions and high en—
ergy barriers between solutions, the LOPR has difficulties finding all ground state

configurations.

6.5 LOPR on the random graph

On the random graph we see that as the connectivity increases the degenerate con-
tinuum decreases for the vertex algorithm and increases for the bond algorithm,
Fig 6.9. Examining the results from the vertex algorithm, we observe dips in the
Frequency(P) near P z 0.2,0.4,0.6,0.8. This is likely due to the increase in the
number of loops interfering with the tree like structure of the clusters. The results
from the bond algorithm shows that the roughness which is present at c = 1.0 has
largely disappeared by c = 2.0 and diminishes even more by c = 4.0. The degen-
erate continuum appears to be roughly symmetric about P = 0.5 as on the square
and cubic lattices. This is likely due to the bipartite tree like structure of dilute
random graphs. The calculations were performed on N = 40000 node random
graphs, with one configuration at each connectivity.

Displayed in Figure 6.10 are the results for the probability of a site being on
the MIS and the frozen fraction. Here, we see very good results for the vertex
algorithm and bond algorithm as compared to the exact results. The random graph
is different from the previous lattices since the connectivity range tested never gets
close to ”filling” the lattice as such there are less short range loops in the graph. The

deviation between the replica symmetric solution and the LoPR solutions occur

137

 

a)

"IMIIIILI
w‘

u g A
kul— u l l 111”

 

Frequency(P)

 

. s 1 ,a a .. ~12"? '
, .‘. '. ”-2" u . - ‘0‘ '
u . at". - .0" .1
j I. w flay!»
. . '- 4 ’ v ‘

 

 

 

1))

p—n
A
A
"pl 111111
V U"

 

Frequency(P)

 

 

Figure 6.9: Distribution of the MIS probabilities Frequency(P) for random graphs
of N=40,000 sites at c=1.0( X), c=2.0(El), c=4.0(o): (a) vertex LOPR and (b) bond
LOPR.

138

 

 

 

 

 

 

 

 

l.- I I T I I f1 I I I I I I I I I I I I I r I .4
E" :
0.9 _—'~‘ 1
I -b :
0.8 _— x T
0.7 — 53” .:
6 E a, I
0.6 "_- j
3 1
0.5 — a... j
i N 113 j
i I‘m if“- .
0.4 E ) $81355!
a -
0.3 P 1 J m 1 l 1 1 1 1 l 1 1 1 l 1 l 1 1 1 1 l 1 1 1 1 l 1 1 1 1 d
0 Cb=1 2 C] 3 4 5 6
C
If I I ' l I l T I F I I I I IT I I I I l l I 1 I I l l 1 7 r _
1 ..
3 ‘° 1 1.11;.
.— i A AAAAAAAAAAA
0'8 T . AAAAAAA?AAAA AA A? E T j
. fees. “W i .
b “no - i ___-__.‘
'- D ----------------------------------------- .1
0.6 — 0000 D _
[5) 1 I :
V +- aon I 1
0.4 — an 1
" c1
- ”no i
0000 -
_ Duo “
0.2 — 0000000000 Donal:
. b) i I .
O ’- I I I I I I I I I I I I I I I I I I I I I I J I I I L L I d
0 cb=1 2 c, 3 4 5 6
C

Figure 6.10: (a) The average MIS per site (P) and (b) the frozen fraction of sites (P)
for N=10,000 random graphs averaged over 100 configurations. The data are for
site LoPR(A), bond LoPR (D), the symmetric Bethe approximation (*) and exact
results on 64 node lattices (o) averaged over 10 configurations, vertex LoPR on 64
node lattices (O) and bond LoPR on 64 node lattices (V). In this figure, Pb is the
connectivity percolation threshold while p l is the core percolation threshold.

139

near the leaf removal threshold, CI- The replica symmetric solution is good until
the Cl = e, above the leaf removal threshold we find that both LoPR algorithms

give a better solution.

The LoPR calculated frozen fraction appears to have more in common with the
triangular and FCC lattice than with the square and cubic lattices. This is likely
due to the omission of triangles and odd loops from the square and cubic lattices.
The data does not show the increase in the frozen fraction from the bond LoPR
algorithm that we see in triangular and FCC lattices, at high connectivities. The
random graph displays a similar two inflection point curve in the frozen fraction as
calculated by bLoPR. Similar to the triangle lattice the first inflection point appears
around the bond percolation threshold, Cb and the second after the leaf removal
threshold, CI- The calculations were carried out on N = 10000 node random lattices
averaged over 100 configurations, and the exact results on N = 64 node random

lattices, averaged over 10 configurations.

6.6 Summary

On all lattices we see individual node probabilities are affected by the type of algo-
rithm, the specific geometries of the lattice, and the occurrence of small structures
specifically, dangling ends and triangles. vLoPR appears to be affected by trian-
gles, but not leaves, while bLoPR is affected by leaves. Triangles give rise to a
peak in the order parameter distribution near P z 0.4 for the FCC and triangu-
lar lattices on vLoPR. There also appears to be a small amount of structure in the
Frequency(P) on the cubic and square lattices near P z 0.5, due to small complete
bipartite structures. vLoPR is less sensitive to leaves, but more sensitive to small
loops such as triangles, as the individual probabilities are affected by highly cor-

related sites. bLoPR includes a more complex treatment which is dependent upon

140

the next nearest neighbor.

In the calculation of the probability of a site being in the MIS, the bond LoPR
procedure shows better performance at high connectivities than the vertex algo-
rithm, with both the vertex and the bond algorithm out performing the symmetric
Bethe approximation. On random graphs, LoPR methods yielded values for the
average MIS that are precise for p < pl, where the symmetric Bethe approxima-
tion are expected to be exact [94] and are accurate to within a few percent for p > p l
where replica symmetry breaking is important. The LoPR method provides a good
lower bound on the MIS. In terms of finding the MIS on bipartite graphs, a lower
bound may be found most easily using leaf removal, where the lower bound is
equal to the number of leaves removed, plus 1/ 2 the number of vertices in the
core.

Estimating the frozen fraction is more difficult, as neither the site nor the edge
algorithm provides correct predictions. The site algorithm consistently over es-
timates the frozen fraction, while the bond algorithm generally underestimates
the frozen fraction. The exception to this being at high connectivity on bipartite

graphs, where both algorithms freeze more nodes than the exact solution.

141

Chapter 7

Conclusion

7.1 Conclusion

In this thesis, we have examined the ground state of the geometrically frustrated
hard-core lattice gas. Geometrical frustration on diluted lattices leads to glassy
behaviour. On bipartite lattices, the hard-core lattice gas maps to the diluted anti-
ferromagnet in a field. Finding the ground state of the hard-core lattice gas is
difficult and has been found to map to the computationally difficult class of prob-
lems known as NP-complete. In order to model the ground state we reduced the
complexity of the lattice by removing small cliques, such as leaves and triangles.
Further, we found that a local heuristic can model the density of the ground state,

and reproduce the non-trivial order-parameter distribution.

We have examined the percolative properties of leaf and triangle removal. Both
leaf-removal and triangle removal run in polynomial time. Similar methods for
larger cliques would exist, though they would eventually become prohibitively
difficult to solve, because clique is also NP-complete. For core percolation, there
exists a series of transitions, for each order of clique removed, that appear to co-

alesce as the dimensionality grows. The results of core percolation in Chapter 5

142

show that triangle and leaf removal are in the same universality class as standard
percolation. Nevertheless, several exponents showed deviation from the standard
values, but these compared favorably to bond percolation calculations made on

similar lattices (see appendix A).

The LoPR algorithm was shown to be robust, providing near extremal values
for the Vertex Cover. The algorithms run very quickly by limiting the number
of times the order of iteration is randomized. The bond algorithm generally out
performed site LoPR. Larger numbers of nodes were frozen by the site algorithm.
Neither algorithm correctly captured the frozen fraction. This means that the al-
gorithm is able to find near optimal solutions, but does not explore the complete
solution space. This doesn’t appear to have a major effect on results of the MIS as
the correct solution appears to be found over 50 percent of the time, after a distinct
instance is generated for the N = 100 triangular lattice tested. Both the site and
bond algorithms out perform the replica symmetric solution. In general, the LoPR
family of algorithms provide a quick method to get the ground state of MIS/VC

within a few percent.

7.2 Further Work

One of the things that needs to be done in the future, is to continue the analysis of
core percolation by studying in more detail the effects of the boundary conditions
on the critical exponents. This .would be particularly useful for the three dimen-
sional lattices. Larger sample sizes for the lattices already studied may be come
accessible as computer speed increases. This would allow greater examination of
the critical exponents affected by finite size effects, particularly B.

The analytic evaluation of the bond-LOPR method needs to be examined in still

greater detail to determine if a generalized equation can be written to describe

143

higher moments. Analytic work on the LoPR algorithms might also provide rigor-
ous lower bounds on MIS.

There are several possible extensions to LOPR; the algorithms could be tested
on different lattices. Perhaps a hybrid algorithm joining site and bond LoPR might
have a better approximation to the frozen fraction and find the correct probabili-
ties on a triangle. An algorithm built on finding the correct probability of triangles,
might provide interesting results. We might try constraining the covered fraction
in the LoPR algorithms. This might allow us to more fully explore the solution
space, by comparing the frozen nodes over a number of similar solutions. Site-
LoPR with a single randomized node list runs quickly and could be used to gen-
erate a ”solution”. We could then flip the probabilities and converge to a second
solution, which could be continued until a ”best” solution is found. This would
likely increase the probability of finding a true minimum. This might also be used
to explore the free energy landscape of the LOPR algorithms.

It would be interesting to examine the behaviour of core percolation and the

LoPR method on scale free random graphs, and small world graphs.

144

APPENDICES

145

Appendix A

Percolation

A.1 Introduction

Percolation is a process where nodes in a lattice are joined randomly. This is a
growth process by which elements of a graph (such as edges or nodes) are placed
into a lattice with some probability p. In bond percolation, the probability, p, is a
function of the average coordination of a site, c, and in the case of a regular lattice,
the coordination of the lattice, 2,

C

The average coordination can be calculated by,
c = —, (A.2)

where, E is the number of edges in the lattice, and N is the number of nodes in the

lattice.

At any concentration there will be a finite probability that the largest cluster

146

will span the sample, P5. For an infinite sample, the probability,

0 p < pc
P307) = (A-3)
1 P 2 Po

9

For finite systems there is a transition region between 0 and 1.
We can also define a probability that a node is on the spanning cluster, Poo, the

infinite cluster probability.

A.2 The infinite cluster on the Bethe lattice

Here we will approximate the infinite cluster near the transition point using a
Bethe lattice. The Bethe lattice has a connections to each subsequent layer, and
the total coordination of each level is z = a + 1. Each bond occurs with probability
p and is absent with probability (1 — p) Then we can write the probability, Pk+1

that a site at level k+1, is connected to the boundary as,

a

Pk+1 =1; (,) (pPk>’(1 — paw-P (A.4)

Where, pPk is the probability that the kth level is node is connected to the boundary
and the bond to the k+1 level is present (with the zeroth level being the boundary).
As the size of the lattice goes toward infinity, the probability converges to a steady

state value that we will call, P.

P = f (“)( P)’(1— P)“" (A5)

121 l p p I .

= 1—(1—pP)“, (A.6)
_ apP 0t

- 1—( ‘7) ‘ (A7)

(A8)

147

If we take the limit of a as it goes to infinity,

P = .tm..(1-( 1%)“), M
= 1—exp(—rxpP). (A.10)

Then if we make an expansion of the exponential to ,

 

 

(0:17P)2 _ WP? +

2' 3' ..., (A.11)

exp(—apP) = 1 — apP +

taking the first three terms and substituting them into our probability, we have,

P=1—1+acpP—Q£%1!12 (A.12)
= P(ap — 9’23), (A.13)
This leads to,
1 2 up — (jig—23. (A.14)
Which has the solution,
p = —( — bi? (A.15)

Thus the probability of a node being on the infinite cluster scales as,
P... o< (p — pat, (ms)

with pc 2 %, and B = 1 for the Bethe lattice.

148

A.3 Mean cluster size

Besides the infinite lattice probability, Poo( p) there are three other quantities of
interest; PS( p), the spanning probability, ns(p), the normalized cluster number,
and (S) the mean cluster size. The normalized cluster distribution is defined as
the number of size 5 clusters per lattice site. This leads to the definition of the

mean cluster size as;

2
<5) = E £5585. (A.17)

 

A.4 Finite-size scaling in percolation

Making the finite size scaling ansatz, we may say that any property of the graph
x(p, L) scales as,

m. L) = (p — pc)—XX((p — pew/V). (A18)

We use finite size scaling to relate the behaviour at the critical point infinite
samples to the behaviour of finite samples [23]. Some scaling relations that we

have used in this dissertation are [84] [12],

"5(PC) °< 8"Tfn(5"(p-pc))L—>°°, (A19)
(5) o< P-P-C_7fa((P-Pc)L1/V)r (A20)
P006012) o< L“fi/V/oo(L1/V(p—pc)) (A21)
MAL) o< fs(L‘1/"(p-Pc)), (A22)
A o< LUV, (A.23)

Poo °< (P—Pclfi, (A24)
(A25)

149

where A is the width of the transition in P3,
A2 = (192) - <p>2- (A26)

A simple power law gives a straight line on a log-log plot, but for some cor-
related percolation processes, like rigidity percolation [66], we need to examine a

next to leading order correction of the form.
x(pc, L) = C1L‘3(1 + ch—w) (A27)

The scaling functions f5, foo, fn, fa include the finite size scaling behaviors and
enable determination of B, U, and '7. Eq. (A.19) also gives the scaling behaviour in
the infinite lattice limit at pc and will enable determination of 1'. Only two of the
exponents are independent, as such a check can be provided by various exponent

relations.

 

=§:::,a+2B+7=2,dv=2—xx, (A28)

where d is the dimension.

A.5 Bond percolation on regular lattices with free

boundary conditions

Table A.1: Standard Percolation Exponents
exponent d=2 sq triangular d=3 cubic FCC
v 4/ 3 135(1) 137(3) 0.88 093(4) 092(2)
'7 43/ 18 226(7) 228(7) 1.8 1.7(1) 1.76(8)
T 187/ 91 206(1) 208(2) 2.18 224(1) 224(2)

 

 

 

 

 

 

 

 

 

 

 

 

 

Here we present bond percolation values calculated for simulations run under

similar conditions to those in Chapter 5. The accepted values of standard percola-

150

Table A.2: Comparison of Percolation Exponents

 

 

 

 

 

 

 

 

 

 

 

 

Vb VI Vt

Sq. 135(1) 139(1) —
Tri. 137(3) 137(1) 133(6)

Cubic 093(4) 100(5) -
FCC 092(2) 0.982(5) 092(2)

’71; ’Yz ”rt

Sq. 226(7) 219(3) —
Tri. 228(7) 216(3) 213(6)

Cubic 1.7(1) 1.7(2) —
FCC 1.76(8) 1.74(2) 161(3)

Tb T I T!

Sq. 206(1) 207(2) —
Tri. 208(2) 209(5) 198(8)

Cubic 224(1) 223(6) -
FCC 224(2) 2.17(8) 207(8)

 

tion, may be easily looked up in any number of books, including ”Introduction to
percolation theory” by Dietrich Stauffer and Amnon Aharony. The primary reason
for doing these calculations was to examine the critical exponents v, T, and ’y, of

the 3-d lattices for free boundary conditions.

Figure A.1 provides an unbiased estimate of the exponent v by using, 5p? =
(p?) — (pg)2 ~ L‘z/V. The results are recorded in Table A.2. The value of u
measured for the 2-d lattices is consistent with the standard percolation value and
the leaf removal values. The values of u calculated for the 3-d lattices are between
the standard values and the leaf removal values. The values are very close to the

value of 11 found for triangle removal.

In Figure A.3 we calculated the exponent "y from the average cluster size, S, on
approach to pc from below. The value of 7 calculated in the 3-d cases are consis-
tent with the standard percolation value of 7 = 1.8 (d = 3). In 2-d, he standard
percolation value of ’y = 2.38 is higher than the values measured 73" = 226(7)
and 'l’tri = 227(7). The values measured here fall between the standard value and

the core percolation values. The values for "y are strongly affected by finite size

151

effects, as the slope is dependent upon the transition point which in finite samples
is a function of the size of the samples.

Figs. A.4 and A.5 show the plots of us Ld verses 3 used to calculated T For
the 3-dimensional lattices we measure a T 2 224(2) for bond percolation, which
is consistent with the leaf removal values of T = 2.17(8) for the FCC and T =
223(6) for the simple cubic lattice. This suggests that the value we calculated for
leaf removal is consistent with standard percolation. The value of T for triangle
removal on the FCC lattice is lower than both the standard quoted value and the
value calculated here, it is however consistent with the standard value. The 2-d
values are consistent with the leaf removal values.

After examining the critical exponents obtained by the same methods as used
in the core percolation calculations, we can see that the values are similar. Any
discrepancies between the standard values and the values measured here, and in
core percolation, can be explained through finite-size effects and the results of the

boundary conditions.

152

 

 

 

 

)- I I I I I I I I I I I I I I I I I T I I I I I I d
_ x‘ q
v ‘ ‘\‘8 ‘A‘..'
" \\\ ‘ \+-. "
‘~x A‘-
x +
-2 1“ A _
_ ". ~x x. -- .(
' \s ‘.
00 _ v . ._'+.. -
_ ~ '~. . '4!“ -
x\\‘\ “\_..
' ‘x‘ ‘ .j ‘
‘ ‘ ' A, '+-.
'- ‘\_ ‘8 “‘ -
.v.‘
-3 . 5".
- _ v. '—
10 I. I I I I I I I I I I I I I I I I I I I I I I I I -
l 2 3
10 10 10

Figure A.1: Plots of 61212 = (p2) — (p)2 as a function of lattice size L on a double
logarithmic graph. The A are data from the triangular lattice, the dashed line is a
best fit from which we extract the estimate 11 2 135(1). The + are data from the
square lattice from which we extract the estimate 11 2 137(3). The V are data from
the FCC from which we extract the estimate u = 092(2). The x are data from the
cubic lattice from which we extract v 2 093(4).

153

 

I F I T I I I I l I I I I I I I j T I I I I I

 

 

 

: I
05 -_...._..,++++ ............. + .................... + ............................. + .......................... 1
0.4 _— -:

"-A-AA-A ------------------ :
«>3 A A ------ A- ____________________________ .
w 0.3 — .......... I
Q I
: “x ...... x ...... x- -.-.-.x ................. x . ................. -l
0.2 L .-.-._._.-._.-._.-.-.-.-.__i
“...? .......................
O l :- V V v .................. v. ............................................ —“‘
: 1
O L 1 l 1 l 1 1 I 4 1 l L 1 ‘ 7
0 0.01 0 02 0.03 0 04 0 05
5pc

Figure A.2: Plots of the average value of PI as a function of 617,, for each sample
size we find Pl (L) and (5p, (L). (5)91 goes to 0 as L goes to co. This allows us to extract
the infinite lattice critical point.

154

 

10 1¥\r..'1 11111] 1 1 111111] T
\'.

I IIIIII

I

104

I I IIIIIII

103

IjIIIIIII I I)‘IIIIID I II
D 0

+1 I IIIIII

<S>

102

I IIIII

Ti I IIIIII

101

 

I I I IIIII

 

 

 

0 1 L 1 1 1 111l 1 1 1 1 1 111l..\- 1
10 - - _
103 102 101

Ip-pcl

 

Figure A.3: Plots of the average cluster size on approach to P1 from below for
lattices of size N = 10, 240, 000 sites, from this plot we extract the exponent ’7. The
A correspond to the triangular lattice yielding 'y = 228(7). The + correspond
to the square lattice yielding "y 2 226(7). The V correspond to the FCC lattice
yielding '7 = 1.76(8). The x correspond to the cubic lattice yielding 'y = 1.7(1).

155

 

10-‘ 1 1 lllllll T Ifrrllll 1 I lllIllI

IIIII l I lIlIIIl I I IIIIIII I I IIIIII

IIIIIIII I I IIIIIII I I IIIII'II l l I

l

I IIIIIIIJ I lIlIIIlI

V

L I IIIIIIl l I lllllll I llIIIIIl

100 101 10 103

fl
0
'I

III

 

 

 

 

‘I I IIIIIII I llllllII I IIIIIIII

3
)—1
O
.p
'l
lllLLLlILJ 1111111l 11111111l 111

I I IIIIIIl

 

 

10 ;— l I I I IALII I :I
100 101 102 103
S

 

Figure A.4: plots of the cluster size distribution for lattices of N = 8, 000, 000 sites.
(a) The FCC lattice yields T = 224(2). (b) The cubic lattice yields T 2 224(1).

156

 

l I IIIIIIT l I IIII'II I I‘I’IIIIII

III

. lIlIllll 4IIIIIIII lIlllllll llIIIIlII l llIIIlIl I II

\

 

)—1
O
IIII'I I lllllllI I IIIIIIII I lllllll' I IllllIll IIIIIIIII l llJ

I IIIIlIl I IIIIILII I I IIIIIII

m‘ m2 m

 

 

3

...
O
o

 

.4
.(
.4
—(
_.

[III I lllllllI l llIIIlII I IIIIIIII l lIlIIllI I II

 

   

 

”"l l lllllllI I lIlIIlIl I IIIIIIII I lllllllI l lllllllI I II

Figure A.5: plots of the cluster size distribution for lattices of N 2 10,240,000
sites. (a) The triangular lattice yields 1’ 2 208(2). (b) The square lattice yields
r=2%u)

157

Appendix B

Replica Symmetric Calculations

This appendix contains an expansion of the math done in Sherrington’s and Kirk-
patrick’s paper titled ”Solvable Model of a Spin-Glass” [83] and the application of
the replica method to the lattice gas [94].

B.1 Replica Method on the Ising Spin Glass [83]

We start with the Ising Model Hamiltonian with zero field, the system has N Ising

spins, S,- = i1,
% )2 [ii-sis) (3.1)
1'70

At this point we make u replica’s of the partition Function, which we denote with

the label a,

NITD

: ZeXP( E Elijsasa)‘ (8'2)
Sf“ iyéj 0‘

The average over the disorder for Z n is,

(2") = / P(Iij)Z"d]l-j. (3.3)

158

We need the average value of the replicated Partition function in order to utilize

the replica trick,
_ . <2") - 1
(1n Z) — 111% n . (3.4)
The form for the Probability density P ( I,- j) for a specific [if is a Gaussian,
_ 1 (Iij -10)2
1301]) — mam—T)- (35)
With the Product of the probability densities for all unique (ij) pairs giving,
2
.. = ; (n(n—1)/2) _ M
P(I,,) ( 1727:) exp( 1% 2], ), (3.6)
2
: 1 (n(n—1)/2) (Iij‘ [0)
(———N2—n) exp(— 2 1;,- _212 ). (37)
Combining (B.2),(B.3) and (8.7) we get,
[2
(2") = (17—) ‘2‘ :fznexp( (——%)
Sf‘ 11
[3
exp (4];2 —- —— +(— 231,154+ 2]?__2)]ij)d]ii. (3.8)
and using the Gaussian identity,
°° 2 b d — ” b2 B 9
[_mexm—ax + x) x — 5 exp(4—a-). ( . )

we can evaluate (Z ") to get our replicated partition function, and the free energy

now looks like,

 

12
(2")- — =EHIex p(4 (kT)2(s “51.) )2+-2——k0T£sf‘s¢)I. (13.10)

S‘?‘ 1]

159

Now, rearrange the sums in the exponential,

2(2) 5“5“)2 — 2 2 (25951- Sp); + Nzn — an. (3.11)
2'21

After this the partition function becomes,

 

 

 

(1.1)]2N2 (”,2 2N ION"
ZR: Wsl xp(l 4(kT)2 (4(kT)2 ( 2kT )
(20602 “11:30.15? (2_I_k0T )(ZsaflH. (3.12)

The terms with N are dropped because they vanish in the thermodynamic limit to

leave our partition function as,

2. = 6.023.212 M .222? )

5‘?‘ “<5

IJexp (%(ES?)2 )I. (B.13)

 

 

Which is the result arrived at by Sherrington and Kirkpatrick. Decompose this
using Eq. (B. 9), where for the yafi integralI a — N / 2 and b2: —kL21%IZ(E,I 80‘8"; )2,

and for the xa integral, a— — N / 2 and b2: ( k1") £0351 S“)2, to get,

2. Mai—.32 29/ [Hf—21%.] / [0921/72]

“(5
lyz j"
(exp(—N ; ¥+ +;. 2 2,3538%...)
2 l3
2 ..
+exp(—Nzx—2“— +(%)1::E)jsf‘x.)). (3.14)
a a i

160

Where i = I N 1/ 2, f0 = ION. At this point we choose to solve for the replica
symmetric solution, which means setting all ya); ——> y and xa —-> x. Now we make

the statement,

“2N N
ZR : 8Xp( all(TTTnZH _I:7I;)dl/2dy]/[1;I(§7—i)1/2
__ 2
dx] exp (— N<£17m— + n—:—-)) (Z?)N. (B.15)

Where 25’ is equal to,

a<B

_ )2_ _I_y" _0
_ SZ‘xexp (T168251!) 2kT+ +(/:S x.) (8.16)

Then we use the Gaussian trick to decompose the this once again, to get,

2'11 = gexp (kT z SaSfly-l- I—O T25“ x),
25“
a

Z" _ 9XP(\/2__7§i71:—¥=)/exp(_2 22)

H<Eexp(( ((I/gz + 2I/kT—gx)Es s“)dz.) (3.17)

Now we can finally sum over S“ = :tl, this makes Z? now,

Iyn - - n
_ ex10(7):) 22 M Io
Z? — T fexp(——2—) 2COSh ( 'k—T'Z + EX) dz. (3.18)

161

Insert this into our Replicated Partition function and get,

 

_ I: 1/2d1/2 _IyN"
z. _ flgqpu y][/ [11(23 7.) dx]exp( ’(k——T—)2)exp( 2k.)
exp(-— N(M+ L?) ))+exp Nln(27r) “2

 

fdzexp(zz2 —— (2cosh (:Ez+ I/zigx) [1.] (8.19)

Now, evaluate the integrals over x and y by the method of steepest descent. But

~

first let us define y —+ (&)q and x ——> m(%%)1/2 this gives,

=f[H(2n)1/2(k_l;_2_)2dq][[1:1(51%QT.)1/2dm
2 ,, f2
exp(—<.’.%<1-(>++’—-—3.:m>>ex)pi.( ”’3 2(2)

+ex Nln 1/2/ j—ql “2 I—O— n
p (2n) dze '2' 2cosh(k qu z+k m) (B.20)

 

. . _ (Nf
F = —kT11mOn 1[/[p(Nn)1/2—(——k:)2dq (dug/FR2 —k—n9r)1/2dm]

 

 

03
szn 2 12an 2
8XP(-<.(k.)2<1—q> +— 3k?“ .2)pr(4(” )
z2
+exp [Nln(27r)_1/2/dzexp(——2—)
(2C05h(klfq1/ZZ-l- +15%,” )) nI—l]. (B21)

162

Now we do the integrals by the method of steepest descent to get the coupled

 

 

equations,
I
N ” amz"
——2—(E’f)2(1—q)+N Bql = 0, (3.22)
b amzf
—N(fi_)m+N am = 0. (3.23)
where we define,
Z", = (2n)—1/2/dzex (——ZE) 2cosh(] 1/22 +1—0m)n (B 24)
1 p 2 H" +kT ' '

Then

 

q = 1 — 712—7:fdzexp(—zz/2)sech2(k—Lqu/ZZ—F +10 m) (3.25)

 

 

kT
m = _I_/dzexp(—zz/2)tanh -]—q1/2z+ I—Om (B.26)
v27: kT +ka
The free energy becomes,
_ _ _ flN _ 2_Efl[2
F _ kT[ 4(kT)2(1 ‘0 2kTm )
+N1n(27t)-1/2/dzexp(—zz/2)
I uzz +h
2cosh(k—Tq +kT m.) (3.27)
and the entropy is,
2 _ _ 1212. F _ _ 22
_1/2 1
+k(27r) [dz exp(——§)1n(2cosh Z). (8.28)

163

The entropy W111 be nonphysical when T -—> O H O m = 0

We define an indicator function

B 2 Replica solution to the lattice gas [94]

x= H< (1 _yiyj) (3.29)
(if)
and a partition functlon
E = Z Xexpwzyil- (8'30)
yi=0 1
The average density at a srte 18

_1a_::

Usmg the ident1ty

[Illl >-‘

(8.31)
-— —limn_,OE

n— 1

[I] l
r.

we shall find the average value of p, by averaging Eq (B 31) usmg (B 32) The
average replicated partition function IS given by,

(3.32)
= 2 exp (qu?)(H[(1N— — )+fiH(1 —y”
yf=0,1 1,11 iyéj a
where a — 1 ' '
exponentiate to find

(3.33)

1 )
n 18 the repllca index. Since we are interested in c
. I
an

' z 1, we can
2 8XP(1¢Zy§-’ - (cN/2)+
yfzog i,a

()c/N )2 “(I — yfyj))
iaéf“

(13.34)
164

Now introduce the variable,

- 1 N
x(y) = if .2 Hay”. (13.35)

with
):x(9) = 1. (8.36)

Notice that we have defined a special notation for 37, = {y},.. .y“,. ..,yi ".} It is a
vector of replicated variables at a single site and thus has 11 components, each of
which can take on the values 0 or 1. The order parameter x(_17) is the fraction of
sites which are in configuration 9’. It is a functional order parameter as each of the
2" components of x can take on a continuum of values between 0 and 1. Using this

order parameter we rewrite the partition function as,

‘51—": f0 yaH dx(y “)(exp —NF[x(37)]). (3.37)

where

+ Ex(y)1nx(g‘) + A(E x117) — 1). (8.38)

9' .17
In this expression y’ - T = 22:1 y“. Eq. (8.38) includes the combinatorial factor
N! / Hy[x(37) N ]! due to the permutations of x(g’). We now use the method of steep-

est descents with x(g') being our set of continuous variables. We have,

3%:-#9’-T—c2x(i’)H(1—y“y“')+1nx(g')+1+x=0 (3.39)

.1/

165

The symmetric ansatz assumes that x is invariant under permutations of the com-

ponents of 9'. This implies that

N

x(.17) -+ x( E y”) (1340)

a=1

It is useful to define the exponential transform,

 

8° e 301 EN_ y“)
x 3 = dh h “-1 3.41
(y) L... ( > (1 +213 < >
which ensures that the constraint (8.36) holds, provided,
00
/ g(h)dh = 1. (3.42)
—00

Within the symmetric assumption, the average density p is the same for all replicas,

so we have,
ex h
p=Hy1=ZX(yw=y1 f: thIg )1+——E-—x(p2h-) (8.43)
Defining s = )2“ y“ and rearranging equation (8.39) yields,
_. I
x(9') = eXPl-A - 1 + 38 + c 2366’) H(1 -— yay“ )] (3.44)
" I
y,

Using Eq. (8.41), we have,

 

/dh8(h)(1:xg;(l:1(sz))n = exp [—A+1+ys+c/dh'g(h’)

exp (—sln (1 + exp(h')) >] (8.45)

The only puzzling piece of this expression is the last term in the exponential on the

RHS. To see how this arises start with the last term on the RHS of Eq. (8.44) (the

166

one proportional to c),

 

I I) exp( (5,7, I)
gfdh 801) (1 ())+exp(h’ '1 H0 ya’)

 

__ —/dh’g(h) )(1+ex1p(h’))"n 2 exp(h’ya)(1—yaya) (8.46)
a’ ya’ =,01

Each term in the product can be summed to give 1 + (1 — y“ )ehl. This term is one

if y“ = 1, and it is 1 + eh, if y” = 0. Using this information, Eq. (8.46) reduces to,

 

_ I I (1+9XP(h’))n—S
—/dh g(h) (1+exp(h’))" , (3.47)

which is the same as the last term in the exponential on the RHS of Eq. (8.45). Now

we take the limit 11 —+ 0 to find,
/ dhg(h)eh8 = exp[—/\ + 1 + 1s + c / dh’g(h') exp(—sln(1 + exp(h’)))1)1 (3.43)
Note that ifs = O, we must have, c — A + 1 = O, which implies that,
A = c + 1 (8.49)

It is useful to make the following changes of variable,

k=h/y ; 02514 (8.50)
We then have,
11 [0” dkg(ky) exp(kv) = exp(v — c + cz(v)) (3.51)
where
v) = 2 / dk’g(k’2)exp<—-;§ln11 +exp(k’2>1> (3.52)

167

”H.411

E
2

m“ ;__

 

Now note that in the limit 14 —+ 00 we have,
5m + exp(k’m —» k’9<k’) (3.53)
This implies that,

z(v) —> y/_: dk’g(k’y)exp(—k’v9(k’)) =

°° I I I 0+ I I
11 [0+ dk g(k y)exp(—k v) + 14 /_oo dk g(k 11). (8.54)

Now we assume that,

00

g(k2)=;1,- )2 gm6(k+m). (8.55)

m=—1

Substituting into Eq. (8.51) (and using Eq. (8.54)) we have,

)2 gm8Xp(-mv)=exp(v-c+c[g_18XP(-v)+go+ 2: M) (356)

From the normalization condition on g(h) (Eq. (8.42)), we obtain,

00 00
[.00 g(h)dh = 1 =2 g_1 + g0 + )3 gm = 1 (3.57)

m=1

Using this result and expanding the g_1 term on the RHS of Eq. (8.56) yields,

if (cg_1)’ exp((1 — 0v)

 

XI gmexp(-mv) = exp(—cg_1)

 

I ' (8.58)
In=—J 1:0 '
To ensure that this equation holds, we need to have,
(Cg—1 )"1+1
gm = exp(—€34) (m + 1)! (B59)

168

Once we know g_1 then all of the other gm are found from it. The equation for
8—1 is,
g_1 = exp(—cg_1). (8.60)

We define W(c) = cg_1, so we have,
C = Wexp(W). (8.61)

This is the definition of the Lambert function. We can now find the average density
on each site of the lattice. The density is given by (see Eq. (8.43))

1 8° exp(ku)
= — dk k
p 14 [0 g( 3)
00 0°

 

1 + exp(ku)’

_ eXP(k#)
- [0 dk E gm6(k+m)1+exp(ky),

 

1 1
) + 580 _.. 8—1 + 82-802 (362)

where the last expression on the RHS applies as we are interested in the limit 14 —>
00. From Eq. (8.59), we have,

W2

30 = 8XP(—cg—1)cg_1 = C(g_1)2 = 73—. (3.63)

The density of the vertex cover is xc = 1 — p which is ,

_2w+w2

22 (8.64)

xc=1

There is more information in the solution above, than just the average cover. Since
the maximum independent set, or the repulsive lattice gas, on random graphs is
highly degenerate, we may define three types of sites: Those that are always un-

covered (fraction pu); those that are always covered (the backbone, fraction pb)

169

and those that are sometimes covered (pg, these contribute to the entropy). That is,
for a given random graph, all of the degeneracy occurs due to rearrangements of
the atoms on the sites with volume fraction (pg). The quantities pu, Pb and pe are
related to the solution we have found in the following way:

- The fraction which is always covered, Pb = g_1 = W/c.

- The fraction which is sometimes covered, pg 2 80 = W2 / c.

- The fraction which is never covered, pu = 1 — Pb — pa = 1 — (W + W2) /c.

170

BIBLIOGRAPHY

171

Bibliography

[1] DJ. Amit, H. Gutfreund, and H. Sompolinsky. Spin-glass models of neural
networks. Physical Review A, 32:1007—1008, 1985.

[2] Wolfgang Barthel and Alexander K. Hartmann. Clustering analysis of
the ground-state structure of the vertex-cover problem. Physical Review E,
70:066120, 2004.

[3] Sorin Bastea and Philip M. Duxbury. Ground state structure of random mag-
nets. Physical Review E, 58:4261, 1998.

[4] M. Bauer and O. Golinelli. Core percolation in random graphs: a critical phe-
nomena analysis. Euro. Phys. jour. B, 24:339-352, 2002.

[5] M. Bauer and O. Golinelli. Random incidence matrices: moments of the spec-
tral density. Euro. Phys. jour. B, 24:339—352, 2002.

[6] Béla Bollobas. The evolution of random graphs. Transactions of the American
Mathematical Society, 286(1):257—274, November 1984.

[7] J. P. Bouchard and M. Mézard. Self induced quenched disorder: a model for
the glass transistion. journal of Physique I, 4:1109, 1994.

[8] Anton Bovier and Pierre Picco, editors. Mathematical Aspects of Spin Glasses
and Neural Networks, volume 41 of Progress in Probability. Birkhauser, 1998.

[9] A.]. Bray and MA. Moore. Metastable states in spin glasses. journal of Physics
C, 13:L469—L476, 1980.

[10] Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, and David Liben-
Nowell. Tetris is hard, even to approximate. International journal of Computa-
tional Geometry and Applications, 14(1-2):41—68, 2004.

[11] Joseph D. Bryngelson and Peter G. Wolynes. Spin glasses and the statistical
mechanics of protein folding. Proceedings of the National Academy of Sciences of
the United States of America, 84(21):7524—7528, Nov 1987.

[12] j. Chayes. Finite-size scaling in percolation. Documenta Mathematica, Extra
Volume ICM III:113—122, 1998.

172

[13] Debashish Chowdhury. Spin glasses and other frustrated systems. Princeton
university press, 1986.

[14] Stephen A. Cook. The complexity of theorem-proving procedures. In STOC
’71: Proceedings of the third annual ACM symposium on Theory of computing,
pages 151—158, New York, NY, USA, 1971. ACM Press.

[15] L. Correale, M. Loeone, A. Pagnani, M. Weigt, and R. Zecchina. Core perco-
lation and onset of complexity in boolean networks. Physical Review Letters,
95:018101, 2006.

[16] ].R.L. de Almida and D. J. Thouless. Stability of the sherrington-kirkpatrick
solution of a spin glass model. journal of Physics A, 11(5):983—990, 1978.

[17] Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell. Tetris is
hard, even to approximate. In COCOON, pages 351—363, 2003.

[18] G. Deutscher, R. Zallen, and Joan Adler, editors. Percolation Structures and
Processes: Annals of the Isreal Physical Society. Adam Hilger and The Isreal
Physical Society, 1983.

[19] SF. Edwards and PW. Anderson. Theory of spin glasses. journal of Physics E,
5:965—974, May 1975.

[20] P. Erdos and A. Rényi. On the evolution of random graphs. Publ. Math. Inst.
Hungar. Acad. Sci, 5:17—61, 1961.

[21] Shirnon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and
multicommodity flow problems. SIAM j. Comput., 5(4):691-703, 1976.

[22] K.H. Fischer and ].A. Hertz. Spin glasses. Cambridge University Press, 1991.

[23] Michael E. Fisher and Michael N. Barber. Scaling theory for finite-size effects
in the critical region. Physical Review Letters, 28(23):1516—1519,]une 1972.

[24] Aviezri S. Fraenkel. Protein folding, spin glass and computational complexity.
In Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, held at the
University of Pennsylvania, june 23 — 25, 1997, pages 175—191, 1997.

[25] S. Franz, M. Mézard, F. Ricci-Tersenghi, M. Weigt, and R. Zecchina. A ferro-
magnet with a glass transition. European Physics Letters, 55:465, 2001.

[26] Y.T. Fu and PW. Anderson. Application of statistical mechanics to np-
complete problems in combinatorial optimization. journal of Physics A,
19:1605—1620, 1986.

[27] E. Gardner. The space on interactions in neural network models. journal of
Physics A, 21:257—270, 1988.

173

'~_‘. —‘.-.

 

g

 

[28] E. Gardner and B. Derrida. Optimal storage properties of neural network
models. journal of Physics A, 21:271-284, 1988.

[29] Michael R. Carey and David S. Johnson. Computers and Intractability: A Guide
to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

[30] A. Glaser, A. C. Jones, and P. M. Duxbury. Domain states in the zero—
temperature diluted antiferromagnet in an applied field. Physical Review B
(Condensed Matter and Materials Physics), 71(17):174423, 2005.

[31] Richard A. Goldstein, Zaida A. Luthey-Schulten, and Peter G. Wolynes. Op-
timal protein-folding codes from spin-glass theory. Proceedings of the National
Academy of Sciences of the United States of America, 89(11):4918—4922, June 1992.

[32] Uwe Gropengiesser and Dietrich Stauffer. Limited universality at the perco-
lation threshold in 2 to 6 dimensions. Physica A, 210:320—325, 1994.

[33] Alexander K. Hartmann and Martin Weight. Statistical mechanics perspec-
tive on the phase transition in vertex covering of finite-connectivity random
graphs. Theo. Comp. Sci, 265:199, 2001.

[34] Alexander K. Hartmann and Martin Weigt. Statistical mechanics of the vertex-
cover problem. MATH.GEN., 36:11069, 2003.

[35] J]. Hopfield. Neural networks and physical systems with emergent collective
computational abilities. Proc. National Academy of Science USA, 79:2554—2558,
1982.

[36] DE. Moneton P.W. Stephens R.J. Bergeneau P.M. Horn and GS. Brown.
Synchrotron x-ray study of the commensurate-incommensurate transition of
monolayer krypton on graphite. Phys. Rev. Iett., 46(23):]533, 1981.

[37] C. W. Fay IV and P. M. Duxbury. Core percolation by leaf removal on diluted
lattices. in preparation, 2007.

[38] C. W. Fay IV and P. M. Duxbury. Core percolation by triangle removal on
diluted lattices. in preparation, 2007.

[39] C. W. Fay IV and P. M. Duxbury. Finding the maximum independent set on
diluted regular lattices. in preparation, 2007.

[40] C. W. Fay IV, J. W. Liu, and P. M. Duxbury. Maximum independent set on
diluted triangular lattices. Physical Review E, 73(056112):1-14, 2006.

[41] B. Joos, B. Bergersen, and ML. Klein. Ground-state properties of xenon on
graphite. Phys. Rev. B, 28(12):7219, 1983.

[42] R]. Gooding B. Joos and B. Bergersen. Krypton on graphite: Microstructure
at zero temperature. Phys. Rev. B, 27(12):7669, 1983.

174

[43] R. Kariotis, J.A. Venables, M. Hamichi, and A.Q.D. Faisal. Xenon-graphite
interaction near the commensurate-incommenserate transition. I. Phys. C,
19:5717—5726, 1987.

[44] R. Karp. Reducibility among combinatorial problems. In R. Miller and
J. Thatcher, editors, Complexity of Computer Computations, pages 85—103.
Plenum Press, 1972.

[45] Richard M. Karp. On the computational complexity of combinatorial prob-
lems. Networks, 5:45—68, 1975.

[46] Richard M. Karp and Micheal Sipser. Maximum matchings in sparse random
graphs. In Proc. 22nd Annual Symp. on Foundations of Computer Science, pages
364—375, 1981.

[47] Richard Kaye. Mastermind is np-complete. Mathematical Intelligencer, 22(2):9—
15, 2000.

[48] J. Keller, P. Miltényi, B. Beschoten, G. Giintherodt, U. Nowak, and K. D. Us-
adel. Domain state model for exchange bias. ii. experiments. Phys. Rev. B,
66(1):014431, Jul 2002.

[49] S. Kirkpatrick and B. Selman. Critical behavior in the satisfiability of random
boolean expressions. Science, 264(5163):1297—1301, May 1994.

[50] S. Kirkpatrick and D. Sherrington. Infinite-ranged models of spin-glasses.
Physical Review B, 17(11):4384—4403, June 1978.

[51] Michele Leone, Federico Ricci-tersenghi, and Riccardo Zecchina. Phase coex-
istence and finite-size scaling in random combinatorial problems. journal of
Physics A, 34:4615, 2001.

[52] L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete
Mathematics, 13:383—390, 1975.

[53] Olivier C. Martin, Rémi Monasson, and Riccardo Zecchina. Statistical me-
chanics methods and phase transitions in optimization problems. Theoretical
Computer Science, 265(1-2):3—67, 2001.

[54] M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random
satisfiability problem. Physical Review Letters, 94:197205, 2005.

[55] M. Mezard, J.P. Nadal, and G. Toulouse. Solvable models of working memo-
ries. journal of Physics, 1986.

[56] M. Mézard and G. Parisi. A replica analysis of the travelling salesman prob-
lem. journal of Physics, 47:1285—1296, 1986.

[57] M. Mézard, G. Parisi, N Sourlas, G. Toulouse, and M. Virasoro. Nature of the
spin-glass phase. Physical Review Letters, 52(13):1156—1159, March 1984.

175

[58] M. Mézard, G. Parisi, N. Sourlas, G. Toulouse, and M. Virasoro. Replica sym—
metry breaking and the nature of the spin glass phase. journal of Physique,
45:843—854, May 1984.

[59] M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of
random satisfiablity problems. Science, 297:812—815, 2002.

[60] M. Mézard and MA. Virasoro. The microstructure of ultrametricity. journal
of Physique, 46:1293—1307, 1985.

[61] Marc Mézard and Riccardo Zecchina. The random k-satisfiability prob-
lem: from an analytic solution to an efficient algorithm. Physical Review E,
66:056126, 2002.

[62] Mark Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin Glass Theory
and Beyond. World Scientific, 1987.

[63] Rémi Monasson. Some remarks on hierarchical replica symmetry breaking in
finite-connectivity systems. Minerva Workshop on Neural Networks, March
1997.

[64] Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and
Lidror Troyansky. Determining computational complexity from characteristic
’phase transistions’. Nature, 297:812—815, 1999.

[65] PA. Heiney R.J. Birgeneau G.S. Brown P.M. Horn D.E. Moneton and PW.
Stephens. Freezing transition of monolayer xenon on graphite. Phys. Rev.
Iett., 48(2):]04, 1982.

[66] C. Moukarzel and P. M. Duxbury. Comparison of rigidity and connectivity
percolation in two dimensions. Phys. Rev. E, 59(3):2614—2622, March 1999.

[67] C. M. Newman and D. L. Stein. Simplicity of state and overlap structure in
finite-volume realistic spin glasses. Physical Review E, 57(2):1356—1366, Febru-
ary 1998.

[68] C. M. Newman and D. L. Stein. Meetastable states in spin glasses and disorder
ferromagnets. Physical Review E, 60(5):5244—5260, November 1999.

[69] Mario Nicoderni, Antonio Coniglio, and Hans J. Hermann. Frustration and
slow dynamics of granular packings. Phys. Rev. E, 55(4):3962, 1997.

[70] M. Nielsen, J. Als-Neilsen, and J. Bohr. Pressure-driven commensurate-

incommensurate transistion in low-temperature submonolayer krypton on
graphite. Phys. Rev. Lett., 47(8):582, 1983.

[71] U. Nowak, K. D. Usadel, J. Keller, P. Miltényi, B. Beschoten, and
G. Giintherodt. Domain state model for exchange bias. i. theory. Phys. Rev.
B, 66(1):014430, Jul 2002.

176

[72] W.J. Nuttall, K.P. Fahey, M.J. Young, 8. Keirner, R.J. Birgeneau, and H. Sue-
matsu. A sychrotron x—ray diffraction study of the structural phase behavior

of multilayer xenon on single-crystal graphite. j. Phys. Conds. Matter, 5:8159—
8176, 1993.

[73] N. Parga and MA. Virasoro. The ultrametric organisation of memories in a
neural network. journal of Physics, 47:1857—1864, 1986.

[74] G. Parisi. Infinite number of order parameters for spin-glasses. Physical Review
Letters, 43(23):1754—1756, 1979.

[75] G. Parisi. The order parameter for spin glasses: A function on the interval 0-1.
journal of Physics A, 13:1101-1112, 1980.

[76] G. Parisi. Order parameter for spin-glasses. Physical Review Letters,
50(24):1946—1948, 1983.

[77] G. Parisi and F. Zamponi. The ideal glass transition of hard spheres.
j.CHEM.PHYS., 123:144501, 2005.

[78] Giorgio Parisi. Mean field theory of spin glasses: statics and dynamics.
arXiv:cond-mat, (0706.0094), 2007.

[79] A P Ramirez. Strongly geometrically frustrated magnets. Annual Review of
Materials Science, 24(1):453—480, 1994.

[80] S. Suresh Rao and Somendra M. Bhattacharjee. Protein folding and spin glass.
Physica A, 224:279—286, 1996.

[81] Francesco M Russo. Lattice gas analogue of the sherrington-kirkpatrick
model: a paradigm for the glass transition. journal of Physics A: Mathemati-
cal and General, 31(35):7249-7264, 1998.

[82] Francesco M. Russo. On lattice gas models for disordered systems. Physics
Letters A, 239:17—20, February 1998.

[83] D. Sherrington and S. Kirkpatrick. Solvable model of a spin-glass. Physical
Review Letters, 35(26):1792-1796, December 1975.

[84] D. Stauffer and A. Aharony. Introduction to Percolation Theory. Taylor 8: Francis
Ltd., revised second edition edition, 1994.

[85] Dietrich Stauffer, Joan Adler, and Amnon Aharony. Universality at the three-
dirnensional percolation threshold. journal of Physics A, 27:L475-L480, 1994.

[86] Jeff Stuckrnan and Guo-Qiang Zhang. Mastermind is np-complete. INFO-
COMP journal of Computer Science, 5(2):25—28, 2006.

[87] Robert Endre Tarjan and Anthony E. Trojanowski. Finding a maximum inde-
pentdent set. Siam j. Comput., 6(3):537—546, 1977.

177

[88] DJ. Thouless, P.W. Anderson, and RC. Palmer. Solution of solvable model of
a spin glass. Philosophical Magazine, 35(3):593—601, 1977.

[89] G. Toulouse. Theory of the frustration effect in spin glasses: 1. Communications
on Physics, 2:115—119, 1977.

[90] G. Toulouse, S. Dahaene, and J.—P changeux. Spin glass model of learning by
selection. Proc. National Academy of Science USA, 83:1695—1698, 1986.

[91] Martin Weight and Alexander K. Hartmann. Typical solution time for a
vertex-covering algorithm on finite-connectivity random graphs. Phys. Rev.
Lett., 86:1658, 2001.

[92] M. Weigt and A. K. Hartmann. Glassy behavior induced by geometrical frus-
tration in a hard-core lattice gas model. Europhysics Letters, 62:533, 2003.

[93] Martin Weigt. Dynamics of heuristic optimization algorithms on random
graphs. Euro. Phys. jour. B, 28:369—381, 2002.

[94] Martin Weigt and Alexander K. Hartmann. Minimal vertex covers on finite-
connectivity random graphs - a hard-sphere lattice-gas picture. Phys. Rev. E,
63(056127), 2001.

[95] Gerhard J. Woeginger. Exact algorithms for np-hard problems: a survey. In
Combinatorial optimization - eureka, you shrinkl, pages 185—207. Springer-Verlag
New York, Inc., New York, NY, USA, 2003.

[96] Takayuki Yato. Complexity and completeness of finding another solution and
its application to puzzles. Master’s thesis, The University of Tokyo, January
2003.

178

 

111111111111