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.
Citation:
V. E. Stepanov, “Phase transitions in random graphs”, Teor. Veroyatnost. i Primenen., 15:2 (1970), 200–215; Theory Probab. Appl., 15:2 (1970), 187–203
\Bibitem{Ste70}
\by V.~E.~Stepanov
\paper Phase transitions in random graphs
\jour Teor. Veroyatnost. i Primenen.
\yr 1970
\vol 15
\issue 2
\pages 200--215
\mathnet{http://mi.mathnet.ru/tvp1705}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=270407}
\zmath{https://zbmath.org/?q=an:0225.90048|0213.45901}
\transl
\jour Theory Probab. Appl.
\yr 1970
\vol 15
\issue 2
\pages 187--203
\crossref{https://doi.org/10.1137/1115027}
Linking options:
https://www.mathnet.ru/eng/tvp1705
https://www.mathnet.ru/eng/tvp/v15/i2/p200
This publication is cited in the following 13 articles:
Sergey Dovgal, Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, Stephan Wagner, “The birth of the strong components”, Random Struct Algorithms, 64:2 (2024), 170
Cecilia Holmgren, Lecture Notes in Computer Science, 12708, Discrete Geometry and Mathematical Morphology, 2021, 20
Wei Huang, Pengcheng Hou, Junfeng Wang, Robert M. Ziff, Youjin Deng, “Critical percolation clusters in seven dimensions and on a complete graph”, Phys. Rev. E, 97:2 (2018)
A. A. Grusho, E. E. Timonina, “Model sluchainykh grafov dlya opisaniya vzaimodeistvii v seti”, Inform. i ee primen., 6:4 (2012), 57–60
Ramon Ferrer i Cancho, “When language breaks into pieces A conflict between communication through isolated signals and language”, Biosystems, 84:3 (2006), 242
Alexander Sapozhenko, Lecture Notes in Computer Science, 3777, Stochastic Algorithms: Foundations and Applications, 2005, 1
Boris Pittel, “On the Largest Component of the Random Graph at a Nearcritical Stage”, Journal of Combinatorial Theory, Series B, 82:2 (2001), 237
B. Pittel, R. Tungol, “A phase transition phenomenon in a random directed acyclic graph”, Random Struct. Alg., 18:2 (2001), 164
Tomasz Łuczak, “Phase transition phenomena in random discrete structures”, Discrete Mathematics, 136:1-3 (1994), 225
Tomasz Łuczak, Boris Pittel, “Components of Random Forests”, Combinator. Probab. Comp., 1:1 (1992), 35
V. E. Stepanov, “Some Features of Structure of Random Graphs in the Neighbourhood of Breakdown Point”, Theory Probab. Appl., 32:4 (1987), 573–594
V. F. Kolčin, “On the behaviour of a random graph near a critical point”, Theory Probab. Appl., 31:3 (1987), 439–451
Michał Karoński, “A review of random graphs”, Journal of Graph Theory, 6:4 (1982), 349