Probabilities of Sentences about Very Sparse Random Graphs

DOI10.1002/RSA.3240030105MaRDI QIDQ3989740zbMATH OpenOpenAlexFDO

Authors James Lynch

Publication date 28 June 1992

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

Full work available at URL https://doi.org/10.1002/rsa.3240030105

zbMATH Keywords

asymptotic probabilityfirst-order logicrandom graphs

Mathematics Subject Classification ID

Model theory (03C99) Random graphs (graph-theoretic aspects) (05C80) Probability theory on algebraic and topological structures (60B99)

Recommendations

• Spectra of short monadic sentences about sparse random graphs
• scientific article; zbMATH DE number 426367
• Some large deviation results for sparse random graphs
• On limits of sparse random graphs
• Sparse graphs using exchangeable random measures
• Short monadic second order sentences about sparse random graphs
• Sparse graphs: metrics and random models
• On the convergence of probabilities of first-order sentences for recursive random graph models

Cites work

• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Almost sure theories
• An application of games to the completeness problem for formalized theories
• Complexity of the first-order theory of almost all finite structures
• Cybernetics
• Probabilities of First-Order Sentences about Unary Functions
• Probabilities on finite models
• Threshold spectra via the Ehrenfeucht game
• Undecidable statements and random graphs
• Zero-One Laws for Sparse Random Graphs

Cited in

(25)

• Listing graphs that satisfy first-order sentences
• Undecidable statements and random graphs
• The first order convergence law fails for random perfect graphs
• Existential monadic second order convergence law fails on sparse random graphs
• Query evaluation on a database given by a random graph
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• The first order theory of \(G(n, c/n)\)
• A simpler axiomatization of the Shelah-Spencer almost sure theories
• In the random graph \(G(n,p), p=n^{-a}\): If \(\psi\) has probability \(O(n^{-\varepsilon})\) for every \(\varepsilon >0\) then it has probability \(O(e^{-n^ \varepsilon})\) for some \(\varepsilon >0\)
• The first-order contiguity of sparse random graphs with prescribed degrees
• Randomness and semigenericity
• scientific article; zbMATH DE number 426367 (Why is no real title available?)
• scientific article; zbMATH DE number 4215043 (Why is no real title available?)
• scientific article; zbMATH DE number 17685 (Why is no real title available?)
• Zero-one \(k\)-law
• scientific article; zbMATH DE number 1341924 (Why is no real title available?)
• An extension of 0‐1 laws
• Random sparse unary predicates
• Infinitary logics and very sparse random graphs
• scientific article; zbMATH DE number 1136073 (Why is no real title available?)
• Convergence in homogeneous random graphs
• Zero-one laws with variable probability
• Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas
• Limiting probabilities of first order properties of random sparse graphs and hypergraphs
• First order complexity of finite random structures

This page was built for publication: Probabilities of Sentences about Very Sparse Random Graphs

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