Multipodal Phases in Dense Networks

Radin, C. UT Austin, USA

We consider asymptotically large, dense, simple graphs constrained in both their edge and triangle densities, and study the associated entropy, the goal being to determine the structure of `exponentially most' graphs with given variable constraints. We have proven there is a sharp phase transition between graphs of large versus low edge density E, at any fixed triangle density T, when T=E^3. Simulations show that the high edge density regime is further broken up into well-defined regions which are overwhelmingly dominated by graphs of very simple `multipodal' structure, simple modifications of balanced multipartite graphs. This is joint work with Kui Ren and Lorenzo Sadun.