Shelah and Spencer  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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics