Random sparse unary predicates

DOI10.1002/RSA.3240050302MaRDI QIDQ4306371zbMATH OpenOpenAlexFDO

Authors S. Shelah, Joel Spencer

Publication date 5 March 1995

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

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

zbMATH Keywords

circular languagerandom unary predicates

Mathematics Subject Classification ID

Zero-one laws (60F20) Basic properties of first-order languages and structures (03C07)

Abstract: The main result is the following Theorem: Let p=p(n) be such that p(n) in [0,1] for all n and either p(n)<< n^{-1} or for some positive integer k, n^{-1/k}<< p(n)<< n^{-1/(k+1)} or for all epsilon >0, n^{- epsilon}<< p(n) and n^{- epsilon}<< 1-p(n) or for some positive integer k, n^{-1/k}<< 1-p(n)<< n^{-1/(k+1)} or 1-p(n)<< n^{-1}. Then p(n) satisfies the Zero-One Law for circular unary predicates. Inversely, if p(n) falls into none of the above categories then it does not satisfy the Zero-One Law for circular unary predicates.

Recommendations

• Random unary predicates: Almost sure theories and countable models
• Limit probabilities for random sparse bit strings
• Probabilities of Sentences about Very Sparse Random Graphs
• Infinitary logics and very sparse random graphs
• Spectra of short monadic sentences about sparse random graphs

Cited in

(6)

• The logic of ordered random structures
• On probabilistic elimination of generalized quantifiers
• Random graph orders do not satisfy a 0–1 law
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• Convergence in homogeneous random graphs
• Random unary predicates: Almost sure theories and countable models

This page was built for publication: Random sparse unary predicates

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