Emergence And Phase Transitions In Uniform Random Graphs

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.

Charles Radin is a professor at the University of Texas at Austin. He received a Ph.D. in physics at the University of Rochester. He was previously a postdoc under physicist Arthur Wightman and mathematicians Mark Kac and Richard Kadison. His work is published in both mathematics and physics journals, and includes experiments on granular matter coauthored with Harry Swinney.

Lorenzo Sadun is Marian Harris Thornberry Centennial Professor at the University of Texas at Austin. He received his Ph.D. from UC Berkeley and was previously a postdoc at Caltech and NYU (Courant). He is the author of more than 100 papers and five books on mathematical physics and related fields. His research interests include aperiodic order (tiling dynamical systems, especially topological dynamics) and random graphs.