Convergence laws for random graphs

MaRDI QIDQ4381414zbMATH OpenFDO

Authors James Lynch

Publication date 19 October 1998

zbMATH Keywords

0-1 lawsconvergence lawsfinite random structurefixed-point logicsinfinitary logicssurvey

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Other infinitary logic (03C75) Random graphs (graph-theoretic aspects) (05C80)

Review text

The convergence law (0-1 law) holds for a logic if for every sentence the probability that it holds for a finite random structure approaches a limit (approaches 0 or 1) as the size of the structure grows. This expository article gives a clear and informative survey on convergence laws and 0-1 laws for fragments of \(L^\omega_{\infty\omega}\). It emphasizes unifying principles in the proofs. For the entire collection see [Zbl 0884.00035].

Recommendations

• Zero-one laws with variable probability
• scientific article; zbMATH DE number 887782
• scientific article; zbMATH DE number 2079030
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• Convergence in homogeneous random graphs

Cited in

(9)

• The metamathematics of random graphs
• Limit laws for UGROW random graphs
• Determined theories and limit laws
• Convergence theorems for some layout measures on random lattice and random geometric graphs
• Almost sure convergence of vertex degree densities in the vertex splitting model
• scientific article; zbMATH DE number 2079030 (Why is no real title available?)
• Law of the iterated logarithm for random graphs
• scientific article; zbMATH DE number 5252621 (Why is no real title available?)
• Graphon convergence of random cographs

This page was built for publication: Convergence laws for random graphs

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