Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Zametki, 2020, Volume 107, Issue 1, Pages 49–58 (Mi mz12043)  

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

M. E. Zhukovskii

Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region

Abstract: We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer $b$ and a sufficiently large number $n$ of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is $b$ decreases with $n$. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large $n$.

Keywords: random graph, strictly balanced graphs, simple paths, medians, Poisson limit theorem, Ramanujan function.

Funding Agency Grant Number
Russian Science Foundation 16-11-10014
This work was supported by the Russian Science Foundation under grant 16-11-10014.


DOI: https://doi.org/10.4213/mzm12043

Full text: PDF file (498 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Mathematical Notes, 2020, 107:1, 54–62

Bibliographic databases:

UDC: 519.175.4
Received: 15.04.2018
Revised: 05.02.2019

Citation: M. E. Zhukovskii, “The Median of the Number of Simple Paths on Three Vertices in the Random Graph”, Mat. Zametki, 107:1 (2020), 49–58; Math. Notes, 107:1 (2020), 54–62

Citation in format AMSBIB
\Bibitem{Zhu20}
\by M.~E.~Zhukovskii
\paper The Median of the Number of Simple Paths on Three Vertices in the Random Graph
\jour Mat. Zametki
\yr 2020
\vol 107
\issue 1
\pages 49--58
\mathnet{http://mi.mathnet.ru/mz12043}
\crossref{https://doi.org/10.4213/mzm12043}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=4045686}
\elib{https://elibrary.ru/item.asp?id=43258479}
\transl
\jour Math. Notes
\yr 2020
\vol 107
\issue 1
\pages 54--62
\crossref{https://doi.org/10.1134/S000143462001006X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000519555100006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85081038363}


Linking options:
  • http://mi.mathnet.ru/eng/mz12043
  • https://doi.org/10.4213/mzm12043
  • http://mi.mathnet.ru/eng/mz/v107/i1/p49

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Математические заметки Mathematical Notes
    Number of views:
    This page:171
    References:9
    First page:6

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021