We look at a competitor of the Erdos-Renyi models of random graphs, one proposed by E. Gilbert (1961): given /spl delta/>0 and a metric space X of diameter >/spl delta/, scatter n vertices at random on X and connect those of distance

Abstract We prove that any positive elementary (least fixed point) induction expressing the negation of transitive closure on finite nondirected graphs requires at least two recursion variables.

The authors establish a general hierarchy theorem for quantifier classes in the infinitary logic L/sub infinity omega //sup omega / on finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure. This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of N. Immerman (1987). The authors also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog.>

It is shown that transitive closure logic (FO+TC) is strictly more powerful than deterministic transitive closure logic (FO+DTC) on unordered structures. In fact, on certain classes of graphs, such as hypercubes or regular graphs of large degree and girth, every query in (FO+DTC) is first-order expressible. On the other hand, there are simple (FO+pos TC) queries on these classes that cannot be defined by first-order formulas.>

Abstract A function is recursive (in given operations) if its values are computed explicitly and uniformly in terms of other “previously computed” values of itself and (perhaps) other “simultaneously computed” recursive functions. Here, “explicitly” includes definition by cases. We investigate those recursive functions on the structure N = 〈ω, 0, succ, pred〉 that are computed in terms of themselves only, without other simultaneously computed recursive functions.