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

 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
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} 

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

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Number of views: This page: 171 References: 9 First page: 6