PHASE_T

We present the outline of a proof for the 3-d phase transition which we hope to carry forth. At the same time this paper provides some physical understanding of the phase transition, in the flavor of relatively simple arguments from an undergraduate course. A number of directions for mathematical research, interesting in their own right, will be suggested by aspects of the development. We hope and believe that readers will be enticed by the naturalness and beauty of the path; some perhaps even, big game veterans, sniffing the quarry, will be ready to join the hunt. The central construct views the trace, Tr(exp(-beta*H)), as a lattice gas of polymers, each representing a cycle in the permutation group, with hard core interactions. The activities of the polymers have expressions as arising from the main conjecture of the paper. The estimates lead to a phase transition in 3-d, but not 2-d. This occurs via the same argument that a random walk in 2-d has certain return to the origin, but not so for a random walk in 3-d.

The Anderson localization problem in one and two dimensions is solved analytically via the calculation of the generalized Lyapunov exponents. This is achieved by making use of signal theory. The phase diagram can be analysed in this way. In the one-dimensional case all states are localized for arbitrarily small disorder in agreement with existing theories. In the two-dimensional case for larger energies and large disorder all states are localized but for certain energies and small disorder extended and localized states coexist. The phase of delocalized states is marginally stable. We demonstrate that the metal–insulator transition should be interpreted as a first-order phase transition. Consequences for perturbation approaches, the problem of self-averaging quantities and numerical scaling are discussed.

In the present Ph.D. dissertation I present results concerning disordered and frustrated models of relevance in statistical mechanics and in combinatorial optimization. As an application of spin glass theory I study the disordered and frustrated Blume-Emery-Griffiths model. The model is treated in its mean-field approximation using replicas. Within the Ansatz of replica-symmetry, I present a complete numerical solution; I also discuss effects of replica symmetry breaking. The stability of the RS solution is studied and the regions of instability inferred. The phase diagram exhibits first and second order transitions. The tricritical point is still present in the frustrated model, in agreement with former work. A version of the BEG model with disordered chemical potential is also studied. The calculations confirm that the disorder decreases the tricritical temperature. Next, I consider the graph partitioning problem, a combinatorial optimization problem, which, from the point of view of statistical mechanics is a spin glass model with the constraint of zero magnetisation. I focus on the statistical properties of low energy solutions generated by heuristic algorithms designed to solve such hard combinatorial optimization problems. Several heuristics proposed to solve this problem were implemented. Scaling laws are obtained; in particular, the average cost and its variance grow linearly with the number of vertices of the graphs. As a consequence the cost found by the heuristics is self-averaging. I suggest that this property is quite general, valid for random solutions, quasi-optimal solutions, and probably for the optimum solutions, too. Furthermore a ranking method is proposed and illustrated on an ensemble of graph partitioning problems. This ranking procedure takes into account the quality of the solution as well as the time necessary to find that solution. In the third part of this dissertation I study in detail the zero-temperatures properties of spin glasses on sparse random graphs with fixed connectivity. Spin glasses on these graphs may be considered as a more realistic approximation to real spin glasses as represented by the model of Sherrington and Kirkpatrick. I have designed a new algorithm for finding low energy states. Second, I present a method for deriving the ground state energy from heuristic algorithms, even though they are not guaranteed to find the optimum. Third, I present a numerical test of a conjecture due to Banavar, Sherrington and Sourlas, giving the large volume energy density of the ground states as function of the connectivity. The distribution of the order parameter is found to be non-trivial, and I give evidence for the presence of ultrametricity for all values of the connectivity. These results confirm the expectation that the remarquable properties of the infinite range Sherrington-Kirkpatrick model carry over to more realistic models, as for example the spin glass model on random graphs with finite connectivity studied in the present work.