Probabilities of Sentences about Very Sparse Random Graphs
From MaRDI portal
Publication:3989740
DOI10.1002/rsa.3240030105zbMath0754.05061OpenAlexW1987966006MaRDI QIDQ3989740
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
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