Random sparse unary predicates

Saharon Shelah; Joel Spencer

doi:10.1002/rsa.3240050302

Random sparse unary predicates

Saharon Shelah, Joel Spencer

Research output: Contribution to journal › Article › peer-review

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 n^k+1 ≪ 1 ≪ np^k 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 language	English (US)
Pages (from-to)	375-394
Number of pages	20
Journal	Random Structures & Algorithms
Volume	5
Issue number	3
DOIs	https://doi.org/10.1002/rsa.3240050302
State	Published - Jul 1994

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.3240050302

Cite this

@article{a4f477c47f514e4a8f5b3d905242efd4,

title = "Random sparse unary predicates",

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. {\textcopyright} 1994 John Wiley & Sons, Inc.",

author = "Saharon Shelah and Joel Spencer",

year = "1994",

month = jul,

doi = "10.1002/rsa.3240050302",

language = "English (US)",

volume = "5",

pages = "375--394",

journal = "Random Structures & Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "3",

}

TY - JOUR

T1 - Random sparse unary predicates

AU - Shelah, Saharon

AU - Spencer, Joel

PY - 1994/7

Y1 - 1994/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84990651366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990651366&partnerID=8YFLogxK

U2 - 10.1002/rsa.3240050302

DO - 10.1002/rsa.3240050302

M3 - Article

AN - SCOPUS:84990651366

SN - 1042-9832

VL - 5

SP - 375

EP - 394

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

IS - 3

ER -

Random sparse unary predicates

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this