Phase transitions in random graphs

V. E. Stepanov

Teoriâ veroâtnostej i ee primeneniâ, Tome 15 (1970) no. 2, pp. 200-215

Résumé

To each subgraph $G$ of a complete graph of $m$ vertices statistical weight $w(G)=x^kh^n$ is assigned, where $k=k(G)$ is the number of components and $n=n(G)$ is the number of edges of graph $G$; $x$ and $h>0$. A random graph $\mathscr G_m(x\mid h)$ is defined by the condition that $\mathbf P(\mathscr G_m(x\mid h)=G)=Z_m^{-1}(x\mid h)w(G)$, where $Z_m(x\mid h)$ is a necessary normalizing coefficient. It is proved that there exists a limit $$ \lim_{m\to\infty}\frac1m\ln Z_m(x\mid y/m)=\chi(x,y). $$ Limit values of density $$ \rho(x,y)=\lim_{m\to\infty}\frac1m\mathbf En(\mathscr G_m(x\mid y/m)) $$ and disconnectedness $$ \varkappa(x,y)=\lim_{m\to\infty}\frac1m\mathbf Ek(\mathscr G_m(x\mid y/m)) $$ of random graph $\mathscr G_m(x\mid y/m)$ are expressed in terms of partial derivatives of $\chi(x,y)$. An investigation of functions $\rho(x,y)$ and $\varkappa(x,y)$ discovers a surprising analogy of the behaviour of these functions to the behaviour of isotherms of physical systems considered in statistical physics. Connections between some properties of functions $\rho(x,y)$ and $\varkappa(x,y)$ and the structure of random graph $\mathscr G_m(x\mid y/m)$ are under investigation.