Consider a network or graph G consisting of a large number N of nodes, each distinct pair of which may or may not be connected by an undirected edge. Think of each of the (N[N-1]/2 unordered) pairs of nodes as a point in a space which may or may not be `occupied' by an edge. We will treat edges as one treats particles in equilibrium statistical mechanics: we will assume that a graph G is a random object in a fixed space of `volume' N(N-1)/2, and will study a two-parameter family of sets of graphs G in analogy with the microcanonical ensemble in statistical mechanics.

In the microcanonical ensemble of statistical mechanics the two parameters are (the dynamical invariants) particle density and energy density, and one studies the partition function Z(d,h;V) which is the volume of the set of configurations of particle density d and energy density h, in a space of fixed volume V [FR]. Z is appropriately normalized as the entropy density s(d,h;V) = (1/V)ln(Z).

The analogue of the particle density for networks will be the edge density d(G) of G. We will take as the energy of G the count of some subgraph; the Strauss model would use the number of triangles in G, though any subgraph H with 2 or more edges would be acceptable. We normalize this energy so that the `energy density' h(G) of the complete graph is 1. So after choosing some finite graph H for use as an energy, we study the entropy s(d,h;N)=[2/N(N-1)]ln(Z).

The interesting features of statistical mechanics come from the interference or tension between the two parameters or densities. For instance, if at constant energy density the particle density is raised high enough, it is typical that the system of particles comes to represent a highly structured crystal, while at low density it represents a disordered gas; see our discussion on hard sphere models [R]. The physical properties of the material are computable from partial derivatives of the entropy [C], so there is obvious interest in parameter values where such derivatives are discontinuous or diverge, which are hallmarks of phase transitions [FR]. Thinking of a large network as a material, one might model it as above if indeed the choice of H for `energy' is reasonable. This is presumably not the case for such networks, so we think of these models as purely mathematical, determining what a typical large, constrained graph is like and exploring the world of phases and phase transitions more generally. Assuming this we have carried out the above to some extent, following the pioneering work of Chatterjee and Diaconis [CD]. More specifically, we have worked in both the grand canonical ensemble and the microcanonical ensemble, and used the large deviation principle of Chatterjee and Varadhan [CV] and formalism of limit graphs developed by Lovász et al [L] to prove various phase transitions in dense networks similar to the liquid/gas [RY], [KRRS1], [KRRS2], and fluid/solid [AR], [RRS1], [RS1], [RS2], [KRRS1], [KRRS3], [NRS1], [NRS2], [NRS3] [NRS4] transitions in molecular materials. (As opposed to statistical mechanics here the microcanonical ensemble plays a privileged role, with a loss of information in the grand canonical ensemble [RS1].) The structure that appears in the `solid' phase of dense networks is balanced multipartite, and the analogue of the `fluid' phase seems to be a monotone state [KRRS1]. The solid/fluid transition is discussed in some depth in [RRS2], [KRRS3], and indirectly in [RRS3], [NRS4].

There is a less-advanced analogue of the above ideas, concerning large permutations, in [KKRW], and an expository article on all the above in [R2].

References

[AR] D. Aristoff and C. Radin, Emergent structures in large networks, J. Appl. Probab. 50(2013) 883-888.

[C] H.G. Callen, Thermodynamics, John Wiley, New York, 1960.

[CD] S. Chatterjee and P. Diaconis, Estimating and understanding exponential random graph models, Ann. Statist. 41 (2013) 2428-2461.

[CV] S. Chatterjee and S.R.S. Varadhan, The large deviation principle for the Erdos-R{e}nyi random graph, Eur. J. Comb. 32 (2011) 1000-1017.

[FR] M. Fisher and C. Radin, Definition of Thermodynamic Phases and Phase Transitions, AIM workshop, (2006), http://www.aimath.org/WWN/phasetransition/Defs16.pdf.

[KRRS1] R. Kenyon, C. Radin, K. Ren and L. Sadun, Multipodal structure and phase transitions in large constrained graphs, J. Stat. Phys. (2017) 233-258 doi:10.1007/s10955-017-1804-0

[KRRS2] R. Kenyon, C. Radin, K. Ren and L. Sadun, Bipodal structure in oversaturated random graphs, Int. Math. Res. Notices 2018(2016) 1009-1044

[KRRS3] R. Kenyon, C. Radin, K. Ren and L. Sadun, The phases of large networks with edge and triangle constraints, J. Phys. A: Math. Theor. 50(2017) 435001.

[KKRW] R. Kenyon, D. Král’, C. Radin and P. Winkler Permutations with fixed pattern densities, Random Structures Algorithms, DOI: 10.1002/rsa.20882.

[L] L. Lovász, Large networks and graph limits, American Mathematical Society, Providence, 2012.

[NRS1] J. Neeman, C. Radin and L. Sadun, Phase transitions in finite random networks, J Stat Phys 181 (2020) 305-328.

[NRS2] J. Neeman, C. Radin and L. Sadun, Moderate deviations in cycle count, arxiv:2101.08249.

[NRS3] J. Neeman, C. Radin and L. Sadun, Typical large graphs with given edge and triangle densities, arxiv:2110.14052, online first, in Probab. Theory Relat. Fields.

[NRS4] J. Neeman, C. Radin and L. Sadun, Existence of a symmetric bipodal phase in the edge-triangle model, arxiv:2211.10498.

[R] C. Radin, The "most probable" sphere packings, and models of soft matter, http://www.ma.utexas.edu/users/radin/spheres.html.

[R2] C. Radin, Phases in large combinatorial systems, Ann. Inst. H. Poincaré D 5(2018) 287-308.

[RRS1] C. Radin, K. Ren and L. Sadun, The asymptotics of large constrained graphs, J. Phys. A: Math. Theor. 47 (2014) 175001 color.pdf    grayscale.pdf

[RS1] C. Radin and L. Sadun, Phase transitions in a complex network, J. Phys. A: Math. Theor. 46 (2013) 305002.

[RS2] C. Radin and L. Sadun, Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015) 853-865.

[RY] C. Radin and M. Yin, Phase transitions in exponential random graphs, Ann. Appl. Probab. 23(2013) 2458-2471.

[RRS2] C. Radin, K. Ren and L. Sadun, A symmetry breaking transition in the edge/triangle network model, Ann. Inst. H. Poincaré D 5(2018) 251-286.

[RRS3] C. Radin, K. Ren and L. Sadun, Surface effects in dense random graphs with sharp edge constraint, arXiv:1709.01036v1 preprint