Disordered models on sparse random graphs

This thesis investigates disordered systems and combinatorial optimization problems through the lens of statistical physics. The main focus is on spin glasses defined on sparse random graphs, with the goal of understanding how the replica symmetry breaking (RSB) picture of the fully connected Sherrington–Kirkpatrick (SK) model in an external field is modified in finite dimensions. Renormalization group (RG) analyses around the SK solution suggest that, if a transition in a field exists below six dimensions, it must correspond to a non-perturbative fixed point—one that cannot be reached continuously from the SK fixed point by lowering the dimension. Notably, a possibility is that such a fixed point is located at zero temperature, since the SK model does not exhibit a phase transition in this regime. To investigate this possibility, we study the Bethe-lattice spin glass (BLSG) at T=0, which displays a genuine field-driven transition absent in the SK model. By analyzing the exact RSB equations, we show that the BLSG exhibits qualitatively different physics: replica symmetry breaking does not occur homogeneously across the system. Near the transition, only a small fraction of spins display RSB, while the rest remain replica-symmetric even within the glassy phase. We show that this coexistence of frozen and fluctuating spins is a finite-connectivity effect also present in the random-field Ising model, where it underlies avalanche dynamics and heterogeneous responses. Using a loop expansion around the Bethe-lattice solution via a RG approach, we identify an upper critical dimension D_U=8 for the spin glass problem, distinct from the classical D_U = 6, predicted by finite-temperature replica field theory, signaling the emergence of a new non-perturbative fixed point and providing the foundation for an epsilon-expansion around the Bethe solution. The thesis also addresses the computation of finite-size correction in disordered systems. Through the cavity method, we computed the average optimal cost and finite-size corrections of a family of random-link matching problems on sparse graphs, relating the corrections to the cost to the existence of rare geometrical structures in the graph.