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

被引：0
作者：
M. E. Zhukovskii
机构：
[1] Moscow Institute of Physics and Technology (State University),
来源：
Mathematical Notes | 2020年 / 107卷
关键词：
random graph; strictly balanced graphs; simple paths; medians; Poisson limit theorem; Ramanujan function;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：54 / 62
页数：8
相关论文
共 41 条
[1]  
Egorova A N(2019)Disproof zero-one law for existential monadic properties of a spare binomial random graph Dokl. Math. 99 68-70
[2]  
Zhukovskii M E(2015)Random graphs: models and asymptotic characteristics Uspekhi Mat. Nauk 70 33-81
[3]  
Zhukovskii M E(2015)Two values of the chromatic number of a sparse random graph Russian Math. Surveys 70 35-88
[4]  
Raigorodskii A M(2019)Balanced graphs and the problem of subgraphs of a random graph Acta Math. Univ. Comenianae 88 849-854
[5]  
Zhukovskii M E(1985)Threshold functions for small subgraphs Congr. Numer. 49 181-190
[6]  
Raigorodskii A M(1981)Small subgraphs and their extensions in a random distance graph Math. Proc. Cambridge Philos. Soc. 90 197-206
[7]  
Kargaltsev S(2018)Distribution of small subgraphs in Buckley–Osthus random graphs Mat. Sb. 209 22-46
[8]  
Shabanov D(2018)Small subgraphs of random regular graphs Sb. Math. 209 163-186
[9]  
Shaikheeva T(2017)Sharp bounds for the chromatic number of random Kneser graphs Izv. Ross. Akad. Nauk Ser. Mat. 81 161-214
[10]  
Ruciński A(2017)On the medians of Gamma distributions and an equation of Ramanujan Izv. Math. 81 391-443
12345