Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the sentence tends to either 0 or 1 as $n$ goes to infinity. It is known that testing, for a given sentence, whether the limit is 0 or whether it is 1 is PSPACE-complete (Grandjean, "Complexity of the first-order theory of almost all finite structures", *Information and Control* 1983). One possible approach to performing this sort of test would be to sample random graphs of sufficiently large size and test whether they model the sentence; but this would be limited both by the difficulty of testing whether a graph models a given sentence and also by the convergence rate of the 0-1 law, as that would control the size of the graphs needed in this sampling scheme.

What if anything is known and published about more explicit upper or lower bounds on the convergence rate of $P_S$, for the worst-case sentence $S$ of a given length, as a function of $S$? Or to put it another way, if one wishes to get the correct limit with probability bounded away from $1/2$, how large a graph should one sample?

One simple example of a sentence that converges slowly is given by the Ramsey property: does this graph contain either a clique of size $k$ or an independent set of size $k$? The sentence for this has length $O(k^2)$ but one needs to sample graphs of size at least exponential in $k$ to discover that the limit probability is one. But maybe there are other sentences that converge even more slowly?