RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1970 Volume 15, Issue 2, Pages 200–215 (Mi tvp1705)

This article is cited in 13 papers

Phase transitions in random graphs

V. E. Stepanov

Moscow

Abstract: 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.

Received: 17.03.1969


 English version:
Theory of Probability and its Applications, 1970, 15:2, 187–203

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024