Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Sufficient condition ...
Article

Sufficient conditions for labelled 0-1 laws

Stanley N. Burris (1), Karen A. Yeats ORCID (2)
(1) Department of Pure Mathematics [Waterloo]
(2) Department of Mathematics and Statistics [Boston]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2008
Last modified on
March 31, 2025
Volume 10
vol. 10:1
Combinatorics
DOI
10.46298/dmtcs.430
License
https://about.hal.science/hal-authorisation-v1
Indicators
727
Views
778
Downloads

Sufficient conditions for labelled 0-1 laws

Stanley N. Burris (1), Karen A. Yeats ORCID (2)
(1) Department of Pure Mathematics [Waterloo]
(2) Department of Mathematics and Statistics [Boston]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Asymptotics of counts of small components in random structures and models of coagulation-fragmentation

    ESAIM Probability and Statistics

    Authors : Boris L. Granovsky

    Journal reference : Volume 17, 2012, pp. 531-549

    DOI : 10.1051/ps/2012007
Preview
Loading PDF preview...