Sufficient Conditions for Labelled 0-1 Laws
Stanley Burris, Karen Yeats
Abstract
If F(x) = eG(x), where F(x) =
Σf(n)xn
and G(x) = Σg(n)xn, with
0≤g(n) =O(nθn/n!),
θ∈(0,1), and gcd(n : g(n)
>0)=1,
then f(n)=o(f(n-1)). This gives an answer to Compton's
request
in Question 8.3 [Compton 1987] for an ``easily verifiable sufficient
condition''
to show that an adequate class of structures has a labelled
first-order
0-1 law, namely it suffices to show that the labelled component count
function
is O(nθn) for some
θ∈(0,1).
It also provides the means to recursively construct an adequate class
of
structures with a labelled 0-1 law but not an unlabelled 0-1 law,
answering Compton's Question 8.4.
Full Text: PDF PostScript