Stanley N. Burris ; Karen A. Yeats - Sufficient conditions for labelled 0-1 laws

dmtcs:430 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.430
Sufficient conditions for labelled 0-1 lawsArticle

Authors: Stanley N. Burris 1; Karen A. Yeats 2

  • 1 Department of Pure Mathematics [Waterloo]
  • 2 Department of Mathematics and Statistics [Boston]

If F(x) = e^G(x), where F(x) = \Sum f(n)x^n and G(x) = \Sum g(n)x^n, 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.


Volume: Vol. 10 no. 1
Section: Combinatorics
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 295 times.
This article's PDF has been downloaded 284 times.