Sufficient conditions for labelled 0-1 laws

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.147--156
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972301
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:07:31
Dernière modification le : samedi 18 novembre 2017 - 01:06:28
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:26:42

Fichier

618-3225-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972301, version 1

Collections

Citation

Stanley N. Burris, Karen A. Yeats. Sufficient conditions for labelled 0-1 laws. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.147--156. 〈hal-00972301〉

Partager

Métriques

Consultations de la notice

62

Téléchargements de fichiers

201