Lower bounds for Ramsey numbers as a statistical physics problem

Ramsey's theorem, concerning the guarantee of certain monochromatic patterns in large enough edge-coloured complete graphs, is a fundamental result in combinatorial mathematics. In this work, we highlight the connection between this abstract setting and a statistical physics problem. Specifically, we design a classical Hamiltonian that favours configurations in a way to establish lower bounds on Ramsey numbers. As a proof of principle we then use Monte Carlo methods to obtain such lower bounds, finding rough agreement with known literature values in a few cases we investigated. We discuss numerical limitations of our approach and indicate a path towards the treatment of larger graph sizes.

Automated summary

This study investigates the connection between Ramsey's theorem and a statistical physics problem. A classical Hamiltonian is designed to establish lower bounds on Ramsey numbers. Monte Carlo methods are used to obtain consistent results, and the limitations and potential extensions of the approach are discussed.