Abstract
Shelah and Spencer [1] proved that the zero-one law holds for the first order sentences on random graphs G(n,n-α) whenever α is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization.
Original language | English (US) |
---|---|
Pages (from-to) | 263-280 |
Number of pages | 18 |
Journal | Combinatorica |
Volume | 20 |
Issue number | 2 |
DOIs | |
State | Published - 2000 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics