Loading [MathJax]/jax/output/SVG/config.js
Teoriya Veroyatnostei i ee Primeneniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Teor. Veroyatnost. i Primenen.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Teoriya Veroyatnostei i ee Primeneniya, 1970, Volume 15, Issue 2, Pages 200–215 (Mi tvp1705)  

This article is cited in 13 scientific papers (total 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, Volume 15, Issue 2, Pages 187–203
DOI: https://doi.org/10.1137/1115027
Bibliographic databases:
Language: Russian
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
Citation in format AMSBIB
\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:
    1. Sergey Dovgal, Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, Stephan Wagner, “The birth of the strong components”, Random Struct Algorithms, 64:2 (2024), 170  crossref
    2. Cecilia Holmgren, Lecture Notes in Computer Science, 12708, Discrete Geometry and Mathematical Morphology, 2021, 20  crossref
    3. 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)  crossref
    4. A. A. Grusho, E. E. Timonina, “Model sluchainykh grafov dlya opisaniya vzaimodeistvii v seti”, Inform. i ee primen., 6:4 (2012), 57–60  mathnet
    5. Ramon Ferrer i Cancho, “When language breaks into pieces A conflict between communication through isolated signals and language”, Biosystems, 84:3 (2006), 242  crossref
    6. Alexander Sapozhenko, Lecture Notes in Computer Science, 3777, Stochastic Algorithms: Foundations and Applications, 2005, 1  crossref
    7. Boris Pittel, “On the Largest Component of the Random Graph at a Nearcritical Stage”, Journal of Combinatorial Theory, Series B, 82:2 (2001), 237  crossref
    8. B. Pittel, R. Tungol, “A phase transition phenomenon in a random directed acyclic graph”, Random Struct. Alg., 18:2 (2001), 164  crossref
    9. Tomasz Łuczak, “Phase transition phenomena in random discrete structures”, Discrete Mathematics, 136:1-3 (1994), 225  crossref
    10. Tomasz Łuczak, Boris Pittel, “Components of Random Forests”, Combinator. Probab. Comp., 1:1 (1992), 35  crossref
    11. V. E. Stepanov, “Some Features of Structure of Random Graphs in the Neighbourhood of Breakdown Point”, Theory Probab. Appl., 32:4 (1987), 573–594  mathnet  mathnet  crossref  isi
    12. V. F. Kolčin, “On the behaviour of a random graph near a critical point”, Theory Probab. Appl., 31:3 (1987), 439–451  mathnet  mathnet  crossref  isi
    13. Michał Karoński, “A review of random graphs”, Journal of Graph Theory, 6:4 (1982), 349  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Теория вероятностей и ее применения Theory of Probability and its Applications
    Statistics & downloads:
    Abstract page:415
    Full-text PDF :275
    First page:1
     
      Contact us:
    math-net2025_04@mi-ras.ru
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025