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, 1969, Volume 14, Issue 3, Pages 393–420 (Mi tvp1195)  

This article is cited in 21 scientific papers (total in 21 papers)

Combinatorial algebra and random graphs

V. E. Stepanov

Moscow
Abstract: Let AA be a finite set of vertices and λa>0λa>0 be the intensity of the vertex aAaA. A random time-dependent graph GL(At) is defined as follows: at time t=0 all the vertices are isolated; the probability that at time t>0 vertices a and b are connected equals 1eλaλbt, and the connections appear independently for different pairs, let PL(At) be the probability that the random graph GL(At) is connected.
In the paper, an explicit expression for PL(At) is found, a number of combinatorial relations including the probabilities PL(At) is obtained, and it is proved that if the set of vertices A, intensities of vertices λa, and time t are changed in a certain way, then, under some conditions, PL(At)eμ(At)1, where
μ(At)=aAexp{tλaL(A)}andL(A)=aAλa.
Received: 05.11.1967
English version:
Theory of Probability and its Applications, 1969, Volume 14, Issue 3, Pages 373–399
DOI: https://doi.org/10.1137/1114052
Bibliographic databases:
Language: Russian
Citation: V. E. Stepanov, “Combinatorial algebra and random graphs”, Teor. Veroyatnost. i Primenen., 14:3 (1969), 393–420; Theory Probab. Appl., 14:3 (1969), 373–399
Citation in format AMSBIB
\Bibitem{Ste69}
\by V.~E.~Stepanov
\paper Combinatorial algebra and random graphs
\jour Teor. Veroyatnost. i Primenen.
\yr 1969
\vol 14
\issue 3
\pages 393--420
\mathnet{http://mi.mathnet.ru/tvp1195}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=263129}
\zmath{https://zbmath.org/?q=an:0239.05124}
\transl
\jour Theory Probab. Appl.
\yr 1969
\vol 14
\issue 3
\pages 373--399
\crossref{https://doi.org/10.1137/1114052}
Linking options:
  • https://www.mathnet.ru/eng/tvp1195
  • https://www.mathnet.ru/eng/tvp/v14/i3/p393
  • This publication is cited in the following 21 articles:
    1. Nicola Galli, “Average Costs of a Graph Exploration: Upper and Lower Bounds”, Journal of Algorithms, 34:1 (2000), 148  crossref
    2. David J. Aldous, Boris Pittel, “On a random graph with immigrating vertices: Emergence of the giant component”, Random Struct. Alg., 17:2 (2000), 79  crossref
    3. Brian D. Jones, Boris G. Pittel, Joseph S. Verducci, “Tree and forest weights and their application to nonuniform random graphs”, Ann. Appl. Probab., 9:1 (1999)  crossref
    4. Michael O. Ball, Charles J. Colbourn, J. Scott Provan, Handbooks in Operations Research and Management Science, 7, Network Models, 1995, 673  crossref
    5. M. Lomonosov, “On Monte Carlo Estimates in Network Reliability”, Prob. Eng. Inf. Sci., 8:2 (1994), 245  crossref
    6. Philippe Blanchard, Georg F. Bolz, Tyll Krüger, Lecture Notes in Physics, 355, Dynamics and Stochastic Processes Theory and Applications, 1990, 55  crossref
    7. Lajos Takács, “A generalization of an inequality of Stepanov”, Journal of Combinatorial Theory, Series B, 48:2 (1990), 289  crossref
    8. A. F. Ronzhyn, “Goodness-of-Fit Test for Generalized Urn Models Based on Divisible Statistics”, Theory Probab. Appl., 33:1 (1988), 86–95  mathnet  mathnet  crossref  isi
    9. A. D. Korshunov, “The main properties of random graphs with a large number of vertices and edges”, Russian Math. Surveys, 40:1 (1985), 121–198  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    10. Béla Bollobás, Andrew Thomason, North-Holland Mathematics Studies, 118, Random Graphs '83, Based on lectures presented at the 1st Poznań Seminar on Random Graphs, 1985, 47  crossref
    11. W. Kordecki, “Some recurrence formulas for probability of connectednes of random graphs”, Theory Probab. Appl., 30:3 (1986), 630–632  mathnet  mathnet  crossref  isi
    12. Michał Karoński, “A review of random graphs”, Journal of Graph Theory, 6:4 (1982), 349  crossref
    13. Donald E. Knuth, Arnold Schönhage, “The expected linearity of a simple equivalence algorithm”, Theoretical Computer Science, 6:3 (1978), 281  crossref
    14. Ove Frank, “Survey sampling in graphs”, Journal of Statistical Planning and Inference, 1:3 (1977), 235  crossref
    15. Yu. D. Burtin, “On extreme metric parameters of a random graph, I”, Theory Probab. Appl., 19:4 (1975), 710–725  mathnet  mathnet  crossref
    16. I. N. Kovalenko, “Theory of random graphs”, Cybern Syst Anal, 7:4 (1974), 575  crossref
    17. G. I. Ivchenko, “The Strength of Connectivity of a Random Graph”, Theory Probab. Appl., 18:2 (1973), 396–403  mathnet  mathnet  crossref
    18. A. K. Kel'mans, “Asymptotic formulas for the probability of k-connectedness of random graphs”, Theory Probab. Appl., 17:2 (1973), 243–254  mathnet  mathnet  crossref
    19. V. E. Stepanov, “Random mappings with one attracting center”, Theory Probab. Appl., 16:1 (1971), 155–162  mathnet  mathnet  crossref
    20. V. E. Stepanov, “Phase transitions in random graphs”, Theory Probab. Appl., 15:2 (1970), 187–203  mathnet  mathnet  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:652
    Full-text PDF :344
    First page:5
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025