Probabilities of Sentences about Very Sparse Random Graphs

DOI10.1002/rsa.3240030105zbMath0754.05061OpenAlexW1987966006MaRDI QIDQ3989740

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

first-order logicrandom graphsasymptotic probability

Mathematics Subject Classification ID

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

Related Items

Zero-one laws with variable probability, The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees, Limiting probabilities of first order properties of random sparse graphs and hypergraphs, The first order theory of \(G(n, c/n)\), Zero-one \(k\)-law, Infinitary logics and very sparse random graphs, Existential monadic second order convergence law fails on sparse random graphs, Query evaluation on a database given by a random graph, The first order convergence law fails for random perfect graphs, Zero-one laws for \(k\)-variable first-order logic of sparse random graphs, Randomness and semigenericity

Cites Work

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