Discrete Mathematics & Theoretical Computer Science, Vol 10, No 1 (2008)

Font Size:  Small  Medium  Large

Sufficient Conditions for Labelled 0-1 Laws

Stanley Burris, Karen Yeats


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