Geodesic
The Median of the Number of Simple Paths on Three Vertices in the Random Graph
Matematičeskie zametki, Tome 107 (2020) no. 1, pp. 49-58.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, Ramanujan function.
Mots-clés : Poisson limit theorem 
@article{MZM_2020_107_1_a4,
     author = {M. E. Zhukovskii},
     title = {The {Median} of the {Number} of {Simple} {Paths} on {Three} {Vertices} in the {Random} {Graph}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {49--58},
     publisher = {mathdoc},
     volume = {107},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_107_1_a4/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
TI  - The Median of the Number of Simple Paths on Three Vertices in the Random Graph
JO  - Matematičeskie zametki
PY  - 2020
SP  - 49
EP  - 58
VL  - 107
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_107_1_a4/
LA  - ru
ID  - MZM_2020_107_1_a4
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%T The Median of the Number of Simple Paths on Three Vertices in the Random Graph
%J Matematičeskie zametki
%D 2020
%P 49-58
%V 107
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_107_1_a4/
%G ru
%F MZM_2020_107_1_a4
M. E. Zhukovskii. The Median of the Number of Simple Paths on Three Vertices in the Random Graph. Matematičeskie zametki, Tome 107 (2020) no. 1, pp. 49-58. http://geodesic.mathdoc.fr/item/MZM_2020_107_1_a4/

[1] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[2] A. N. Egorova, M. E. Zhukovskii, “Disproof of the zero-one law for existential monadic properties of a spare binomial random graph”, Dokl. Math., 99:1 (2019), 68–70 | DOI | Zbl

[3] S. Janson, T. Łuczak, A. Ruciński, Random Graphs, Wiley-Interscience, New York, 2000 | MR | Zbl

[4] A. S. Razafimahatrata, M. Zhukovskii, “Zero-one laws for $k$-variable first-order logic of sparse random graphs”, Discrete Appl. Math., 2019 (to appear) | DOI

[5] M. E. Zhukovskii, A. M. Raigorodskii, “Sluchainye grafy: modeli i predelnye kharakteristiki”, UMN, 70:1 (421) (2015), 35–88 | DOI | MR | Zbl

[6] S. Kargaltsev, D. Shabanov, T. Shaikheeva, “Two values of the chromatic number of a sparse random graph”, Acta Math. Univ. Comenianae, 88:3 (2019), 849–854

[7] A. Ruciński, A. Vince, “Balanced graphs and the problem of subgraphs of a random graph”, Congr. Numer., 49 (1985), 181–190 | MR | Zbl

[8] B. Bollobás, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206 | DOI | MR | Zbl

[9] A. V. Burkin, M. E. Zhukovskii, “Malye podgrafy i ikh rasshireniya v sluchainom distantsionnom grafe”, Matem. sb., 209:2 (2018), 22–46 | DOI | Zbl

[10] S. D. Tilga, “O raspredelenii malykh podgrafov v sluchainom grafe Bakli–Ostgusa”, Izv. RAN. Ser. matem., 81:2 (2017), 161–214 | DOI | MR | Zbl

[11] J. H. Kim, B. Sudakov, V. Vu, “Small subgraphs of random regular graphs”, Discrete Math., 307:15 (2007), 1961–1967 | MR | Zbl

[12] S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random Kneser graphs”, Acta Math. Univ. Comenianae, 88:3 (2019), 861–865

[13] K. P. Choi, “On the medians of Gamma distributions and an equation of Ramanujan”, Proc. Amer. Math. Soc., 121:1 (1994), 245–251 | DOI | MR | Zbl

[14] S. Ramanujan, “Some properties of Bernoulli's numbers”, J. Indian Math. Soc., 3 (1911), 219–234 | Zbl

[15] G. Szegő, “Űber einige von S. Ramanujan Gestellte Aufgaben”, J. London Math. Soc., 3:3 (1928), 225–232 | DOI | MR | Zbl

[16] G. N. Watson, “Theorems stated by Ramanujan (V): Approximations connected with $e^x$”, Proc. London Math. Soc. (2), 29:4 (1927), 293–308 | MR

[17] K. Hamza, “The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions”, Statist. Probab. Lett., 23:1 (1995), 21–25 | DOI | MR | Zbl

[18] R. Kaas, J. M. Buhrman, “Mean, median and mode in binomial distributions”, Statist. Neerlandica, 34:1 (1980), 13–18 | DOI | MR | Zbl

[19] O. Riordan, L. Warnke, “The Janson inequalities for general up-sets”, Random Structures Algorithms, 46:2 (2015), 391–395 | DOI | MR | Zbl

[20] W. Feller, “On the normal approximation to the binomial distribution”, Ann. Math. Statistics, 16 (1945), 319–329 | DOI | MR | Zbl

[21] B. C. Berndt, R. A. Rankin, Ramanujan: Letters and Commentary, Amer. Math. Soc., Providence, RI, 1995 | Zbl

[22] P. Flajolet, P. J. Grabner, P. Kirschenhofer, H. Prodinger, “On Ramanujan's $Q$-function”, J. Comput. Appl. Math., 58:1 (1995), 103–116 | DOI | MR | Zbl

[23] S. E. Alm, “Monotonicity of the difference between median and mean of gamma distributions and of a related Ramanujan sequence”, Bernoulli, 9:2 (2003), 351–371 | DOI | MR | Zbl

[24] H. Alzer, “On Ramanujan's inequalities for $\exp(k)$”, J. London Math. Soc. (2), 69:3 (2004), 639–656 | DOI | MR | Zbl

[25] K. Jodgeo, S. M. Samuels, “Monotone convergence of binomial probabilities and a generalization of Ramanujan's equation”, Ann. of Math. Stat., 39:4 (1968), 1191–1195 | DOI