THESIS

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.