scientific article; zbMATH DE number 1072412

Let \(G_n\) denote the random graph selected uniformly from among all graphs on vertex set \(1\dots n\). We restrict attention to sentences in the first-order theory of ordered graphs. For such a sentence \(A\), let \(f_A(n)\) denote the probability that \(G_n\) has property \(A\). \textit{K. J. Compton}, \textit{C. W. Henson}, and \textit{S. Shelah} [Ann. Pure Appl. Logic 36, 207-224 (1987; Zbl 0632.03037)] showed that convergence does not hold in this system: There are sentences \(A\) for which \(\lim_{n\to\infty} f_A(n)\) does not exist. More recently, \textit{S. Shelah} [Random. Struct. Algorithms 9, 351-358 (1996)] showed that this system obeyed what he termed a ``very weak 0-1 law, by which he meant that for any \(A\), \(\lim_{n\to\infty} f_A(n+ 1)- f_A(n)= 0\). (We call such a law a smoothness law.) Here we consider the analytic question of just how quickly \(f_A\) can oscillate. In one direction, we show: Theorem 1.1. For every sentence \(A\) there exists a number \(t\) so that \(f_A(n+ 1)- f_A(n)= O(n^{-1}\ln^t n)\). Corollary 1.2. For every sentence \(A\) there exists a number \(t\) so that \(m(n)= O(n\ln^{-t} n)\) implies \(\lim_{n\to\infty} f_A(n+ m(n))- f_A(n)= 0\). Observe that Corollary 1.2 follows from Theorem 1.1 by summing. In the opposite direction, we show: Theorem 1.3. For every number \(t\) there exists a sentence \(A\) and a function \(m(n)= O(n\ln^{-t}n)\) so that \(f_A(n+ m(n))- f_A(n)\) does not approach \(0\). For the entire collection see [Zbl 0872.00029].

Recommendations

Cited in

(6)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359309)