Scott Kirkpatrick

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.

Extensions of percolation theory to treat transport are described. Resistor networks, from which resistors are removed at random, provide the natural generalization of the lattice models for which percolation thresholds and percolation probabilities have previously been considered. The normalized conductance, $G$, of such networks proves to be a sharply defined quantity with a characteristic concentration dependence near threshold which appears sensitive only to dimensionality. Numerical results are presented for several families of $3D$ and $2D$ network models. Except close to threshold, the models based on bond percolation are accurately described by a simple effective medium theory, which can also treat continuous media or situations less drastic than the percolation models, for example, materials in which local conductivity has a continuous distribution of values. The present calculations provide the first quantitative test of this theory. A "Green's function" derivation of the effective medium theory, which makes contact with similar treatments of disordered alloys, is presented. Finally, a general expression for the conductance of a percolation model is obtained which relates $G$ to the spin-stiffness coefficient, $D$, of an appropriately defined model dilute ferromagnet. We use this relationship to argue that the "percolation channels" through which the current flows above threshold must be regarded as three dimensional.

We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied.

Abstract Percolation theory, the theory of the properties of classical particles interacting with a random medium, is of wide applicability and provides a simple picture exhibiting critical behaviour, the features of which are well understood and amenable to detailed calculation. In this review the concepts of percolation theory and the general features associated with the critical region about the onset of percolation are developed in detail. In particular, several dimensional invariants are examined which make it possible to unify much of the available information, and to extend the insights of percolation theory to processes which have not yet received numerical study. The compilation of the results of percolation theory, both exact and numerical, is believed to be complete through 1970. A selective bibliography is given. In a concluding chapter several recent applications of percolation theory to classical and to quantum mechanical problems are discussed.

The classical planar Heisenberg model is studied at low temperatures by means of renormalization theory and a series of exact transformations. A numerical study of the Migdal recursion relation suggests that models with short-range isotropic interactions rapidly become equivalent to a simplified model system proposed by Villain. A series of exact transformations then allows us to treat the Villain model analytically at low temperatures. To lowest order in a parameter which becomes exponentially small with decreasing temperature, we reproduce results obtained previously by Kosterlitz. We also examine the effect of symmetry-breaking crystalline fields on the isotropic planar model. A numerical study of the Migdal recursion scheme suggests that these fields (which must occur in real quasi-two-dimensional crystals) are strongly relevant variables, leading to critical behavior distinct from that found for the planar model. However, a more exact low-temperature treatment of the Villain model shows that hexagonal crystalline fields eventually become irrelevant at temperatures below the ${T}_{c}$ of the isotropic model. Isotropic planar critical behavior should be experimentally accessible in this case. Nonuniversal behavior may result if cubic crystalline fields dominate the symmetry breaking. Interesting duality transformations, which aid in the analysis of symmetry-breaking fields are also discussed.