Name
Abstract | ||
|---|---|---|
Shelah and Spencer [1] proved that the zero-one law holds for therst order sentences on random graphs G(n; n) whenever is axed positive irrational. This raises the question what zero-one valuedfunctions on the positive irrationals arise as the limit probability ofa rst order sentence on these graphs. Here we prove two necessaryconditions on these functions, a number-theoretic and a complexitycondition. We hope to prove in a subsequent paper that these conditionstogether... |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s004930070025 | Combinatorica |
Keywords | Field | DocType |
first order,random graph | Discrete mathematics,Combinatorics,Random graph,First order,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 2 | 0209-9683 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joel Spencer | 1 | 41 | 4.73 |
| Gábor Tardos | 2 | 1261 | 140.58 |