Convergence in homogeneous random graphs

DOI10.1002/RSA.3240060402MaRDI QIDQ4845076zbMATH OpenOpenAlexFDO

Authors Tomasz Łuczak, S. Shelah

Publication date 4 September 1995

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9501221

zbMATH Keywords

convergencefirst-order theoriesprobabilitiesrandom graphs

Mathematics Subject Classification ID

Classical first-order logic (03B10) Random graphs (graph-theoretic aspects) (05C80) Convergence of probability measures (60B10) Zero-one laws (60F20)

Abstract: For a sequence p=(p(1),p(2), ...) let G(n,p) denote the random graph with vertex set {1,2, ...,n} in which two vertices i, j are adjacent with probability p(|i-j|), independently for each pair. We study how the convergence of probabilities of first order properties of G(n,p), can be affected by the behaviour of p and the strength of the language we use.

Recommendations

• Convergence law for random graphs with specified degree sequence
• On limits of sparse random graphs
• scientific article; zbMATH DE number 1341924
• Poisson convergence of numbers of vertices of a given degree in random graphs
• Probabilities of Sentences about Very Sparse Random Graphs

Cites work

• Almost sure theories
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• On random models of finite power and monadic logic
• On the connectedness of a random graph
• Probabilities on finite models
• Random sparse unary predicates
• When Does the Zero-One Law Hold?
• Zero-One Laws for Sparse Random Graphs

Cited in

(15)

• On a method for random graphs
• On the convergence of probabilities of first-order sentences for recursive random graph models
• The metamathematics of random graphs
• Random graphs and the strong convergence of bootstrap means
• Almost sure convergence of vertex degree densities in the vertex splitting model
• Hereditary zero-one laws for graphs
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• Convergence of mixing times for sequences of random walks on finite graphs
• scientific article; zbMATH DE number 1136104 (Why is no real title available?)
• The first order convergence law fails for random perfect graphs
• On limits of sparse random graphs
• Convergence law for random graphs with specified degree sequence
• scientific article; zbMATH DE number 238432 (Why is no real title available?)
• Graphon convergence of random cographs
• Limits of randomly grown graph sequences

This page was built for publication: Convergence in homogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4845076)