Sufficient Conditions for Labelled 0-1 Laws
If F(x) = e G(x), where F(x) = Σf(n)x n and G(x) = Σ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''...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/618 |
| Summary: | If F(x) = e G(x), where F(x) = Σf(n)x n and G(x) = Σ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. |
|---|---|
| ISSN: | 1462-7264 1365-8050 |