Abstract:
This is a survey of known results related to the asymptotic behaviour of the probabilities of first-order properties of random graphs. The results presented in this paper are concerned with zero-one laws for properties of random graphs. Emphasis is placed on the Erdős–Rényi model of a random graph. Also considered are some generalizations of this model motivated by various problems in the theory of coding and combinatorial geometry.
Bibliography: 65 titles.
This work was supported by the Russian Foundation for Basic Research (projects nos. 13-01-00612 and 15-01-00350) and by the Council of the President of the Russian Federation for the Support of Young Russian Scientists and Leading Scientific Schools, grants МД-6277.2013.1, MK-2184.2014.1, and НШ-2519.2012.1.
This publication is cited in the following 47 articles:
S.N. Popova, “Bounded quantifier depth spectrum for random uniform hypergraphs”, Discrete Applied Mathematics, 345 (2024), 215
Yury Yarovikov, Maksim Zhukovskii, “Spectrum of FO Logic with Quantifier Depth 4 is Finite”, ACM Trans. Comput. Logic, 25:2 (2024), 1
J. C. Buitrago Oropeza, “Maximum Induced Trees in Sparse Random Graphs”, Dokl. Math., 109:2 (2024), 167
J. C. Buitrago Oropeza, “Maximum induced trees in sparse random graphs”, Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, 516 (2024), 83
Farid Nahli, Alexander Paramonov, Naglaa F. Soliman, Hussah Nasser AlEisa, Reem Alkanhel, Ammar Muthanna, Abdelhamied A. Ateya, “Novel Path Counting-Based Method for Fractal Dimension Estimation of the Ultra-Dense Networks”, 36, no. 1, 2023, 561
A.D. Matushkin, S.N. Popova, “Strictly balanced uniform hypergraphs and generalizations of Zero-One Law”, Discrete Mathematics, 345:6 (2022), 112835
M. E. Zhukovskii, E. D. Kudryavtsev, M. V. Makarov, A. S. Shlychkova, “Logical complexity of induced subgraph isomorphism for certain families of graphs”, Sb. Math., 212:4 (2021), 517–530
Malyshkin Y.A., Zhukovskii M.E., “Mso 0-1 Law For Recursive Random Trees”, Stat. Probab. Lett., 173 (2021), 109061
Popova S.N., “Limit Points of Spectra For First-Order Properties of Random Hypergraphs”, Discret Appl. Math., 293 (2021), 134–142
Juan Carlos Buitrago Oropeza, “Zero-one laws for random k-partite
graphs”, Moscow J. Comb. Number Th., 10:4 (2021), 315
Ivan M. Buchinskiy, Alexander V. Treier, “On first order definability of equationally noetherian graphs”, J. Phys.: Conf. Ser., 1901:1 (2021), 012032
Dmitry Kamaldinov, Arkadiy Skorkin, Maksim Zhukovskii, “Maximum sparse induced subgraphs of the binomial random graph with given number of edges”, Discrete Mathematics, 344:2 (2021), 112205
M. E. Zhukovskii, “The Median of the Number of Simple Paths on Three Vertices in the Random Graph”, Math. Notes, 107:1 (2020), 54–62
D. A. Migov, “Dekompozitsiya seti po secheniyam pri raschete ee nadezhnosti”, PDM, 2020, no. 47, 62–86
A. Egorova, M. Zhukovskii, “Existential monadic second order convergence law fails on sparse random graphs”, Eur. J. Comb., 83 (2020), UNSP 103017
M. E. Zhukovskii, N. M. Sveshnikov, “First-order zero-one law for the uniform model of the random graph”, Sb. Math., 211:7 (2020), 956–966
A. S. Razafimahatratra, M. Zhukovskii, “Zero-one laws for k-variable first-order logic of sparse random graphs”, Discret Appl. Math., 276:SI (2020), 121–128
M. E. Zhukovskii, “Logical laws for short existential monadic second-order sentences about graphs”, J. Math. Log., 20:2 (2020), 2050007
Citation in format AMSBIB
Contact us: