Ups and Downs of First Order Sentences on Random Graphs |
| |
| Authors: | Joel Spencer Gábor Tardos |
| |
| Institution: | (1) Courant Institute of Mathematical Sciences; 251 Mercer St., New York, NY 10012, USA; E-mail: spencer@cs.nyu.edu, US;(2) Rényi Institute of Mathematics; Reáltanoda u. 13–15., Budapest, H-1053 Hungary; E-mail: tardos@math-inst.hu, US |
| |
| Abstract: | 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.
Received October 2, 1998 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 05C80 60F20 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
