Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics
Подождите немного. Документ загружается.
stationary point. For this reason, the points (x
0
,
0
)
at which is not transversal to the fibers of
:T
M !M are called the caustic points of .
Their projections x
0
2 M form the caustic set in M.
In the theory of unfoldings of singularities, the
germs of the families of functions x 7!( 7!’(x, ))
and y 7!( 7! (y, )) are called equivalent if there
exists a germ of a diffeomorphism of the form
H :(x, ) 7!(y(x), ( x, )) and a smooth function (x)
such that (y(x), (x, )) = ’(x, ) þ (x). If J(y, !)is
an oscillatory integral with phase function ,
integration variable and parameter y, then the
substitution of variables = (x, ) in the integral,
followed by the substitution of variab les
y = y(x)in
the parameters, yields that J(y, !) = e
i!(x)
I(x, !), in
which I(x, !) is an oscillatory integral with phase
function ’ and an amplitude function of the same
order as the amplitude function of J. The germ ’ is
called stable if every nearby germ is equivalent to
’. The Morse lemma with parameters implies that
this is the case if 7!’(x
0
, ) has a nondegenerate
stationary point at
0
. However, the theory of
unfoldings of singularities of Thom and Mather
shows that there are many stable germs with
degenerate critical points. Moreover, in dimension
n 5 the generic germ is stable, and is equiva lent to
a germ in a finite list of normal forms.
The simplest example of a normal form with
degenerate critical points is ’(x, ) =
3
þ x
1
. Here
we have taken k = 1, but still allowed an arbitrar y
dimension n 1ofM. In this normal form, the
stationary points correspond to 3
2
þ x
1
= 0, which
is a manifold which over the x-space folds over at
x
1
= 0. The stationary point is degenerate if and only
if 6 = 0, hence x
1
= 0, which means that x
1
= 0is
the caustic set. If the amplitude is equal to 1, then
the oscillatory integral is equal to !
1=3
Ai(!
2=3
x
1
),
in which Ai(z) denotes the Airy function. If the
amplitude is nonzero at a degenerate critical point,
then the oscillatory integral near the corresponding
caustic point is asymptotically of the same order as
!
1=3
Ai(!
2=3
x
1
), which implies that the oscillatory
integral is a factor !
1=6
larger at these caustic points
than at the points away from the caustic set. In Airy
(1838), where the Airy function was introduced, Airy
considered light in a neighborhood of a caustic as an
oscillatory integral. Then, under suitable genericity
conditions, he brought the phase function into the
normal form
3
þ x
1
. Even for stable normal forms
in low dimensions, the interference patterns near the
caustic points can be very intricate (see, e.g., Berry
et al. (1979)). A survey of the application of the
theory of unfoldings to caustics in oscillatory
integrals can be found in Duistermaat (1974).
See also: Equivariant Cohomology and the Cartan
Model; Feynman Path Integrals; Functional Integration in
Quantum Physics; Hamiltonian Group Actions;
h-Pseudodifferential Operators and Applications;
Multiscale Approaches; Normal Forms and Semiclassical
Approximation; Optical Caustics; Path Integrals in
Noncommutative Geometry; Perturbation Theory and its
Techniques; Schro
¨
dinger Operators; Singularity and
Bifurcation Theory; Wave Equations and Diffraction.
Further Reading
Airy GB (1838) On the intensity of light in a neighborhood of a
caustic. Transactions of the Cambridge Philosophical Society
6: 379–403.
Atiyah MF and Bott R (1984) The moment map and equivariant
cohomology. Topology 23: 1–28.
Berline N and Vergne M (1982) Classes caracte´ristiques e´quivar-
iante. Formules de localisation en cohomologie e´quivariante.
Comptes Rendus Hebdomadaires des Seances de l’Academie
des Sciences, Paris 295: 539–541.
Berry MV, Nye JF, and Wright FJ (1979) The elliptic umbilic
diffraction catastrophe. Philosophical Transactions of the
Royal Society of London A291: 453–484.
Cartan H (1950) Notion d’alge` bre diffe´rentielle; applications ou
ope` re un groupe de Lie, and: La transgression dans un groupe
de Lie et dans un fibre´ principal. In: Colloque de Topologie,
pp. 15–27, 57–71 Bruxelles: C.B.R.M.
Duistermaat JJ (1974) Oscillatory integrals, Lagrange immersions
and unfoldings of singularities. Communications in Pure and
Applied Mathematics 27: 207–281.
Duistermaat JJ and Heckman GJ (1982) On the variation in the
cohomology of the symplectic form of the reduced phase
space. Inventiones Mathematical 69: 259–268.
Duistermaat JJ and Heckman GJ (1983) On the variation in the
cohomology of the symplectic form of the reduced phase
space. Inventiones Mathematical 72: 153–158.
Ho¨ rmander L (1971) Fourier integral operators I. Acta Mathe-
matica 127: 79–183.
Ho¨ rmander L (1983, 1990) The Analysis of Linear Partial
Differential Operators I. Berlin: Springer.
Ho¨ rmander L (1985) The Analysis of Linear Partial Differential
Operators IV. Berlin: Springer.
Huygens C (1690) Traite´ de la Lumie`re, Leyden: Van der Aa.
(English translation: Treatise on Light, 1690, reprint by Dover
Publications, New York, 1962.)
Maslov VP (1965) Perturbation Theory and Asymptotic Methods
(In Russian), Moscow: Moskov. Gos. University. (French
translation by Lascoux J and Se´ne´or R (1972) Paris: Dunod.)
Stationary Phase Approximation 49
Statistical Mechanics and Combinatorial Problems
R Zecchina, International Centre for Theoretical
Physics (ICTP), Trieste, Italy
ª 2006 Elsevier Ltd. All rights reserved.
Introduction
Equilibrium statistical mechanics and combinatorial
optimization – which is viewed here as a branch of
discrete mathematics and theoretical computer
science – have common roots. Phase transition are
mathematical phenomena which are not limited to
physical systems but are typical of many combina-
torial problems, one famous example being the
percolation transition in random graphs. Similarly,
the understanding of relevant physical problems,
such as three-dimensional lattice statistics or two-
dimensional quantum statistical mechanics pro-
blems, is strictly related to the question of purely
combinatorial origin of solving counting problems
over nonplanar lattices. Most of the tools and
concepts which have allowed to solve problems in
one field have a natural counterpart in the other.
While the possibility of solving exactly physical
models is always connected to the presence of some
algebraic properties which guarantee integrability, in
the combinatorial approach the emphasis is more on
algorithms that can be applied to problem instances
in which the symmetries behind intergrability might
be absent. Also at the level of out-of-equilibrium
phenomena, there exists a deep connection between
physics and combinatorics: just like physical pro-
cesses, local algorithms have to deal with an
exponentially large set of possible configurations
and their out-of-equilibrium analysis constitutes a
theory of how problems are actually solved.
Computational complexity theory deals with
classifying problems in terms of the computational
resources, typically time, required for their solution.
What can be meas ured (or computed) is the time
that a particular algorithm uses to solve the
problem. This time in turn depends on the imple-
mentation of the algorithm as well as on the
computer the program is running on. The theory of
computational complexity provides us with a notion
of complexity that is largely independent of imple-
mentational details and the computer at hand. This
is not surprising, since it is related to a highly
nontrivial question, that is: what do we mean by
saying that a combinatorial problem is solvable?
Problems which can be solved in polynom ial time
are considered to be tractable and compose the so-
called polynomial (P) class. The harder problems are
grouped in a larger class called NP, where NP stands
for ‘‘nondeterministic polynomial time.’’ These
problems are such that a potential solution can be
checked rapidly in polynomial time, while finding a
solution may require exponential time in the worst
case. In turn, the hardest problems in NP belong to a
subclass called NP-complete: an efficient algorithm
for solving one NP-complete problem could be
easily modified to effect ively solve any problem in
NP. By now, a huge number of NP-c omplete
problems has been identified, and the lack of such
an algorithm corroborates the widespread conjec-
ture P 6¼ NP, that is, that no such algorithm exists.
However, NP-complete problems are not always
hard: when their resolution complexity is measured
with respect to some underlying pro bability distri-
bution of problem instances, NP-complete problems
are often easy to solve on averag e. To deepen the
understanding of the average-case complexity (and
of the huge variability of running times observed in
numerical experiments), computer scienti sts, mathe-
maticians, and physicists have focuse d their atten-
tion on the study of random instances of hard
combinatorial problems, seeking for a link between
the onset of exponential-time complexity and some
intrinsic (i.e., algorithm independent) propert ies of
the randomized NP-complete problems. These types
of questions have merged combinatorial optimiza-
tion with statistical physics of disordered systems.
Computational complexity theory can also be
formulated for counting problems: similarly to
optimization problems, equivalence classes can be
defined which separate polynomially solvable count-
ing problems with the hard ones – the so-called #P
and #P-complete problems. Complexity theory for
counting problems makes the connections with
statistical mechanics even more direct in that
counting solutions is nothing but a computation of
a partition function.
Two simple theorems by Jerrum and Sincla ir
(1989) (which can be easily extended to many
combinatorial problems) can help in clarifying
these connections.
The first theorem tells us that any randomized
algorithm (e.g., Monte Carlo) for approximating the
partition function of a generic spin glass model – the
so-called spin glass problem – could be used to solve
all the other NP combinatorial problems. The
second theorem tells us that an algorithm for
evaluating exactly the partition function of the
ferromagnetic Ising model over a general graph
would again solve any other problem in the class #P,
which, as mentioned above, is the generalization of
50 Statistical Mechanics and Combinatorial Problems
the NP class to counting problems and obviously
contains the class NP as a particular case.
Let us consider the following sightly simplified
definition of the Ising and the spin glass problems.
Problem instance A symmetric matrix J
ij
with
entries in {1, 0, 1} and an inverse temperature .
Output The partition function Z =
P
{
i
}
2
H(s)
,
where H(s) =
P
i,j
J
ij
i
j
with
i
= 1.
Moreover, let us define the fully polynomial
randomized approximation scheme (FPRAS) for
counting and decision problems. A FPRAS for a
function f from problem instances to real numbers is
a probabilistic algorithm that in polynomial time in
the problem size n and in the relative error 2 [0, 1],
outputs with high probability a number which
approximates f (n) within a ratio 1 þ . Given the
above definitions, the theorems can be stated as
follows:
Theorem 1 There can be no FPRAS for the spin
glass problem unless P = NP, that is, all problems in
NP turn out to be solvable in polynomial time.
Theorem 2 The Ising problem is #P-complete even
when the matrix J
ij
is non-negative, that is, an
algorithm which outputs in polynomial time the
exact Ising partition function for an arbitrary graph
could be used to solve any other counting problem
in #P.
The above theorems hold for arbitrary graphs,
in particular for those graph or lattice realizations
which are particularly hard to analyze, the so-called
worst cases. There exist no similar proofs of
computational hardness for more restricted and
realistic structures, such as, for instance, three-
dimensional regular lattices for the Ising problem
or finite connectivity random graphs for spin glasses.
As a final introductory remark, it is worth
mentioning that the connections between worst-
case complexity and the average case one is the
building block of modern cryptography and com-
munication theory. On the one hand, the so-called
RSA cryptosystem is based on factoring large
integers, a problem which is believed to be hard on
average while it is not known to be so in the worst
case. On the other hand, alternative cryptographic
systems have been proposed which rely on a worst-
case/average-case equivalence (see, e.g., the theorem
of Ajtai (1996) concerning some hidden vector
problems in high-dimensional lattices.)
As far as comm unication theory is concerned,
average-case complexity is indeed crucial: while
Shannon’s theorem (1948) provides a very general
result stating that many optimal codes do exist (in
fact, random codes are optimal), the decoding
problem is in general NP-complete and therefore
potentially intractable. However , since the choice of
the coding scheme is part of the design, what
matters are the average-case behavior of the decod-
ing algorithm (and its large deviations ) and very
efficient codes which can solve on average the
decoding problem close to Shannon’s bounds are
known.
In what follows, we will limit the discussion to
two basic examples of combinatorial and counting
problems which are representative and central to
both computer science and statistical physics.
Constraint Satisfaction Problems
Combinatorial problems are usually written as
constraint satisfaction problems (CSPs): n discrete
variables are given which have to satisfy m
constraints, all at the same time. Each constraint
can take different forms depending on the prob-
lem under study: famous examples are the
K-satisfiability (K-SAT) problem in which constraints
are an ‘‘OR’’ function of K variables in the ensemble
(or their negations) and the graph Q-coloring
problem in which constraints simply enforce the
condition that the endpoints of the edges in the graph
must not have the same color (amo ng the Q possible
ones). Quite in general a generic CSP can be written
as the problem of finding a zero-energy ground state
of an appropriate energy function and its analysis
amounts at performing a zero-temperature statistical
physics study. Hard combinatorial problems are
those which correspond to frustrated physical model
systems.
Given an instance of a CSP, one wants to know
whether there exists a solution, that is, an assign-
ment of the variables which satisfies all the
constraints (e.g., a proper coloring). When it exists,
the instance is called SAT, and one wants to find
a solution. Most of the interesting CSPs are
NP-complete: in the worst case, the number of
operations ne eded to decide whether an instance
is SAT or not is expected to grow exponentially
with the number of variables. But recent years
have seen an upsurge of interest in the theory of
typical-case complexity, where one tries to identify
random ensembles of CSPs which are hard to solve,
and the reason for this difficulty. As already
mentioned, random ensembles of CSPs are also
of great theoretical and practical im portance in
communication theory, since some of the best
modern error-correcting codes (the so-called low-
density parity check codes) are based on such
constructions.
Statistical Mechanics and Combinatorial Problems 51
Satisfiability and Spin Glass Models
The archetypical example of CSP is satisfiability
(SAT). This is a core problem in computational
complexity: it is the first one to have been shown
NP-complete, and since then thousands of problems
have been shown to be computationally equivalent
to it. Yet it is not so easy to find difficult instances.
The main ensemble which has been used for this
goal is the random K-SAT ensemble (for K > 2,
K-SAT is NP-complete).
The SAT problem is defined as follows. Given a
vector of {0, 1} Boolean variables x = {x
i
}
i2I
, where
I = {1, ..., n}, consider a SAT formula defined by
F xðÞ¼
^
a2A
C
a
xðÞ
where A is an arbitrary finite set (disjoint with I)
labeling the clauses C
a
; C
a
(x) =
W
i2I(a)
J
a, i
(x
i
); any
literal J
a, i
(x
i
) is either x
i
or x
i
(‘‘not’’ x
i
); and
finally, I(a) I for every a 2 A. Similarly to I(a), we
can define the set A( i) A as A(i) = {a : i 2 I(a)}, that
is, the set of clauses containing variable x
i
or its
negation.
Given a formula F, the problem of finding a
variable assignment s such that F(s) = 1, if it exists,
can also be written as a spin glass problem
asfollows:ifweconsiderasetofn Ising s pins,
i
2 {1} in place of the Boolean variables
(
i
= 1, 1 $x
i
= 0, 1) we may write the ene rgy
function associated to each clause as follows:
E
a
¼
Y
K
r¼1
1 þ J
a;i
r
i
r
2
where J
a, i
= 1 (resp. J
a, i
= 1) if x
i
(resp.
~
x
i
) appears
in clause a. The total energy of a configuration
E =
P
jAj
a = 1
E
a
is nothing but a K-spin spin glass
model.
Random K-SAT is a version of SAT in which each
clause is taken to involve exactly K distinct
variables, randomly chosen and negated with uni-
form distribution. Its energy function corresponds to
a spin glass system over a finite connectivity
(diluted) random graph.
In recent years random K-SAT has attracted much
interest in computer science and in statistical
physics. The interesting limit is the thermodynamic
limit n !1, m = jAj!1 at fixed clause density
= m=n.
Its most striking feature is certainly its sharp
threshold. It is strongly believed that there exists a
phase transition for this problem: numerical and
heuristic analytical arguments are in support of the
so-called satisfiability thres hold conjecture:
Conjecture There exists
c
(K) such that with high
probability:
if <
c
(K), a random instance is satisfiable;
if >
c
(K), a random instance is unsatisfiable.
Although this conjecture remains unproven, the
existence of a nonuniform sharp threshold has been
established by Friedgut (1997). A lot of effort has been
devoted to understanding this phase transition. This is
interesting both from physics and the computer science
points of view, because the random instances with
close to
c
are the hardest to solve. There exist
rigorous results that give bounds for the threshold
c
(K): using these bounds, it was shown that
c
(K)
scales as 2
K
ln (2) when K !1.
On the statistical physics side, the cavity method
(which is the generalization to disordered systems
characterized by ergodicity breaking of the iterative
method used to solve exactly physical models on the
Bethe lattice), is a powerful tool which is claimed to
be able to compute the exact value of the threshold,
giving for instance
c
(3) ’ 4.266 7 ... It is a non-
rigorous method but the self-consistency of its
results have been checked by a ‘‘stability analysis,’’
and it has also led to the development of a new
family of algorithms – the so-called ‘‘survey propa-
gation’’ – which can so lve efficiently very large
instances at clause densities which are very close to
the threshold (for technical details see Me´zard and
Zecchina (2002) and Braunstein et al. (2005) and
references therein).
The main hypothesis on which the cavity analysis
of random K-SAT relies is the existence, in a region
of clause density [
d
,
c
] close to the threshold, of
an intermediate phase called the ‘‘hard-SAT’’ phase;
see Figure 1. In this phase the set S of solutions
(a subset of the vertices in an n-dimensional
hypercube) is supposed to split into many discon-
nected clusters S= S
1
[S
2
[. If one considers
two solutions X, Y in the same cluster S
j
,itis
Easy SAT Hard SAT
UnSAT
m/
n
O(n)
Figure 1 A pictorial representation of the clustering transition
in random K-SAT.
52 Statistical Mechanics and Combinatorial Problems
possible to walk from X to Y (staying in S)by
flipping at each step a finite numbers of variables. If,
on the other hand, X and Y are in different cluster s,
in order to walk from X to Y (staying in S), at least
one step will involve an extensive number (i.e., /n)
of flips. This clustered phase is held responsible for
entrapping many local-search algorithms into non-
optimal metastable states. This phenomenon is not
exclusive to random K-SAT. It is also predicted to
appear in many other hard SAT and optimization
problems such as ‘‘coloring,’’ and corresponds to the
so called ‘‘one-step replica symmet ry breaking’’
(1RSB) phase in the language of statistical physics.
It is also a crucial limiting feature for decoding
algorithms in some error correcting codes.
The only CSP for which the existence of the
clustering phase has been established rigorously is
the polynomial problem of solving random linear
equation in GF (Motwani and Raghavan 2000). For
random K-SAT, rigorous probabilistic bounds can
be used to prove the existence of the clustering
phenomenon, for large enough K, in some region of
included in the interval [
d
(K),
c
(K)] predicted by
the statistical physics analysis.
In the analysis of CSP like K-SAT, two main
questions are in order. The first is of algorithmic
nature and asks for an algorithm which decides
whether for a given CSP instance all the constr aints
can be simultaneously satisfied or not. The second
question is more theoretical and deals with large
random instances, for which one wants to know the
structure of the solution space and predict the
typical behavior of classes of algorithms.
Message-Passing Algorithms from
Statistical Physics
The algorithmic contributions of statistical
mechanics to combinatorial optimization are numer-
ous and important (a representative example being
the celebrated ‘‘simulated annealing algorithm’’).
For the sake of brevity, here we limit the discussion
to the so-called ‘‘message-passing algorithms’’ which
are also of great interest in coding theory.
The statistical analysis of the cavity equations
allows to study the average properties of ensemble
of problems and it is totally equivalent to the replica
method in which the average over the ensemble is
the first step in any calculation. The survey
propagation (SP) equations are a formulation of
the cavity equations which is valid for each specific
instance and is able to provide information about
the statistical behavior of the individual variables in
the stable and metastable states of a given energy
density (i.e., given fraction of violate d constraints).
The single-sample SP equations are nicely described
in terms of the factor graph representation used in
information theory to characterize error-correcting
codes. In the factor graph, the N variables i, j, k, ...are
represented by circular ‘‘variable nodes,’’ whereas the
M clauses a, b, c, ... are represented by square ‘‘func-
tion nodes.’’ For random K-SAT, the function nodes
have connectivity K, while the variable nodes have an
average Poisson connectivity K.
The iterative SP equations are examples of message-
passing procedures. In message-passing algorithms
such as the so-called ‘‘belief propagation (BP)
algorithm’’ used in error-correcting codes and
statistical inference problems, the unknowns which
are self-consistently evaluated by iteration are the
marginals over the solution space of the variables
characterizing the combinatorial problem (the prob-
ability space is the set of all solutions sampled with
uniform measure). According to the physical inter-
pretation, the quantities that are evaluated by SP are
the probability distributions of local fields over the set
of clusters. That is, while BP performs a ‘‘white’’
average over solutions, SP takes care of cluster-to-
cluster fluctuations, telling us which is the probability
of picking up a cluster at random and finding a given
variable biased in a certain direction (or unfrozen if it
is paramagnetic in the cluster). SP computes quantities
which are probabilities over different pure states: the
order parameter which is evaluated as fixed point of
the SP equations is a probability measure in a space of
functions, or for finite n, the full list of probability
densities describing the cluster-to-cluster fluctuations
of the variables.
In both SP and BP one assumes knowledge of the
marginals of all variables in the temporary absence
of one of them and then writes the marg inal
probability induced on this ‘‘cavity’’ variable in
absence of another third variable interacting with it
(i.e., the so-called Bethe lattice approximation for
the problem). These relations define a closed set of
equations for such cavi ty marginals that can be
solved iteratively (this fact is known as message-
passing technique). The equations become exact if
the cavity variables acting as inputs are uncorre-
lated. They are conjectured to be an asymptotically
exact approximation over random locally tree–like
structures such as, for instance, the random K-SAT
factor graph. Both BP and SP can be derived in a
variational framework.
Complexity of Counting Problems
In order to describe the nature of computational
complexity of coun ting in physical models, it is
enough to consider the classical Ising problem. The
Statistical Mechanics and Combinatorial Problems 53
computation of the Ising partition function or, more
in general, of the weighted matching polynomial, is
the root problem of lattice statistics.
For planar graphs like, for example, two-dimensional
regular lattices, counting problems can often be
solved by a variety of different methods, for
example, transfer matrices and Pfaffians, which
require a number of operations which are poly-
nomial in the number of vertices.
The complexity of the counting problems changes
if one considers nonplanar graphs, that is, graphs
with a nontrivial topological genus. In discrete
mathematics, such problems are classified as
#P-complete, meaning that the existence of an
exact polynomial algorithm for the evaluation of the
generating functions would imply the polynomial
solvability of many known counting combinatorial
problems, the most famous one being the evaluation of
the permanent of 0–1 matrices. In statistical mechanics
and mathematical chemistry, the interest in nonplanar
lattices is obviously related to their D > 2character:
the three-dimensional cubic lattice is nothing but a
nonplanar graph of topological genus g = 1 þ N=4,
where N is the number of sites.
The planar two-dimensional Ising model was solved
in 1944 by Onsager using the algebraic transfer matrix
method. Successively, alternative exact solutions have
been proposed which resorted to simple combinatorial
and geometrical reasoning. As is well known, the
underlying idea of the combinatorial methods consists
in recasting the sum over spin configurations of the
Boltzmann weights as a sum over closed curves (loops)
weighted by the activity of their bonds. Double
counting is avoided by a proper cancellation mechan-
ism which takes care of the different intrinsic
topologies of loops which give rise to the same
contribution in the partition function. Such an
approach has been developed first by Kac and Ward
(1952) and provides a direct way of taking the field
theoretic continuum limit. In D > 2, the general-
ization of the above method encounters enormous
difficulties due to the variety of intrinsic topologies of
surfaces immersed in D > 2lattices.
Another combinatorial method proposed in the
1960s by Kasteleyn is the so-called Pfaffian method.
It consists in writing the weighted sum over loops as
a dimer covering or prefect matching generating
function. Once the relationship between loop count-
ing and dimer coverings (or perfect matchings) over
a suitably decorated and properly oriented lattice is
established, the Pfaffian method turns out to be a
simple technique for the derivation of exact solu-
tions or for the definition of polynomial algor ithms
over planar lattices which are applicable also to the
two-dimensional Ising spin glass.
The generalization of the Pfaffian construction to
the nonplanar case must deal with the ambiguity of
orienting the homology cycles of the graph. Such a
problem can be formally solved in full generality for
any orientable lattice and leads to an expression of
the Ising partition function or the dimer coverings
generating function given as a sum over all possible
inequivalent orientations of the lattice (or its embed-
ding surface): for a graph of genus g, the homology
basis is composed of 2g cycles and, therefore, there
are 2
2g
inequivalent orientations. It is only for graphs
of logarithmic genus that the generalized Pfaffian
formalism provides a polynomial algorithm.
Counting perfect matchings can be thought of as
the problem of evaluating the permanent of 0–1
matrices over properly constructed bipartite graphs,
which is among the oldest and most famous
#P-complete problems.
The Pfaffian formalism when applied to the perma-
nent problem leads to a simple general result, that is, it
provides a general formula for writing the permanent
of a matrix in terms of a number of determinants which
is exponential in the genus of the underlying graph.
See also: Combinatorics: Overview; Determinantal
Random Fields; Dimer Problems; Phase Transitions in
Continuous Systems; Spin Glasses; Two-Dimensional
Ising Model.
Further Reading
Achlioptas D, Naor A, and Peres Y (2005) Rigorous location of
phase transitions in hard optimization problems. Nature 435:
759–764.
Ajtai N (1996) Generating hard instances of lattice problems.
Electronic Colloquium on Computational Complexity
(ECCC) 7: 3.
Braunstein A, Me´zard M, and Zecchina R (2005) Survey
Propagation: an Algorithm for Satisfiability. Random Struc-
tures and Algorithms 27: 201–226.
Cocco S and Monasson R (2004) Heuristic average-case analysis
of the backtrack resolution of random 3-satisfiability
instances. Theoretical Computer Science A 320: 345.
Distler J (1992) A note on the 3D Ising model as a string theory.
Nuclear Physics B 388: 648.
Dubois O, Monasson R, Selman B, and Zecchina R (eds.) (2001)
NP-hardness and Phase transitions (Special Issue), Theoretical
Computer Science, vol. 265 (1–2). Elsevier.
Friedgut E (1999) Sharp threshold of graph properties, and the
KSat problem. Journal of American Mathematical Society 12:
1017–1054.
Jerrum M and Sinclair A (1989) Approximating the permanent.
SIAM Journal on Computing 18: 1149.
Lova´sz L and Plummer MD (1986) Matching Theory. North-
Holland Mathematics Studies 121, Annals of Discrete Mathe-
matics (29). New York: North-Holland.
Me´zard M, Mora T, and Zecchina R (2005) Clustering of
solutions in the random satisfiability problem. Physics Review
Letters 94: 197205.
54 Statistical Mechanics and Combinatorial Problems
Me´zard M and Parisi G (2001) The Bethe lattice spin glass
revisited. European Physical Journal B 20: 217.
Me´zard M, Parisi G, and Virasoro MA (1987) Sping Glass
Theory and Beyond. Singapore: World Scientific.
Me´zard M, Parisi G, and Zecchina R (2002) Analytic and
algorithmic solution of random satisfiability problems. Science
297: 812–815.
Me´zard M and Zecchina R (2002) Random K-satisfiability: from
an analytic solution to a new efficient algorithm. Physical
Review E 66: 056126.
Monasson R, Zecchina R, Kirkpatrick S, Selman B, and
Troyansky L (1999) Determining computational complexity
from characteristic ‘‘phase transitions’’. Nature 400: 133.
Motwani R and Raghavan P (2000) Randomized Algorithms.
Cambridge: Cambridge University Press.
Nishimori H (2001) Statistical Physics of Spin Glasses and
Information Processing. Oxford: Oxford University Press.
Papadimitriou CH (1994) Computational Complexity. Addison-
Wesley.
Regge T and Zecchina R (2000) Combinatorial and topological
approach to the 3D Ising model. Journal of Physics A:
Mathematical and General 33: 741.
Richardson T and Urbanke R (2001) An introduction to the analysis
of iterative coding systems. In: Marcus B and Rosenthal J (eds.)
Codes, Systems, and Graphical Models.NewYork:Springer.
Statistical Mechanics of Interfaces
S Miracle-Sole´ , Centre de Physique The
´
orique,
CNRS, Marseille, France
ª 2006 Elsevier Ltd. All rights reserved.
Introduction
When a fluid is in contact with another fluid, or
with a gas, a portion of the total free energy of the
system is proportional to the area of the surfa ce of
contact, and to a coefficient, the surface tension,
which is specific for each pair of substances.
Equilibrium will accordingly be obtained when the
free energy of the surfaces in contact is a minimum.
Suppose that we have a drop of some fluid, b,
over a flat substrate, w, while both are exposed to
air, a. We have then three different surfaces of
contact, and the total free energy of the system
consists of three parts, associated to these three
surfaces. A drop of fluid b will exist provided its
own two surface tensions exceed the surface tension
between the substrate w and the air, that is,
provided that
wb
þ
ba
>
wa
If equality is attained, then a film of fluid b is
formed, a situation which is known as perfect, or
complete wetting (see Figure 1 ).
When one of the substances involved is aniso-
tropic, such as a crystal, the contribution to the total
free energy of each element of area depends on its
orientation. The minimum surface free energy for a
given volume then determines the ideal form of the
crystal in equilibrium.
It is only in recent times that equilibrium crystals
have been produced in the laboratory, first, in
negative crystals (vapor bubbles) of organic sub-
stances. Most crystals grow under nonequilibrium
conditions and it is a subsequent relaxation of the
macroscopic crystal that restores the equilibrium.
An interesting phenomenon that can be observed
on these crystals is the roughening transition,
characterized by the disappearance of the facets of
a given orientation, when the temperature attains a
certain particular value. The best observations have
been made on helium crystals, in equilibrium with
superfluid helium, since the transport of matter and
heat is then extremely fast. Crystals grow to sizes of
1–5 mm and relaxation times vary from milliseconds
to minutes. Roughening transitions for three differ-
ent types of facets have been observe d (see, e.g.,
Wolf et al. (1983)).
These are some classical examples among a
variety of interesting phenomena connected with
the behavior of the interface between two phases in
a physical system. The study of the nature and
properties of the interfaces, at least for some simple
systems in statistical mechanics, is also an interesting
subject of mathematical physics. Some aspects of
this study will be discussed in the prese nt article.
We assume that the interatomic forces can be
modeled by a lattice gas, and consider, as a simple
example, the ferromagnetic Ising model. In a typi cal
two-phase equilibrium state, there is a dense
w
w
a
a
b
b
Figure 1 Partial and complete wetting.
Statistical Mechanics of Interfaces 55
component, which can be interpreted as a solid or
liquid phase, and a dilute phase, which can be
interpreted as the vapor phase. Considering certain
particular cases of such situations, we first introduce
a precise definition of the surface tension and then
proceed on the mathematical analysis of some
preliminary properties of the corresponding inter-
faces. The next topic concerns the wetting properties
of the system, and the final section is dev oted to the
associated equilibrium crystal.
Pure Phases and Surface Tension
The Ising model is defined on the cubic lattice L= Z
3
,
with configuration space ={1, 1}
L
.If 2 ,the
value (i) = 1 or 1 is the spin at the site
i = (i
1
, i
2
, i
3
) 2L, and corresponds to an empty or an
occupied site in the lattice gas version of the model.
The system is first considered in a finite box L,
with fixed values of the spins outside.
In order to simplify the exposition, we shall
mainly consider the three-dimensional Ising model,
though some of the results to be discussed hold in
any dimension d 2. We shall also, sometimes,
refer to the two-dimensional model, it being under-
stood that the definitions have been adapted in the
obvious way. We assume that the box is a
parallelepiped, centered at the origin of L, of sides
L
1
, L
2
, L
3
, parallel to the axes.
A configuration of spins on ((i), i 2 ), denoted
, has an energy defined by the Hamiltonian
H
ð
jÞ¼J
X
hi;ji\6¼;
ðiÞðjÞ½1
where J is a positive constant (ferromagnetic or
attractive interaction). The sum runs over all
nearest-neighbor pairs hi, jiL, such that at least
one of the sites belongs to , and one takes
(i) =(i) when i 62 , the configuration 2
being the given boundary condition. The probability
of the configuration
, at the inverse temperature
= 1=kT, is given by the Gibbs measure
ð
jÞ¼Z
ðÞ
1
expðH
ð
jÞÞ ½2
where Z
() is the partition function
Z
ðÞ¼
X
expðH
ð
jÞÞ ½3
Local properties at equilibrium can be described by
the correlation functions between the spins on finite
sets of sites,
ððAÞÞ ¼
X
ð
jÞ
Y
i2A
ðiÞ½4
The measures [2] determine (by the Dobrushin–
Lanford–Ruelle equations) the set of Gibbs states of
the infinite system, as measures on the set of all
configurations. If a Gibbs state happens to be equal
to lim
(j), when L
1
, L
2
, L
3
!1, under a fixed
boundary condition , we shall call it the Gibbs
state associated to the boundary condition . One
also says that this state exists in the thermodynamic
limit. Then, equivalently, the correlation functions
[4] con verge to the corresponding expectation values
in this state.
This model presents, at low tem peratures (i.e., for
>
c
, where
c
is the cri tical inverse temperature),
two different thermodynamic pure phases, a dense
and a dilute phase in the lattice gas language (calle d
here the positive and the negative phase). This
means two extremal translation-invariant Gibbs
states,
þ
and
, obtained as the Gibbs states
associated with the boundary conditions , respec-
tively equal to the ground configurations (i) = 1
and (i) = 1, for all i 2L. The spontaneous
magnetization
m
ðÞ¼
þ
ððiÞÞ ¼
ððiÞÞ ½5
is then strictly positive. On the other hand, if
c
,
then the Gibbs state is unique and m
= 0.
Each configuration inside can be described in a
geometric way by specifying the set of Peie rls
contours which indicate the boundaries between
the regions of spin 1 and the regi ons of spin 1.
Unit-square faces are placed midway between the
pairs of nearest-neighbor sites i and j, perpendicu-
larly to these bonds, whenever (i)( j) = 1. The
connected components of this set of faces are the
Peierls contours. Under the boundary conditions (þ)
and (), the contours form a set of closed surfaces.
They describe the defects of the considered config-
uration with respect to the ground states of the
system (the constant configurations 1 and 1), and
are a basic tool for the investigation of the model at
low temperatures.
In order to study the interface between the two
pure phases, one needs to construct a state describ-
ing the coexistence of these phases. This can be done
by means of a new boundary condition. Let
n = (n
1
, n
2
, n
3
) be a unit vector in R
3
, such that
n
3
> 0, and introduce the mixed boundary condition
(, n), for which
ðiÞ¼
1ifi n 0
1ifi n < 0
½6
This boundary condition forces the system to
produce a defect going transversally through the
box , a large Peierls contour that can be
56 Statistical Mechanics of Interfaces
interpreted as the microscopic interface (also called
a domain wall). The other defects that appear above
and below the interface can be described by closed
contours inside the pure phases.
The free energy per unit area due to the presence
of the interface is the surface tension. It is defined by
ð nÞ¼ lim
L
1
;L
2
!1
lim
L
3
!1
n
3
L
1
L
2
ln
Z
;n
ðÞ
Z
þ
ðÞ
½7
In this expression the volume contributions propor-
tional to the free energy of the coexisting phases, as
well as the boundary effects, cancel, and only the
contributions to the free energy due to the interface
are left. The existence of such a quantity indicates
that the macroscopic interface, separating the
regions occupied by the pure phases in a large
volume , has a microscopic thickness and can
therefore be regarded as a surface in a thermo-
dynamic approach.
Theorem 1 The interfacial free energy per unit
area, (n), exists, is bounded, and its extension by
positive homogeneity, f (x) = jxj(x=jxj), is a convex
function on R
3
. Moreover, (n) is strictly positive
for >
c
, and vanishes if
c
.
The existence of (n) and also the last statement
were proved by Lebowitz and Pfister (1981),inthe
particular case n = (0, 0, 1), with the help of correla-
tion inequalities. A complete proof of the theorem
was given later with similar arguments. The con-
vexity of f is equivalent to the fact that the surface
tension satisfies a thermodynamic stability condi-
tion known as the pyramidal inequality (see
Messager et al. (1992)).
Gibbs States and Interfaces
In this section we consider the (, n
0
) boundary
condition, also simply denoted (), associated to the
vertical direction n
0
= (0, 0, 1),
ðiÞ¼1ifi
3
0; ðiÞ¼1ifi
3
< 0 ½8
The corresponding surface tension is
= (n
0
). We
shall first recall some classical results which concern
the Gibbs states and interfaces at low temperatures.
According to the geometrical description of the
configurations introduced in the last section, we
observe that
Z
;n
ðÞ=Z
þ
ðÞ¼
X
exp 2JjjU
ðÞðÞ½9
where the sum runs over all microscopic interfaces
compatible with the boundary condition and jj is
the number of faces of (inside ). The term U
()
equals ln Z
þ
(, )=Z
þ
(), the sum in the partition
function Z
þ
(, ) being extended to all configura-
tions whose associated contours do not intersect .
Each term in sum [9] gives a weight proportional to
the probability of the corresponding microscopic
interface.
At low (positive) temperatures, we expect the
microscopic interface corresponding to this bound-
ary condition, which at zero temperature coincides
with the plane i
3
= 1=2, to be modified by small
deformations. Each microscopic interface can then
be described by its defects, with respect to the
interface at = 1. To this end, one introduces some
objects, called walls, which form the boundaries
between the horizontal plane portions of the micro-
scopic interface, also called the ceilings of the
interface.
More precisely, one says that a face of is a
ceiling face if it is horizontal and such that
the vertical line passing through its center does not
have other intersections with . Otherwise, one
says that it is a wall face. The set of wall faces splits
into maximal connected components. The set of
walls, associated to , is the set of these compo-
nents, each component being identified by its
geometric form and its projection on the plane
i
3
= 1=2. Every wall !, with projection (!),
increases the energy of the interface by a quantity
2Jk ! k, where k!k= j!jj(!)j, and two walls are
compatible if their projections do not intersect. In
this way, the microscopic interfaces may be inter-
preted as a ‘‘gas of walls’’ on the two-dimensional
lattice.
Dobrushin, who developed the above analysis,
also prov ed the dilute character of this ‘‘gas’’ at low
temperatures. This im plies that the microscopic
interface is essentially flat, or rigid. One can under-
stand this fact by noticing first that the probability
of a wall is less than exp (2Jk!k) and, second,
that in order to create a ceiling in , which is not in
the plane i
3
= 1=2, one needs to surround it by a
wall, that one has to grow when the ceiling is made
over a larger area.
Using correlation inequalities one proves that the
Gibbs state
, associated to the () boundary
conditions, always exists, and that it is invariant
under hor izontal translations of the lattice, that is,
((A þ a)) =
((A)) for all a = (a
1
, a
2
, 0). It is
also an extremal Gibbs state. Let m(z) be the
magnetization
(((z)) at the site z = (0, 0, z). The
function m(z) is monotone increasing and satisfies
the symmetry pro perty m(z) = m(z þ 1). Some
consequences of Dobrushin’ s work are the following
properties.
Statistical Mechanics of Interfaces 57
Theorem 2 If the temperature is low enough, that
is, if J c
1
, where c
1
is a given constant, then
m
ð0Þ is strictly positive ½10
m
ðzÞ!m
; when z !1; exponentially fast ½11
Equation [10] is just another way of saying that
the interface is rigid and that the state
is non-
translation invariant (in the vertical direction).
Then, the correlation functions
((A)) describe
the local properties, or local structure, of the
macroscopic interface. In particular, the function
m(z) represents the magnetization profile. Then
statement [11], together with the symmetry prop-
erty, tells us that the thickness of this interface is
finite, with respect to the unit lattice spacing.
The statistics of interfaces has been rewritten in
terms of a gas of walls and this system may further
be studied by cluster expansion techniques . There is
an interaction between the walls, coming from the
term U
()ineqn [9], but a convenient mathema-
tical description of this interaction can be obtained
by applying the standard low-temperature cluster
expansion, in terms of contours, to the regions
above and below the interface.
This method was introduced by Gallavotti in his
study (mentioned below) of the two-dimensional
Ising model. It has been applied by Bricmont and
co-workers to examine the interface structure in the
present case. As a consequence, it follows that
the surface tension, more exactly
(), and also
the correlation functions, are analytic functions at
low temperatures. They can be obtained as explicit
convergent series in the variable = e
2J
.
The same analysis applied to the two-dimensional
model shows a very different behavior at low
temperatures. In this case, the microscopic interface
is a polygonal line and the walls belong to the one-
dimensional lattice. One can then increase the size of
a ceiling without modifying the walls attached to it.
Indeed, Gallavotti turned this observation into a
proof that the Gibbs state
is now translation
invariant. The line undergoes large fluctuat ions of
order
ffiffiffiffiffiffi
L
1
p
, and disappears from any finite region of
the lattice, in the thermodynamic limit. In particular,
we have then
= (1=2)(
þ
þ
), a result that
extends to all boundary conditions (, n).
Using these results Bricmont and co-workers also
studied the local structure of the interface at low
temperatures and showed that its intrinsic thickness
is finite. To study the global fluctuations, one can
compute the magnetization profile by introducing,
before taking the thermodynamic limit, a change of
scale:
((zL
1
)), with = 1=2 or near to this value.
This is an exact computation that has been done by
Abraham and Reed.
Let us come back to the three-dimensional Ising
model where we know that the interface orthogonal
to a lattice axis is rigid at low temperatures.
Question 1 At higher temperatures, but before
reaching the critical temperature, do the fluctuations
of this interface become unbounded, in the thermo-
dynamic limit, so that the corresponding Gibbs state
is translation invariant?
One says then that the interface is rough, and it is
believed that, effectively, the interface becomes
rough when the temperature is raised, undergoing
a roughening transition at an inverse temp erature
R
>
c
.
It is known that
R
d = 2
c
, the critical inverse
temperature of the two-dimensional Ising model,
since van Beijeren proved, using correlation inequal-
ities, that above this value, the state
is not
translation invariant. Recalling that the rigid inter-
face may be viewed as a two-dimensional system,
the system of walls, a representation that would
become inappropriate for a rough interface, one
might think that the phase transition of the two-
dimensional Ising model is relevant for the rough-
ening transition, and that
R
is somewhere near
d = 2
c
. Indeed, approximate methods, used by Weeks
and co-workers give some evidence for the existence
of such a
R
and suggest a value slightly smaller
than
d = 2
c
, as shown in Table 1. To this day,
however, there appears to be no proof of the fact
that
R
>
c
, that is, that the roughening transition
for the three-dimensional Ising model really occurs.
At prese nt one is able to study the roughening
transition rigor ously only for some simplified mod-
els with a restricted set of admissible microscopic
interfaces. Moreover, the closed contours, describing
the defects above and below , are neglected, so that
these two regions have the constant configurations 1
or 1, and one has U
() = 0ineqn [9].
The be st known of these models is the classic SOS
(solid-on-solid) model in which the interfaces have
the property of being cut only once by all vertical
lines of the lattice. This means that is the graph of
a function that can equivalently be used to define
the possible configurations of .If contains the
horizontal face with center (i
1
, i
2
, i
3
1=2), then
Table 1 Some temperature values
d = 3
c
J 0:22 approximate critical temperature
d = 3
R
J 0:41 conjectured roughening temperature
d = 2
c
J = 0:44 exact critical temperature
58 Statistical Mechanics of Interfaces