Random sparse unary predicates

Saharon Shelah, Joel Spencer

Research output: Contribution to journalArticle

Abstract

Random unary predicates U on [n] holding with probability p are examined with respect to sentences A in a first‐order language containing U and “less than.” When p = p(n) satisfies nk+1 ≪ 1 ≪ npk it is shown that Pr[A] approaches a limit dependent only on k and A. In a similar circular model the limit is shown to be zero or one. © 1994 John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)375-394
Number of pages20
JournalRandom Structures & Algorithms
Volume5
Issue number3
DOIs
StatePublished - Jul 1994

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random sparse unary predicates'. Together they form a unique fingerprint.

Cite this