From Statistical Mechanics to Large Deviations of Uniformly Random d-Regular Graphs

ABSTRACT

A Large system is difficult to study globally. Its study requires some random procedure that can expose some of its properties to enable the identification of its typical behaviour. To this end, uniformly random regular graphs were generated due to their fascinating properties and applications. The Potts model was used to assign spin values to the vertices of the graph from a finite spin space. Errors do occur in large system rarely but when they do, their impact may cause some destruction. The randomness in rare events allows the use of probability theory to assess it. Large deviations principle measures the probabilities of rare event and the rate at which they occur. The aim of this thesis was to derive the Large Deviations Principle of the joint empirical spin and bond measures of the uniformly random -regular graphs. Subsequently, the rate function of the large deviation probabilities was derived. To achieve this, the method of types of the joint empirical measure was used. The rate function was expressed in terms of sum of the relative entropies of the joint empirical measures. The upper and lower bounds of the large deviation probabilities were formulated using the types and type class of the measures. It is recommended that to examine a large system, it is more parsimonious to find the large deviations of the interaction of its components which would describe vividly the typical behaviour of the system.