Random graphs: models and asymptotic characteristics

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

Full description

Saved in:
Bibliographic Details
Published in:Russian mathematical surveys 2015-01, Vol.70 (1), p.33-81
Main Authors: Zhukovskii, M. E., Raigorodskii, A. M.
Format: Article
Language:English
Subjects:
Asymptotic properties
Coding
Combinatorial analysis
distance graphs
first-order properties
Graphs
limit theorems
Mathematical models
random graphs
zero-one laws
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0036-0279
1468-4829
DOI:10.1070/RM2015v070n01ABEH004936