Random graphs: models and asymptotic characteristics
From MaRDI portal
Publication:5262204
DOI10.1070/RM2015v070n01ABEH004936zbMath1408.05116OpenAlexW2337348193MaRDI QIDQ5262204
M. E. Zhukovskii, Andrei M. Raigorodskii
Publication date: 13 July 2015
Published in: Russian Mathematical Surveys (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1070/rm2015v070n01abeh004936
Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Basic properties of first-order languages and structures (03C07)
Related Items
Spectra of short monadic sentences about sparse random graphs ⋮ On limit points of spectra of the random graph first-order properties ⋮ Bounded quantifier depth spectra for random graphs ⋮ \( \gamma \)-variable first-order logic of preferential attachment random graphs ⋮ When does the zero-one \(k\)-law fail? ⋮ Universal zero-one \(k\)-law ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Small subgraphs and their extensions in a random distance graph ⋮ Limit points of spectra for first-order properties of random hypergraphs ⋮ Monadic second-order properties of very sparse random graphs ⋮ Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations ⋮ Diameters of random distance graphs ⋮ Quantifier alternation in first-order formulas with infinite spectra ⋮ The median of the number of simple paths on three vertices in the random graph ⋮ Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph ⋮ First order sentences about random graphs: small number of alternations ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs ⋮ First-order properties of bounded quantifier depth of very sparse random graphs ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ Logical laws for existential monadic second-order sentences with infinite first-order parts ⋮ First-order zero-one law for the uniform model of the random graph ⋮ Maximum sparse induced subgraphs of the binomial random graph with given number of edges ⋮ Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false ⋮ On the distribution of the maximum \(k\)-degrees of the binomial random graph ⋮ A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences ⋮ On first-order definitions of subgraph isomorphism properties ⋮ On the convergence of probabilities of first-order sentences for recursive random graph models ⋮ First-order and monadic properties of highly sparse random graphs ⋮ MSO 0-1 law for recursive random trees ⋮ Existential monadic second order convergence law fails on sparse random graphs ⋮ The size of a maximum subgraph of the random graph with a given number of edges ⋮ Zero-one laws for \(k\)-variable first-order logic of sparse random graphs ⋮ Infinite spectra of first-order properties for random hypergraphs ⋮ Zero-one laws for sentences with \(k\) variables ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ \(\gamma\)-variable first-order logic of uniform attachment random graphs
