Emergence and Phase Transitions in Uniform Random Graphs

A volume on emergent features of large graphs, proving phases and phase transitions through new techniques of nonconvex optimization.

This book for applied mathematicians and scientists focuses on structure that emerges in systems of many components. It uses ideas from statistical mechanics to prove the emergence of structure, including many phase transitions, in a setting where this was not previously possible.This book studies the emergence of large-scale structure from small structures in the context of random graphs. Typical large graphs with fixed edge density e and triangle density t are described by a 'graphon' that solves a constrained optimization problem. Proofs are provided of the existence of infinitely many open sets ('phases') in the (e,t) plane where the optimal graphon is unique and varies analytically with (e,t). The optimal graphons take a simple form, with symmetries that vary from phase to phase, indicating an emergent self-organization of the corresponding graphs. Besides being of independent interest in the theory of random graphs, extremal combinatorics and the calculus of variations, this provides a rigorous framework for studying ideas from statistical physics that have never been proven in their original setting. The techniques presented in this book can serve as a guide for optimization problems in other fields.