Citation
S. Shelah et J. Spencer, RANDOM SPARSE UNARY PREDICATES, Random structures & algorithms, 5(3), 1994, pp. 375-394
Citations number
4
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
ISSN journal
10429832
Volume
5
Issue
3
Year of publication
1994
Pages
375 - 394
Database
ISI
SICI code
1042-9832(1994)5:3<375:RSUP>2.0.ZU;2-8
Abstract
Random unary predicates U on [n] holding with probability p are examin
ed with respect to sentences A in a first-order language containing U
and ''less than. '' When p = p(n) satisfies np(k+1) much less than 1 m
uch less than np(k) it is shown that Pr[A] approaches a limit dependen
t only on k and A. In a similar circular model the limit is shown to b
e zero or one. (C) 1994 John Wiley & Sons, Inc.